Showing two sets of formulas are logically equivalent using induction.

144 Views Asked by At

Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, and messy, so I redid my answer. Hopefully, it looks a bit more cleaned up. I appreciate anyone's help!

enter image description here

1

There are 1 best solutions below

5
On BEST ANSWER

What have you done so far is NOT enough to prove that the two infinite sets of formulas $\Phi = \{\varphi_n \mid n \in \mathbb{N}^+ \}$ and $\Phi' = \{(\bigwedge_{i=1}^{n-1} \varphi_i) \to \varphi_n \mid n \in \mathbb{N}^+\}$ (where, given infinitely many propositional variables $p_1, p_2, \dots$, we set $\varphi_n = p_1 \land \ldots \land p_n$ for all $n \in \mathbb{N}^+$) are logically equivalent. There are two errors in your approach.

  1. First, proving that $\Phi$ and $\Phi'$ are logically equivalent amounts to show that for every truth valuation $\sigma$, one has $\sigma \models \Phi$ if and only if $\sigma \models \Phi'$. In your approach you are just trying to show that if $\sigma \models \Phi$ then $\sigma \models \Phi'$, you forgot to show the vice-versa.

  2. Second (and this is subtler), your proof by induction show that your property $S(n)$ is true for all $n \in \mathbb{N}^+$, so it does not prove that if $\sigma \models \Phi$ then $\sigma \models \Phi'$, it proves only that, for every $n \in \mathbb{N}^+$, if $\sigma \models \Phi_n$ then $\sigma \models \Phi_n'$, where $\Phi_n = \{\varphi_i \mid 1\leq i \leq n\}$ and $\Phi_n' = \{(\bigwedge_{j=1}^{i-1} \varphi_j) \to \varphi_i \mid 1 \leq i \leq n\}$. You can see the difference if you note that $\Phi$ and $\Phi'$ are infinite sets, whereas, given $n \in \mathbb{N}^+$, $\Phi_n$ and $\Phi_n'$are finite sets. Induction allows you to prove only something about finite (although arbitrarily large) sets. To move from finite to infinite you need also another ingredient: compactness theorem.