What is the largest set for which its set of self bijections is countable?

Question

I recently came across a problem which required some knowledge about the self bijections of $\mathbb{N}$, and after looking up how to construct some different bijections I came across the result that the set of self bijections of $\mathbb{N}$ is uncountable.

And this got me wondering, what is the largest set for which its set of self bijections is countable? This obviously holds true for any finite set, but what is the last example of a set whose set of self bijections is countable?

Answer 1

There is no such maximal set, because $\aleph_0=|\mathbb{N}|$ is the smallest infinite cardinal.

Answer 2

Let $B(X)$ be the set of bijections of $X$ to itself.

To expand upon the already given answer, it's obvious that the number of bijections from a finite set to itself is finite because the number of functions from a finite set to itself is finite. Thus we are interested in infinite sets. It should also be obvious that if $|X|\geq|Y|$ then $|B(X)|\geq|B(Y)|$

Since there exists a bijection between two sets if and only if they have the same cardinality and the composition of two bijections is a bijection, the set exact you are looking at in this context doesn't matter, only its cardinality. To see this, let $|X|=|Y|$ and let $f:X\to Y$ be a bijection. Then $B(Y)=\{fgf^{-1}(x):g\in B(X)\}$ and so there are exactly the same number.

Now we have established:

1) No finite set has infinitely many bijections the set to itself.

2) $|B(S)|$ depends only on $|S|$.

3) $|X|>|Y|\Rightarrow |B(X)|\geq|B(Y)|$

It follows from the above that there is no set $X$ for which $|B(X)|$ is infinite and $B(X)<B(\mathbb{N})$ since $|\mathbb{N}|$ is the smallest infinite cardinal, which means that, by your observation, no set has countably infinite many bijections with itself! But then the largest set with countably many bijections to itself is finite, and every finite set exhibits this, so there is no largest set.

Answer 3

Let's write $X!$ for the set of bijections $X\to X$. It is true that $$ |X| < |Y| \implies | X! | \le | Y! |. $$ However, it is not true that strict equality always holds. This is independent of set theory (ZFC). See below for details.

First, though, to address the question: There is no "largest [size of] set for which its set of self bijections is countable".

For finite $X,Y$, clearly the set of bijections $X\to Y$ are a subset of $Y^X$, the set of all functions $X\to Y$; so the set of bijections is finite.

The next largest size is $\aleph_0$, the cardinality of $X = \Bbb N$. The bijections $X!$ from this set to itself have cardinal $2^{\aleph_0}$, as shown below, so already the number of bijections is uncountable. If $Y$ is any larger set, then $|X!| = 2^{|X|} \le 2^{|Y|} = |Y!|$, so the cardinality of the bijections of $Y$ is uncountable too.

---

It is not true that $|X| < |Y|$ implies that there are more bijections $Y\to Y$ than there are $X\to X$, for infinite $X,Y$. This is independent of ZFC, so it's not likely to be "obvious";/ We have:

$$2^{|X|} \le (\text{# of bijections } X\to X) \le |X|^{|X|} = 2^{|X|},\tag{*} $$ To see the first inequality, consider the injection $$f\mapsto \big(x\mapsto (f(x), x)\big) \colon 2^X \to (\text{bijections } X \to 2\times X).$$

Similarly, (*) holds for $Y$.

However, in some models of ZFC, there are infinite $X,Y$ with $|X| < |Y|$ but $2^{|X|} = 2^{|Y|}$. In other models, there are no such $X,Y$ and the property is true. Assuming ZFC is consistent, neither is provable.