# How to determine the existence of all subsets of a set?

Given

1. The definition of subset;
2. The axiom of power set: for any set $S$, there exists a set $\wp$ such that $X \in \wp$ if and only if $X\subseteq S$

we know what a subset is and what a power set contains.

In a simple case where a set $A$ is supposed to exist, with $A=\{a, b, c\}$, we know what is and what is not a subset of $A$:

$\{a\}, \{b\}, \{c\}, \{a, b\}, \{a,c\}, \emptyset$ and $A$ are subsets of $A$ and anything different is not.

$\wp(A)=\big\{\{a\}, \{b\}, \{c\}, \{a, b\}, \{b,c\}, \{a,c\}, \{a, b, c\}, \emptyset\big\}$.

However the mere definition of something (and consequently it's recognition as such) does not guarantee its existence. $\emptyset$ and $A$ seem like the only subsets whose existence is immediate.

In other words, I know what a power set contains, but how do I know that the things it contains exist in the first place?

Because such a well-defined and existent set such as $\wp(A)$ should not contain nonexistent elements, to prove the existence of its elements is important. It seems that two alternatives arise:

1. Being a member of $\wp(A)$ automatically makes this thing to exist;

or

1. There should be an alternative to prove the existence of all subsets of $A$ without the axiom of power set.
• That's a good question. And in general the is no guarantee a thing exists be its definition. But in this case you are overlooking def. 0. The definition of a set itself. A set is a collection of objects, and objects, existentiallt,... are. So it is a nature of being a set itself that it must be able to have subsets. Not by definition of subset but by the empirical nature of a set. At least that's how I see it. I realize that's philosophically and ontologically vague. But there it is. Jun 19, 2016 at 17:56
• I am interpreting this as you asking how we know the subsets of $A$ other than $A$ and $\emptyset$ exist. To answer this, it follows from the axiom of specification. For example $\{a,b\} = \{x \in A : x \neq c\}$ Jun 19, 2016 at 17:59
• One way to prove the existence of a subset $B$ of $A$ is to apply the Axiom of Separation with a suitable formula defining $B$. Jun 19, 2016 at 18:07
• See Cantor's theorem. Jun 19, 2016 at 18:13
• The Powerset axiom states that for any set $X$, the powerset of X is also a set -- that is, it exists. In ZF(C), to exist means to be a set means to be a member of something (else). Jun 19, 2016 at 21:11

The power set axiom just tells you what it says: for every $A$, there exists a set $\mathcal{P}(A)$ such that $$\text{for all B, B\in\mathcal{P}(A) if and only if B\subseteq A}$$ There is no claim of “existence” of any particular subset of $A$. In $\mathsf{ZFC}$ one can show that $|\mathcal{P}(A)|>|A|$, so there is plenty of subsets.

It should be noted that, if $A$ is infinite, there is no hope to find, for each subset of $A$, a formula “describing it”, because $\mathcal{P}(A)$ is uncountable. This is however not a problem: the axiom tells you that you have a “container” for all subsets of $A$; when you prove that a set $B$ is a subset of $A$, then you know it belongs to $\mathcal{P}(A)$; and conversely, if you pick $B\in\mathcal{P}(A)$, you know $B\subseteq A$.

The real purpose of the axiom is that the subsets of a set form a set. In particular, for instance, the equivalence relations on a set form a set that can be isolated from $\mathcal{P}(A\times A)$ using a suitable predicate and the axiom of separation.

I remember some good notes about this in Paul J. Cohen's “Set theory and the continuum hypothesis”.

• But, is there a "claim of existence" of all subsets of $A$ from the axiom?
– user36546
Jun 29, 2016 at 15:35
• @Fred By definition, whatever qualifies as a subset of $A$ belongs to the power set of $A$. The axiom says this is a set (that is, it can belong to some other set and you can apply the axiom of replacement to it); it doesn't tell you how to build subsets of $A$. Jun 29, 2016 at 15:39
• I see that it doesn't provide any instructions to build subsets, but my question is: can we claim the existence of anything that qualifies as subset of $A$ because it's a member of $\wp (A)$ (known to exist, from the axiom)?
– user36546
Jun 29, 2016 at 15:44
• @Fred In order to say that something belongs to the power set of $A$ you have to prove it belongs to it. Jun 29, 2016 at 15:52
• Sure. The question is: if we are talking about some set whose existence we are not sure about; and if we come to prove it belongs to $\wp (A)$ have we then proved its existence?
– user36546
Jun 29, 2016 at 15:59

I don't think you can actually derive what $P(S)$ is for any random $S$, from the axioms. Try to describe $P(\mathbb N)$ for instance.

If you have described a set $P'$ and want to know if $P'=P(S)$, then you can't do much more than try to prove that $$X\in P'\implies X\subset S\\ X\notin P'\implies X\not\subset S.$$ But that's only if you have found a way to describe $P'$, which will not always be possible.

Lastly, $\emptyset$ and $S$ are not the only subsets whose existence is immediate, for any set $S$. It is not very hard to prove the existence of sets with more than one element. This means we can do the following:

Suppose we have a set nonempty $S$ which is not a singleton, i.e. $(\forall x)(\emptyset\neq S\neq\{x\})$. Now, assume that $P(S)=\{\emptyset, S\}$. $$x\in S\implies \{x\}\subset S\implies \{x\}=\emptyset \vee \{x\}=S$$ Both $\{x\}=\emptyset$ and $\{x\}=S$ give a contradiction, so there have to be subsets of $S$, other than $\emptyset$ or $S$.

1. Axiom of Extensionality .$\forall x\;\forall y\; (x=y \iff \forall z\;(z\in x \iff z\in y)\;).$

2. Axiom of Pairing. $\forall x \;\forall y\;\exists z\;\forall w\; (w\in z\iff (w=x\lor w=y)\;).$

We write $x=\{y,z\}$ as an abbreviation for $\forall w\;(w\in x\iff (w=y\lor w=z)\;).$ It is is a justifiable abbreviation because of Extensionality. Then the existence of an $x$ satisfying $x=\{y,z\}$ is Pairing.

The Power-Set Axiom by itself cannot imply that anything other than $A$ is a subset of $A$.

The axiom of the unordered pair guarantees existence for every set since it explicitly states that for any set, the union of that set with any other set exsits. So it stipulates that the union of any set with itself exists. The union of any set with itself is itself, therefore every set exists.

Every subset of the Power Set is a set, therefore every subset of a set exists.

The most relevant axiom is actually the one mentioned by MathematicsStudent1122 and MauroALLEGRANZA, namely the Axiom of Separation (sometimes called specification). Whenever you have a property expressed for example by a formula, this axiom guarantees that there is a subset whose members are precisely those entities that have the property or satisfy the formula.

For example, you can write down the property of a natural number $n$ that $(\exists m\in\mathbb{N})\,\big(n=2m\big)$ meaning that $n$ is an even integer. But how do you know that the set of even integers exists? That's the role of the separation axiom.

In certain interesting mathematical theories, you can have predicates that do not satisfy separation. One such theory is Nelson's.

• If you read the comments, there is a criticism of this: there are only countably many predicates but $\mathcal{P} (\mathbb{N})$ is uncountable. Jun 24, 2016 at 0:29
• @Mathematics, by downward Lowenheim-Skolem, there are models of set theory where there will be externally only countably many subsets of N. The OP's problem is a view of foundations that's too realist. I merely gave a possible source of infinitely many subsets, since it is clearly possible to write down infinitely many predicates. Jun 30, 2016 at 14:53