Results 1 to 8 of 8

Math Help - need help, order theory

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    82

    need help, order theory

    Hi, can anyone help me on these two problems? thank you so muchhhh..

    1) Let D(n) denote the partially ordered set of positive integers d which divide n, and take the divisibility relation a l b to be the partial ordering. Prove that D(28) and D(45) are order-isomorphic, but the sets D(8) and
    D(15) are not even though they have the same numbers of elements.

    2) Let N be the nonnegative integers with the usual ordering, and take the lexicographic ordering on N X N. Prove that the linearly ordered sets N and
    N X N have different order types. (hint: for each x in N, the set of all y such that y < x is finite).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by jenjen View Post
    2) Let N be the nonnegative integers with the usual ordering, and take the lexicographic ordering on N X N. Prove that the linearly ordered sets N and
    N X N have different order types. (hint: for each x in N, the set of all y such that y < x is finite).
    Given any y \in N it is easy to show that there are a finite number of x \in N such that x < y. Now, given any y \in N \times N there are an infinite number of x \in N \times N such that x < y. For example, let y = 3 x 2. The set of x such that x < y is all elements below y or to the left of y. So we have 3 x 1 and 3 x 0 are less than y, but we also have the sets 2 \times N, 1 \times N, and 0 \times N, all three of which are countably infinite.

    Another way to approach this is to look at the sets N and N x N in terms of elements that have immediate predecessors. All elements in N except 0 have immediate predecessors. However all elements in N x N of the form y x 0 (an infinite number of them) have no immediate predecessors. Thus there is no bijection between the two sets and thus they don't have the same order type.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2006
    Posts
    82
    thanks topsquark!! that was a quick reply!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2006
    Posts
    82

    set theory: need helpp..plzzz.

    Hi, can anyone help me on these two problems? thank you so muchhhh..

    1) Let D(n) denote the partially ordered set of positive integers d which divide n, and take the divisibility relation a l b to be the partial ordering. Prove that D(28) and D(45) are order-isomorphic, but the sets D(8) and
    D(15) are not even though they have the same numbers of elements.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by jenjen View Post
    Hi, can anyone help me on these two problems? thank you so muchhhh..

    1) Let D(n) denote the partially ordered set of positive integers d which divide n, and take the divisibility relation a l b to be the partial ordering. Prove that D(28) and D(45) are order-isomorphic, but the sets D(8) and
    D(15) are not even though they have the same numbers of elements.
    Can you define the term "order-isomorphic" for me? I don't recognize the term.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by topsquark View Post
    Can you define the term "order-isomorphic" for me? I don't recognize the term.

    -Dan
    I am not familar with order theory but it makes sense to say.

    It is a partial ordered set. Such as,
    Two partial ordered sets are isomorphic when, there exists a bijection \phi:S \to S' and such that if, a\leq b\to \phi(a)\leq \phi(b).

    The problem is I do not see an isomorphism, I am sure there is some theorem when the order relation is division. But I do not know of one and I do not really want to check all the cases (there are 6^6 of them). I would guess that if the minimal and maximal elements exist (and they do by Zorn's lemma) then \phi (\min )\leq \phi (x)
    And \phi (\max)\geq \phi (x)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2006
    Posts
    82
    Hi Topsquark,

    definition: Let (A, < A) and (B, < B) be partially ordered sets. We say that A and B are similar, or have the same order types, or are order-isomorphic, if there exists a 1-1 correspondence f: A --> B such that for all u, v, in A we have u < A V if and only if f(u) < B f(v).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,842
    Thanks
    320
    Awards
    1
    Quote Originally Posted by jenjen View Post
    Hi Topsquark,

    definition: Let (A, < A) and (B, < B) be partially ordered sets. We say that A and B are similar, or have the same order types, or are order-isomorphic, if there exists a 1-1 correspondence f: A --> B such that for all u, v, in A we have u < A V if and only if f(u) < B f(v).
    The best I can do is by actually constructing the sets.

    D(28) has 5 elements, of which there are two subsets: {1, 2, 4, 28} and {1, 7, 28} that are completely ordered by the partial ordering.

    D(45) also has 5 elements, of which there are two subsets: {1, 3, 9, 45} and {1, 5, 45} that are completely ordered by the partial ordering.

    So if we propose the following relation:
    f: D(28) \to D(45) = {(1, 1), (2, 3), (4, 9), (7, 5), (28, 45)}
    we can easily see that it is a bijection.

    Now,
    D(8) = {1, 2, 4, 8} is completely ordered by the partial ordering and D(15) is not.
    D(15) has two subsets {1, 3, 15} and {1, 5, 15} that are completely ordered. Thus we cannot form a bijection between these two sets that preserves the partial ordering.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Group Theory and Order of Elements
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: July 31st 2013, 09:17 PM
  2. First Order Perturbation Theory help
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: October 23rd 2011, 12:17 PM
  3. first-order theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 7th 2010, 04:29 AM
  4. Group Theory - order of element
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: December 2nd 2009, 04:50 AM
  5. Number theory, order of an integer
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 05:53 AM

Search Tags


/mathhelpforum @mathhelpforum