First Order Logic problem with Compactness theorem

128 Views Asked by At

Let Γ a set of sentences such that every interpretation makes true at least one sentence of Γ. Show that there is a finite set of sentences Γ such that the disjunction of its elements is going to be a valid formula.

Tip: construct Γ from one unsatisfiable set and apply Compactness theorem.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $\Delta$ be the set of negations of sentences of $\Gamma$. We show that some conjunction of sentences of $\Delta$ is inconsistent.

For suppose to the contrary that every finite subset of $\Delta$ is consistent. Then by Compactness there is a model of $\Delta$, that is, a structure $M$ in which all the sentences of $\Delta$ are true. Thus all sentences of $\Gamma$ are false in $M$. This contradicts the given fact that in every interpretation at least one sentence of $\Gamma$ is true.

So some finite subset of $\Delta$ is inconsistent. Suppose that this subset consists of the sentences $\lnot\phi_i$, $i=1$ to $n$. Then the disjunction of the $\phi_i$ is valid.