I'm a student and I'm taking an intro course on set theory. I found this question online and I've spent the last couple of days on this and I can't figure out if my conclusion is correct, I would appreciate any insight.
I'm trying to determine the cardinality of the following set:
$S = \{f: P(\mathbb{N}) \to P(\mathbb{N}) \mid$ ($f$ is a total function) $\land (\forall A \in P(\mathbb{N})$, $|f(A)| = |A|)\}$
I'm hesitant, but I think that $|S| = \aleph $. This is how I reached this conclusion:
- $|S| \leq \aleph$: We define the function $h: P(\mathbb{N})^{\mathbb{N}} \to S$ in the following manner:
- Let $q \in P(\mathbb{N})^{\mathbb{N}}$ be an infinite sequence of sets of natural numbers.
- If there exists a function $f \in S$ such that for any set $A \in P(\mathbb{N})$ in an odd index '$i$' and for any set $B \in P(\mathbb{N})$ in the following even index '$i+1$' (the indices of the sequence $q$) it hold that $f(A) = B$, then $h(q) = f$.
Clearly, $h$ is surjective. As a countably infinite cartesian product of a set of cardinality $\aleph$, it follows that $|P(\mathbb{N})^{\mathbb{N}}| = \aleph$. Therefore, $|S| \leq \aleph$. (*)
- $|S| \geq \aleph$: We define the function $g: S \to P(\mathbb{N})$ in the following manner:
- Let $f \in S$ be some function.
- If there exists a finite set $A \in P(\mathbb{N})$ such that $f(A) = A$ (if there exists mutiple such sets, we choose the set of the lowest cardinality, and again if there exists mutilple such sets, we arbitrarily choose one), then $g(f) = A$.
Clearly, $g$ is surjective. Therfore, $|S| \geq |P(\mathbb{N})| = \aleph$. (**)
Since both (*) and (**) hold, it follows that $|S| = \aleph$. $\blacksquare$
My concern is from part 1. Is it true to say that all infinite sequences of sets from $P(\mathbb{N})$ can be found in $P(\mathbb{N})^{\mathbb{N}}$ or should the domain of $h$ be $P(\mathbb{N})^{P(\mathbb{N})}$? On the other hand, I cracked my head on this and ,no matter what I tried, I coulnd't think of any way to prove that $S \gt \aleph$.
Also if there is anything else in what I wrote that is incorrect, please tell me.
Best Answer
You are incorrect. $|S| = 2^{2^{\aleph_0}}$.
First, clearly, $|S| \leq \aleph^\aleph$.
In the following we show $|S|\geq\aleph^\aleph$. Set $Q = \{x \in P(\mathbb{N}) \mid |x| = \aleph_0\}$. Note that $|Q| + \aleph_0 = \aleph$ (just taking $Q^c = \{x \in P(\mathbb{N}) \mid x$ finite$\}$ and noting that $P(\mathbb{N})$ is the disjoint union of $Q$ and $Q^c$); therefore, $\max(|Q|, \aleph_0) = \aleph)$; therefore, $|Q| = \aleph$.
We will see that $Q^Q$ injects into $S$. For given some $f : Q \to Q$, define $g_f : P(\mathbb{N}) \to P(\mathbb{N})$ by $g_f(s) = s$ if $s$ is finite, $f(s)$ otherwise. Clearly, $g : Q^Q \to S$ is injective. Therefore, $|Q^Q| = |Q|^{|Q|} = \aleph^\aleph \leq |S|$. So $S \geq \aleph^\aleph$.
So $|S| = \aleph^\aleph$. Note that $\aleph^\aleph = 2^{2^{\aleph_0}}$ because $2^\aleph \leq \aleph^\aleph \leq (2^\aleph)^\aleph = 2^{\aleph \cdot \aleph} = 2^\aleph$ and $\aleph=2^{\aleph_0}$.
Therefore, $|S| = 2^{2^{\aleph_0}}$.