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.
Solution 1:
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:
- Is there an absolute notion of the infinite?
- In set theory, how are real numbers represented as sets?
Solution 2:
$\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}$.