# 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

**whose elements are all subsets of the set**

*A***.**

*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

**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).**

*A*

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

**uniquely to a subset of the set**

*A***, such that all subsets of**

*A***are referenced by that function.**

*A*

**1**.

We now define a set, that we call the set ** B**, to be the set which includes every element of

**which is matched to a subset that does not contain that actual element itself.**

*A***2**.

It follows that ** B** defines a set, which must either have no elements (and so is the ‘empty set’ (Footnote:
For more on the ‘empty set’, see the page: The ‘Empty Set’.)), or have elements which are elements of the set

**.**

*A***3**.

It follows that this set ** B** must be a subset of

**.**

*A***4**.

But it is also the case that the set ** B** must be the set given by the matching function for some element

**, that is, that**

*n***.**

*B*=*E*(*n*)**5**.

Now, since the element ** n** of the set

**is matched to the set**

*A***, it follows, from the definition of the set**

*B***, that the element**

*B***cannot appear in the set**

*n***itself.**

*B***6**.

But this results in a contradiction, since the definition of the set ** B** stipulates that any element of

**which is matched to a subset of**

*A***that does not contain that element must be an element of the set**

*A***.**

*B***7**.

Therefore the original assumption that there can be some matching function ** E(x)** must be false.

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

**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**

*A**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*

**L****, but that ordering is not in the same language**

*E*(*x*)*as those definitions, it is in a language*

**L***that is a*

**M***to that language*

**meta-language***.*

**L**

By the argument of the proof, if ** B** can have a valid definition, its definition must be in terms of the function

**. But if the function**

*E*(*x*)**is the meta-language**

*E*(*x*)*, rather than in the language*

**M***, we now have a contradiction, since we have on the one hand that*

**L****must be defined in the language**

*B**, but on the other hand, since it is a definition of a subset of*

**M****, the definition must be in the language**

*A**. 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.)*

**L**

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.

Footnotes:

Rationale: Every logical argument must be defined in some language, and every language has limitations. Attempting to construct a logical argument while ignoring how the limitations of language might affect that argument is a bizarre approach. The correct acknowledgment of the interactions of logic and language explains almost all of the paradoxes, and resolves almost all of the contradictions, conundrums, and contentious issues in modern philosophy and mathematics.Site MissionPlease see the menu for numerous articles of interest. Please leave a comment or send an email if you are interested in the material on this site.

Interested in supporting this site?You can help by sharing the site with others. You can also donate at

_{}where there are full details.