Why there's a finite $\Gamma '$ such that $\Gamma ' \vDash \varphi$?

61 Views Asked by At

Suppose $\Gamma$ is an infinite set of formulas in FOL. It is given that for a structure, $M$: If $\Gamma$ is satisfiable in $M$ then $\varphi$ is valid in $M$.

Why is it true that there's some finite $\Gamma ' \subset \Gamma$, such that $\Gamma ' \vDash \varphi$?

It reminds the compactness theorem in a way, but it's not quite the same.

2

There are 2 best solutions below

3
On BEST ANSWER

It is indeed a consequence of compactness. HINT: If $\Gamma\models\varphi$, then $\Gamma\cup\{\neg\varphi\}$ is unsatisfiable. What does the contrapositive of the Compactness Theorem tell you about a theory which is unsatisfiable?

1
On

From the Compactness Theorem, if there is no finite $\Gamma'\subset\Gamma$ with $\Gamma'\models\varphi$, then $\Gamma\not\models\varphi$. From your hypothesis, it follows that $\Gamma$ cannot be satisfiable. But then, again by Compactness, there is a finite $\Gamma'\subset\Gamma$ with $\Gamma'\vdash\perp$, which means $\Gamma'\models\varphi$.

If otherwise there is a finite $\Gamma'$ as you ask, the thesis follows immediately.