How can we tell if there are more odd or even numbers? What about the natural numbers? Are there more natural numbers, even numbers, or rational numbers? It’s not easy to tell because there are an infinite amount of natural or rational numbers. Yet, we can somehow compare their sizes.

Let’s start with simple finite and small sets. Imagine two sets of numbers: blue numbers and red numbers.

1
2
3
4
5
6
7
8
9

Can we tell which set contains more numbers? Red or blue set? We can clearly see that… What? You’re colorblind? Ok, no problem. Let’s draw the red numbers as squares instead of circles:

1
2
3
4
5
6
7
8
9

Ok, now we can all see there are more blue circles than red squares. It was easy because we are dealing with finite sets of numbers. We were able to count them so we knew there are six blue numbers and just three red numbers. This won’t be so easy when dealing with infinite sets such as the natural numbers. Let’s try to answer the question from the title: Are there more odd or even numbers? We’ll stick to just positive numbers for now. Imagine one bag full of odd numbers and one bag full of even numbers. Which bag is bigger?

1
3
5
7
9
11
13
15
…
2
4
6
8
10
12
14
16
…

It’s kind of hard to picture an infinite amount of numbers. You will need to use your imagination. How can we decide which bag is bigger? We can count the numbers. There is an infinite amount of odd numbers and an infinite amount of even numbers. Does it mean the sets are equally big? Does it mean that all infinite sets have the same amount of members? Maybe we should try to use a different way to decide which set is bigger.

Comparing Two Sets

Imagine we have a bag of husbands and a bag of wives. If we have a wife for each husband and if we have a husband for each wife, we can tell there is the same amount of husbands and wives.

๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต

See? Each wife from the first row has an unique husband from the second row and the other way arround. But if there is one husband left without a wife, there is more husbands than wifes:

๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
 
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต

We were able to pair each wife to a husband, but we were not able to pair every husband. There is one husband left, without a loving wife. Poor guy. It brings a sad memories to my first school dance… Nevertheless, we can say the set of husbands if bigger than the set of wifes. And to ilustrate the last case:

๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿ‘ฐ
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
๐Ÿคต
 

Now we have one wife without a husband. It means the set of wives is bigger than the set of husbands. This is a nice way of comparing sets without counting their members.

Comparing Two Infinite Sets

Can we use the same approach when comparing infinite sets? Can we pair each odd number to some unique even number and the other way arround? It turns out we can. We can pair each odd number x to the even number x + 1. E. g. we pair 1 to 2, 3 to 4, 17 to 18, 149 to 150 etc. You can watch this magnificent animation that demonstrates it:

1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50

For every red odd number, we have a matching blue even number. And there are no leftovers. Every single odd number has a matching unique even number. And every single even number has a matching unique odd number. For example, the odd number 197 is matched to the even number 198 and the even number 2048 is matched to the odd number 2047. Hence the set of odd numbers and the set of even numbers has the same size.

Well, that wasn’t surprising, right? Let’s try to compare all natural numbers and all even numbers.

Comparing Natural Number and Even Numbers

Which set is bigger? A set of natural numbers or a set of positive even numbers?

1
2
3
4
5
6
7
8
…
 
2
 
4
 
6
 
8
…

This one is obvious. We can clearly see that the set of the natural numbers contains all of the even numbers and then the set contains some additional numbers – odd numbers. The set of natural numbers must be bigger because it simply contains more numbers. Twice as many numbers.

If only life was that easy.

Our definition of set comparison doesn’t care if one set contains all the elements of the other set. We told ourselves we would compare sets simply by trying to pair each element from one set to some element from the other set. Can we find such a pairing function? Surprisingly, we can. We can pair each natural number n to the even number 2ยทn (two times n) and every even number e can marry natural number eโ„2. E. g. we can pair natural number 5 to the even number 10, natural number 16 to the even number 32, etc. We can pair the even number 84 to the natural number 42, etc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50

Suddenly, each natural number can be paired to some unique even number. And each even number can be paired to some unique natural number. It means… The set of the natural numbers has the same size as the set of all even numbers!

I know it’s weird and counterintuitive. The set of natural numbers contains all the even numbers and moreover, it contains another infinite amount of odd numbers. Yet, the sets have equal size.

Comparing Natural Number and Rational Numbers

Rational numbers are fractions. Anything that can be denoted as a fraction pโ„q where p and q are integers is a rational number. So 1โ„2 is a rational number. Other examples: 2โ„5, โˆ’7โ„8, or 5. Be aware that every integer is also a rational number. We have only one integer between numbers 2 and 4 and that is number 3. On the other hand, we have an infinite amount of rational numbers between the numbers 2 and 4. There is even an infinite amount of rational numbers between numbers 0.01 and 0.02. So much rational numbers!

Hence one would say there must be more rational numbers than natural numbers, right? I can sense your spider-sense is tingling! Your intuition is correct. We can prove there is the same amount of rational numbers as there are natural numbers.

But how can we pair each rational number to an unique natural number? Imagine all rational numbers written in the form table as follows:

1โ„1
1โ„2
1โ„3
1โ„4
1โ„5
1โ„6
2โ„1
2โ„2
2โ„3
2โ„4
2โ„5
2โ„6
3โ„1
3โ„2
3โ„3
3โ„4
3โ„5
3โ„6
4โ„1
4โ„2
4โ„3
4โ„4
4โ„5
4โ„6
5โ„1
5โ„2
5โ„3
5โ„4
5โ„5
5โ„6
6โ„1
6โ„2
6โ„3
6โ„4
6โ„5
6โ„6

You should be able to see the pattern: in the first row, we have always fractions in the form 1โ„q, on the second row 2โ„q while in the first column we have fractions in the form pโ„1, in the second row pโ„2, etc. Every fraction is somewhere in the table. For example, fraction 1478โ„517 is in the 1478th row and 517th column. Now we need to find a pairing function. We need to pair each natural number to some fraction and the other way around: we need to pair each fraction to some natural number.

We can try to pair the first row. Let’s assign 1 โ†’ 1โ„1, 2 โ†’ 1โ„2, 3โ†’1โ„3, 4โ†’1โ„4, etc. Does it work? Well, it does not because we exhausted all of the natural numbers to the first row of fractions. The natural number x is paired with the fraction 1โ„x. But there is no natural number paired to the fraction 2โ„3 which sits in the second row. And there cannot be because we used all of them. Does it mean the set of rational numbers is bigger than the set of natural numbers?

Not really. We just haven’t found any suitable pairing yet. So don’t give up! We can try another approach. Let’s divide our table into diagonals. I can try to describe the diagonals but a picture speaks thousands words:

1โ„1
1โ„2
1โ„3
1โ„4
1โ„5
1โ„6
2โ„1
2โ„2
2โ„3
2โ„4
2โ„5
2โ„6
3โ„1
3โ„2
3โ„3
3โ„4
3โ„5
3โ„6
4โ„1
4โ„2
4โ„3
4โ„4
4โ„5
4โ„6
5โ„1
5โ„2
5โ„3
5โ„4
5โ„5
5โ„6
6โ„1
6โ„2
6โ„3
6โ„4
6โ„5
6โ„6

The first diagonal is just the fraction 1โ„1, the second one contains fractions 1โ„2 and 2โ„1, the third one 1โ„3, 2โ„2 and 3โ„1, etc.

  • Each diagonal contains a finite amount of fractions. the 5798th diagonal contains 5798 fractions.
  • There are an infinite amount of such diagonals and they cover the whole fraction space.

We can create the pairing functions as follows:

  • we pair the natural number 1 to the fraction in the first diagonal: 1 โ†’ 1โ„1
  • we pair the natural numbers 2, 3 to the fractions in the second diagonal: 2 โ†’ 1โ„2, 3 โ†’ 2โ„1
  • we pair the natural numbers 4, 5, 6 to the fractions in the third diagonal: 4 โ†’ 1โ„3, 5 โ†’ 2โ„2, 6 โ†’ 3โ„1
  • etc.

You can watch the pairing in the following animation:

1โ„1
1
1โ„2
2
1โ„3
4
1โ„4
7
1โ„5
11
1โ„6
16
2โ„1
3
2โ„2
5
2โ„3
8
2โ„4
12
2โ„5
17
2โ„6
 
3โ„1
6
3โ„2
9
3โ„3
13
3โ„4
18
3โ„5
 
3โ„6
 
4โ„1
10
4โ„2
14
4โ„3
19
4โ„4
 
4โ„5
 
4โ„6
 
5โ„1
15
5โ„2
20
5โ„3
 
5โ„4
 
5โ„5
 
5โ„6
 
6โ„1
21
6โ„2
 
6โ„3
 
6โ„4
 
6โ„5
 
6โ„6
 

This way we can cover all the fractions. No diagonal is infinite so we always pair the fractions in some diagonal and then we can go to the next diagonal. We don’t get stuck. In the end, every fraction is going to have a matching unique natural number and the other way around.

Well… Not really. Because there are many duplicated numbers in the table. The fractions 1โ„1, 2โ„2, 3โ„3, … all denote a single rational number: the one. But we should map each natural number to some unique rational number. We were cheating! But don’t worry, we can easily fix it. Just remove the duplicated fractions and follow the same algorithm. So instead of pairing the natural number 5 to the fraction 2โ„2, we can pair it with the following fraction 3โ„1. Now each natural number is paired with some unique rational number and the other way around.

This means the set of rational numbers has the same size as the set of natural numbers! Surprise, right?

It gets even weirder. If you take all rational numbers between 1 and 2 you get a set of the same size as the size of rational numbers. If you take any two different rational numbers a and b, there are an infinite amount of rational numbers between them. And the size of such numbers is again the same as the size of natural numbers.

But hey, we inspected the size of many different sets: odd and even numbers, natural numbers, and rational numbers. And they have the same size! Is there any set that is greater or smaller than these?

Comparing Natural Numbers and Real Numbers

Our natural numbers have finally met a match: real numbers. We need to understand the difference between a rational number and an irrational number. The decimal expansion of a rational number either:

  • terminates after a finite number of digits: 15.78, 0.98784487748841, 89225,
  • begins to repeat the same finite sequence of digits over and over: 3.333333…, 9.97365454545454545454…

While irrational number never terminates and never repeats the same finite sequence of digits over and over. The number ฯ€ is irrational because we cannot enumerate all of the digits. After all, there are an infinite amount of them and they do not repeat. We can list the first 100,000 digits of ฯ€ but not all of them.

Real numbers consist of both rational and irrational numbers. I can promise you that there are more real numbers than rational or natural numbers. Yay! But how to prove it? Imagine we have found some pairing function that pairs all the natural numbers to all the real numbers. For example this one:

1 โ†’ 0.3452807674449021โ€ฆ
2 โ†’ 0.8978319745321683โ€ฆ
3 โ†’ 0.8972169570849831โ€ฆ
4 โ†’ 0.0635759905832629โ€ฆ
5 โ†’ 0.0081863365749335โ€ฆ
6 โ†’ 0.4000559394278442โ€ฆ
7 โ†’ 0.8637537627594889โ€ฆ
โ€ฆ

We are assuming this pairing function contains all the natural numbers on the left and all the real numbers on the right. If this was the case the set of real numbers would be of the same size as the set of natural numbers. Since I spoiled you the result we know it’s not the case. Which means that on the right there are missing some real numbers. But what real number is missing on the right? Well, we can see just seven of them which makes it easy: we don’t see the number 0.4818063607183678 on the right. Ok, let’s add it to the table:

1 โ†’ 0.3452807674449021โ€ฆ
2 โ†’ 0.8978319745321683โ€ฆ
3 โ†’ 0.8972169570849831โ€ฆ
4 โ†’ 0.0635759905832629โ€ฆ
5 โ†’ 0.0081863365749335โ€ฆ
6 โ†’ 0.4000559394278442โ€ฆ
7 โ†’ 0.8637537627594889โ€ฆ
8 โ†’ 0.4818063607183678
โ€ฆ

We don’t see the number 0.4208424736008147 on the right. Let’s add it there:

1 โ†’ 0.3452807674449021โ€ฆ
2 โ†’ 0.8978319745321683โ€ฆ
3 โ†’ 0.8972169570849831โ€ฆ
4 โ†’ 0.0635759905832629โ€ฆ
5 โ†’ 0.0081863365749335โ€ฆ
6 โ†’ 0.4000559394278442โ€ฆ
7 โ†’ 0.8637537627594889โ€ฆ
8 โ†’ 0.4818063607183678
9 โ†’ 0.4208424736008147
โ€ฆ

This looks tedious. Can we somehow find such a number that cannot be simply added as a new pairing? Can we construct a real number that is different than all the real numbers in the table? Can we construct a real number that cannot possibly be on the right side of the table?

Yes, we can. We just need to be sure that the new real number has at least one digit different than all the real numbers in the table. We can make by it assuming that the n-th digit in the new real number is different than n-th digit of the n-th real number in the table.

1 โ†’ 0.3452807674449021โ€ฆ
2 โ†’ 0.8978319745321683โ€ฆ
3 โ†’ 0.8972169570849831โ€ฆ
4 โ†’ 0.0635759905832629โ€ฆ
5 โ†’ 0.0081863365749335โ€ฆ
6 โ†’ 0.4000559394278442โ€ฆ
7 โ†’ 0.8637537627594889โ€ฆ
8 โ†’ 0.4818063607183678
9 โ†’ 0.4208424736008147
โ€ฆ

I highlighted the n-th digit behind the decimal point in the n-th real number. So the second real number has the second digit behind the decimal point highlighted. Now we can construct our new real number: just start with 0. and then choose any digit that is different from the highlighted ones. For example this one: 0.123123127 If we write it down to the table

1 โ†’ 0.3452807674449021โ€ฆ
2 โ†’ 0.8978319745321683โ€ฆ
3 โ†’ 0.8972169570849831โ€ฆ
4 โ†’ 0.0635759905832629โ€ฆ
5 โ†’ 0.0081863365749335โ€ฆ
6 โ†’ 0.4000559394278442โ€ฆ
7 โ†’ 0.8637537627594889โ€ฆ
8 โ†’ 0.4818063607183678
9 โ†’ 0.4208424736008147
? โ†’ 0.123123127

We can see the new number is different than all the numbers in the table because it differs at least in one digit. Let’s say we add another pairing to our table: 10 โ†’ 0.29505973509060723.

 1 โ†’ 0.3452807674449021โ€ฆ
 2 โ†’ 0.8978319745321683โ€ฆ
 3 โ†’ 0.8972169570849831โ€ฆ
 4 โ†’ 0.0635759905832629โ€ฆ
 5 โ†’ 0.0081863365749335โ€ฆ
 6 โ†’ 0.4000559394278442โ€ฆ
 7 โ†’ 0.8637537627594889โ€ฆ
 8 โ†’ 0.4818063607183678
 9 โ†’ 0.4208424736008147
10 โ†’ 0.29505973509060723
 ? โ†’ 0.123123127

We simply update our number and we add another digit:

 1 โ†’ 0.3452807674449021โ€ฆ
 2 โ†’ 0.8978319745321683โ€ฆ
 3 โ†’ 0.8972169570849831โ€ฆ
 4 โ†’ 0.0635759905832629โ€ฆ
 5 โ†’ 0.0081863365749335โ€ฆ
 6 โ†’ 0.4000559394278442โ€ฆ
 7 โ†’ 0.8637537627594889โ€ฆ
 8 โ†’ 0.4818063607183678
 9 โ†’ 0.4208424736008147
10 โ†’ 0.29505973509060723
 ? โ†’ 0.1231231271
  • Any time we add another natural number โ†’ real number pairing to the table we just add a new digit to the new real number to make sure the real number is different.
  • If we add another thousand pairings to the table, we add a thousand digits to our new real number to make sure the real number is different.
  • If we add infinite pairings to the table we add an infinite amount of digits to our new real number to make sure the real number is different.

The table cannot keep up. We can always construct some irrational number that is not in the table. It doesn’t matter how hard you try, constructing some irrational number that is not present in the table is a piece of cake.

This means such a table can never contain all of the real numbers. We cannot pair the set of natural numbers to the set of real numbers because there will always be some real numbers left. There will be some real numbers without their natural match.

And that is why the set of real numbers is bigger than the set of natural numbers of rational numbers. Isn’t that exciting?

Final Notes

  • We didn’t deal with negative numbers, just positives. But it does not change anything. You can try to find the pairing functions as your homework.
  • The size of the set of natural numbers has its own “name”. We call it Aleph-zero, denoted as โ„ตโ‚€.
  • Often, we don’t use the term “size” of a set, we rather use “cardinality” of a set. A set {a, b, c} has a size of three or a cardinality of three.