Omega, $\omega$

From Cantor's Attic
Jump to: navigation, search

The smallest infinite ordinal, often denoted $\omega$ (omega), has the order type of the natural numbers. As a von Neumann ordinal, $\omega$ is in fact equal to the set of natural numbers. Since $\omega$ is infinite, it is not equinumerous with any smaller ordinal, and so it is an initial ordinal, that is, a cardinal. When considered as a cardinal, the ordinal $\omega$ is denoted $\aleph_0$. So while these two notations are intensionally different---we use the term $\omega$ when using this number as an ordinal and $\aleph_0$ when using it as a cardinal---nevertheless in the contemporary treatment of cardinals in ZFC as initial ordinals, they are extensionally the same and refer to the same object.

Countable sets

A set is countable if it can be put into bijective correspondence with a subset of $\omega$. This includes all finite sets, and a set is countably infinite if it is countable and also infinite. Some famous examples of countable sets include:

  • The natural numbers $\mathbb{N}=\{0,1,2,\ldots\}$.
  • The integers $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$
  • The rational numbers $\mathbb{Q}=\{\frac{p}{q}\mid p,q\in\mathbb{Z}, q\neq 0\}$
  • The real algebraic numbers $\mathbb{A}$, consisting of all zeros of nontrivial polynomials over $\mathbb{Q}$

The union of countably many countable sets remains countable, although in the general case this fact requires the axiom of choice.

A set is uncountable if it is not countable.