Cantor's diagonal argument: Difference between revisions

Revision as of 12:56, 25 July 2024

Revision as of 07:40, 9 December 2024

Line 87:

===General sets===

[[File:Diagonal argument powerset svg.svg|thumb|250px|Illustration of the generalized diagonal argument: The set ''<math>T'' = \{''n''∈<math> \in \mathbb{N}</math>: ''n''∉'' \not\in f''(''n'')\}</math> at the bottom cannot occur anywhere in the range[[Range of ''f'':[[naturala numberfunction|range]] of <math>f:\mathbb{N}</math>]]→[[power set|'''''\to\mathcal{P''''']]}(<math>\mathbb{N})</math>). The example mapping ''f'' happens to correspond to the example enumeration ''s'' in the picture [[#Lead|above]] picture.]]

A generalized form of the diagonal argument was used by Cantor to prove [[Cantor's theorem]]: for every [[Set (mathematics)|set]] ''S'', the [[power set]] of ''S''—that is, the set of all [[subset]]s of ''S'' (here written as '''''P'''''(''S''))—cannot be in [[bijection]] with ''S'' itself. This proof proceeds as follows:

Let ''f'' be any [[Function (mathematics)|function]] from ''S'' to '''''P'''''(''S''). It suffices to prove ''f'' cannot be [[surjective]]. That means that some member ''T'' of '''''P'''''(''S''), i.e. some subset of ''S'', is not in the [[Image (mathematics)|image]] of ''f''. As a candidate consider the set:

:''<math>T'' = \{ ''s'' ∈\in ''S'' : ''s'' ∉\not\in ''f''(''s'') \}</math>.

For every ''s'' in ''S'', either ''s'' is in ''T'' or not. If ''s'' is in ''T'', then by definition of ''T'', ''s'' is not in ''f''(''s''), so ''T'' is not equal to ''f''(''s''). On the other hand, if ''s'' is not in ''T'', then by definition of ''T'', ''s'' is in ''f''(''s''), so again ''T'' is not equal to ''f''(''s''); cf. picture.