Countable set

In mathematics, a set is called countable if it is either small and has a limited number of items, or if we can match each item in the set with a unique whole number. This means we can "count" the items one by one, even if there are infinitely many. For example, the numbers 1, 2, 3, and so on are countable because each number can be paired with its position in the list.

A set that is countable but not limited in size is called countably infinite. This includes sets like all the whole numbers or all the fractions. These sets have an endless number of elements, but we can still arrange them in a way that lets us count them, step by step.

The idea of countable sets was developed by Georg Cantor. He also discovered that there are sets that are not countable, meaning they are too large and complex to pair with the whole numbers. An example is the set of all real numbers, which includes both whole numbers and numbers with decimals that go on forever without repeating.

A note on terminology

Sometimes people use the word "countable" to mean only what we call "countably infinite." In that case, they use "at most countable" for what we simply call "countable."

Other words like "enumerable" and denumerable are also used, but their meanings can change, so it's important to be careful, especially when thinking about things that can be listed step-by-step, known as recursively enumerable.

Definition

A set is called countable if it either has a limited number of elements or can be matched perfectly with the set of natural numbers (like 1, 2, 3, and so on). This means we can list all its elements one by one, even if it takes forever because there are infinitely many.

For example, the natural numbers themselves are countable because we can pair each natural number with another one in a never-ending list. However, some sets, like all the real numbers between 0 and 1, are not countable. This is because no matter how we try to list them, we can always find a real number that isn't on our list. This idea was shown by a mathematician named Georg Cantor.

Formal overview

A set is called countable if we can pair each item in the set with a unique natural number, like 1, 2, 3, and so on. This means we can "count" the items in the set, even if there are infinitely many.

For example, the set of numbers {1, 2, 3} is countable because we can pair 1 with 1, 2 with 2, and 3 with 3. Even infinite sets, like the set of all whole numbers, are countable because we can create a never-ending list that includes every number exactly once.

Minimal model of set theory is countable

If there is a special collection of numbers and ideas that follows all the rules of ZFC set theory, then there is a smallest such collection. We can use a special math rule called the Löwenheim–Skolem theorem to show that this smallest collection can be counted, even though it seems strange because it contains things that look like they can't be counted.

This smallest collection includes all the algebraic numbers and many other types of numbers that we can calculate.

Total orders

Countable sets can be arranged in a specific way, called a total order, in different manners. One common way is called a well-order, where every part of the set has a smallest element. For example, the natural numbers (0, 1, 2, 3, and so on) are a well-order. Another example is the integers arranged as (0, 1, 2, 3, ...; −1, −2, −3, ...).

Other orders are not well-orders. For instance, the integers in their usual order (..., −3, −2, −1, 0, 1, 2, 3, ...) and the rational numbers are examples where some parts of the set do not have a smallest element. This difference helps us understand if an order is also a well order.