Im tackling this question: enter image description here

So Im ok with part (a)

For part (b) I came up with

$\sigma_n :=\exists x_1 \exists x_2 ... \exists x_n \Bigg(\bigwedge_{i\neq j}\Big(\neg (x_i\leq x_j)\wedge \neg (x_j\leq x_i)\Big)\Bigg)$

But I don't understand part (c). To me if you have $\sigma_n$ true for all $n$ then I can find an anti-chain with arbitrarily large size so there is an infinite anti chain.


2 Answers 2


Your answer to part b) looks correct to me.

Suppose we have a set $\{X_n: n \in \mathbb{N} \}$ of antichains in some model $\mathcal{M}$, where $X_i$ is of size $i$. Then, although we have arbitrarily large finite antichains, we don't necessarily have an infinite antichain. If we also knew that $X_i \subseteq X_{i+1}$ for each $i$, then $\bigcup_{n \in \mathbb{N}} X_n$ would be an infinite antichain - but that assumption does not always hold true.

A case in point is the model in part c). We have that $x \preccurlyeq y$ iff $x=y$, or there is some $n^2$ less than $y$ but not less than $x$. Thus to find an antichain of size $k$, we just need to find a set of $k$ natural numbers $x_1, \ldots, x_k$ such that if $n^2 < x_i$ then $n^2 < x_j$ for any $i, j \le k$. In other words, we need to find a gap between two consecutive squares that's at least $k$ numbers long. (This is clearly possible, as $(k+1)^2 - k^2$ is unbounded.) Thus for any $k$, $(\mathbb{N}, \preccurlyeq) \vDash \sigma_k$. However, there's no infinite antichain $\{x_1, x_2, \ldots \}$ in $(\mathbb{N}, \preccurlyeq)$ as this would imply that there is a square number with an infinite gap before the next square, i.e. a biggest square number.


Alex McKenzie has already given a good explanation (which I’ve upvoted) of why (c) contains arbitrarily large finite antichains but no infinite antichain; I can only add that you should verify that $k\not\preceq\ell$ and $\ell\not\preceq k$ if and only if $k\ne\ell$ and there is an $n\in\Bbb N$ such that $n^2<k,\ell\le(n+1)^2$.

However, I thought that it might help to see another example of the phenomenon. The underlying idea is exactly the same, but seeing it in a different guise may help.

For $n\in\Bbb N$ let $N_n=\{0,1,\ldots,n\}$, and let $L_n=\{n\}\times I_n$; in other words,

$$L_n=\left\{\langle n,k\rangle\in\Bbb N\times\Bbb N:k\le n\right\}=\{\langle n,0\rangle,\langle n,1\rangle,\ldots,\langle n,n\rangle\}\;.$$

Let $P=\bigcup_{n\in\Bbb N}L_n$, and define a relation $\preceq$ on $P$ by $\langle m,k\rangle\preceq\langle n,\ell\rangle$ if and only if $\langle m,k\rangle=\langle n,\ell\rangle$ or $m<n$. It’s very easy to check that $\preceq$ partially orders $P$, and that $L_n$ is an antichain of cardinality $n+1$ for each $n\in\Bbb N$. In fact, the sets $L_n$ are the ‘levels’ in the Hasse diagram of $\langle P,\preceq\rangle$, and in the Hasse diagram there is an edge between $\langle n,k\rangle$ and $\langle n+1,\ell\rangle$ for every $n\in\Bbb N$, $k\in N_n$, and $\ell\in N_{n+1}$. (In the language of graph theory, the subgraph of the Hasse diagram induced by levels $L_n$ and $L_{n+1}$ is a complete bipartite graph $K_{n+1,n+2}$.)

Now let $A$ be an infinite subset of $P$, and let $M=\{n\in\Bbb N:A\cap L_n\ne\varnothing\}$; $M$ is the set of levels that $A$ ‘hits’. Each $L_n$ is finite, so $M$ must be infinite. In particular, there are $m,n\in M$ such that $m<n$. But then there are $k,\ell\in\Bbb N$ such that $\langle m,k\rangle\in A$ and $\langle n,\ell\rangle\in A$, and it follows that $A$ cannot be an antichain, since $\langle m,k\rangle\preceq\langle n,\ell\rangle$.

The partial order is carefully constructed so that any antichain must be confined to one level: points that are from different levels are always related by $\preceq$, the one from the lower level being smaller in the partial order $\preceq$ than the one from the higher level. And since each level is finite, all antichains are finite, though they can be of as large a finite size as we wish.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .