Some numbers are not fractions.

In yesterday’s post math I described a proof that there are more real numbers than integers. Since that was a proof by contradictiona.k.a. reductio ad absurdum a non-trivial number of people won’t accept the proof. Today I look at another proof about real numbers, this one intuitionistic: not all numbers can be expressed as fractions.

No finite fraction, when squared, yields 2

Let’s start by showing that √2 is not a rational number. We’ll do this by showing that, if a ÷ b = √2 then both a and b are even numbers. That fact will allow us to show they are both infinite as well.

We’ll need two facts for this proof. First, every even integer a can be written as some other integer times 2: a = 2b. Second, squaring does not change evenness: an odd number squared is still odd, and an even number squared is still even.

Now we’ll show that, if (x ÷ y)² = 2, then both x and y are even.

1. Start with (x ÷ y)² = 2.
2. Rearrange this to be x² = 2y².
3. That means that x² is even, so x must also be even.
4. Since x is even, x = 2z for some integer z.
5. Stick this into our equation to get (2z)² = 2y².
6. Simplify that to 4z² = 2y².
7. Divide both sides by 2 to get 2z² = y²,
8. That means that y² is even, so y must also be even.

Thus, x and y are even.

When we have a fraction of two even integers, we can divide both by 2 and get another fractional representation of the same number. Since it’s still a representation of √2 we can re-use the same steps above to show that it’s still a fraction of two even numbers. Thus, we can divide both by 2 again, show the new numbers are even and divide by 2 again, and again, and so on forever. Thus, x and y each have an infinite number of factors of 2: x = 2^∞k for some k, and likewise for y.

Other irrationals, and beyond

The square root of 2 isn’t rational a rational number is one that can be written as the ratio of two integers. , but it is hardly the only irrational number. A similar argument From prime p, use “‍p‍” in place of “‍2‍” and “‍multiple of p‍” in place of “‍even‍” throughout. works for the root of any prime integer and, by the fundamental theorem of arithmetic Fundamental theorem of arithmetic: every integer greater than 1 has a unique prime factorization. , any integer whose root is not integral. It also works for cube roots, quartic roots, etc. There is also a “‍rational root theorem‍” Rational root theorem: if a ÷ b is a root of a polynomial c_nxⁿ + … + c₀x⁰, then a is a factor of c₀ and b is a factor of c_n. that generalizes it further to the roots of general polynomials.

If rational numbers are what you get using division and integers, algebraic numbers are what you get using polynomials and rationals. Algebraic numbers include all the examples I’ve mentioned, but there are also transcendental numbers that aren’t algebraic either. Two classic examples are π and e, though I wont go through the rather involved proof.

Each algebraic number, π, and e can be expressed as the limit of an infinite summation of algebraic terms, but we can come up with numbers that can’t be defined using that tool either. We humans are pretty good at finding new things to talk about that are outside our existing set of tools.

Eventually, assuming the Church-Turing thesis holds, we will arrive at “‍numbers that are the language of some Turing machine.‍” That is the biggest set of numbers that we can recognize when we see and compute to arbitrary precision, since any process for recognizing and/or computing the numbers can be expressed in terms of any Turing-complete tools, such as a Turing machine.

Can describe in some way numbers that we can’t recognize or compute? The answer to that will have to wait until we discuss the decidability problem, Gödel encodings, and Rice’s theorem.