The Power Set Proof

Page last updated 11 Mar 2022

The Power Set proof is a proof that is similar to the Diagonal proof, and can be considered to be essentially another version of Georg Cantor’s proof of 1891, (Footnote: Georg Cantor, ‘Über eine elemtare Frage de Mannigfaltigkeitslehre’, Jahresberich der Deutsch. Math. Vereing. Bd. I, S.  pp 75-78 (1891). An English translation of the original can be seen at Cantor’s original 1891 proof.) and it is usually presented with the same secondary argument that is commonly applied to the Diagonal proof. The Power Set proof involves the notion of subsets. A subset of a set is a set that includes some or all of the elements of a given set. In standard set theory, given a set A, there can be a power set of A whose elements are all subsets of the set A.

The Power Set proof states that, given a set A with an infinite number of elements, there cannot be a function that matches each element of the Power Set of A to each element of the set A; that is, there is no function that matches every element of the set A to every subset of the set A (see also one-to-one correspondence).

The usual version of the proof as is commonly used today is as follows:

We start with an initial assumption; the object of the proof is to prove that this assumption cannot be correct. The assumption is that there is a function, which we call E(x), that maps every element of the set A uniquely to a subset of the set A, such that all subsets of A are referenced by that function.

And as for the Diagonal proof, this proves that there can be no function that gives a one-to-one correspondence of the elements of a set and the subsets of a set, where the function is in the same language as the definitions of the sets.

However, it says nothing about the case where the function E(x) is in a different language to the language in which the subsets of A are defined. (Footnote: No-one has ever encountered an infinite set other than by way of some definition. And no-one has ever encountered an infinite subset of any infinite set other than by way of some definition. And every definition must be a definition in some language. Given a definition of an infinite set, we can define various subsets of that set, some of which are finite, others infinite.) Given a language L in which those subsets are defined, then it is a simple matter to make a lexicographical⁠ (Footnote: A lexicographical ordering is a method of setting sequences of symbols in a definitive order, in the same way as words are ordered in a dictionary, see for example Lexicographic order.) ordering of the sequences of symbols that comprise the definitions of the subsets, and one can call that ordering E(x), but that ordering is not in the same language L as those definitions, it is in a language M that is a meta-language to that language L.

By the argument of the proof, if B can have a valid definition, its definition must be in terms of the function E(x). But if the function E(x) is the meta-language M, rather than in the language L, we now have a contradiction, since we have on the one hand that B must be defined in the language M, but on the other hand, since it is a definition of a subset of A, the definition must be in the language L. This is a contradiction which means that at least one prior assumption and/or some step in the argument is incorrect.⁠ (Footnote: Interestingly, while Cantor’s proof of 1891 does not provide a generalized proof of the Power set proof, but the second part of the paper describes a specific case of a Power set, and shows for that specific case there cannot be a function that defines a one-to-one correspondence between real numbers and functions that define the subsets of real numbers, where the functions are all in the same language.)

On the page Diagonal proof, there is a detailed analysis of the fallacious assumption that different levels of language can be ignored in such proofs (see the secondary argument of the Diagonal proof) and the same analysis applies also to the Power set proof, and so the analysis will not be repeated on this page. See also A List with no Diagonal number, and Proof of more Real numbers than Natural numbers.

When the Power Set proof is divested of any Platonist assumptions concerning the ‘existence’ of things independently of language, the proof only proves that there cannot be a matching function E(x) that matches up every element of a set to every subset of a set, in the same language as the language being used for the definition of the sets.

For more on Platonism see Platonism, The Myths of Platonism, Platonism’s Logical Blunder, Numbers, chairs and unicorns and the posts Moderate Platonism and Descartes’ Platonism.