# Prove $\{a,b\}=\{c,d\} \implies [[(a=c)\land (b=d)]\lor [(a=d)\land (b=c)]]$. (Terence Tao Analysis I Exercise $3.1.1$)

This is Exercise $$3.1.1$$ on Tao's Analysis. The exact wording is:

Let $$a$$, $$b$$, $$c$$, $$d$$ be objects such that $$\{a, b\} = \{c, d\}$$. Show that at least one of the two statements “$$a = c$$ and $$b = d$$” and “$$a = d$$ and $$b = c$$” hold.

There are two reasons I'm posting this. First is the fact that in previous editions this exercise on Tao's book was different; see here: Why does one have to check if axioms are true? and I'm wondering if this is new exercise is somehow equivalent to the old one. I'm also wondering if maybe this change happened because of concerns such as the one in this afore-mentioned post. The second reason is to check if my proof is correct.

I think axioms up to $$3.4$$ can be used here, since the next exercise also limits you to using these 4 axioms.

Axiom 3.1 (Sets are objects). If $$A$$ is a set, then $$A$$ is also an object. In particular, given two sets $$A$$ and $$B$$, it is meaningful to ask whether $$A$$ is also an element of $$B$$.

Axiom 3.2 (Equality of sets). Two sets $$A$$ and $$B$$ are equal, $$A = B$$, iff every element of $$A$$ is an element of $$B$$ and vice versa. To put it another way, $$A = B$$ if and only if every element $$x$$ of $$A$$ belongs also to $$B$$, and every element $$y$$ of $$B$$ belongs also to $$A$$.

Axiom 3.3 (Empty set). There exists a set $$∅$$, known as the empty set, which contains no elements, i.e., for every object $$x$$ we have $$x \notin ∅$$.

Axiom 3.4 (Singleton sets and pair sets). If $$a$$ is an object, then there exists a set $$\{a\}$$ whose only element is $$a$$, i.e., for every object $$y$$, we have $$y \in \{a\}$$ if and only if $$y = a$$; we refer to $$\{a\}$$ as the singleton set whose element is $$a$$. Furthermore, if $$a$$ and $$b$$ are objects, then there exists a set $$\{a, b\}$$ whose only elements are $$a$$ and $$b$$; i.e., for every object $$y$$, we have $$y \in \{a, b\}$$ if and only if $$y = a$$ or $$y = b$$; we refer to this set as the pair set formed by $$a$$ and $$b$$.

Proof. Since $$a$$, $$b$$, $$c$$, $$d$$ are objects, by Axiom $$3.4$$ we have the pair sets $$\{a, b\}$$ and $$\{c, d\}$$. Also by Axiom $$3.4$$, $$x\in \{a, b\}$$ iff $$x=a$$ or $$x=b$$ and similary, $$y\in \{c, d\}$$ iff $$y=c$$ or $$y=d$$. Let $$\{a, b\} = \{c, d\}$$ then by Axiom $$3.2$$, $$\{a, b\} = \{c, d\}$$ iff "for $$a\in \{a,b\}$$ and $$b\in \{a,b\}$$ we have that $$c \in \{a,b\}$$ and $$d \in \{a,b\}$$" AND "for $$c\in \{c,d\}$$ and $$d\in \{c,d\}$$ we have that $$a \in \{c,d\}$$ and $$b \in \{c,d\}$$". Since $$a\in \{c,d\}$$ and $$b\in \{c,d\}$$ while also $$y\in \{c,d\} \iff [(y=c)\lor (y=d)]$$, suppose that $$a\neq c$$ and $$a \neq d$$ then we have $$a\notin \{c,d\}$$ since $$\neg y \in \{c,d\}\equiv y \notin \{c,d\} \iff \neg [(y=c)\lor (y=d)]\equiv [(y \neq c) \land (y\neq d)]$$ which is a contradiction for $$y=a$$. Similarly we get contradictions for $$[(b\neq c)\land (b\neq d)]$$, $$[(c\neq a)\land (c\neq b)]$$, and $$[(d\neq a)\land (d\neq b)]$$. So since the statement $$a=c$$ or $$a=d$$ is true, at least one of the statements $$a=c$$ and $$a=d$$ must be true. If $$a=c$$ then since $$\neg[(b\neq c)\land (b\neq d)]\equiv [(b=c) \lor (b=d)]$$ and since $$a=c$$ we must have $$b=d$$ $$\color{red}{\text{(but is this good enough? or should I consider the case }a=b?\text{ would it be enough to consider }a=b=c=d \text{ trivially true at the start?})}$$.

If $$a=d$$ then similarly $$b=c$$. Which concludes the proof.

I found it difficult to follow the logic in the question.

Note that $$a \in \{c,d\}$$, hence $$(a=c) \lor(a=d)$$. Furthermore, $$b \in \{c,d\}$$, hence $$(b=c) \lor(b=d)$$. Since both are true, we have $$( (a=c) \lor (a=d) ) \land ( (b=c) \lor (b=d) )$$.

Using the relevant distributive properties we see that $$( (a=c) \land (b=c) ) \lor ( (a=c) \land (b=d) ) \lor ( (a=d) \land (b=c) ) \lor ( (a=d) \land (b=d) )$$.

Now note that $$(a=c) \land (b=c) \implies (a=c) \land (b=d)$$ (since $$\{a,b\}$$ is a singleton, so is $$\{c,d\}$$). Similarly, $$(a=d) \land (b=d) \implies (a=c) \land (b=d)$$.

Hence $$( (a=c) \land (b=d) ) \lor ( (a=d) \land (b=c) )$$.

• I agree that the question in red doesn’t make much sense; I got lost in what I was asking myself as I was typing it. Could you follow the rest of the proof? Is it ok?
– Eric
Jul 24, 2023 at 7:56
• The question in red was posed because I’m not sure that $a=c$ being true is enough to force $b=d$ to be true as well. Since maybe $a=c$ doesn’t force $b=c$ to not be true, since if for example they were all equal that wouldn’t be the case.
– Eric
Jul 24, 2023 at 8:12