Strategies for proving logical equivalencies in first order logic: Using a proof about ordered pair equivalency as an example.

Question

In Tao's Analysis I, one of the exercises ($3.5.1$) asks the reader to demonstrate that the Kuratowski definition of an ordered pair (i.e. when $(x,y):=\{\{x\},\{x,y\}\}$) "obeys" the following property:

$(x,y)=(x',y') \iff (x=x' \land y=y')$

I believe I have successfully proven this, but I wanted to make sure that I performed the proof correctly.

There were four statements that I proved, reframing the definition as:

$\{\{x\},\{x,y\}\} = \{\{x'\},\{x',y'\}\} \iff (x=x' \land y=y')$

1. If $\{\{x\},\{x,y\}\} = \{\{x'\},\{x',y'\}\}$, then $x=x' \land y=y'$
2. If $x=x' \land y=y'$, then $\{\{x\},\{x,y\}\} = \{\{x'\},\{x',y'\}\}$
3. If $\{\{x\},\{x,y\}\} \neq \{\{x'\},\{x',y'\}\}$, then $x\neq x' \lor y\neq y'$
4. If $x\neq x' \lor y\neq y'$, then $\{\{x\},\{x,y\}\} \neq \{\{x'\},\{x',y'\}\}$

Although I was able to prove all four statements, I wasn't certain if I needed to explicitly demonstrate statements $3$ and $4$ (i.e. I wasn't sure if I could classify these statements as vacuously true and therefore ignore them without an explicit proof).

---

When it comes to proving logical equivalencies (biconditionals), I sort of get confused whether or not I need to demonstrate the negated versions of the implications. The confusion arises for the following reason:

A biconditional will evaluate to true in two instances: when $P$ and $Q$ are true (and their reciprocal implications are true) and when $P$ and $Q$ are false (and their reciprocal implications are true). Now, statements $1$ and $2$ correspond to the first instance. Statements $3$ and $4$ correspond to the second instance.

In thinking about the second instance, one could frame it in two different, but logically equivalent, ways.

Assume $P$ is false and therefore $P \implies Q$ is vacuously true. Assume $Q$ is false and therefore $Q \implies P$ is vacuously true (and therefore, I believe, I should not need a proof to demonstrate either of these).

Equivalently, assume $\neg P$ is true. Therefore I need to demonstrate that from $\neg P$ I can arrive at $\neg Q$, which will establish that $\neg P \implies \neg Q$ is true. Assume $\neg Q$ is true. Therefore I need to demonstrate that from $\neg Q$ I can arrive at $\neg P$, which will establish that $\neg Q \implies \neg P$ is true. This seems to be the strategy that I employed for statements $3$ and $4$...but, once again, couldn't I have just argued using the former strategy (where the statements are vacuously true) and therefore proofs of statements $3$ and $4$ are not required?

Hopefully I expressed my confusion sufficiently. I will happily edit if I have not. Any clarification is greatly appreciated! Cheers~

Answer 1

You only need to prove the positive implications, and right to left is trivial in $$\{x,\{x,y\}\}=\{x',\{x',y'\}\} \iff x=x' \land y=y'$$

basically by substitution. The left to right implication is a little more work, but not that hard. I don't see any need to prove more. $\lnot Q \implies \lnot P$ is just proving $P \implies Q$ again, by logical tautology.

Answer 2

Your 3 is the contrapositive of 2, so they are logically equivalent statements. Meaning that once you have proven 2, you have thereby proven 3 as well. Likewise, 4 is the contrapositive of 1. So, no need to prove 4 separately once you have proven 1.

Indeed, any statement of the form $P \leftrightarrow Q$ is equivalent to $(P \to Q) \land (Q \to P)$, and so in this case you really only have to show 1 and 2 to prove the desired biconditional.