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.

What is the difference between $\omega$ and $\mathbb{N}$?

I know that $\omega$ is the "natural ordering" of $\mathbb{N}$. And I know that $\mathbb{N}$ is the set of natural numbers (order doesn't matter?). And so, $\omega$ is a well-ordered set? an ordinal number? and $\mathbb{N}$ is an un-ordered set?

Is this right, is there anything else?

A little context: I'm wondering why people here have been telling me that a set $A$ is countable iff there exists a bijection between $A$ and $\omega$, as opposed to $A$ and $\mathbb{N}$. Does it make a difference?

Thanks.

share|improve this question
7  
"I'm wondering why people here have been telling me that a set A is countable iff there exists a bijection between A and ω, as opposed to A and N. Does it make a difference?" No, it does not. The difference between $\omega$ and $\mathbb N$ is, in my experience, generally one of different notations being used in different fields. Sure, a set and an ordered set are technically different objects, but we use $\mathbb N$ to refer to the set and the semiring all the time. So it's not really much more than a difference in notation. –  Alex Becker May 28 '12 at 1:27
    
Also, $\omega$ often refers to the ordinal (that is, we consider the well-ordering) while $\mathbb{N}$ refers to the set of natural numbers. –  Arturo Magidin May 28 '12 at 2:01
1  
@Andres: And with this the list is clear! Huzzah. –  Asaf Karagila May 2 at 6:21

2 Answers 2

up vote 3 down vote accepted

$\omega$ usually refers to ordinal, i.e. the least infinite ordinal.

However, I am not sure if this is standard (I think Simpson does this also in his book), but when I do Reverse Mathematics I usually distinguish between $\omega$ and $\mathbb{N}$.

In the language of second order arithmetics and in any structure $\mathcal{M}$ of second order arithmetics, I usually call $\mathbb{N}$, the set defined by $x = x$, i.e. the domain of the $\mathcal{M}$.

However, there are many models of second order arithmetics. In Reverse Math, there special models called $\omega$-models whose underlying domain is the the standard model of the natural number. Hence, when I am working in second order arithmetics, I will use $\omega$ to denote standard model of the natural numbers. Note there are nonstandard models of the natural number.

When I have a general model $\mathcal{M}$ of second order arithmetics, I use $\mathbb{N}$ to denote the domain of the models which may not be standard.

In summary I use $\mathbb{N}$ to refer to the set defined by $x = x$ in any model of second order arithmetics. Where as, $\omega$ refer to the actual natural numbers that everyone is familiar with.

To answer your question about countability. In any model of set theory (lets say ZFC), there is a set denoted $\omega$ which is the least infinite ordinal. A set $A$ is countable if there is a bijection between $A$ and $\omega$. Also if you take $\mathbb{N}$ to mean the domain of the structure of second order arithmetics, then within the fixed model of set theory, $\mathbb{N}$ may not be countable (by upward Lowenheim-Skolem); however, of course within a model of second order arithmetics the definition of countable means that a set is in bijection with $\mathbb{N}$.

share|improve this answer

Outside of set theory $\mathbb N$ is agreed to be the standard model of the Peano Axioms. Indeed this is a countable set.

When approaching foundational set theory (which I am now going to assume is ZFC), one prefers to avoid referencing more theories. In particular theories which we will later interpret within our universe.

On the other hand, the ordinal $\omega$ is a very concrete set in ZFC. It means that if I write $\omega$ I always mean one very concrete set. Of course that $\omega$, along with its natural order and the ordinal arithmetics is a model of the Peano Axioms, even the second-order theory.

Let us see why I take this as important (at least when talking about axiomatic set theory, in naive set theory I will usually let go of this). We often think of the following chain of inclusions:

$$\mathbb N\subseteq\mathbb Z\subseteq\mathbb Q\subseteq\mathbb R\subseteq\mathbb C$$ On the other hand we think of $\mathbb N$ as the atomic set from which we start working, $\mathbb Z$ is created by an equivalence relation on $\mathbb N$; later $\mathbb Q$ is defined by an equivalence relation over $\mathbb Z$; then $\mathbb R$ is defined by Dedekind cuts (or another equivalence relation); and lastly $\mathbb C$ is again defined by an equivalence relation.

How can we say that $\mathbb N\subseteq\mathbb C$? What we mean is that there is a very natural and canonical embedding of $\mathbb N$ (and all the other levels of the construction) which we can identify as $\mathbb N$ or $\mathbb R$, etc. In many places in mathematics it is enough to identify things up to isomorphism.

Note, however that it is still not the same set. In fact the result of $\mathbb C$ as a set will vary greatly on the choices we made along the way.

What about $\omega$? Well, that is always the smallest set such that $\varnothing\in\omega$ and if $x\in\omega$ then $x\cup\{x\}\in\omega$. Very concrete indeed.

I also find that this distinction helps to somewhat defuse the "how can the continuum hypothesis be independent of ZFC?" question, because $\mathbb N$ is an extremely concrete notion in mathematics, and people see it in a very concrete way. Of course it's not a great solution and it doesn't mean people accept the independence of the cardinality of the power set of $\omega$ instead, it's just easier.


To Read More:

  1. Is there an absolute notion of the infinite?
  2. In set theory, how are real numbers represented as sets?
share|improve this answer

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.