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!

  • 2
    $\begingroup$ 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$. $\endgroup$ – Andreas Blass Mar 31 '15 at 13:06
  • $\begingroup$ @Andreas: Ha! It didn't even cross my mind. Thanks! $\endgroup$ – Asaf Karagila Mar 31 '15 at 13:09
  • $\begingroup$ Or follow Sierpinski and define the sequence explicitly for irrational $r>1$: let $r_n=\frac1n\lfloor nr\rfloor$ $\endgroup$ – 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}.$

  • $\begingroup$ 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". $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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