[JustForFunMath] Basics for Set Theory: Cardinality and Countable Set
Really? Is there a ‘countable’ infinite sets? Does this make sense?
What would be the most fundamental concept in understanding derivatives and integrals? The answer might be ‘limit’, as derivative is the limit of the ratio, and integrals is that of the sum.
So, to grasp what ‘limit’ is, we need the concept of ‘infinity’. To talk about that, we will start from ‘set’.
Set theory was created by Georg Cantor. For more detailed information, check out the Wikipedia page below!
1. Set theory — Cardinality
Cardinality means the number of elements in a set. In a finite set, cardinality is just easy to go, but in an infinite set, the concept becomes more important.
1.1 Mapping (or function)
So, as a warm-up, let’s think about one-to-one mapping. The word mapping perhaps can be replaced by function. If the following two conditions are satisfied, set f is called a mapping or a function from set X into set Y.
(condition.A) For any element x in a set X, there is an element y in a set Y that the (x,y) pair belongs to the set f. Often, this is written as f(x) = y.
(condition.B) If (x, y1) if in the set f, and (x, y2) is also in the set f, then y1 is equal to y2, in other words, y1 = y2.
1.2 One-to-one mapping
- Injective (in Korean, 단사)
If x1 is not equal to x2 then f(x1) is not equal to f(x2).
x1 != x2 then f(x1) != f(x2)- Surjective (in Korean, 전사)
For any element y in a set Y, there exists x in a set X that satisfying y = f(x).
It is also called that a function that x in X goes onto the y in Y.
- Bijective (in Korean, 전단사)
If a mapping or a function is both injective and surjective at once, this is called bijective. Basically, if a mapping f:X->Y is bijective signifies that for any y in Y there is only one x in X that satisfying f(x) = y. Therefore, if a mapping is bijective, we can also come up with an inverse function g:Y->X, and this mapping is also bijective. Furthermore, if mapping f:X->Y is bijective, then this mapping f is also injective. So, in this case, mapping f is also called ‘one-to-one correspondence’ from set X to set Y.
This ‘one-to-one correspondence’ property can be simply put ‘equivalent’. This equivalent property means ‘cardinality equivalence’ and can be written as ‘X~Y’.
1.3 Equivalence
There is always a good Wikipedia page for it!
So based on the explanation from the page, for any set X, Y, Z, they are equivalent if and only if they satisfy the following three properties: reflectivity, symmetry, and transitivity.
(1) Reflexivity: X~X
(2) Symmetry: X~Y => Y~X
(3) Transitivity: X~Y and Y~Z => X~Z
The above can be easily shown using the definition of the one-to-one correspondence. But, let’s just try to pull out some useful intuitions about one-to-one correspondence by using finite sets.
First of all, it is just more than obvious that a finite set X = {x1, x2, x3…….x(n)} containing different elements are having one-to-one correspondence in itself. Therefore, the first property Reflexivity holds.
Second of all, if a finite set X is in one-to-one correspondence with another finite set Y, this means that elements in the set Y are all different from each other. Therefore Y is also in one-to-one correspondence with X.
Lastly, if a finite set X is in one-to-one correspondence with another finite set Y, then elements of Y are different from each other. Likewise, if Y is in one-to-one correspondence with a finite set Z, the elements of Z are also different from each other. Therefore set Z is in one-to-one correspondence with X.
If there exists bijective between two different sets, such as between X and Y, then we can say both sets have the same cardinal number and can be written as #X = #Y.
Then out of many infinite sets, which would have the smallest cardinal number? Perhaps the set of natural numbers? Yes, it can be. But, not only that, we can say that the set of rational numbers has the smallest cardinal number, too. Isn’t this sound weird to you? For me, it is. So, next step, let’s figure out about this.
1.4 Countable set
The term ‘countable’ was the most confusing term for me when I took the Real Analysis course last semester. It sounded something that countable, which seems finite, but unlike what I expected, clearly, the term was used to describe some infinite sets!
So, what does ‘countable’ means in terms of infinite sets?
It means if an infinite set X has the same cardinality number with that of natural number N, in other words — equivalent, then we say X is a countable set.
Therefore, for any element in the natural number set N, there exists a bijective mapping f:N->X. As a result, we can denote elements of X with natural numbers, like {x1, x2, x3, x4,…..}. So, it IS countable. That is why we put ‘countable’ to some infinite sets.
Lastly, let’s look into a statement to utilize what we just learned.
‘Any subset of a countable set is countable.’
We know that by definition that if a set X satisfies #X=#N (X; any infinite set, N; the set of natural numbers), a set X is countable.
So, proving the above statement is the same as proving that any subset of N is countable. Let’s say we have a subset of N whose name is C. Let’s pick the smallest element in C and label it as ‘c1’. And the rest, excluding c1, let’s call them C2. So, now C = {c1, C2}.
Now, within C2, let’s pick the smallest, and label it as ‘c2’, and call the rest C3. So, after this step, C = {c1, c2, C3}.
If we keep repeating this process, then C would be equal to {c1, c2, c3, c4, c5, ……..}. Therefore, we can clearly say that C, which is a subset of a countable set N, is countable.
Yey, wrap it up for today, and hopefully, I will see you in the next posting!
