4
$\begingroup$

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}$?

$\endgroup$
4

3 Answers 3

12
$\begingroup$

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!

$\endgroup$
3
  • 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$ Mar 31, 2015 at 13:06
  • $\begingroup$ @Andreas: Ha! It didn't even cross my mind. Thanks! $\endgroup$
    – Asaf Karagila
    Mar 31, 2015 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, 2018 at 15:04
6
$\begingroup$

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

$\endgroup$
1
  • $\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, 2015 at 13:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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