Cantor’s diagonal argument

Cantor’s diagonal argument is a beautiful proof of the uncountability of the real numbers.

First we need some definitions.

Two sets are said to be one-to-one if each member of the first set maps to exactly one member of the second set. We say a set maps onto another set if each member of the first set maps onto a unique member of the second set. If two sets are both one-to-one and onto, then we say they have one-to-one correspondence. For example, the set of uppercase letters and the set of lowercase letters have one-to-one correspondence.

We say a set is countable if it has a finite number of elements or if it has a one-to-one correspondence with the set of positive integers. Essentially, if you can count the members of the set, even if you’d have to count forever, the set is countable.

Cantor’s diagonal argument uses proof by contradiction. That means we’ll start with an assumption and then demonstrate how that assumption leads to a logical contradiction.

Assume the set of real numbers is countable. The set of real numbers is infinite so it must have one-to-one correspondence with the set of positive integers.

If the set of real numbers is countable, then it follows that the subset of real numbers from zero to one is also countable. (If you can count everything in the set, then you can count a subset of the set.)

Since we are assuming the set of real numbers is countable, it must be possible to create a numbered list the real numbers. (This sounds like counting!) Let this list be designated {s1, s2, s3, …}. Here is the start of one such list. The numbers chosen are not significant.

09315285-0668-44F1-82E6-87D998E38299

We must accept that this infinitely long list contains all real numbers between zero and one.

Next, let’s define a number a which will be formed by using the following rule:

The n-th digit of a will not be the same number as the n-th digit of sn.

Here is one possible construction of a. Each digit of a is chosen to be different than the bracketed number in that column.

EB91E22F-69AE-45B2-A9A3-0D5F3C7A155C

We can clearly see that a is a real number in the range zero to one, so there must be a number sn which equals a. However, by definition, the n-th digit of a cannot equal the n-th digit of sn. So a is not a member of our list. We have just shown that the set of positive integers does not map onto the set of real numbers. Thus the set of positive integers does not have one-to-one correspondence with the set of real numbers.

This is a contradiction with our original assumption that the set of real numbers is countable.

Thus the set of real numbers is not countable.

Simulating a half adder

I’m starting to simulate larger circuits in LTSpice. Here’s my attempt at a half adder. Obviously I need to work on my layout skills. It started off well, but the components were too close together.

Total current consumption of the half adder with both inputs high and LEDs on the outputs is 9.4mA.

The circuit is constructed from RTL inverter gates.

half adder