The Diagonalisation Argument begins with two sets of numbers\u2014 the set of the real numbers, denoted \u211d and the set of the natural numbers, denoted \u2115. First consider the set of natural numbers, or the countable numbers. \u2115 is the set of numbers that you would think of when you\u2019re counting, or all the integers greater than zero. We can say \u2115 = {1, 2, 3, 4, 5\u2026} and so on until infinity\u2014 \u2115 is an infinite set, because you can count forever. \u2115 is an infinity, but it\u2019s an infinity you can count, so to describe the size, or cardinality of \u2115, we say it\u2019s a countably<\/i> infinite set.<\/p>\n
Our argument focuses on one thing\u2014 proving that the cardinality of \u2115 and the cardinality of \u211d are are different, which would mean that there are at least two different sizes of infinity. To prove this, we have to prove that there is no bijection between \u211d and \u2115. However, the concept of a bijection, and how it proves this, requires some explaining.<\/p>\n
Defining A Bijection<\/strong><\/p>\n First, a function can be thought of as a way to match two sets together- a first set and a second set, which we can call set A and set B. There are other definitions of functions, but this one is the most useful for this case. From this definition of a function, two other concepts are required to understand a bijection- surjection and injection. Before, though, it\u2019s important to note that the definition of a function does not allow for multiple elements of the second set to map onto the same element in the first set! You always match from the first to the second, so that is not possible.<\/p>\n Moving forward, a surjection is a way to match the first set (A) to the second set (B) so that every element in B corresponds to some member of A. More simply, no elements in B are left unmatched. However, a surjection can still have multiple elements in A correspond to the same member of B. An injection, on the other hand, matches A to B so that no members of A correspond to the same member of B, but there can still be some unmatched members of B. A bijection is both a surjection and an injection- so there are no unmatched members of B, and no members of A correspond to the same member of B. Informally, this is just a one to one correspondence between A and B. So, for every element of A, there is a singular corresponding element of B and vice versa. These definitions are all a little confusing, though, so the diagram below might help: Now that a bijection is defined, we can see why a bijection between two sets means that the two sets will always have the same size- all the elements will be in a one-to-one correspondence, or a one-to-one ratio. Then, a bijection between the sets \u211d and \u2115 means that both sets are the same size. So, by proving that there is no bijection between \u211d and \u2115, we prove that they do not have the same cardinality (are not the same size).<\/p>\n Mapping A Bijection<\/strong><\/p>\n So, consider the hypothetical mapping function between \u211d and \u2115. To make the argument simpler, we can shorten our proof to the subset of \u211d between 0 and 1, and if we show this subset is bigger than \u2115,\u00a0 \u211d is definitely bigger than \u2115 since it contains this subset. For the interested, this function is\u2014 This looks like a terrifying thing at first, but it\u2019s easily explained. This function returns an ordered pair of one element which we call x from the input set \u2115 and its corresponding element which we call y in the output set, \u211d, represented as (x, yx). To get yx from x, you first have an infinite summation that gives you an infinitely long decimal; for example, yxi=5 for all i is 0.5555\u2026 where the digit 5 repeats forever. yxi is a function that gives you a random number between 0 and 10, while the (0.1)i part of the equation just makes it so that the element returned by yxi is the ith element to the right of the decimal point. A summation just sums all of the terms as i increases\u2014 (0.1)1yxi +(0.1)2yxi +(0.1)3yxi \u2026 assigning a random integer yxi for to every decimal place to make an infinite decimal. This will be our mapping function.<\/p>\n Proof by Contradiction<\/strong><\/p>\n Using the mapping function, we can make a table of just a couple example values to illustrate our proof. Now that we have our mapping between \u211d and \u2115, we can get started. To make things easier, we can imagine every number mapped onto \u211d from \u2115 as something like 0.d11d12d13d14d15\u2026, where di<\/i>n is a single digit, with the subscript i<\/i> representing the index of the number the digit is in and n representing the place of the digit to the right of the decimal point. Table 1 is a hypothetical mapping with numbers in place for the digits to make the idea easier to understand, while Table 2 is a universal mapping using the di<\/i>n notation for each digit. This is a great starting point for our goal of proving that this bijection cannot exist.<\/p>\n To prove it doesn\u2019t exist, you can take the diagonal of the numbers in this table (the numbers highlighted in red) and construct a new number from them, with an extra one added to each digit. For example, in the first table, the number constructed would be 0.69979\u2026 and in the second, it would be the expression below.<\/p>\n 0.(d11+1)(d22+1)(d33+1)(d44+1)…<\/p>\n Now, we prove that this number is not included in our mapping. It can\u2019t be equal to the number mapped to 1, because the digit in red, 5 is now 6, and similarly, d11 is d11 + 1. It also can\u2019t be equal to the number mapped to 2, because the digit in red, 8, is now 9, and similarly, d22 is d22 + 1, and so on. For the nth number, the nth digit will always differ, so they can\u2019t be the same. Repeat this argument forever, and congrats\u2014 your number isn\u2019t in the mapping! For any mapping like this, we can use this same diagonal argument to forever construct a number that isn\u2019t in the mapping but is in \u211d, meaning there is no bijection between the sets.<\/p>\n Conclusion<\/strong><\/p>\n That\u2019s Cantor\u2019s Diagonalisation Argument. Some readers might notice a flaw, though\u2014 can\u2019t we just add this constructed number to the mapping, then add the next constructed number, and the next, and the next, and have a full mapping? However, since the argument works for all mappings, you will always be able to create a new number not in the current mapping. Even if we continually add the diagonal number we construct to the mapping, we can always construct another<\/i> number not in it, so you end up adding numbers forever and never creating a true bijection. To truly disprove the Diagonalisation Argument, you need to prove that you can never<\/i> create a new number not in the mapping, which is impossible, because you can always<\/i> create a new number not in the mapping- the diagonal number. So, this is why the infinity of the real numbers is bigger than the infinity of the natural numbers, perfectly illustrating the point so aptly made by that simple statement\u2014 some infinities really are bigger than others.<\/i><\/p>\n Sources:<\/p>\n Google, Translate & Tm, Deepl & Jones, Peter. (2019). A Translation of G. Cantor\u2019s \u201cUeber eine elementare Frage der Mannigfaltigkeitslehre\u201d. https:\/\/www.researchgate.net\/publication\/335364685_A_Translation_of_G_Cantor’s_Ueber_eine_elementare_Frage_der_Mannigfaltigkeitslehre\/citation\/download<\/a><\/p>\n Oxford College. (n.d.). Cantor\u2019s Diagonal Argument<\/i>. Cantor\u2019s diagonal argument. https:\/\/mathcenter.oxford.emory.edu\/site\/math125\/cantorsDiagonalArgument\/<\/a><\/p>\n![\"\"](\"http:\/\/sites.imsa.edu\/hadron\/files\/2025\/09\/Screenshot-2025-09-30-at-9.42.01\u202fPM-300x185.png\")
<\/p>\n![\"\"](\"http:\/\/sites.imsa.edu\/hadron\/files\/2025\/09\/Screenshot-2025-09-30-at-9.41.34\u202fPM-300x57.png\")
<\/p>\n![\"\"](\"http:\/\/sites.imsa.edu\/hadron\/files\/2025\/09\/Screenshot-2025-09-30-at-9.45.22\u202fPM-300x91.png\")
<\/p>\n