A quick way of recognising countable sets

a repository of mathematical know-how

A quick way of recognising countable sets

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[QUICK DESCRIPTION]

A set $ A$ is countable if there is a way of giving a finite description to every element of $ A$.

[PREREQUISITES]

The definition of a countable set, the content of [[A good way of proving that a set is countable|this article]].

===See also===
[[A good way of proving that a set is countable]]

[GENERAL DISCUSSION]

It is not hard to prove that the set of all finite strings of symbols taken from a fixed finite alphabet is countable. Indeed, we can count in turn the strings of length 0, 1, 2, and so on. If the size of the alphabet is $k$ then for each $n$ there are $k^n$ strings of length $n$, and in particular finitely many. Therefore, by the simple lemma discussed in [[A good way of proving that a set is countable|this article]], we are done (either by saying that we have expressed the set of all finite strings as a countable union of finite sets or by considering the function that takes each string to its length).

It follows from this that if $A$ is any set, and if we can come up with a procedure for giving a finite description (in, say, the English language augmented by a few convenient mathematical symbols) to each of the elements of $A$, then $A$ is countable. After all, the description takes the form of a finite string of symbols taken from some fixed "alphabet" of symbols, and there are only countably many of those.
 
This is significant because it often gives an easy way of recognising that a set is countable. It also gives proofs of countability, though these proofs are usually slightly "silly" and better replaced by simpler ones. But if you have ever known instinctively that a set is countable before you have actually come up with a proof, then it may well be something like this principle that is in the back of your mind.

[EXAMPLE]

The rationals are countable because every rational has a description such as -35792/1293879861. Here, the alphabet is $\{0,1,2,3,4,5,6,7,8,9,-,/\}$.

[EXAMPLE]

The set of all polynomials with integer coefficients is countable since (a very slight modification of) the normal way of writing down such a polynomial is a finite string of symbols taken from the alphabet $\{0,1,2,3,4,5,6,7,8,9,+,-,x,\wedge\}$. Here, the symbol $\wedge$ is used instead of the normal notation for exponentiation, so for instance instead of writing $x^3-3x+1$ we would write $x\wedge 3-3 x+1$.

[EXAMPLE]

The set of all algebraic numbers is countable, since each one is a root of a polynomial that can be described as above, and for any fixed polynomial we can specify which root we are talking about in terms of the ordering on $\mathbb{R}$. For example, we could describe $(1+\sqrt{5})/2$ as "the second root of $x \wedge 2-x-1$". If we allow complex numbers then we could choose an ordering of the roots by taking them in order of their modulus, and for roots of equal modulus we could order them by their arguments (defined to lie in the interval $[0,2\pi)$). For example, $-i$ could be defined as "the second root of the polynomial $x\wedge 2+1$".

Alternatively, and more naturally, we could argue that since the set of polynomials with integer coefficients is countable and each such polynomial has finitely many roots, an easy deduction from the article [[A good way of proving that a set is countable]] shows that the algebraic numbers are countable.

[EXAMPLE]

The set of all non-increasing functions from $\mathbb{N}$ to $\mathbb{N}$ is countable. This time the fact that there is a finite description relies on the well-ordering principle for the natural numbers, which implies that every non-increasing function from $\mathbb{N}$ to $\mathbb{N}$ is constant from some point on. So every such function will have a description such as "$f(1)=23$, $f(2)=12$, $f(3)=f(4)=5$ and $f(n)=3$ for every $n\geq 5$."

[EXAMPLE]

The set of all finite subsets of $\mathbb{N}$ is countable, since each one can be finitely described by simply writing it in the usual way using the symbols, $\{$, $\}$, the integers from 0 to 9, and commas.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

A quick way of recognising countable sets

Recent articles

Active forum topics

Recent comments