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

This is an exercise from Kunen's book.

Write a formula expressing $z=\langle \langle x,y\rangle, \langle u,v\rangle \rangle$ using just $\in$ and $=$.

What I've tried: because $\langle x,y\rangle= \{\{x\},\{x,y\}\}$ and $\langle u,v\rangle= \{\{u\},\{u,v\}\}$, and hence $z=\{\{\langle x,y\rangle\},\{\langle x,y\rangle,\langle u,v\rangle\}\}= \{\{\{\{x\},\{x,y\}\}\} ,\{\{\{x\},\{x,y\}\},\{\{u\},\{u,v\}\}\}\}$.

So the formula expressing is this: $z_1\in z$, then $z_1= \{\{x\},\{x,y\}\}$ or $z_1= \{\{u\},\{u,v\}\}$

Am I right? Thanks ahead:)

share|cite|improve this question
That formula does not use "just $\in$ and $=$", as required. It makes heavy use of $\{ \}$. – Chris Eagle Aug 3 '12 at 10:03
Also, where did $u$ come from? – Chris Eagle Aug 3 '12 at 10:04
oops. Sorry. I make a mistake. – Paul Aug 3 '12 at 10:06
@Chris, unfortunately Paul's user page doesn't give a location... – draks ... Aug 3 '12 at 10:50
up vote 1 down vote accepted

Write a formula:

$$\varphi(u,v,z)= \forall x\bigg(x\in z\leftrightarrow \underbrace{\forall y(y\in x\leftrightarrow y=u\lor y=v)}_{\Large x=\{u,v\}}\lor\underbrace{\forall y(y\in x\leftrightarrow y=u)}_{\Large x=\{u\}}\bigg)$$

Note that $\varphi(u,v,z)$ holds if and only if $z=\langle u,v\rangle$.

Now define the following formula:

$$\psi(x,y,u,v,z)=\exists a\exists b(\varphi(x,y,a)\land\varphi(u,v,b)\land\varphi(a,b,z))$$

Namely, $z$ is the ordered pair $\langle a,b\rangle$, and $a,b$ are both the ordered pairs $\langle x,y\rangle,\langle u,v\rangle$ respectively.

Note that not only that you can "expand" $\psi$ by replacing the instances of $\varphi$ by its explicit formulation; you can replace equality by $\in$, and use the axiom of extensionality to prove it is the same thing.

share|cite|improve this answer
Thanks Asaf; The exercise askes the formula only use "$\in$" and "=". However in your formula you use the symbol $\forall$. This is what I still don't know. Could you explain more for me? – Paul Aug 4 '12 at 8:07
@Paul: It also uses $u,v,z,x,y,\land,\varphi,(,)$. When we say "use only $R$ and $S$" we mean that those are the only relation symbols appearing in the formula. – Asaf Karagila Aug 4 '12 at 8:15
O, I see. Chris note that my formula is wrong for I use the symbol $\{,\}$. In the formula, can we use such symbol? – Paul Aug 4 '12 at 8:21
@Paul: It is a bit complicated. The symbols $\{,\}$ are not officially part of the language (unlike the symbols I used), and formally $\{a\}$ is the set defined by $$\tau(a,z)=\forall u(u\in z\leftrightarrow u=a)$$ – Asaf Karagila Aug 4 '12 at 8:24
So, your answer seems that the translation of $z=\{\{\{\{x\},\{x,y\}\}\} ,\{\{\{x\},\{x,y\}\},\{\{u\},\{u,v\}\}\}\}$ by take place of $\{\}$ using the above definition. Am I right? – Paul Aug 4 '12 at 8:32

Although I am not an expert in this field (merely a beginning student), maybe I can help you out.

We will have to find a formula only using $\in$ and $=$ to describe $z = \langle \langle x, y \rangle, \langle u, v \rangle \rangle$. This essentially means we want to say that: '$z$ is an ordered pair of two ordered pairs $a$ and $b$. The ordered pair $a$ consists of the elements $x$ and $y$, the ordered pair $b$ consists of the elements $a$ and $b$.'


To describe that $z$ is an ordered pair, you can use the formula:

$$(\exists a \in z)(\exists b \in z)(\exists d \in a)(\exists f \in b) \left[ (\forall c \in z)(c = a \vee c = b) \wedge (\forall c \in a)(c = d) \wedge (d \in b) \wedge (\forall c \in b)(c = d \vee c = f) \right]$$

Lets call this formula $o(z)$.


Given that $z$ is an ordered pair, we can describe that $g$ is the first coördinate of $z$ with:

$$(\forall a \in z)(g \in a)$$

Lets call this formula $p(z, g)$.


Given that $z$ is an ordered pair, we can describe that $i$ is the second coördinate of $z$ with:

$$(\exists a \in z)(i \in a) \wedge (\forall b \in z)(\forall c \in z)(b \neq c \Rightarrow (i \notin b \vee i \notin c))$$

Call this formula $q(z, i)$.


By combining these formulas, we can describe $z = \langle \langle x,y \rangle, \langle u,v \rangle \rangle$ as follows:

$$o(z) \wedge (\exists a)(\exists b)(o(a) \wedge o(b) \wedge p(z, a) \wedge q(z, b) \wedge p(a, x) \wedge q(a, y) \wedge p(b, u) \wedge p(b, v))$$



As I do not have enough reputation to post a comment on other answers yet (:-s), I will comment on Asaf Karagila's answer in this way. The formula $\phi(u,v,z)$ you use is not correct, because $\phi(u,v,z)$ does not hold if and only if $z = \langle u, v \rangle$. It is for example possible that $z = \{ \{ u \} , \{ v \} \}$, or $z = \{ \{ u \} \}$ with $u \neq v$.

You really need to use the definition of ordered pairs with first and second coördinate I use in my answer, elsewise you won't have an 'if and only if':

$$z = \langle u, v \rangle \mbox{ if and only if } o(z) \wedge p(z, u) \wedge q(z, v)$$

share|cite|improve this answer
$a$ and $b$ are free variables in your expression, but not in $z = \langle \langle x,y\rangle, \langle u,v\rangle \rangle$. You'd want something along the lines of $o(z) \wedge \exists a, \exists b \phi$ where $\phi$ is the rest of your formula – Amit Kumar Gupta Aug 4 '12 at 10:24
Or if you want the formula to still be $\Delta_0$, you'd want $o(z) \wedge \exists c \in z, \exists a,b \in c \phi$ – Amit Kumar Gupta Aug 4 '12 at 10:28
@AmitKumarGupta: True. I have edited my answer to reflect your comments. – Thanaton Aug 4 '12 at 12:21
re. your comment on Asaf's answer: Actually, he is correct. As an example, let's show that $z = \{ \{ u \} , \{ v \} \}$ does not satisfy his formula. Note that $x = \{ v \}$ does not satisfy $( \forall y ) ( y \in x \leftrightarrow ( y = u \vee y = v ) )$ (since $u \notin x$ however, $u = u \vee u = v$ is clearly true), and it also does not satisfy $( \forall y ) ( y \in x \leftrightarrow y = u )$, since $v \in x$ is true, while $v = u$ is false). However we clearly have $x \in z$! – arjafi Aug 4 '12 at 12:58
Note the two ways arrow. It means if $y\in x$ then $y=u$ or $y=v$ AND if $y=u$ or $y=v$ then $y\in x$. Therefore $\{u\}$ and $\{v\}$ fail to satisfy $\forall y(y\in x\leftrightarrow y=u\lor y=v)$. – Asaf Karagila Aug 4 '12 at 14:16

Your Answer


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

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