Vergauwen, A Metalogical Theory of Reference, 2.2 Cantor's Diagonal Method

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Logic & Semantics, Entry Directory]
[Vergauwen's Metalogical Theory of Reference, Entry Directory]

[The following is summary. Paragraph headings are my own.]

Roger Vergauwen

A Metalogical Theory of Reference: Realism and Essentialism in Semantics

Chapter 2: Reference and Theory of Reference

2.2 Cantor's Diagonal Method

Cantor wanted to distinguish different types of infinite sets. Consider the rational numbers, which are the numerical values that may be expressed by the quotient of two integers. Exceptions would be irrational numbers, like pi or the golden number. Then, he demonstrated that the set of rational numbers (set R) is a denumerable set. For, they may be placed into a one-to-one correspondence with the natural numbers. He also examined the real numbers. These include both rational and irrational numbers. He found that there was no such one-to-one correspondence between the reals and the naturals.

We will follow his indirect proof.

We first suppose the opposite, that in fact that there is a one-to-one correspondence between

a) the set of real numbers, and

b) the set of natural numbers.

So let's put the natural numbers in a left-hand column.

Now consider some real, such as pi. We may represent it digitally as 3.14159.... We can represent any such real number by means of a decimal expansion like this. We see that there is a whole number (in this case 3) followed by a series of other numbers (1 4 1 5 9 . . .) We will want create a vertical list of real numbers. But we will want to line-up their decimals, and keep track of their coordinates in reference to each other's relative positions. So we will use this format:

The N's are whole numbers. Their subscripts indicate their row. The a's tell us the decimal value for that particular decimal place. So each a represents either zero or some natural number that is less than 10. We see also that there are two subscripts for each a. The first one indicates its row. The second tells us its place in the series of decimal expansion. Let's consider a possible listing that fulfills the above formulation.

So if each natural number corresponded one-to-one to each real number, then the set would be denumerably infinite. However, it would be non-denumerably infinite if:

a) each natural number can be unambiguously associated with a real number, and

b) in spite of this it is possible to construe a real number which is different from all the previous ones present in the correspondence list as it is presented. (18d)

Such a set that cannot be mapped one-to-one onto the denumerably infinite set of natural numbers would be a non-denumerable set:

a set is non-denumerable if it has a cardinal number which is greater than

Cantor did in fact make such a demonstration. He showed that we may construe a real number that is not present on the list of correspondences as they are drawn up.

Cantor looks at the coordinates, and takes from them a diagonal selection.

This produces for us a real number with the formulation:

So in our case, we would take these numbers:

And thereby we obtain:

33, 0117

We will now change this number into a new number. We will substitute each a number with a new number. We will refer to any such a number as

and the number that will replace it would be

We will say that if the a number does not equal 1, then we will replace it with 1 (the b number). More formally,

If instead the a number does equal 1, then we substitute it with 2.

This will create a new real number. Its called the diagonal number. If we perform this operation, the diagonal number in our example would be

33, 0117............ becomes

33, 1221 ............

Now we will show why this number could not have been present in the original series. For, if this number were in the series, it would correspond to a natural number n just like all the other numbers in the series. That corresponding number determines the first subscripts for the a numbers. Hence we would obtain:

But, let's consider

33, 1221 ............

as an example. Let's imagine that it were in the series that produced this very number,

33, 1221 ...... Could it be the first one in the series? If it were, in order to obtain this same number as the diagonal, then the first digit of the first number would need to not equal one. For if it did, then the substitution process would have rendered a diagonal with 2 as the first decimal. Can this diagonal then be the second one in the series? No, because if it were, in order to have also obtained it as the diagonal, the second digit of the second number would have to equal 1. But here we are presuming it to be 2. We will find then that it is impossible for the diagonal to have been in the series.

So we see that if we try to match up the reals with the natural numbers, there will always be another number possible that is not among the one-to-one correspondences. Hence the set of real numbers is non-denumerably infinite. And it has a cardinal number that is greater than the cardinal number for a denumerably infinite set, which we symbolized as:

Cantor's diagonal method will prove vital when we discuss Gödel's incompleteness theorems. And we will apply it also to the concept of reference. Along with reference there is meaning. We will then use a theory of meaning, namely, Montague's model-theoretic semantics for natural languages. We noted previously that Tarski did not think his Truth-conditional semantics could apply to natural languages. But Montague will show otherwise.

[Other Entries in this Series]

Vergauwen, Roger. A Metalogical Theory of Reference: Realism and Essentialism in Semantics. London: University Press of America, 1993.