diagonal procedure

Related Overviews

Georg Cantor (1845—1918) Russian-born German mathematician

Richard's paradox

liar paradox


'diagonal procedure' can also refer to...


More Like This

Show all results sharing this subject:

  • Philosophy


Show Summary Details

Quick Reference

The method first used by Cantor to show that there cannot be an enumeration of the real numbers. Any real number can be written as an infinite decimal. So we imagine a correspondence with the natural numbers, giving us some real as the first, another as the second, and so on. Given such a list, Cantor defines a real number that differs from the first real in the first decimal place, the second in the second place, and so on for every listed real. Thus if the decimal expansion of the first real is written as the sequence of digits x01x02x03…and the reals are laid out in order:

x00   x01   x02   x03  …

x10   x11   x12   x13  …

x20   x21   x22   x23  …

x30   x31   x32   x33  …

We then consider the diagonal (highlighted) real x00x11x22…and define a non-terminating decimal that differs in each place: e.g. let ynn=5 if xnn ≠ 5, and ynn=6 otherwise. This then is a real that was not on the original list, for it differs from the nth real on the list in the nth place. The construction refutes the thesis that we had enumerated all the reals. Diagonal arguments are one of the most powerful tools of set theory and metamathematics. They also bear a close relationship to arguments of the Liar family: an explicit use of diagonal reasoning occurs in Richard's paradox.

Subjects: Philosophy.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.