# Write a formula expressing $z=\langle \langle x,y\rangle, \langle u,v\rangle \rangle$

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\}\}$

-
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

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.

-
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))$$

--

EDIT (NOT APPLICABLE ANYMORE)

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)$$

-
$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