First order logic. Independent set of sentences.

Question

Let $\Delta$ be a finite, consistent set of first-order sentences and $\Sigma$ be a finite signature. Prove that there exists such $\Delta_0 \subseteq \Delta $ that $\Delta_0 \models \Delta$ and : for every $\phi \in \Delta_0 , \Delta_0 \setminus \{\phi\} \not \models \Delta_0 $

I tried to do it. I am asking for hint.

$$ \Delta \text{ is independent iff for every } \phi \in \Delta_0, \Delta_0 \setminus \{\phi\} \not \models \Delta_0$$

Solution:

Base induction

Let $|\Delta| = 0, \Delta = \emptyset$. $\emptyset \models \Delta, \emptyset$ is indenpendent.

Induction step Let $|\Delta| = n $ and $\Delta_0 \subseteq \Delta, \Delta_0 \models \Delta, \Delta_0 $ is independent. Let's consider two cases:

Let $\Delta' = \Delta \cup \{\phi\} $ for any $\phi$

1. $\Delta_0 \models \{\phi\}$. Then $\Delta_0 \models \Delta' $ and $\Delta_0 $ is still independent

2. $\Delta_0 \not \models \{\phi\}$ Let $\Delta_0' = \Delta_0 \cup \{\phi\}$. Then $\Delta_0' \models \Delta' $ Now, let consider two cases:

   2.1 $\Delta_0'$ is independent. Thesis.

   2.2 $\Delta_0'$ is not independent. Therefore, there exists a such $\psi \in \Delta_0 $ that $\Delta_0' \setminus \{\psi \} \models \Delta_0'$. Let $\Gamma = \Delta_0' \setminus \{\psi\}$. Note, that $|\Gamma| \le |\Delta|$. So, from the inductive assumption, we have that there exists a such $\sigma \subseteq \Gamma $ that $\sigma \models \Gamma $ and $\sigma$ is independent. $\sigma \models \Gamma, \Gamma \models \Delta_0' $ so $\sigma \models \Delta_0'$

Is it ok?

Answer 1

A possible hint, expanding on Carl Mummert's and answering the question, "Why induction?" is this:

Let $P(n)$ stand for the claim that every finite, consistent set $\Delta$ of $n$ sentences from a first-order language with signature $\Sigma$ contains an independent subset $\Delta_0$. Your problem consists of proving $\forall n . P(n)$. Therefore induction is the natural approach to the proof. Each $n$ is finite, but you want a proof for all $n$.

Answer 2

Among finite subsets of $\Delta$, there are some of them that satisfy $\Delta_0 \vDash \Delta$, and some of them that do not. Pick one that is minimal: $\Delta_0 \vDash \Delta$, but for all $\Delta_0' \subsetneq \Delta_0$, $\Delta_0' \not \vDash \Delta$.

Now you have to prove that for any $\phi \in \Delta_0$, $\Delta_0 \setminus \{\phi\} \not \vDash \Delta_0$. Suppose towards contradiction that $\Delta_0 \setminus \{\phi\} \vDash \Delta_0$. Then we have $\Delta_0 \setminus \{\phi\} \vDash \Delta_0$ and $\Delta_0 \vDash \Delta$, so $\Delta_0 \setminus \{\phi\} \vDash \Delta$. This contradicts the minimality of $\Delta_0$.