Set $A$ has the cardinality of $\aleph_0$. Prove some properties of partial order $ \langle \mathcal P (A), \subseteq \rangle$.

Question

I try to solve the following task:

Set $A$ has the cardinality of $\aleph_0$. The truth is that in the partial order $ \langle \mathcal P (A), \subseteq \rangle$: (answer true or false)

a) every subset has upper bound

b) exists chain of the cardinality of the continuum

c) exists antichain of the cardinality of the continuum

What I have found so far:

a) The upper bound for every subset of set $A$ is simpy set $A$. So here TRUE.

b) Set $A$ has the cardinality of $\aleph_0$, so every chain can be also of the cardinality of $\aleph_0$. Suppose that some chain that has the cardinality of continuum. Then, this chain must have two sets that have the same number of elements. But if two sets have the same number of elements, they cannot be compared (in the inclusion relation). So, they cannot be in the same chain simultaneously. So here is FALSE (some chain has cardinality of at most $\aleph_0$).

c) And here I suppose that there exists antichain of the cardinality of the continuum, but I cannot prove it. I have tried to prove it this way: In point b) I proved that all sets having the same number of elements cannot be compared. So they are in the antichain. But I cannot prove that this antichain has the cardinality of the continuum (maybe it has not such a cardinality).

I am grateful for any hint!

Answer 1

There is an error in your argument for (b). It is quite possible for two sets to have the same infinite cardinality but have one be a proper subset of the other. For example, $\{0,1,2,\dots\}$ and $\{0,2,4,\dots,\}$ have the same cardinality, but they can be compared via inclusion. Indeed, one definition of being $X$ being infinite is that $X$ has a proper subset of the same cardinality.

Indeed, there is a definition of the real line which essentially gives for each real $x$ an $A_x\subset \mathbb Q$ such that if $x<y$ then $A_x\subset A_y$.

Since you were wrong in (b), your argument for (c) is incorrect, since it uses the same flawed argument.

For (c), for each $X\subseteq \mathbb N$, define $o(X)=\{2n: n\in X\}\cup \{2n+1:n\notin X\}$. So that if $X\neq Y$ then $o(X)$ and $o(Y)$ are incomparable. In particlar, $o(X)\neq O(Y)$, so we have an anti-chain in $1-1$ correspondence with $\mathcal P(\mathbb N)$.

Answer 2

Ok so your a) is correct, upper bounds exist.

Your b) is wrong, for two reasons firstly your proof is incorrect, and secondly the answer is actually yes.

To see the flaw in your proof let $a\in A$ then $A\setminus\{a\}, A$ is a chain in the partial order yet $|A\setminus\{a\}|=|A|$ as $A$ is infinite.

To prove b) is true you need a trick. Firstly $|\mathcal{P}(A)|=|\mathbb{R}|$ and $|A|=|\mathbb{Q}|$.

So put $A$ in bijection with $\mathbb{Q}$, and consider dedekind cuts. We can associate a real number $x$ uniquely with a pair $(P_x,Q_x)$ where $P_x=\{p\in\mathbb{Q}\,:\, p\leq x\}$ and $Q_x=\{q\in\mathbb{Q}\,:\, x<q\}$, so now for each real number we have a set $P_x$ of rationals, and you can see that $x<y$ implies $P_x\subset P_y$. So replace the elements of $P_x$ with those in $A$ using our bijection and you have your continuum chain.

Answer 3

Your answer to (a) is correct.

Your answer to (b) is incorrect. The statement "if two sets have the same number of elements, then one cannot be a proper subset of the other" only holds for finite sets. Let $A=\{x+iy:x,y=1,2,3,\dots\}$, the Gaussian integers in the open first quadrant; of course $|A|=\aleph_0\cdot\aleph_0=\aleph_0$. For each angle $\theta\in(0,\frac{\pi}2)$ let $S_{\theta}=\{z\in A:0\lt\arg z\lt\theta\}\in\mathcal P(A)$. It's easy to see that $\{S_{\theta}:\theta\in(0,\frac{\pi}2)\}$ is a chain of the cardinality of the continuum.

For (c), let $\mathbb Q=\{q_n:n\in\mathbb N\}$ be an enumeration of the rational numbers. For each real number $t$ let $X_t=\{n:q_n\lt t\}\cup\{n+i:q_n\gt t\}\in\mathcal P(A)$. It's easy to see that $\{X_t:t\in\mathbb R\}$ is an antichain of the cardinality of the continuum.