How to verify $(a,b) = (c,d) \implies a = c \wedge b = d$ naively

Question

Given set $A, B$, $a\in A, b\in B$, we call

$$(a, b) = \{a, \{a, b\}\}.$$

How do we show naively that $$(a, b) =(c, d) \Rightarrow a =c , b=d?$$

The proof that I have in mind is the following:

Given $(a, b) = (c, d)$, so

$$\{a, \{a, b\}\} = \{ c, \{ c, d\}\}.$$

First of all $a \neq \{ a, b\}$, or this will give $a\in a$. Similarly $c\neq \{c, d\}$.

Now $a\in \{c, \{c, d\}\}$ so either $a = c$ or $a= \{c, d\}$.

If the latter is true, then we have

$$ c = \{ a, b\} = \{ \{ c, d\} , b\}$$

This implies

$$c \in \{ c, d\} \in c$$

and it is not allowed. Thus $a=c$. So

$$\{a, b\} = \{c, d\} = \{ a, d\}$$

and from there we can show also $b=d$.

Question: This results is stated in p.8 of this book, but they never mention that infinite chain is not allowed. So I was wondering if there is an even more naive way to prove the above assertion.

Answer 1

It is not possible to prove this without using the axiom of regularity. Indeed, suppose you have a set $a$ such that $a=\{\{a\},a\}$ but $a\neq \{a\}$ (the existence of such a set is consistent with all the axioms of ZFC except regularity; for instance, it follows from Boffa's anti-foundation axiom). Then $$(a,a)=\{a,\{a\}\}=a$$ and also $$(\{a\},a)=\{\{a\},\{\{a\},a\}\}=\{\{a\},a\}=a$$ so $(a,a)=(\{a\},a)$ even though $a\neq \{a\}$.

Answer 2

Allow me to define $$ \langle a,b \rangle = \{ \{a\}, \{a,b\} \} $$ and I claim that $\langle a,b \rangle = \langle c,d \rangle \implies a = c \wedge b = d$.

Proof. If $X= \{ \{a\}, \{a,b\} \} = \{ \{c\}, \{c,d\} \}$. Then $a$ is the unique element of the unique singleton of $X$ and so is $c$. Therefore we must have $a = c$.

If $a = b$ (or $c = b$), then $X = \{ \{a \} \} = \{ \{c\} \}$ and we must have $c = d$ (or $a = b$) and we are done.

Hence we may assume that $a \neq b$ and $c \neq d$. Now $b$ is the unique element of the unique $2$-element set in $X$ that is not equal to $a =c$ and likewise for $d$. But this implies that $b = d$. Q.E.D.

Answer 3

If you omit the axiom of foundation/regularity from ZFC, you cannot prove this. It is consistent with the rest of the axioms that you can have $(a,b)=(c,d)$ with $a \neq c$ and $b \neq d$.