$\Phi$ is consistent $\iff$ every finite subset of $\Phi$ is consistent

first-order-logiclogic

I am not sure if I have memorized the definition correctly but a formula $\psi$ is derivable from $\Phi$ ($\Phi\vdash\psi$) iff there is a subset $\Gamma$ such that the sequence $\Gamma\Rightarrow\psi$ is derivable in sequent calculus.

And $\Phi\subseteq FO$ (set of sentences without free variables) is consistent iff $\Phi$ is not inconsitent and $\Phi$ is inconsistent iff every sentence without free variables $\psi$ can be derived from $\Phi$.

I have trouble to understand the $\Leftarrow$ side of the equivalence in the title.

How can I prove that if every subset of $\Phi$ is consistent then $\Phi$ is also consistent?

I could not find a proof, my attempt:

Suppose $\Phi$ is inconsistent but every subset of it is consistent. I don t see why this would yield a contradiction. Because $\Phi$ is inconsistent. I know that for every $\psi$ there is a subset $\Gamma$ such that the sequence $\Gamma\Rightarrow\psi$ can be derived from sequent calculus.

Best Answer

Using the contrapositive, assume $\Phi$ is inconsistent. This means there is a proof of a contradiction from $\Phi$. As proofs are finite in length, it can only use finitely many statements from $\Phi$. That finite subset is then inconsistent.

Related Solutions

Proving that $\{P_1,P_2, \dots, P_n\}$ is complete but not maximally consistent

Your question is slightly ambiguous. In my opinion, there are two possible interpretations of your question:

Let $V$ be the set of all propositional variables (they are countably infinitely many). Then, $V$ is consistent and complete but not maximally consistent.

Proof.
- Consistency: Clearly, there is a model $v$ of $V$, the one such that $v(P) = \top$ for all $P \in V$. By soundness theorem, $V$ is consistent i.e. there is no formula $\varphi$ such that $V \vdash \varphi$ and $V \vdash \lnot \varphi$.
- No maximal consistency: As you correctly said, for any $P, Q \in V$, one has $V \vdash P \land Q$ since $V \vdash P$ and $V \vdash Q$, but the formula $P \land Q \notin V$.
- Completeness: Let $\varphi$ be a formula. There is only one truth assignment $v$ that is a model of $V$: it is the truth assignment $v$ such that $v(P) = \top$ for all $P \in V$. As any truth assignment, either $v \vDash \varphi$ or $v \vDash \lnot \varphi$. Hence, either $V \vDash \varphi$ or $V \vDash \lnot \varphi$, i.e. either all the models of $V$ are a model of $\varphi$ or all the models of $V$ are a model of $\lnot \varphi$. By completeness theorem, $V \vdash \varphi$ or $V \vdash \lnot \varphi$. $\quad\square$
Let $V$ be a proper subset of the set of all propositional variables (in particular, this is the case if $V$ is a finite set of propositional variables). Then, $V$ is consistent but neither complete nor maximal consistent.

Proof.
- Consistency: As above.
- No maximal consistency: given a propositional variable $P \notin V$ (it exists by hypothesis), $V \cup \{P\}$ is consistent (see consistency in Point 1), but $V \subsetneq V \cup \{P\}$.
- No completeness: As correctly suggested by Asaf Kasaglia's comment, given a propositional variable $P \notin V$ (it exists by hypothesis), from the consistency of $V \cup \{P\}$ it follows that $V \not\vdash \lnot P$. But $V \cup \{\lnot P\}$ is consistent as well (take the truth assignment $v$ such that $v(Q) = \top$ for all $Q \in V$, and $v(P) = \bot$, then use soundness theorem to conclude), hence $V \not \vdash P$. $\qquad \square$

Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\neg\varphi\}$ is inconsistent.

If you are allowed to use soundness and completeness theorems (which hold not only in propositional logic but also in first-order logic), the proof is quite easy.

$\Leftarrow$: Suppose $\Sigma \cup \{\neg\varphi\}$ is inconsistent, then there exists a formula $\psi$ such that $\Sigma \cup \{\neg\varphi\}\vdash\psi$ and $\Sigma\,\cup \{\neg\varphi\}\vdash\neg\psi$. By soundness theorem, $\Sigma \cup \{\neg\varphi\} \models \psi$ and $\Sigma \cup \{\neg\varphi\}\models \neg\psi$, which means that every model of $\Sigma \cup \{\neg\varphi\}$ satisfies both $\psi$ and $\lnot \psi$. Now, by definition, there is no structure in first-order logic that satisfies a formula and its negation. Therefore, there is no model of $\Sigma \cup \{\neg\varphi\}$, which means that every model of $\Sigma$ is a model of $\varphi$ as well, i.e. $\Sigma \models \varphi$. According to completeness theorem, $\Sigma \vdash \varphi$.

$\Rightarrow:$ Suppose $\Sigma \vdash \varphi$. Then, $\Sigma \cup \{\lnot \varphi\} \vdash \varphi$, according to the weakening property (which holds in any deduction system for "traditional logics"). But $\Sigma \cup \{\neg\varphi\} \vdash \lnot \varphi$ as well, since $\lnot \varphi \in \Sigma \cup \{\neg\varphi\}$. Hence, $\Sigma \cup \{\neg\varphi\}$ is inconsistent. $\qquad\square$

Note the your use of the soundness theorem in your original post is not correct, or at least not well-written: according to soundness theorem, $\Sigma \vdash \varphi$ does not imply that $\varphi$ is logically valid (a formula is logically valid iff every structure satisfies it), but it implies that every model of $\Sigma$ satisfies $\varphi$ (it is possible that $\Sigma$ has no models and $\varphi$ is unsatisfiable as well).

Roughly, weakening property says that if you can prove something starting from some hypothesis $\Sigma$, you can prove it even when you add more hypotheses to $\Sigma$.

If you are not allowed to use soundness and correctness theorems, the proof of ($\Leftarrow$) is slightly more technical and it depends on the deduction system and the inference rules you are allowed to use. This means that soundness and completeness theorems are not necessary to prove ($\Leftarrow$) but they simplify the proof and also they "universalize" the proof, in the sense that by appealing to these theorems the proof of ($\Leftarrow$) does not depend explicitly on the deduction system and the inference rules you are allowed to use.

Anyway, if the deduction system you are using is Hilbert system with the axiom $(\lnot \varphi \to \lnot \psi) \to ((\lnot \varphi \to \psi) \to \varphi)$ (as the systems described in Mendelson's book, pp. 35 and 69 for propositional and first order logic, respectively), you can easily prove $(\Leftarrow)$ as described in this post, without appealing to the semantic notions involved in soundess and completeness theorems.

Best Answer

Related Solutions

Proving that $\{P_1,P_2, \dots, P_n\}$ is complete but not maximally consistent

Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\neg\varphi\}$ is inconsistent.

Related Question