📂Set Theory

Countable and Uncountable Sets

Definitions ¹

1. A set $X$ is called a countable set if it is either a finite set or $X \sim \mathbb{N}$.
2. A set that is not countable is called an uncountable set.

---

• $\mathbb{N}$ is the set of natural numbers.
• $X \sim Y$’s $\sim$ denotes the equivalence of sets.

Explanation

The concept of countable sets might not be intuitively accepted by Easterners, including Koreans. This comes from a fundamental difference in thought between the language groups of Indo-European languages, including English, and our mindset. As known, European languages have gender for nouns, and verbs and adjectives inflect according to number and case, presenting ‘hard to sympathize with’ grammatical characteristics. Especially regarding numbers, before even touching on grammar, there’s a lot of puzzlement about why such distinctions are made, and this linguistic mindset difference manifests itself in the difference between Eastern and Western mathematics.

To count means to be able to count ‘one, two, …’ and how many items there are. For instance, humans, wrist watches, and oranges. Uncountable things include water or bread, which have a quantity, not a count, and can be arbitrarily divided. Thus, A dog means one dog and Dogs means several dogs, but Dog would mean dog meat. Obviously, context exists in language, and it’s not interpreted this extremely, but it’s possible.

It seems explaining the why behind this distinction is harder than explaining that we also use weird expressions. For example, in East Asian countries including Korea, we use ‘useless’ units like person for people, animal for creatures, long thin objects receive a unit, as do thin broad objects and buildings, etc. It doesn’t mean these expressions are never used in English or that Korean always uses them, but it’s important that we naturally accept them at the base of our thought process.

That is, although one could simply say “one pencil,” if someone asks to “borrow one pencil,” the natural feeling that it doesn’t feel odd to count pencils by the unit decides the real language habit. If one doesn’t fully internalize English to the bone, even if their English is good enough to not hinder communication, the usage of articles like a, the could be all over the place, feeling awkward. That’s just how language is. You accept it, and there’s no choice but to accept it. And the differences between languages are essentially nothing to worry about since it’s just how things always have been.

---

• [1]: If $X \sim \mathbb{Z}$, then $X$ is a countable set.
• [2]: If $X \sim \mathbb{Q}$, then $X$ is a countable set.
• [3]: If $X \sim \mathbb{R}$, then $X$ is an uncountable set.

Surprisingly, such differences also manifest in actual mathematics, and, as [3] suggests, it’s possible to explicitly propose uncountable sets. This fact was proven by the father of set theory, Georg Cantor, who himself was amazed by the existence of such uncountable sets. But could such concepts, not to mention the distinction between singular and plural, have emerged in East Asian mathematics? While it’s not possible to say for sure, it took a staggering 2500 years after Pythagoras for a single genius to discover uncountable sets. If pure mathematics had developed in the East, there might have been amazing discoveries from an Eastern perspective, but the concepts of countable and uncountable sets are definitely a legacy left by the Indo-European languages.

Proof

Perhaps Cantor had initially tried to prove that all infinite sets are countable. Because intuitively, that seems simpler, and if true, it means all sets can be thought of as being brought down to natural numbers. To follow Cantor’s journey, let’s look at the proofs of [1] and [2] first.

[1]

We show that there exists a bijection between $\mathbb{N}$ and $\mathbb{Z}$. By defining the following correspondence, it becomes a bijection. $$ (1,2,3,4,5, \cdots ) \mapsto (0,-1,1,-2,2, \cdots ) $$

■

[2]

We show that there exists a bijection between $\mathbb{N}$ and $\mathbb{Q}$. Let’s define the following correspondence. $$ \begin{bmatrix} 1 & 2 & 6 & 7 & \cdots \\ 3 & 5 & 8 & \ddots & \\ 4 & 9 & \ddots & & \\ 10 & \ddots & & \\ \vdots & & \end{bmatrix} \mapsto \begin{bmatrix} 1/1 & 1/2 & 1/3 & 1/4 & \cdots \\ 2/1 & 2/2 & 2/3 & \ddots & \\ 4/1 & 4/2 & \ddots & & \\ 5/1 & \ddots & & \\ \vdots & & \end{bmatrix} $$ After simplifying, there will be duplicate elements and those that are not. For example, $2/2 = 1/1$ is therefore a duplicate. Now, let’s correspond these elements with non-duplicate elements multiplied by $-1$ in order. $$ \begin{bmatrix} 1 & 2 & 6 & 7 & \cdots \\ 3 & 5 & 8 & \ddots & \\ 4 & 9 & \ddots & \\ 10 & \ddots & \\ \vdots & & \end{bmatrix} \mapsto \begin{bmatrix} 1/1 & 1/2 & 1/3 & 1/4 & \cdots \\ 2/1 & -(1/1) & 2/3 & \ddots & \\ 4/1 & -(1/2) & \ddots & & \\ 5/1 & \ddots & & \\ \vdots & & \end{bmatrix} $$ Then, this correspondence becomes a bijection.

■

[3]

Even from middle school, when we learn about numbers, we go through natural numbers, integers, rational numbers, real numbers, and complex numbers. Clearly, Cantor would have tried to find a bijection that demonstrated $\mathbb{N} \sim \mathbb{R}$. However, it’s likely that these attempts failed one after another, and eventually, he tried to prove that such a bijection does not exist. The method he used at this point is the famous Cantor’s diagonal argument.