How to prove that these two second order formulas are equivalent?

Question

Let $F_1 = \exists P\exists Q\exists R \forall x\forall y\forall z (P(x,y) \land Q(y,z) \rightarrow R(x,z))$

and $F_2 =\exists P\exists Q\exists R \forall x\forall y\forall z (Q(x,y) \land P(y,z) \rightarrow R(x,z))$

So P and Q have swapped position in $F_2$.

Are $F_1$ and and $F_2$ logically equivalent? I believe so because $P$ and $Q$ are existentially quantified variables. However, I am not sure how to express this. How do you prove this?

Answer 1

For a formal proof, you need rules for second-order logic; see Dirk van Dalen, Logic and Structure (5th ed - 2013), page 147, for the natural deduction version.

In both cases, you have to apply $\exists^2$-E twice, then use propositional rules to have :

$[(P(x,y)∧Q(y,z))→R(x,z)] \leftrightarrow [(Q(x,y)∧P(y,z))→R(x,z)]$

and finally apply $\exists^2$-I twice.

Answer 2

Well sure. Starting with $F_1$:

1. (Rename variables). Replace all instances of $P$ with $Q$ and vice-versa (simultaneously)
2. (Commute existential quantifiers). Replace the string $\exists Q\exists P$ with the string $\exists P \exists Q$.
3. Note that you've obtained $F_2$.
4. Note also that all steps yielded equivalent sentences.