Cantor's diagonal argument: Difference between revisions

Revision as of 21:45, 21 April 2023

Revision as of 23:13, 21 April 2023

Line 102:

Assuming the [[law of excluded middle]] every [[subcountable]] set (a property in terms of surjections) is already countable, i.e. in the surjective image of <math>{\mathbb N}</math>, and every unbounded subset of <math>{\mathbb N}</math> is in bijection with <math>{\mathbb N}</math> itself. Likewise, by the classical [[Schröder–Bernstein theorem]], any two sets which are in the injective image of one another are in bijection as well.

With equality defined as the existence of a bijection between their underlying sets, Cantor also defines a [[preorder]] of cardinalities <math>|S|</math> and <math>|T|</math> in terms of the [[Cardinality#Comparing_sets|existence of injections]] between <math>S</math> and <math>T</math>. One can embed the naturals into the binary sequences, thus proving various ''injection existence'' statements explicitly, so that in this sense <math>|{\mathbb N}|\le|2^{\mathbb N}|</math>, where <math>2^{\mathbb N}</math> denotes the function space <math>{\mathbb N}\to\{0,1\}</math>. But following from the argument in the previous sections, there is ''no surjection'' and so also no bijection, and in this sense <math>|{\mathbb N}|<|2^{\mathbb N}|</math>. In the context of [[classical mathematics]], this exhausts the possibilities, giving a [[partial order|non-strict partial order]] or even a [[total order]] andwhen assuming [[axiom of choice|choice]]. setsSets such as <math>2^{\mathbb N}</math> are not enumerable, which is to say <math>\neg(|2^{\mathbb N}|\le|{\mathbb N}|)</math>. The diagonal argument thus establishes that, although both sets under consideration are infinite, there are actually ''more'' infinite sequences of ones and zeros than there are natural numbers.

Cantor's result then also implies that the notion of the [[set of all sets]] is inconsistent: If <math>S</math> were the set of all sets, then <math>{\mathcal P}S</math> would at the same time be bigger than <math>S</math> and a subset of <math>S</math>.