0

Let $\mathcal{L}_0$ be the language consisting of all propositional symbols $A_n$, along with all formulas formed by using $\neg$ and $\to$. In other words, it is the smallest set $L$ such that $A_n \in L$ for all $n \in \mathbb{N}$, and if $\varphi,\psi \in L$ then $(\neg \varphi), (\varphi \to \psi) \in L$.

Show that, for any set $\Gamma \subseteq \mathcal{L}_0$, there exists an independent set $\Delta$ which is logically equivalent to $\Gamma$.

I am not interested in the case where $\Gamma$ is finite. It is easy to show, in this case, not only that $\Delta$ exists but that $\Delta$ is actually a subset of $\Gamma$. Here, $\Gamma$ is not finite but it IS countable (you can show actually that $\mathcal{L}_0$ is countable, so of course $\Gamma \subseteq \mathcal{L}_0$ is countable).

A very similar question has already been asked here:

Proving that a propositional theory of any cardinality has an independent set of axioms.

However, the solution posted (given in the third paragraph of the question) seems completely flawed to me. I've tried several approaches but I've found nothing. I would have thought that this would be a well-known exercise, but I haven't found it discussed anywhere online except for in this one link I've given above.

Community
  • 1
Michael Knopf
  • 496
  • Please, can you be more explicit about the point of the referred post that is not correct, according to you ? – Mauro ALLEGRANZA Sep 17 '14 at 07:59
  • In the third paragraph, the author begins using $\sigma_i$. I assume the $\sigma_i$ are the consequences of $\Gamma$. They could also be the elements of $\Gamma$. In either case, it is completely possible that $\sigma_0$, for instance, is a tautology. Then in his argument, $\delta_0 = \psi_0 = \sigma_0$ could be a tautology, thus his set $\Delta$ is definitely not independent. – Michael Knopf Sep 17 '14 at 15:48

1 Answers1

0

I believe I have a solution, but I'd appreciate if anyone could check it to make sure I'm not crazy:

Let $\Phi$ be the set of all consequences of $\Gamma$. Since $\Phi \subseteq \mathcal{L}_0$, we know that $\Phi$ is countable. So $\Phi$ = $\{ \varphi_i \}_{i=0}^\infty$.

Define a sequence $\{ \Delta_n \}$ as follows: If $\{ \varphi_0 \}$ is independent, let $\Delta_0 = \{ \varphi_0 \}$. Otherwise, let $\Delta_0 = \emptyset$. Next, for $n>0$, if $\Delta_{n-1} \cup \{\varphi_n \}$ is independent, let $\Delta_n = \Delta_{n-1} \cup \{\varphi_n \}$. Otherwise, if $\Delta_{n-1}$ is logically equivalent to $\Delta_{n-1} \cup \{\varphi_n \}$, then let $\Delta_n = \Delta_{n-1}$. Otherwise, let $$\Delta_n = \Delta_{n-1} \cup \left \{ \left( \left( \bigwedge_{i=0}^{n-1} \varphi_i \right) \to \varphi_n \right) \right \}.$$

Finally, let $$\Delta = \bigcup_{i=0}^\infty \Delta_i.$$ I believe $\Delta$ is now independent and logically equivalent to $\Gamma$.

Michael Knopf
  • 496