# Antichain on $\mathcal{P}(\omega)/fin$ of cardinality $2^{\aleph_0}$?

We define an equivalence relation on $\mathcal{P}(\omega)$: for $x,y\in\mathcal{P}(\omega)$ we say $$x\simeq_{fin} y \text{ iff there is } n \in \omega \text{ such that } x\setminus \{0,\ldots,n\} = y \setminus \{0,\ldots,n\}.$$

The set $\mathcal{P}(\omega)/\simeq_{fin}$ is usually written as $\mathcal{P}(\omega)/fin$. For $[x], [y]\in \mathcal{P}(\omega)/fin$ we say $[x]\leq[y]$ iff there is $n \in \omega$ such that $(x\setminus \{ 0,\ldots,n\}) \subseteq (y \setminus \{0,\ldots,n\})$. It is a routine verification that this relation is well-defined.

Does $\mathcal{P}(\omega)/fin$ contain an anti-chain of cardinality $2^{\aleph_0}$?

Yes. This is an easy exercise:

For every $r\in\Bbb R$ fix some sequence of rational numbers $r_n$ such that $\lim r_n=r$. Now enumerate $\Bbb Q$ as $\{q_n\mid n\in\Bbb N\}$ and consider $A_r=\{k\mid\exists n:q_k=r_n\}$.

Then given $r\neq r'$, the sequences $r_n$ and $r'_n$ must be disjoint from some point onwards, because $\Bbb R$ is Hausdorff. Therefore $A_r$ and $A_{r'}$ have finite intersection. And so $\{[A_r]\mid r\in\Bbb R\}$ is an antichain of size $2^{\aleph_0}$.

And behold, by choosing $r_n$ to be $q_k$, such that $k$ is the least for which $0<|q_k-r|<\frac1n$, the entire thing doesn't require a smidgen of choice too!

• It might be worth pointing out that this example works whether you use the set-theorist's definition of antichain (pairwise incompatible) or everybody else's definition (pairwise incomparable). If you wanted only the latter, weaker sort of antichain, you could take the sets $\{k:r<q_k<r+1\}$ for all reals $r$. – Andreas Blass Mar 31 '15 at 13:06
• @Andreas: Ha! It didn't even cross my mind. Thanks! – Asaf Karagila Mar 31 '15 at 13:09
• Or follow Sierpinski and define the sequence explicitly for irrational $r>1$: let $r_n=\frac1n\lfloor nr\rfloor$ – KP Hart Sep 20 '18 at 15:04

Consider the antichain $\{ [x]: x\in A \},$ where $A$ is an almost disjoint family of subsets of $\omega$ of size $2^{\aleph_0}.$

• That's circular, isn't it? It's like saying to someone who asks how to prove something without the axiom of choice "Oh, just use Zorn's lemma". – Asaf Karagila Mar 31 '15 at 13:00

You can build a perfect tree where the branching happens always and only at certain specified levels.

There is an antichain of $2^n$ many finite strings $\sigma_{i, n}$ of length $2^n$.

Consider sequences $\tau =\lim_{n}\tau_n$ where $$\tau_n = \tau_{n-1}\sigma_{[\tau_{n-1}]\cdot 2+i_n, n}$$ (concatenation denoted by juxtaposition here) where the $[\sigma]$th string of the same length as $\sigma$ is $\sigma$. There are continuum many choices of $i_n \in \{0,1\}$ in an infinite sequence $\tau$ and these $\tau$ form an antichain.