I want to prove existence of intersection $x\cap y=\{z\in x| z\in y\}$ and set difference $x\setminus y=\{z\in x| \neg z\in y\}$using an axiom schema of specification.

My first thought was to use $\exists z\forall t (t\in z \leftrightarrow \phi(t))$ and set $z=x\cap y$, then I have $(t\in x\cap y\leftrightarrow z\in x \wedge z\in y)$, but this does not prove there exists such a set $z$ which contains elements that are only in $x$ and $y$. I have the same problem for the set difference, may you could show how to show the existence formally.

I have also a second question concerning a Lemma from ZFC, it is stated in my logic book. $ZFC\vdash \forall x,y,x',y' (x,y)=(x',y')\rightarrow x=x'\wedge y=y'$

How can this be proven using extensionality and pairing axiom? I write the pair as $(x,y)=\{\{x\},\{x,y\}\}\rightarrow \{x'\}\in\{\{x\},\{x,y\}\} $. Now in either case we have $x'\in\{x\}$, i.e $x=x'$, but why? What about $y=y'$?


For the first question, note that the subset schema (as well replacement schema) allow parameters. This means that you can write the formula $\phi(x,p):= x\in p$ where $p$ is a parameter from the universe. Now use it with $z$ as parameter to define a subset of $x$, and the negation of $\phi$ for the difference.

For the second question, first show that $\{x\}=\{x,y\}$ if and only if $x=y$, then conclude that if $\{\{x\},\{x,y\}\}=\{\{x'\},\{x',y'\}\}$ then either $x'=x=y=y'$, or that you can easily discern between the pair and the singleton, as well the element of the pair which is not an element of the singleton.

Of course this is easier if you already have the rest of $\sf ZFC$ and can use unions and basic set operations. Note that $x=\bigcap(x,y)$ and $y=\bigcup(x,y)\setminus\bigcap(x,y)$.

  • $\begingroup$ Thanks, still I am uncertain about the first part, could you explain this a little bit more in detail? I do not see how the existence follows using the $\phi$-formula. $\endgroup$ – Babla May 1 '13 at 16:20
  • $\begingroup$ We have two sets $y,z$ then $a=\{x\in y\mid\phi(x,z)\}$ is a set by the subset axiom for $\phi$, where $z$ is a parameter. But what is $a$? It is the set $\{x\in y\mid x\in z\}$ so it is the set of those $x$ which are in both $y$ and $z$, which is exactly $y\cap z$. $\endgroup$ – Asaf Karagila May 1 '13 at 17:47
  • $\begingroup$ Two more things, first: Is it possible to prove exitence using only one first order sentence? Second: I thought $\{x\}$ can either be $\{x',y'\}$ or $\{x'\}$ and in each case $x=x'$ ? From which axiom follows your first identity that $\{x\}=\{x,y\}$ iff $x=y$ $\endgroup$ – Babla May 1 '13 at 18:56
  • $\begingroup$ I don't understand the first question; as for the second extensionality, which is probably the most fundamental axiom of set theory. If $\{x\}=\{x',y'\}$ then it is necessarily that $x=x'=y'$, and therefore $\{\{x'\},\{x',y'\}\}=\{\{x\}\}$ and from this we can also conclude that $x=y$ by the same method. $\endgroup$ – Asaf Karagila May 2 '13 at 6:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.