# Proving two equal ordered pairs have equal elements

I am having trouble with the equality of elements in ordered pairs. It makes intuitive sense, but I am lost on proving it, or how to understand the proof. $$\langle a, b\rangle = \langle c, d\rangle \rightarrow a=c\ \land \ b = d$$ Here are the steps I am taking:

First, I expand the ordered pair: $$\{x|x=\{a\}\ \lor\ x=\{a, b\}\} = \{x|x=\{c\}\ \lor\ x=\{c, d\}\}$$ Use the definition of equality: $$(\forall y) [y\in\{x|x=\{a\}\ \lor\ x=\{a, b\}\} \leftrightarrow y\in\{x|x=\{c\}\ \lor\ x=\{c, d\}\}]$$ Use a logical axiom to replace y with a new free variable e: $$e\in\{x|x=\{a\}\ \lor\ x=\{a, b\}\} \leftrightarrow e\in\{x|x=\{c\}\ \lor\ x=\{c, d\}\}$$ Using a class definition to replace x with e: $$[e=\{a\}\ \lor\ e=\{a, b\}] \leftrightarrow [e=\{c\}\ \lor\ e=\{c, d\}]$$ Expand the unordered pairs; since e equals all of them, I use the same bound variable: $$[e=\{x|x=a\}\ \lor\ e=\{x|x=a \lor x=b\}] \leftrightarrow [e=\{x|x=c\}\ \lor\ e=\{x|x=c \lor x=d\}]$$ Use the definition of equality: $$(\forall y)[y \in e \leftrightarrow y \in \{x|x=a\}\ \lor\ y \in e \leftrightarrow y \in \{x|x=a \lor x=b\}] \leftrightarrow [y \in e \leftrightarrow y \in \{x|x=c\}\ \lor\ y \in e \leftrightarrow y \in \{x|x=c \lor x=d\}]$$ Use a logical axiom to replace y with a new free variable f: $$[f \in e \leftrightarrow f \in \{x|x=a\}\ \lor\ f \in e \leftrightarrow f \in \{x|x=a \lor x=b\}] \leftrightarrow [f \in e \leftrightarrow f \in \{x|x=c\}\ \lor\ f \in e \leftrightarrow f \in \{x|x=c \lor x=d\}]$$ Use a definition to replace the bound variable in the class definition with the free variable contained in it: $$[f \in e \leftrightarrow f=a\ \lor\ f \in e \leftrightarrow f=a \lor f=b] \leftrightarrow [f \in e \leftrightarrow f=c\ \lor\ f \in e \leftrightarrow f=c \lor f=d]$$ Replace biconditionals with single arguments: $$[f=a\ \lor\ [f=a \lor f=b]] \leftrightarrow [f=c\ \lor\ [f=c \lor f=d]]$$ Remove redundant arguments: $$[f=a \lor f=b] \leftrightarrow [f=c \lor f=d]$$

This is where I am stuck. I am assuming this is pretty much the end, but am unsure how to go from here to $$[a=c\ \land \ b = d]$$

I am also unsure how I am supposed to look at this statement. I am assuming I can't just accept all arguments that give me true although there are cases where they would be true.

Constructing a truth table, I get:

$$\begin{array}{|c|c|c|c|} \hline f=a & f=b & f=c & f=d & [f=a \lor f=b] \leftrightarrow [f=c \lor f=d]\\\hline 0 & 0 & 0 & 0 & T \\\hline 0 & 0 & 0 & 1 & F \\\hline 0 & 0 & 1 & 0 & F \\\hline 0 & 0 & 1 & 1 & F \\\hline 0 & 1 & 0 & 0 & F \\\hline 0 & 1 & 0 & 1 & T \\\hline 0 & 1 & 1 & 0 & T \\\hline 0 & 1 & 1 & 1 & T \\\hline 1 & 0 & 0 & 0 & F \\\hline 1 & 0 & 0 & 1 & T \\\hline 1 & 0 & 1 & 0 & T \\\hline 1 & 0 & 1 & 1 & T \\\hline 1 & 1 & 0 & 0 & F \\\hline 1 & 1 & 0 & 1 & T \\\hline 1 & 1 & 1 & 0 & T \\\hline 1 & 1 & 1 & 1 & T \\\hline \end{array}$$ The 1st row is not applicable assuming both sides must be T.

The 6th says b=d.

The 7th says b=c.

The 8th says b=c=d.

The 10th says a=d.

The 11th says a=c.

The 12th says a=c=d.

The 14th says a=b=d.

The 15th says a=b=c.

The 16th says a=b=c=d.

I'm pretty sure this is useless for the argument to be made, but row 6 and 11 are the two statements that need to be proved.

Do I go about disproving every other row with true?

• You can get proper angle brackets with langle ($\langle$) and \rangle ($\rangle$). Are you required to use predicate logic, or can you simply give a reasonably detailed and rigorous argument? Aug 17, 2020 at 2:25
• A detailed and rigorous argument would be enough Aug 17, 2020 at 3:13
• Okay; I’ve given an answer with one possible argument. Aug 17, 2020 at 3:43
• Perhaps I was wrong and I do need an answer with predicate logic. Aug 19, 2020 at 0:13

Suppose that $$\langle a,b\rangle=\langle c,d\rangle$$. Then $$\big\{\{a\},\{a,b\}\big\}=\big\{\{c\},\{c,d\}\big\}$$, so

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

and therefore $$a=c$$. Then

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

so

$$\{a,b\}=\bigcup\big\{\{a\},\{a,b\}\big\}=\bigcup\big\{\{a\},\{a,d\}\big\}=\{a,d\}\,.$$

If $$a=b$$, then $$\{a\}=\{a,b\}=\{a,d\}$$, and therefore $$d=a=b$$. If $$a\ne b$$, then

$$\{b\}=\{a,b\}\setminus\{a\}=\{a,d\}\setminus\{a\}=\begin{cases} \{d\},&\text{if }a\ne d\\ \varnothing,&\text{if }a=d\,. \end{cases}$$

Clearly $$\{b\}\ne\varnothing$$, so $$a\ne d$$, $$\{b\}=\{d\}$$, and $$b=d$$.

Suppose that $$\langle a,b\rangle=\langle c,d\rangle$$. We distinguish two cases. Suppose first that $$a=b$$. Then

$$\langle a,b\rangle=\big\{\{a\},\{a,a\}\big\}=\big\{\{a\}\big\}=\big\{\{c\},\{c,d\}\big\}\,,$$

so $$\{c,d\}=\{a\}$$, and therefore $$c=d=a$$. Thus, $$a=c$$ and $$b=d$$.

Now suppose that $$a\ne b$$; we still have

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

and $$a\in x$$ for each $$x\in\big\{\{a\},\{a,b\}\big\}$$, so $$a\in x$$ for each $$x\in\big\{\{c\},\{c,d\}\big\}$$. In particular, $$a\in \{c\}$$, so $$a=c$$. Now $$\{a,b\}$$ is the unique element of $$\big\{\{a\},\{a,b\}\big\}$$ that is not equal to $$\{a\}$$, and $$\{c,d\}=\{a,d\}$$ is the unique element of $$\big\{\{c\},\{c,d\}\big\}$$ that is not equal to $$\{a\}$$, so $$\{a,d\}=\{a,b\}$$. But then $$b\in\{a,d\}$$, and $$b\ne a$$, so $$b=d$$.

• This works, but the book I'm reading hasn't covered unions and intersections at this point in the book. Aug 17, 2020 at 21:27
• @JohnGlen: I’ve added a second argument that does not rely on intersection or union; see it it will serve. Aug 17, 2020 at 21:56