Exercise 1.6.10

Question

%1.6.10
  As a final exercise, answer each of the following by establishing a $1-1$ correspondence with a set of known cardinality.
  \begin{enumerate}[label=(\alph*)] 
  \item Is the set of all functions from $\{0,1\}$ to $\mathbf{N}$ countable or uncountable?
  \item Is the set of all functions from $\mathbf{N}$ to $\{0,1\}$ countable or uncountable?
  \item Given a set $B$, a subset $\mathcal{A}$ of $P(B)$ is called an antichain if no element of $\mathcal{A}$ is a subset of any other element of $\mathcal{A} .$ Does $P(\mathbf{N})$ contain an uncountable antichain?
   \end{enumerate}

Ulisse Mini · Accepted Answer

\begin{enumerate}[label=(\alph*)] 
  \item The set of functions from $\{0, 1\}$ to $\mathbf{N}$ is the same as $\mathbf N^2$ which we found was countable in Exercise 1.5.9.
  \item This is the same as an infinite list of zeros and ones which we showed was uncountable in Exercise 1.6.4.
  \item Let $\mathcal A$ be an antichain of $P(\mathbf N)$, let $\mathcal A_l$ be the sets in $\mathcal A$ of size $l$.
    For finite $l$, $\mathcal A_l$ is countable since $\mathcal A_l \subseteq \mathbf N^l$ is countable (shown in 1.5.9). Therefore the countable union
    $\bigcup_{l=0}^\infty \mathcal A_l = \mathcal A$
    is countable. Thus, if $P(\mathbf N)$ contains an uncountable antichain, ``most" sets in the antichain must be infinite (in that there will be uncountably many sets in the antichain will be infinite, whereas only countably many sets in the antichain will be finite).

This observation inspires the following construction, using a variant of the set $S$ from Exercise 1.6.4. Define the set
    $$\mathcal A = \left\{ \{10n + d(x, n) : n \in \mathbf N\}: x \in (0, 1)\right\}$$
    where $d(x, n)$ is the $n$'th digit in the decimal expansion of $x$. To avoid the issue of some numbers having two equivalent decimal representations, always use the representation with repeating 9's. In this manner, each element of $\mathcal A$ encodes a particular real number, in a similar way that each element of $S$ encodes a particular real number through its binary expansion.

Note that each element of $\mathcal A$ is infinite. Note also that since any two distinct real numbers will differ in at least one place in their decimal expansions, the corresponding elements in $\mathcal A$ will differ there as well, and hence $\mathcal A$ is an antichain.

Formally, let $x_1, x_2$ be two distinct real numbers, $A_1, A_2$ be the elements of $\mathcal A$ corresponding to $x_1, x_2$ respectively, and $n$ be the first decimal position where $x_1$ and $x_2$ differ. Then $10n + d(x_1, n)$ will be in $A_1$ but not $A_2$, and $10n + d(x_2, n)$ will be in $A_2$ but not $A_1$. Thus, neither $A_1 \subseteq A_2$ nor $A_2 \subseteq A_1$. Since $(0, 1)$ is uncountable, $\mathcal A$ is an uncountable antichain in $P(\mathbf N)$.
   \end{enumerate}

Richard Ganaye · Answer

(O.K. with the proof of Ulisse Mini. I propose another approach.)

\begin{proof} c)
Consider first $$E = (\mathbf{N} 	imes \{0\}) \cup (\mathbf{N} 	imes \{1\}).$$
Then $E \sim \mathbf{N}$ (Theorem 1.5.8(i)). We will prove that $P(E)$ contains an uncountable antichain $\mathcal A$.

Let
$${\mathcal A} =\{(A 	imes\{0\}) \cup (A^c 	imes \{1\}) \mid A \in P(\mathbf{N})\} \subseteq P(E),$$
where $A^c = \mathbf{N} \setminus A$ .

If $a \in {\mathcal A} , b \in {\mathcal A} $, then, for some $A,B \in P(\mathbf{N})$,
$$a = (A 	imes\{0\}) \cup (A^c 	imes \{1\}) ,\qquad b = (B 	imes\{0\}) \cup (B^c 	imes \{1\}).$$
Suppose that  $a \subseteq b$. For all $x\in a$, $x \in A 	imes\{0\}$ or $x \in A^c 	imes\{1\}$.

If $x \in A 	imes\{0\}$, then $x = (n,0)$ for some natural number $n$, thus $x 
ot \in B^c 	imes \{1\}$, so $x \in B 	imes\{0\}$. This shows that $A	imes\{0\} \subseteq B 	imes \{0\}$, and similarly $A^c 	imes\{ 1\} \subseteq B^c	imes \{1\}$, hence
$$A \subseteq B,\qquad A^c \subseteq B^c.$$
Therefore $A \subseteq B, B \subseteq A$, so $A=B$, thus $a = b$. This proves $a \subseteq b \Rightarrow a = b$ for all $a,b\in  {\mathcal A} $. No element of $\mathcal{A}$ is a subset of any other element of $\mathcal{A}$, so that ${\mathcal A} $ is an antichain.

Moreover
$$\varphi
\left\{
\begin{array}{ccl}
P(\mathbf{N}) & 	o & {\mathcal A}\
A & \mapsto & (A 	imes\{0\}) \cup (A^c 	imes \{1\})
\end{array}
ight.
$$
is bijective:
\begin{enumerate}
\item[$\bullet$] surjective by definition of $ {\mathcal A}$.
\item[$\bullet$] injective, since
 $$(A 	imes\{0\}) \cup (A^c 	imes \{1\})  = (B 	imes\{0\}) \cup (B^c 	imes \{1\}) \Rightarrow A 	imes\{0\} = B 	imes\{0\} \Rightarrow A = B.$$
\end{enumerate} 
Therefore ${\mathcal A}$ is uncountable.

\medskip
To finish the proof, knowing that $E \sim \mathbf{N}$, there is some $f : E 	o \mathbf{N}$ bijective. Then $f({\mathcal A})$ is an uncountable antichain of $P(\mathbf{N})$:
if $a',b' \in f({\mathcal A})$, then $a' = f(a), b' = f(b)$ for some $a,b \in {\mathcal A}$, and
$$a' \subseteq b' \Rightarrow f(a) \subseteq f(b) \Rightarrow a \subseteq b \Rightarrow a = b \Rightarrow a' = b'.$$
(so $a' 
e b' \Rightarrow a' 
ot \subseteq b' 	ext{ and } b' 
ot \subseteq a'$.)
\end{proof}

Exercise 1.6.10

Answers

Comments

Comments

Exercise 1.6.10

Answers

Comments

Comments

Add answer