0
$\begingroup$

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

  • 2
    @Chris, unfortunately Paul's user page doesn't give a location...2012-08-03

2 Answers 2

1

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.

  • 0
    Okey. thanks for many helps:)2012-08-04
-2

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

  • 0
    Thanks all the commenters. By your comments, everything is clear for me. It is very helpful for me!2012-08-05