Proof of Principle of Duality: Show that $φ$' is logically equivalent to $¬φ$

Question

Could anyone check if my proof is ok/ suggest any improvement please? I couldn't find a way to utilise the induction hypothesis so I am not sure if this is ok.

---

Let $φ$ be a formula built up using the connectives $¬, ∧, ∨$. The dual $φ$' of $φ$ is the formula obtained from $φ$ by replacing all occurrences of $∧$ by $∨$, of $∨$ by $∧$, and all propositional variables by their negations. Show that $φ$' is logically equivalent to $¬φ$.

Induction on occurrence of operator.

Base case: operator occurence of $φ$'=$0$ - this is only possible if double negation elimination has been applied, since if $φ$=$P$ $\to$ $φ$'=$\lnot P$, or $φ$=$\lnot P$ $\to$ $φ$'=$\lnot \lnot P$. $φ$' has at least one operator no matter what. Therefore $φ$ must already have a $\lnot$ and get another $\lnot$ added on when transformed into $φ$', then have them cancelled by double negation. Thus $φ$' $\equiv$ $\lnot φ$.

Hypothesis: Assume that for all $φ$' whose length $\le n$, $φ$' $\equiv φ$.

Since $φ$ is only built up with 3 types of operators, there can only be 3 possible scenarios:

1. $φ$'=$\psi$ $\land$ $\phi$: Therefore $φ=\lnot \psi \lor \lnot \phi$. Applying DeMorgan then $φ$'$=\lnotφ=\lnot(\lnot\psi\lor\lnot\phi)$.

2. $φ$'=$\psi$ $\lor$ $\phi$: Similar approach to 1.

3. $φ$'=$\lnot \psi$:Therefore $φ=\lnot \psi$, and $φ$'$=φ=\lnot \psi$.

Answer 1

I would strongly suggest structural induction. That is, rather than using some unnecessarily convoluted way of doing induction on the length of the statement or number of operators, you can simply follow the recursive definition of statements, which is:

1. All propositional variables are statements

2a. If $\psi$ is a statement, then $\neg \psi$ is a statement

2b. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

2c. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

3. Nothing else is a statement

Structural induction mirrors this very recursive definition. That is, in order to show that all statements have some property, show that:

Base: Show that all propositional variables have the property

Step:

a. Show that $\neg \psi$ has the property assuming that $\phi$ has the property

b. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

c. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

If we can show these things, and given that nothing else is a statement (that is why 3 in the definition is important to have), we can conclude that all statements haven the property in question.

Also, make sure to clearly and explicitly state what you are trying to prove. Here is what you are trying to prove:

CLAIM

For all statements $\phi$ it is true that $\phi' \Leftrightarrow \neg \phi$

Note that I use $\Leftrightarrow$ here, because that is the symbol typically used for logical equivalence. The $=$ is often used to indicate that some statement is syntactically identical to some other statement, which is not the same as logical equivalence. For example, $P \land Q \Leftrightarrow Q \land P$, but they are not the same symbol string, i.e. $P \land Q \not = Q \land P$

OK, so let's apply structural induction to your problem:

Base case: $\phi$ is some atomic formula $P$. Then $\phi' = P' = \neg P = \neg \phi$, and therefore certainly $\phi' \Leftrightarrow \neg \phi$. Check!

Step: Take any complex $\phi$, i.e. $\phi = \psi_1 \land \psi_2$, $\phi = \psi_1 \lor \psi_2$, or $\phi = \neg \psi$

Let's just do the $\phi = \psi_1 \land \psi_2$ case.

By inductive hypothesis we have $\psi_1' \Leftrightarrow \neg \psi_1$, and $\psi_2'\Leftrightarrow \neg \psi_2$

So then:

$$\phi'=(\psi_1 \land \psi_2)'=(\psi_1' \lor \psi_2') \overset{I.H.}{\Leftrightarrow} (\neg \psi_1 \lor \neg \psi_2) \overset{D.M.}{\Leftrightarrow} \neg (\psi_1 \land \psi_2) = \neg \phi$$

Do you see now how the inductive hypothesis was used?

Answer 2

I would strongly suggest structural induction. That is, rather than using some unnecessarily convoluted way of doing induction on the length of the statement or number of operators, you can simply follow the recursive definition of statements, which is:

1. All propositional variables are statements

2a. If $\psi$ is a statement, then $\neg \psi$ is a statement

2b. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

2c. If $\psi_1$ and $\psi_2$ are statements, then $\psi_1 \land \psi_2$ is a statement

3. Nothing else is a statement

Structural induction mirrors this very recursive definition. That is, in order to show that all statements have some property, show that:

Base: Show that all propositional variables have the property

Step:

a. Show that $\neg \psi$ has the property assuming that $\phi$ has the property

b. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

c. Show that $\psi_1 \land \psi_2$ has the property assuming that $\psi_1$ and $\psi_2$ have the property

If we can show these things, and given that nothing else is a statement (that is why 3 in the definition is important to have), we can conclude that all statements haven the property in question.

Also, make sure to clearly and explicitly state what you are trying to prove. Here is what you are trying to prove:

CLAIM

For all statements $\phi$ it is true that $\phi' \Leftrightarrow \neg \phi$

Note that I use $\Leftrightarrow$ here, because that is the symbol typically used for logical equivalence. The $=$ is often used to indicate that some statement is syntactically identical to some other statement, which is not the same as logical equivalence. For example, $P \land Q \Leftrightarrow Q \land P$, but they are not the same symbol string, i.e. $P \land Q \not = Q \land P$

OK, so let's apply structural induction to your problem:

Base case: $\phi$ is some atomic formula $P$. Then $\phi' = P' = \neg P = \neg \phi$, and therefore certainly $\phi' \Leftrightarrow \neg \phi$. Check!

Step: Take any complex $\phi$, i.e. $\phi = \psi_1 \land \psi_2$, $\phi = \psi_1 \lor \psi_2$, or $\phi = \neg \psi$

Let's just do the $\phi = \psi_1 \land \psi_2$ case.

By inductive hypothesis we have $\psi_1' \Leftrightarrow \neg \psi_1$, and $\psi_2'\Leftrightarrow \neg \psi_2$

So then:

$$\phi'=(\psi_1 \land \psi_2)'=(\psi_1' \lor \psi_2') \overset{I.H.}{\Leftrightarrow} (\neg \psi_1 \lor \neg \psi_2) \overset{D.M.}{\Leftrightarrow} \neg (\psi_1 \land \psi_2) = \neg \phi$$

Do you see now how the inductive hypothesis was used?