Results 1 to 2 of 2

Math Help - Compactness Theorem and partial orderings

  1. #1
    Newbie
    Joined
    Feb 2011
    From
    Penn State
    Posts
    1

    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!)

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    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., 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Corollary of compactness theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 7th 2011, 08:57 AM
  2. Set Theory - Total vs Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 12th 2011, 08:23 AM
  3. compactness theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 27th 2010, 09:46 AM
  4. Topological Compactness and Compactness of a Set
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 22nd 2009, 12:16 AM
  5. Equivalence Relations and Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2007, 10:13 PM

Search Tags


/mathhelpforum @mathhelpforum