# Thread: need help, order theory

1. ## 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).

2. Originally Posted by jenjen
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

3. thanks topsquark!! that was a quick reply!

4. ## 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.

5. Originally Posted by jenjen
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

6. Originally Posted by topsquark
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)$

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

8. Originally Posted by jenjen
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