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

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.

-
"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
@Andres: And with this the list is clear! Huzzah. –  Asaf Karagila May 2 at 6:21

$\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}$.

-

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.