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

  • 1
    That formula does not use "just $\in$ and $=$", as required. It makes heavy use of $\{ \}$.2012-08-03
  • 0
    Also, where did $u$ come from?2012-08-03
  • 0
    oops. Sorry. I make a mistake.2012-08-03
  • 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
    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?2012-08-04
  • 0
    @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.2012-08-04
  • 0
    O, I see. Chris note that my formula is wrong for I use the symbol $\{,\}$. In the formula, can we use such symbol?2012-08-04
  • 0
    @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)$$2012-08-04
  • 0
    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?2012-08-04
  • 0
    @Paul: Pretty much, yes.2012-08-04
  • 0
    You see, the problem with $\{,\}$ notation is that $\{a\}$ and $\{a,b\}$ are defined by *different* formulas, but they are denoted in a similar way. This makes an ambiguous reading.2012-08-04
  • 0
    I see. Thanks again for your patience:)2012-08-04
  • 0
    Well, Asaf, the last question: How to define the set $ \{a,b\}$?2012-08-04
  • 0
    @Paul: $$\phi(a,b,z)=\forall u(u\in z\leftrightarrow u=a\lor u=b)$$2012-08-04
  • 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
    $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 formula2012-08-04
  • 0
    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$2012-08-04
  • 0
    @AmitKumarGupta: True. I have edited my answer to reflect your comments.2012-08-04
  • 2
    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$!2012-08-04
  • 0
    @ArthurFischer: I am still not convinced. Let's assume $z = \{ \{ u \}, \{ v \} \}$. If $x = \{ u \}$, then $(\forall y)(y \in x \leftrightarrow (y = u \vee y = v))$ is true. If $x = \{ v \}$, then also $(\forall y)(y \in x \leftrightarrow (y = u \vee y = v))$ is true. Thus the formula $(\forall x)(x \in z \leftrightarrow (\forall y)(y \in x \leftrightarrow (y = u \vee y = v)) \vee (\forall y)(y \in x \leftrightarrow y = u))$ is true. Therefore $z = \{ \{ u \}, \{ v \} \}$ satisfies $\phi(u, v, z)$.2012-08-04
  • 1
    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)$.2012-08-04
  • 0
    @AsafKaragila: You are right. I am used to quantified quantors (eg. $\forall y \in x$; is that the correct term?), and therefore I didn't see we were 'looping' over 'all' possible elements. I will remove my edit, sorry Asaf!2012-08-04
  • 0
    Thanks all the commenters. By your comments, everything is clear for me. It is very helpful for me!2012-08-05