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.

  • $\begingroup$ Why doesnt "The set of all sets of two elements does not exist" ? $\endgroup$ – TROLLHUNTER Feb 5 '11 at 10:30

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.

  • $\begingroup$ 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. $\endgroup$ – user6655 Feb 5 '11 at 10:00
  • $\begingroup$ @youser: The first proof is fine, yes. $\endgroup$ – Asaf Karagila Feb 5 '11 at 10:28
  • $\begingroup$ "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. $\endgroup$ – Tanner Swett Aug 30 '11 at 22:24
  • $\begingroup$ @Tanner: I think that your using Axiom E, also known as Global Choice. $\endgroup$ – Asaf Karagila Aug 30 '11 at 22:26
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Aug 30 '11 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy