Finding a countable, independent, and equivalent set.

122 Views Asked by At

For countable consistent set of well-formed formulas $\Phi$, I have to find a set $\Psi$ that is not necessarily a subset of $\Phi$ that is countable, independent, and equivalent to $\Phi$.

My idea is using the countable consistent set $\left \{ p_{1}, p_{1}\wedge p_{2}, (p_{1}\wedge p_{2}) \wedge p_{3}, ... \right \}$ for variables $p_{i}$. Can I break down these elements and create a set that is both independent and equivalent to $\Phi$? Or is there a better set to work with?

1

There are 1 best solutions below

0
On

Suppose $\Phi = \{\varphi_1,\varphi_2,\varphi_3,\dots\}$. Note that we can first go through the list and remove any formula $\varphi_n$ such that $\{\varphi_1,\dots,\varphi_{n-1}\}\models \varphi_n$, since then $\varphi_n$ is redundant.

So we may assume that no formula follows from the previous formulas on the list, i.e. for all $n$, there is a model $M_n$ such that $M_n\models \varphi_i$ for all $i<n$, but $M\models \lnot \varphi_n$. But this is not enough to ensure that $\Phi$ is independent, since some formula may follow from the later formulas on the list.

To fix this, let $\psi_1 = \varphi_1$, and for all $n>1$, let $\psi_n= \left(\bigwedge_{i<n} \varphi_i \right)\rightarrow \varphi_n$. Let $\Psi = \{\psi_1,\psi_2,\psi_3,\dots\}$.

Now you can prove:

  • $\Phi$ and $\Psi$ are equivalent.
  • For all $n$, $M_n\models \psi_i$ for all $i\neq n$.
  • For all $n$, $M_n\models \lnot \psi_n$.

So the models $M_n$ witness that $\Psi$ is independent.