Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to wrap my head around this concept of extracting sets from a given set to show that a subset is indeed a subset.

Suppose I want to show that the set of all sets of two elements does not exist. I approach it like this.

Suppose such a set $V$ exists of all elements containing exactly the sets of two elements. Then for any nonempty set $X$, the set $\{X,\emptyset\}$ is a set, by the pairing axiom, and since $X\neq\emptyset$, $\{X,\emptyset\}$ has two elements, so $\{X,\emptyset\}\in V$ for all sets $X$. Then by the power set axiom, $\bigcup V$ is the set of all sets, since $\emptyset\in\bigcup V$, and any nonempty set $X\in\bigcup V$ as well. But the set of all sets does not exist, a contradiction, so such a set $V$ does not exist. Does this approach work?

However, if I'm given a nonempty set $A$, is the following a proper formulation that shows that the set of all sets of the form $\{a,b\}$ for $a,b\in A$ is a set?

If $a,b\in A$, then $\{a,b\}\subset A$, and $\{a,b\}\in\mathscr{P}(A)$. Assuming that $a$ and $b$ need not be distinct, consider $$ \{t\in\mathscr{P}(A)\ |\ \exists x\exists y(x\in A\land y\in A\land t=\{x,y\}\}. $$ This is a set by the subset schema. Have I correctly specified the type of sets I want, or do I need to include something about if $z\in t\implies z=x\vee z=y$?, or is that unnecessary? Thanks.

share|cite|improve this question
Why doesnt "The set of all sets of two elements does not exist" ? – TROLLKILLER Feb 5 '11 at 10:30
up vote 5 down vote accepted

The problem is that $V$ is not a set, it is in fact a proper class. A good rule of thumb when it comes to these sort of problems is that if you can map each set into your collection - it's a proper class.

If, on the other hand, you started with a set $A$ (which you already know that it is a set) then you can have the collection of all pairs from the set. The formula which you wrote above is indeed the collection of all singletons and pairs from the set $A$, if you want to exclude the singletons you have to add $x\not= y$ as well.

This is a result from the Subset Axiom/Replacement Axiom - both are schemes and not actual axiom - which state that if you have a formula in one free variable, then the collection of elements which satisfies the formula coming from a set $A$ is a set itself, namely - if it's a subcollection of a set then it is a set.

The replacement axiom is slightly more complicated in that matter, but it says that the range of a function whose domain is a set is also a set, from this the subset axiom can be deduced easily.

share|cite|improve this answer
Thank you Asaf. I gather that I at least did the second part correctly. Is my proof by contradiction of the first part correct, by assuming $V$ is a set, and then showing that I prove that there exists a set of all sets, which is of course wrong? I'm not sure if you're saying it's wrong, or just not as elegant as it could be. – user6655 Feb 5 '11 at 10:00
@youser: The first proof is fine, yes. – Asaf Karagila Feb 5 '11 at 10:28
"A good rule of thumb when it comes to these sort of problems is that if you can map each set into your collection - it's a proper class." — In NBG set theory, this is more than just a rule of thumb: all proper classes are the same size, so you can show that a class is proper by mapping it onto any other proper class. – Tanner Swett Aug 30 '11 at 22:24
@Tanner: I think that your using Axiom E, also known as Global Choice. – Asaf Karagila Aug 30 '11 at 22:26
@Tanner: While I believe that Axiom E is indeed a consequence of Axiom of Limitation of Size, I tend to question Wikipedia on rather advanced mathematical pages. Checking Jech Set Theory, 3rd Millennium Edition yields that NBG is without this axiom, as well without Axiom E. NBGC would be included. Furthermore, it would seem historically peculiar before proving the axiom of choice is consistent with ZF there would be a proven conservative extension of ZF which implies the axiom of choice. – Asaf Karagila Aug 30 '11 at 23:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.