1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.