2
$\begingroup$

This is an exercise in Naive Set Theory by P. R. Halmos.

If $\text{card }A=a$, what is the cardinal number of the set of all one-to-one mappings of $A$ onto itself? What is the cardinal number of the set of all countably infinite subsets of $A$?

It is easy to see that, for the first question, the cardinal number is less than or equal to $a^a$, and for any finite set the cardinal number is $a!$; for the second one, the cardinal number is less than or equal to $2^a$, and for any finite set the cardinal number is $0$.
I guess for infinite sets the equality holds in both questions. Is that correct? Can anyone give some suggestions on what to do next?
Edit: As is suggested by Arthur, the second cardinal number is at most $a^\omega$.

$\endgroup$

closed as off-topic by user642796 Dec 2 '14 at 17:40

  • This question does not appear to be about math within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ There are at most as many subsets that there are functions $\omega\to A$, so the cardinality is at most $a^\omega$. $\endgroup$ – Arthur Nov 21 '14 at 15:28
  • $\begingroup$ @DietrichBurde When I say two cardinal numbers are equal, I mean that the correspondent ordinal numbers are equivalent. $\endgroup$ – Eclipse Sun Nov 21 '14 at 15:38
  • $\begingroup$ Are you assuming the axiom of choice? In either case both these questions has been answered several times before. This should be closed as a duplicate (of at least one), but with the bounty this is impossible. $\endgroup$ – Asaf Karagila Nov 24 '14 at 9:24
  • 3
    $\begingroup$ This question shows there is a maximal number of 1-1 functions since those which are bijections already have that cardinality; and this question shows that indeed $a^\omega$ is the right cardinal for an infinite set, and it is $0$ for a finite set, as you observed. Of course, both assuming choice, otherwise all hell breaks loose. $\endgroup$ – Asaf Karagila Nov 24 '14 at 9:32
  • 1
    $\begingroup$ This question appears to be off-topic because it contains two largely unrelated questions which should be asked separately. $\endgroup$ – user642796 Dec 2 '14 at 17:40
1
$\begingroup$

If $|A|=a$ is infinite then the cardinal number of the set of all countably infinite subsets of $A$ is $a^\omega$.

The upper case is trivial because every subset can be represented by an ordered sequence and there are $|A|^\omega$ sequences.

Due to $a^2=a$, the set $\mathbb{Z}\times A$ is equivalent to $A$, so there is a bijection $\varphi:A\to (\mathbb{Z}\times A)$. So the set $A$ can be partitioned into infinitely many disjoint subsets, all of cardinality $a$: $$ A=\bigcup_{n=1}^\infty A_n; \quad |A_1|=|A_2|=\ldots=|A|=a. $$ Now there are $a^\omega$ distinct subsets that contain exactly one element of every $A_n$.

$\endgroup$
1
$\begingroup$

For the first question: Suppose that $A$ is infinite, since every function $f:A\rightarrow A$ is given by a subset of $A\times A$, and $a^2=a$, the cardinality of the set of all functions from $A$ to $A$ is at most $2^a$. In fact $a^a=2^a$ since $2\leq a$ implies $2^a\leq a^a\leq 2^a$.
Now we prove that the cardinality of all the bijective functions is $2^a$ and then we are done with the first question. Given any subset $S\subset A$ we choose any bijective function $f_S:A\setminus S\rightarrow A\setminus S$ without a fixed point (prove that there is at least one, by Zorn) and we extend this function to a bijective function from $A$ to $A$ as the identity in $S$. This proves that there is at least $2^a$ bijective functions from $A$ to $A$, so the equality holds.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.