Proving That (Some) Countable Infinite Sets Have The Same Cardinality
Published on January 23rd, 2025
Hello! This is my first post on pure mathematics per se, what makes me feel strange since from the beginning of this quasi-blog I said I would write about mathematics. To be honest, this wouldn't become a post. I was just curious about the topic and wanted to try doing the proof myself as some kind of exercise, however - as it took me a while to complete it - I decided to post it here. Moreover, I didn't know I could add math symbols to HTML and I got excited with this (I thought I'd have to first write in LaTeX and then use images of the writings).
In my opinion, this set of proofs is neither elementary or advanced. It is quite hard to get a first (it can escalate to really hard concepts if you keep asking deeper questions), but it is nothing from other world. Other proofs involving infinite sets cardinalities - especially those uncountable - are way harder. Basically, it consists of creating a one-one and onto map of the elements of one set (domain) to another (image). This means that the value in the image - or counterdomain as both are equal in this case - is unique for every single value of the domain and every single value of the image has a correspondent element in the domain that fits this requisites. As a consequence of these conditions, the cardinality of the image (number of elemts on it) should be equal to the one from the domain.
What I said can be expressed mathematically the following way:
∃ f : X → Y | ∀y ∈ Y, ∃!x ∈ X, f (x) = y ⇒ |X| = |Y|.
Now, I'll shortly explain the difference between countable and uncountable sets since it's important to know this difference for the proofs I'll show you. In summary, Georg Cantor proved that there are different kinds of infinites. Meaning that even with have two infinite sets, we might not be able to create such a mapping between them. For example, we can't map the whole numbers to the real numbers since one infinite is "bigger" than the other one. Thus, it is common to use different notations to differ (a pleonasm!) these infinities when we're talking about sets. We call every single set with the same cardinality as ℕ a countable infinite set, a little bit vague, but this is what we have. I like to see these sets as sets where there is no elements in-between the two extremes of an interval of a given size, in other words (a,b) = ∅, where a = min([a,b]) and b = max([a,b]) (I think this might create problems somewhere, that's why the formal definition is different, but it helps me to imagine things better).
With all the things we had to do before starting to prove things done, let's start! In my opinion, the best proof to start is proving that the cardinalities of the set of natural even numbers and the natural numbers are equal. Also, we define the cardinality of the last one as ℵ₀ by convention. As stated, the first thing to do is find a mapping between the two sets. A really simple one is the following: (0,0), (2,1), (4,2), (6,3), and so on. Getting the pattern of it is simple since the first element of the order pair is the double of the second (or the second element is half the first, do it as you want). Thus, we can write f(x) = x/2, with f: 2ℕ → ℕ (note that 2ℕ means the set of multiples of two in ℕ ).
After defining the function, we have to prove it bijective. Firstly, let's start with injection:
Let x and x' be in 2ℕ. Suppose f(x) = f(x') ⇒ x/2 = x'/2 ⇒ x = x' ∴ f is injective.
Now let's do the same, but for surjection:
Observe that every x in 2ℕ is of the form 2y, where y is a natural number. Thus, f(x) is defined for every x. By consequence, f(x) = y, ∀x ∈ 2ℕ with all values of y being in the set of natural numbers. We can easily perceive that all natural numbers are possible y values, thus there exits a value x in the domain for every single value y in the image, meaning that f is surjective.
Hence, we have proven |2ℕ| = |ℕ| = ℵ0.
Let us then do our final proof. In this case, we will show |ℕ| = |ℤ|. The best way to do this is by using a function by parts to map the elements of the sets. So, lets organize our ordered pairs in the following way: (0,0), (1,-1), (2,1), (3,-2), (4,2), and so on. To see how the function actually looks like, lets separate it in odd and even x values. Thus, we have (0,0), (2,1), (4,2), and so on, and (1,-1), (3,-2), (5,-3), and so on. For the evens, f(x) = x/2, which implies that the part of the whole positive numbers is covered since we proved this function is bijective above. Now, it might be quite hard to observe, but we can say that f(x) = -(2x + 1)/2 for odd values (test it yourself).
Then, we just have to do our procedure from before:
Let x and x' be in ℕ. Suppose f(x) = f(x') ⇒ -(2x+1)/2 = -(2x'+1)/2 ⇒ -2x+1 = -2x'+1 ⇒ -2x = -2x' ⇒ x = x',∀x ∈ ℕ. Observe that every negative whole number can be represented this way, therefore f is surjective. As f is both injective and surjective, we can say that it is bijective. Hence, |ℕ| = |ℤ| = ℵ0.
So, that's it for this post. I decided to show this proofs because they're cool enough to be here, because in my view they show the concept of "infinites greater than other infinites" is more complex than what is commonly thought. Also, they're simple enough to a high schooler understand, however you can estipulate questions such: "How could I expand this proofs to the rational numbers?", or "How can I demonstrate the real numbers are of different cardinality?". From now on, if I find some problem I solved to be interesting I'll try to bring it here. If there were any typos or math mistakes in this post, please contact me because I will promptly change them. Thanks for reading!