First order logic. Independent set of sentences. 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$


*

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

*$\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?
 A: 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$.
A: 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$.
