# Compactness Theorem and partial orderings

• Feb 1st 2011, 07:44 PM
Compactness Theorem and partial orderings
Hello folks,

I've been asked 'If P is a partial ordering, how do I use the compactness theorem to show that P is the union of k chains iff each finite subset on P is the union of k chains?'

But, I have absolutely no idea what this question is even driving at. Set theory and logic is easily my weakest area of maths and any help would be much appreciated (I will attempt to reciprocate in differenctial equations or algebra - things I can actually do!)

• Feb 2nd 2011, 12:35 PM
emakarov
A chain is a totally ordered subset.

There is a question what a subset of P is. Let's say P is an order on a set A, i.e., $\displaystyle P\subseteq A\times A$. Then a subset of P could mean a subrelation on the same set A. However, if A is infinite, the premise of the statement is trivially false and so the statement is trivially true. Indeed, each finite subrelation has infinitely many isolated points, and each of them is a degenerate chain. So I think the problem is talking about finite subsets of A and restrictions of P on these subsets.

I have not worked out all details, but the idea may be as follows. Let C be a formula saying that for any k + 1 elements, some pair of them are comparable. We can prove that C holds for P.

Let A_n be a subset of A with n elements and let P_n be the restriction of P to A_n. By [P_n] I will denote a single formula that records the structure of P_n. It has constants c_1, ..., c_n and is a big conjunction of inequalities between these constants. If constants' names are chosen consistently, then [P_n] implies [P_k] for k < n. The problem statement implies that for each n, the set {[P_1], ..., [P_n], C} is consistent since P_n is its model. Therefore, the union of these sets is consistent by compactness theorem. A model of this union must include P as a substructure and so C is true on P.