# 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$

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?

• Hello - welcome to the site. Posts that merely pose a problem, without context, are discouraged (indeed, they are often indistinguishable from copies of homework problems) There is some advice at this link about how to write a good post: meta.math.stackexchange.com/questions/9959/… . You can edit your post at any time to improve it. Information that could be included: where did the problem arise? What is your interpretation of it? What have you attempted already? – Carl Mummert Nov 19 '16 at 21:09
• The main hint I can think of is to use induction. What have you tried? – Carl Mummert Nov 19 '16 at 21:12
• Ok, good idea- I wil try to use induction, but why do I should- after all- sets are finite? – user376326 Nov 19 '16 at 21:14
• @Logic Carl means induction on the size of $\Delta$. – Noah Schweber Nov 19 '16 at 21:22
• @NoahSchweber, I edited. – user376326 Nov 20 '16 at 13:00

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$.
• It's a good start. You may want to work on the wording. For instance, "Now let $n>0$ and $\Delta = \Delta' \cup \{\phi\}$ with $\phi \not\in \Delta'$. By the induction hypothesis,..." – Fabio Somenzi Nov 20 '16 at 15:10
• It's close. For instance, when you say, "Let \Delta' = \Delta \cup \{\phi\}$for any$\phi$," you actually mean "some$\phi$." Rewriting the proof as I suggested in my previous post would take care of some of these details. Also, switching from uppercase ($\Delta$,$\Gamma$) to lowercase ($\sigma$) is not a mistake, but should be avoided. – Fabio Somenzi Nov 20 '16 at 15:45 • Yes, I meant some instead any. So, generally it is ok, yeah? – user376326 Nov 20 '16 at 15:52 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\$.