1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Aug 17, 2020 at 2:25
  • $\begingroup$ A detailed and rigorous argument would be enough $\endgroup$
    – John Glen
    Aug 17, 2020 at 3:13
  • $\begingroup$ Okay; I’ve given an answer with one possible argument. $\endgroup$ Aug 17, 2020 at 3:43
  • $\begingroup$ Perhaps I was wrong and I do need an answer with predicate logic. $\endgroup$
    – John Glen
    Aug 19, 2020 at 0:13

1 Answer 1

4
$\begingroup$

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

Added in response to comment:

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .