Proving contradiction with logical identities

Question

We know that p → q is not equivalent to q → p. But suppose we make a proof system that has all the rules of logical identities plus the rule (“commutativity of implies”) p → q ≃ q → p. (We are using the new symbol ≃ because these are not really equivalent.)

This new proof system is not sound. The point of this question is to show that you can prove any contradiction in this system.

Prove true ≃ false in this proof system.

Hint: You might want to start your chain of ≃ in the middle with false → true ≃ true → false. Note that the logical identities do not include a rule ¬true ≡ false, so if you want to use this, you should derive it from the other logical identities.

---

How do I go about starting this proof? Can someone explain the hint to me?

Thanks!

EDIT: Here's a list of identities we're allowed to use.

Commutativity

p∧q ≡ q∧p

p∨q ≡ q∨p

p↔q ≡ q↔p

Associativity

p∧(q∧r) ≡ (p∧q)∧r

p∨(q∨r) ≡ (p∨q)∨r

Distributivity

p∨(q∧r) ≡ (p∨q)∧(p∨r) p∧(q∨r) ≡ (p∧q)∨(p∧r)

De Morgan

¬(p∧q) ≡ ¬p∨¬q

¬(p∨q) ≡ ¬p∧¬q

Negation ¬(¬p) ≡ p

Excluded Middle

p∨¬p ≡ true

Contradiction

p∧¬p ≡ false

Implication

p→q ≡ ¬p∨q

Contrapositive

p→q ≡ ¬q→¬p

Equivalence

p↔q ≡ (p→q)∧(q→p)

Idempotence

p∨p ≡ p

p∧p ≡p

Simplification I

p ∧ true ≡ p

p ∨ true ≡ true

p ∧ false ≡ false

p ∨ false ≡ p

Simplification II

p∨(p∧q) ≡ p

p∧(p∨q) ≡ p

Answer 1

We assume that if $\phi \equiv \psi$, then $\phi \simeq \chi$ if and only if $\psi \simeq \chi$ (and similar for the right-hand side). Otherwise, we can do nothing meaningful with $\simeq$, and this rule of substitution is one of the cornerstones of propositional logic, so it seems reasonable to use it here.

---

For brevity, denote $\top$ for true and $\bot$ for false.

Using the rule for implication, we infer from $\bot \to \top \simeq \top \to \bot$ that: $$\neg \bot \lor \top \simeq \neg \top \lor \bot$$

If we can derive:

$$\neg\bot \equiv \top \\ \neg\top \equiv \bot$$ then it follows from idempotence that $\top \simeq \bot$.

To prove these identities, we can use excluded middle and contradiction.

Answer 2

As suggested, let’s start with

$$\text{false}\to\text{true}\simeq\text{true}\to\text{false}\;,$$

which follows immediately from the new rule. From Implication we get

$$\neg\text{false}\lor\text{true}\simeq\text{false}\to\text{true}\simeq\text{true}\to\text{false}\simeq\neg\text{true}\lor\text{false}\;.\tag{1}$$

You have a Simplification rule that you can usefully apply to the lefthand side of $(1)$ to reduce it to a single term. On the righthand side use Negation to rewrite it as $\neg\text{true}\lor\neg(\neg\text{false})$, apply De Morgan, and Simplification and Negation again; I’ll it to you to work out the details, but feel free to leave a question if you get completely stuck.