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


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?

  • $\begingroup$ 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? $\endgroup$ – Carl Mummert Nov 19 '16 at 21:09
  • $\begingroup$ The main hint I can think of is to use induction. What have you tried? $\endgroup$ – Carl Mummert Nov 19 '16 at 21:12
  • $\begingroup$ Ok, good idea- I wil try to use induction, but why do I should- after all- sets are finite? $\endgroup$ – user376326 Nov 19 '16 at 21:14
  • $\begingroup$ @Logic Carl means induction on the size of $\Delta$. $\endgroup$ – Noah Schweber Nov 19 '16 at 21:22
  • $\begingroup$ @NoahSchweber, I edited. $\endgroup$ – user376326 Nov 20 '16 at 13:00

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

  • $\begingroup$ I edited my post $\endgroup$ – user376326 Nov 20 '16 at 12:28
  • 1
    $\begingroup$ 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,..." $\endgroup$ – Fabio Somenzi Nov 20 '16 at 15:10
  • $\begingroup$ Is it correct or not? $\endgroup$ – user376326 Nov 20 '16 at 15:15
  • $\begingroup$ 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. $\endgroup$ – Fabio Somenzi Nov 20 '16 at 15:45
  • $\begingroup$ Yes, I meant some instead any. So, generally it is ok, yeah? $\endgroup$ – 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$.

  • $\begingroup$ I edited my post $\endgroup$ – user376326 Nov 20 '16 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy