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.

Let $\omega$ be the order type of the totally ordered set $\mathbb{N}$, and $\omega +1$ the set $\Bbb{N}\cup \{0\}$.

$0$ is greater than all the natural numbers as per this ordering.

My question is why can't $\Bbb{N}$ be bijectively mapped to $\Bbb{N}\cup\{0\}$? I understand the basic argument:

  1. There is no element in $\Bbb{N}$ which maps to $\{0\}$.

  2. $\Bbb{N}$ is bijectively mapped to a proper subset of $\Bbb{N}\cup\{0\}$. A set can't be bijectively mapped to a proper subset of the co-domain and also the co-domain.

But I'm not confident about whether these arguments work for infinite sets. One of the reasons being I used to think if a set can be bijectively mapped to another set, then any permutation of that set can be bijectively mapped to the same set. But this is not true for mapping $\Bbb{N}\cup\{0\}$ to $\Bbb{N}$. Hence I'm not quite sure what arguments are valid for infinite sets. My questions:

1. Do my arguments work for infinite sets? If not, what arguments are required to prove that $\omega$ can't be bijectively mapped to $\omega + 1$?

2. Is picking out every element from the co-domain and proving that it has been injectively mapped to the only way of proving bijection? Does the selection of such an element assume the axiom of choice?

I realise my question may be unclear, and will attempt to make it more clear should anyone find it difficult to navigate this mess. Thanks in advance!

share|improve this question
    
It's common to define $\omega+1$ as $\omega\cup\{\omega\}$. Since $0$ is a natural number in the context of set theory, you should probably write $\Bbb N\cup\{\Bbb N\}$. –  Asaf Karagila Jul 14 '13 at 11:34

1 Answer 1

up vote 10 down vote accepted

But $\omega$ and $\omega+1$ are equipotent, which is to say: there is a bijection between the two sets. Consider the map $f(n)=n+1, f(\omega)=0$.

There is just no order isomorphism between the two sets. Because order isomorphism preserves the properties of the order, in particular the existence of a maximal element. $\omega+1$ has a maximal element, whereas $\omega$ doesn't.

But more can be said: If two ordinals are order-isomorphic then they are equal.


Note that when working with sets which are well-ordered, the axiom of choice is not used. We have a definable choice function (definable from the well-order, that is). In particular, if the codomain is countable we can always make choices.

share|improve this answer
    
Yes sorry I meant a 'similarity mapping' as described in a book. $f(a)\geq f(b)$ iff $a\geq b$. I suppose that is what is meant by order isomorphism. –  Ayush Khaitan Jul 14 '13 at 11:34
    
Sorry I'd like to add a small question with respect to your answer. You said $f(\omega)=0$. Can we do that? Is that different from saying $f(\infty)=0$ because this is a specific infinite number out of many possible infinitely huge numbers like $\omega^2$ etc? Thanks. –  Ayush Khaitan Jul 14 '13 at 11:38
    
You should review your basics again. What is $\infty$? $\omega$ is an element in the set $\omega+1$. If we want to define a bijection we need to say where does it go. $\infty$ is not a well-defined set (at least not without context). Is it in the domain of $\omega+1$? Is it something else? Why should $f$ be defined on $\infty$? –  Asaf Karagila Jul 14 '13 at 11:39
    
Note that there are bijections between $\omega$ and any countable ordinal, and there are countable ordinals that you can't even begin to imagine. None of these bijections is order preserving, except for the identity function. –  Asaf Karagila Jul 14 '13 at 11:40
    
Thanks for your answer! With regard to my argument: set $A$ can't be order isomorphic with both set $B$ and a proper subset of set $B$; is this argument also valid for infinite sets? –  Ayush Khaitan Jul 14 '13 at 11:48

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.