Antichains of maximal size in the set of all finite subsets of a singular cardinal

infinitary-combinatoricsorder-theoryset-theory

Let $P = (P, \le)$ be a partially ordered set. A subset $T$ of $P$ is called:

  1. cofinal (in $P$), if for all $x \in P$ there is a $t \in T$ such that $x \le t$,
  2. antichain, if for all $x, y \in T$, $x \le y$ implies $x = y$.

Now let $\kappa$ be an uncountable cardinal,
$P = [\kappa]^{< \omega}$ be the set of all finite subsets of $\kappa$, partially ordered by inclusion.
For $T \subset P, n < \omega$, define $T_n = \{a \in T: |a| = n\}$.

Question: Let $T \subset P$ be cofinal in $P$.
Does $T$ contain an antichain of size $\kappa$ ?

Notes.

  1. It is well-known (and easy to see) that $|T| = |P| = \kappa$.
  2. The question would be trivial, if we just considered $P$ instead of $T$, since
    $P_1 = \{ \{\alpha\}: \alpha < \kappa\}$ is an antichain
    of size $\kappa$.
  3. This is false for $\kappa = \omega$, since
    $T = \{ \{0, \ldots, n \}: n \in \omega \}$ is linearly ordered and
    cofinal in $[\omega]^{< \omega}$.
  4. This is true, if $ \omega < \text{cf}(\kappa)$ (in particular, if
    $\kappa$ is regular uncountable).
    [Since $T = \bigcup_{n < \omega} T_n$, there is a $n < \omega$, such that
    $|T_n| = \kappa$.]
  5. Hence, the first interesting case is $\kappa = \aleph_\omega$.
    (And I believe the question boils down to this case.)
  6. For $\kappa = \aleph_\omega$, such an easy attempt
    as in 4. does not work:
    for $n < \omega$ let
    $S_n = \{a \subset \aleph_n: |a| = n\}$.
    Then $\bigcup_{n < \omega} S_n$ is cofinal in $P$,
    but
    $|(\bigcup_{n < \omega} S_n)_m| = |S_m| = \aleph_m$
    for each $m < \omega$.
  7. $T$ contains an antichain of size $\lambda$
    for each cardinal $\lambda < \kappa$.
    [Use the same partition of $T$ as in 4.]

Best Answer

$T$ does indeed contain an antichain of size $\kappa$. This appears to not really be about cofinality, and is rather an argument about cardinality in general, i.e., any uncountable subset $T\subseteq [\kappa]^{< \omega}$ will have an antichain of the same cardinality $|T|$.

Here is a proof.

Given subsets $A,B\subseteq T$, denote by $R(A,B)$ the set of all $b\in B$ such that $a\not\leq b,b\not\leq a$ for every $a\in A$. These should be thought of as the remaining elements of $B$ that are candidates for our antichain once we decide to include $A$.

Now, let $n_i$ be the subsequence of indices for which $|T_{n_i}|$ is uncountable, and note that $|T|=|\bigcup_i T_{n_i}|$. We could actually still make the ensuing induction argument even if this subsequence were finite, but in any case we lose no generality assuming the subsequence is infinite, as otherwise (as noted in the comments below) we have some $n$ with $|T_n|=|T|$, and we could then simply take $T_n$ as our antichain.

For each stage $i$, we will inductively construct $S_i\subseteq T_{n_i}$ so that

  1. $\bigcup_{k\leq i}S_k$ is an antichain.
  2. $|S_i|=|T_{n_i}|$.
  3. For each $j>i$, $\left|R\left(\bigcup_{k\leq i}S_k,T_{n_j}\right)\right|=|T_{n_j}|$.

It will then follow that $\bigcup_{k=1}^\infty S_k$ is an antichain with the desired cardinality $|T|$.

Having defined $S_k$ for all $k<i$, we define $S_i$ as follows.

Let $\lambda=|T_{n_i}|=\left|R\left(\bigcup_{k<i}S_k, T_{n_i}\right)\right|$, with the second equality holding trivially if $i=0$ and by Property 3) for stage $i-1$ otherwise. Let $$f\colon \lambda\times \lambda \to R\left(\bigcup_{k<i}S_k, T_{n_i}\right)$$ be a bijection. Let $S_{i}^\alpha$ denote $f(\{\alpha\}\times \lambda)$ for each $\alpha\in \lambda$.

We observe that for every $j>i$, there are at most finitely many $\alpha$ for which $$\left|R\left(\left(\bigcup_{k<i} S_k\right)\cup S_{i}^\alpha,T_{n_j}\right)\right|<|T_{n_j}|.\tag{P}$$ In fact, there can be at most $\binom{n_j}{n_i}$. To see this, first note that given a finite collection of such indices $\alpha_m$, since we have $$\left|\bigcup_m R\left(\left(\bigcup_{k<i} S_k\right)\cup S_{i}^{\alpha_m},T_{n_j}\right)\right| < |T_{n_j}|=\left|R\left(\bigcup_{k<i} S_k,T_{n_j}\right)\right|,$$

there is some $$t\in R\left(\bigcup_{k<i} S_k,T_{n_j}\right)\backslash \bigcup_m R\left(\left(\bigcup_{k<i} S_k\right)\cup S_{i}^{\alpha_m},T_{n_j}\right).$$ Therefore $t\in T_{n_j}$ is comparable to one element in each of the disjoint sets $S_{i}^{\alpha_m}\subseteq T_{n_i}$, and an element in $T_{n_j}$ can only be comparable to $\binom{n_j}{n_i}$ elements of $T_{n_i}$.

It follows that there are at most countably many indices $\alpha$ for which (P) holds for any $j>i$, so we may choose some index $\alpha_0\in \lambda$ for which (P) always fails. We let $S_i=S_i^{\alpha_0}$, and argue our three inductive properties are satisfied.

Indeed, for Property 1), $S_i$ was chosen from elements of $R\left(\bigcup_{k<i}S_k, T_{n_i}\right)$, which are not comparable with each other, nor with any members of $S_k$ for $k<i$, so $\bigcup_{k\leq i}S_k$ is an antichain.

Property 2) is ensured by the construction of $S_i$ via the bijection $f$.

Property 3) is ensured since (P) always fails.

Thus the induction can proceed, and we are finished.

Related Question