Prove ...is a well-order

**tcRom** · October 14th 2009, 10:56 AM

Given P={1,2,3,...} with usual < ordering
Let f(n)= the number of distinct prime divisors of n
(ie: f(1)=0, f(2)=1, f(3)=1, f(4)=1, f(5)=1, f(6)=2,...)

Now, define $\triangleleft$ on P where:
a $\triangleleft$ b iff f(a) < f(b) OR [f(a) = f(b) and a < b]

So, I need to prove that P with $\triangleleft$ is a well-ordering; prove transitive, irreflexive, comparable, and that every non-empty subset has a least element. The last part here is my problem, everything else is fine but I need help proving the least element part.

I know that if you break up P into sets so that all numbers with 1 unique prime divisor goes into a subset, then all the numbers with 2 unique prime divisors go into a disjoint subset, and so on, where each subset is ordered as usual by <. Then, take the union of these subsets and it can be shown that it still holds the usual ordering of <, but we are now dealing with $\triangleleft$ ordering so it is a well-ordering (since < is a well ordering). As a restatement of my issue, I need help writing this out and actually making it solid. I've been working on it for a while...

Cheers and thank you!

**clic-clac** · October 14th 2009, 11:13 AM

You can prove $\triangleleft$ is a well ordering using that $<$ is a well ordering.

Let $X$ be a non empty subset of $P.$ Then $f(X)$ is a non empty subset of $P,$ which has a least element $b$ for $<.$

Consider $X\cap f^{-1}(b)\subseteq P,$ which is also a non empty subset (why?) of $P.$ Once again, it has a least element for $<,$ let say $a.$

Prove that $a$ is the least element for $\triangleleft$ in $X.$

Thread: Prove ...is a well-order

LinkBack

Thread Tools

Display

Prove ...is a well-order

Similar Math Help Forum Discussions

Prove: order ab = ord a * ord b

Prove that a group of order 375 has a subgroup of order 15

Prove that a^k has and order m/d

Prove that if b is the only element of order 2 in G, then b E Z(G)

Prove that the order of Z(G) is either <e> or G

Search Tags