Show that $P$ is the union of $k$ chains . 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.
 A: 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.
A: 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$.
A: 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:

*

*$(p_{a1}\vee\ldots\vee p_{ak})$ for all $a\in P$.

*$\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}$.
