# need help, order theory

• Nov 7th 2006, 02:50 PM
jenjen
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).
• Nov 7th 2006, 03:45 PM
topsquark
Quote:

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 $\displaystyle y \in N$ it is easy to show that there are a finite number of $\displaystyle x \in N$ such that x < y. Now, given any $\displaystyle y \in N \times N$ there are an infinite number of $\displaystyle 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 $\displaystyle 2 \times N$, $\displaystyle 1 \times N$, and $\displaystyle 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
• Nov 7th 2006, 05:56 PM
jenjen
thanks topsquark!! that was a quick reply! :)
• Nov 7th 2006, 08:02 PM
jenjen
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.
• Nov 8th 2006, 04:05 AM
topsquark
Quote:

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
• Nov 8th 2006, 07:19 AM
ThePerfectHacker
Quote:

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 $\displaystyle \phi:S \to S'$ and such that if, $\displaystyle 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 $\displaystyle \phi (\min )\leq \phi (x)$
And $\displaystyle \phi (\max)\geq \phi (x)$
• Nov 8th 2006, 07:40 AM
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).
• Nov 8th 2006, 09:22 AM
topsquark
Quote:

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:
$\displaystyle 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