Show that $P$ is the union of $k$ chains .

Question

I just started taking an introduction to logic course and came across this problem:

Let $P$ be a partial ordering such that every finite subset of $P$ is the union of $k$ chains. Show that $P$ is the union of $k$ chains.

I tried to do this assuming that $P$ is countable: Let $P$ be countable and let $A_0$ be a finite subset of $P$. Then we can write $ P\setminus A_0= \cup_{j=1}^{\infty}\{p_j\}$. By assumption, $A_0$ is the union of $k$ chains and for $p_1 \notin A_0$, $A_0 \cup \{p_1\}$ is also a finite subset of $P$ and thus is the union of $k$ chains. By letting $A_n = A_{n-1} \cup \{p_n\}$ we see by induction that $A_n$ is the union of $k$ chains for any $n$ and since $A_n \nearrow P$, we get that $P$ is the union of $k$ chains.

I'm not sure if my last line is correct as I am saying the limit of the $A_n$'s is a $k$-chain.

How else should I go about this? What should I do if $P$ is uncountable?

Thanks in advance for any help.

Answer 1

Given a set $I$, and a finite set $A_i$ for each $i\in I$, a choice function $f$ on a subset $X\subseteq I$, selects an element $f(x)\in A_x$ for each $x\in X$.

Suppose for each finite subset $J\subseteq I$ we have a choice function $f_J$ on $J$.

Rado selection principle: There is a choice function $f$ on $I$, that on any finite set $J$ agrees with one of the $f_K$, where $K\supseteq J$.

Solution to your problem:

Setup:

Let $I=P$ your poset. Let $A_i=\{1,2,\cdots, k\}$ for each $i\in I$. For each finite set $J$ let $f_J$ be a choice function, so that the preimage $f_J^{-1}(t)$ is a chain for each $t=1,\cdots,k$. (The existence of $f_J$ is equivalent to $J$ being a union of $k$ chains).

Applying the Rado selection principle:

we obtain a choice function $f$ on $I$, which on each finite set agrees with some $f_K$. Thus if $f(x)=f(y)$ then $f_K(x)=f_K(y)$ for some $K$ and $x\leq y$ or $y\leq x$. Thus $P$ is the union of the $f^{-1}(t)$, for $t=1,\cdots,k$, and each of these is a chain.

---

Proof of the Rado selection principle from Zorn's lemma:

Say that a choice function $g$ on a subset $X\subseteq I$ is extendable if for all finite subsets $J\subseteq I$, there exists a finite subset $K\supseteq J$, such that $g$ agrees with $f_K$ on $X\cap J$.

We can partially order extendable choice functions: If $g,h$ are extendable choice functions on subsets $X,Y\subseteq I$ respectively, we say $g\leq h$ whenever $X\subseteq Y$ and $g,h$ agree on $X$.

Note that the empty choice function on the empty set is extendable, as it agrees with any $f_J$ on the empty set.

Suppose we have a chain of extendable choice functions $g_\alpha$ on subsets $X_\alpha\subseteq I$. Let $X$ be the union of the $X_\alpha$ and let $g$ be the induced choice function on $X$. We claim that $g$ is extendable:

Given a finite subset $J\subseteq I$, we have $J\cap X=J\cap X_\alpha$ for some $\alpha$. As $g_\alpha$ agrees with some $f_K$ on $X_\alpha\cap J$, we have that $g$ agrees with $f_K$ on $X\cap J$.

Thus applying Zorn's lemma, we may select $f$ to be a maximal extendable choice function. Let $X\subseteq I$ be the domain of $f$. Suppose $X\neq I$ so we have some $y\in I$ with $y\notin X$.

For each $a\in A_y$, let $f_a$ be the extension of $f$ to $X\cup\{y\}$ mapping $y\mapsto a$.

We claim that some $f_a$ is extendable. If not, we must have finite subsets $J_a\subseteq I$ for each $a \in A_y$ such that $f_a$ does not agree with any $f_K$ on $(X\cup\{y\})\cap J_a$. Note for all $a\in A_y$ we must have $y\in J_a$.

Let $J$ be the union of the $J_a$ and let $f$ agree with $f_K$ on $J$, for some $K\supseteq J$. Let $a=f_K(y)$. Then $K\supseteq J\supseteq J_a$ and $f_a$ agrees with $f_K$ on $(X\cup\{y\})\cap J_a$, giving the desired contradiction.

Thus $f<f_a$ for some $a\in A_y$, contradicting the maximality of $f$. We conclude that $X=I$. Thus $f$ is a choice function on $I$, and as it is extendable, it satisfies the required property.

Answer 2

Here is an easy proof using the compactness theorem for first-order logic. It applies to posets of arbitrary cardinality.

Let $L = \{\leq, C_1,\dots,C_k\}\cup \{c_a\mid a\in P\}$, where $\leq$ is a binary relation, the $C_i$ are unary relations, and the $c_a$ are constant symbols (one for each element of the poset).

Consider the theory $T$ containing:

• The poset axioms for $\leq$.
• Axioms asserting that each $C_i$ defines a chain.
• An axiom asserting that every element is in one of the $C_i$.
• The diagram of $P$.

Now $T$ is finitely satisfiable: Any finite subset $T'\subseteq T$ mentions only finitely many constant symbols from a finite subset $P'\subseteq P$. We can turn $P'$ into a model of $T'$ by interpreting $\leq$ and the constant symbols in the obvious ways and interpreting the $C_i$ as chains whose union is $P'$.

By compactness, $T$ has a model $\mathbb{P}$. Now $\mathbb{P}$ is a poset which is a union of $k$ chains (the $C_1^\mathbb{P},\dots,C_k^{\mathbb{P}}$), and it contains an isomorphic copy of $P$ as a substructure (the interpretations of the constants). Then $P$ is a union of restrictions of the $k$ chains: $C_i^\mathbb{P}\cap P$.

Answer 3

Let $(P,\preceq)$ be a poset. Then $P$ is the union of $k$ chains if and only if each finite subset of $P$ is the union of $k$ chains.

We define a propositional language $L$ to be the set having propositional atoms $p_{ai}$, for each element $a\in P$ and each $1\leq i\leq k$. An atom $p_{ai}$ expresses element $a$ is in the $i^{th}$ chain when true. Then we define $C_{k}(P)$ to be the set of $L$-formulas:

1. $(p_{a1}\vee\ldots\vee p_{ak})$ for all $a\in P$.
2. $\neg(p_{ai}\wedge p_{bi})$ for all incomparable $a,b\in P$ and $1 \leq i\leq k$.

Note that, when true, 1. expresses each element $a\in P$ is in at least one chain, and 2. expresses any two incomparable elements $a,b\in P$ cannot be in the same chain.

Now we will prove the $\Leftarrow$ implication by showing that $C_{k}(P)$ is satisfiable and use any $L$-assignment satisfying $C_{k}(P)$ to express $P$ as the union of $k$ chains.

First, we prove that $C_{k}(P)$ is finitely satisfiable. Indeed, suppose that $S$ is a finite subset of $C_{k}(P)$. Then the elements of $P$ mentioned in $S$ constitute a finite subset $P_{S}\subseteq P$, and restricting $\preceq$ to this subset yields a finite poset $(P_{S},\preceq)$. By hypothesis $P_{S}$ is the union of $k$ chains, say $X_{1},\ldots, X_{k}$. Then we define an $L$-assignment $\nu$ by $$\nu(p_{ai})=\rm{T}\rm{\;\;iff\;\;} a\in X_{i}.$$ Clearly $\nu$ satisfies $S$ and, by the Compactness Theorem, $C_{k}(P)$ is satisfiable.

Second, note that if $\nu$ is an $L$-assignment satisfying $C_{k}(P)$ we can define for each $1\leq i\leq k$ the set $$X_{i} = \{a\in P : \nu(p_{ai}) = \mbox{T}\},$$ which, by 2. will be a chain. When this is combined with 1. we have that $P=X_{1}\cup\ldots\cup X_{k}$, as desired.

The $\Rightarrow$ implication is quite straightforward because if $P$ is the union of $k$ chains $X_{1},\ldots, X_{k}$ and $P_{0}$ is a any subset of $P$, then the sets $Y_{i}=P_{0}\cap X_{i}$, $1\leq i\leq k$ are $k$ chains whose union is $P_{0}$.