Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. Let $w$ be an ordinal for a denumerable set. Prove that$(w+w)w=ww$

  2. Let A and B be sets. Let A be ordered by G and B by H. Let f be an isomorphism such that x≦y in G implies f(x)≦f(y) in H. Now, reorder A by an order relation G'. Then does there exist an isomorphism f' such that x≦y in G' implies f'(x)≦f'(y) in H?

Dear Asaf I think the book I'm studying is not really a good one. I'm really sorry that everytime i come up with easy questions, seems like I'm using this website to just do my homework quickly, but i don't.. I want you to know that I'm studying set theory by myself and this book gives only some definitions and leaves important theorems in exercises. I swear that i post questions I've tried to solve at least for an hour or a day.. Plus, even though i have solved problems, for some problems, I didn't like the way I solved because it's kinda messy so I wanted to know how to solve the problems easily

share|improve this question
    
@MarkDominus $\omega+\omega\ne\omega$ so it is not always true. –  azarel May 16 '12 at 1:28
    
@MarkDominus As azarel says, your statement isn't true for ordinal arithmetic. –  Steven Stadnicki May 16 '12 at 1:29
    
Two of us have already deleted our wrong answers for this question - I'd say it's far from easy! This is really an excellent exercise, and thank you for offering it up. –  Steven Stadnicki May 16 '12 at 1:49
1  
Katlus: Could you please clarify whether by $w$ you mean $\omega$. You can type it like this: $\omega$. Maybe adding the name of the book, together with page and number of exercise could be useful, too. (If some of the users have the book, they can look into the book if there some part of the questions are unclear.) To me the second question seems unclear, too - I've tried to explain my concerns below. –  Martin Sleziak May 16 '12 at 12:34
1  
Is it just me, or is there a personal message for me in this question? –  Asaf Karagila May 16 '12 at 12:36
show 3 more comments

2 Answers 2

up vote 4 down vote accepted

The result is false. A counterexample is obtained by taking $w=\omega^2+\omega+1$.

Note $w+w=\omega^2\cdot2+\omega+1$. Now, adding $z=\omega^2\cdot2+\omega+1$ to itself $\omega$ times is $\omega^3$, and adding $z$ to itself $\omega^2$ times is therefore $\omega^4$.

Then $(w+w)w=z(\omega^2+\omega+1)=\omega^4+\omega^3+\omega^2\cdot2+\omega+1$.

On the other hand, $ww=\omega^4+\omega^3+\omega^2+\omega+1<(w+w)w$.


In general, one can obtain many counterexamples by considering $w$ whose Cantor normal form includes indecomposables of several kinds, not all of them limit ordinals.

share|improve this answer
    
It may be a good replacement exercise to characterize the ordinals $w$ for which equality holds. –  Andres Caicedo May 16 '12 at 2:28
    
Andres: maybe (like my original post suggested) by $w$ he actually meant 'the' $\omega$, the ordinal of the naturals? The statement is certainly true there, and seems true for all (countable?) limit ordinals by some version of the argument Jason and I initially made... –  Steven Stadnicki May 16 '12 at 2:30
    
I've added Wikipedia link to Cantor normal form - I guess this might be useful for the users who just start to learn about ordinal arithmetic and do not know about CNF yet. I hope you don't mind my edit. –  Martin Sleziak May 16 '12 at 12:38
add comment

I assume that by $w$ you mean $\omega$.

Then showing $\omega\omega=(\omega+\omega)\omega$ is relatively easy.

The first one is the set $\omega\times\omega$, the second one is $(\omega\times\{0\}\cup(\omega\times\{1\}))\times\omega$, both of them with antilexicographic order, i.e. the second coordinate is more important.

The isomorphism between the two sets is $(a,2b)\mapsto((a,0),b)$ and $(a,2b+1)\mapsto((a,1),b)$.


In fact, this can be visualized quite easily $\alpha\times\beta$ means that you take ordinal $\beta$ and replace each element by a copy of $\alpha$. I.e. $\alpha\beta$ consists of "$\beta$-many" copies of $\alpha$ which you put one after each another, and they are ordered according to $\beta$.

In this sense $\omega\omega$ consists of $\omega$ copies of $\omega$.

What is $(\omega+\omega)\omega$? I've put several pairs of copies of $\omega$ after each other. This is the same as $2\omega$ copies of $\omega$, but $2\omega=\omega$. (If I replace each element in $\omega$ by a pair of elements, then I do not change the order type.)

At the moment I do not have time to draw a nice picture illustrating this but this might help too:

  • $\omega$ looks like $\ast \ast \ast \cdots$
  • $2$ is simply the two points $(\circ \circ)$
  • To get $2\omega$ we simply replace each $\ast$ by $(\circ \circ)$ and we get $(\circ \circ) (\circ \circ) (\circ \circ) \cdots$
  • Of course we can take parentheses away (they are just an auxiliary thing to show where the copies of $2$ were added), so this is simply $\circ \circ \circ \circ \circ \circ \cdots$
  • The two things look the same, only we have used $\ast$ to denote the elements in one of them and $\circ$ in another one.

You can prove the same thing using some rules for cardinal arithmetic, namely you have $\omega+\omega=\omega\cdot 2$ so it suffices to show that $2\omega=\omega$ (which might be easier for you). If you know both these things you get $$(\omega+\omega)\omega=(\omega2)\omega=\omega(2\omega)=\omega\omega.$$



More importantly I would like to ask you to clarify the second part (perhaps ti would be even better to post it as a separate question).

You have something like this:

Let $A$ and $B$ be sets. Let $A$ be ordered by $\le_G$ and $B$ by $\le_H$. Let $f$ be an isomorphism such that $x\le_G y$ implies $f(x)\le_H f(y)$. Now, reorder $A$ by an order relation $\le_{G'}$. Then does there exist an isomorphism $f'$ such that $x\le_{G'}y$ implies $f'(x)\le_H f'(y)$?

What precisely do you mean under isomorphism? If you mean isomorphism of ordered sets $(A,\le_G)$ and $(B,\le_H)$, then the definition of isomorphism includes that $x\le_G y$ $\Leftrightarrow$ $f(x)\le_H f(y)$. So your sentence such that $x\le_G y$ implies $f(x)\le_H f(y)$ seems to be redundant. Now if there are no conditions on $\le_{G'}$, you are basically asking whether two orders of the same set must be isomorphic. This is certainly not true. (But maybe I've misunderstood the question.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.