I am learning propositional logic via a script.
The compactness theorem is presented as: " Let S be a set of propositional formulas. If each finite subset of S is satisfiable, then
S is satisfiable."
(The countability of a set isn't relevant to my question.)
Now, satisfiability is earlier defined as: "A set of formulas S is said to be satisfiable if there exists
an assignment M which satisfies S, i.e., vM (A) = T for all A ∈ S."
i.e. if all elements of a set are satisfiable, then the set itself is by definition satisfiable.
To note vM(A) is the truth valuation of a formula A and M is a mapping of all propositional atoms to {T,F} (The truth valuation) i.e. one of the possible assighments of truth values to propositional atoms.
My question is then, if we know all finite subsets of a given set S are satisfiable, then we also know all subsets with 1 element as satisfiable, whitch are equivlent to all elements themselves, making S satisfiable. (Since S is a subset of itself we could also say S is satisfiable by default if it isn't an infinite set).
The scrpit presents the convoluted proof (for the countable sets) that involves infinitely extending tableu trees via könig's lemma and hitikka's lemma to prove its satiffiability:
" Let S = {A1, A2, . . . , Ai, . . .}. Start with A1 and generate a finite
replete tableau, τ1. Since A1 is satisfiable, τ1 has at least one open path.
Append A2 to each of the open paths of τ1, and generate a finite replete tableau, τ2.
Since {A1, A2} is satisfiable, τ2 has at least one open path. Append A3 to each of the open paths of τ2, and generate a finite replete tableau, τ3. . . . .
Put τ = ⋃∞i=1 τi.
Thus τ is a replete tableau.
Note also that τ is an infinite, finitely branching tree.
By König’s Lemma (Theorem 1.6.6), let S′ be an infinite path
in τ .
Then S′ is a Hintikka set containing S.
By Hintikka’s Lemma, S′ is satisfiable.
Hence S is satisfiable"
The uncountable case is ommited for brevity.
Is this convoluted of proof really necessary, or am I missing something important?
Best Answer
I think you are misunderstanding the quantifiers. To say that a set $\Gamma$ is satisfiable is not to say that, for each sentence $\phi \in \Gamma$, there is a valuation $v$ such that $v(\phi)= T$. Rather, it is to say that there is a valuation $v$ such that, for each $\phi \in \Gamma$, $v(\phi) = T$. As Karl remarked, the former is compatible with each $\phi \in \Gamma$ being made true by a different valuation, whereas the latter calls for a single valuation making all the sentences in the set true.
To see that it is not trivial to pass from several valuations to a single one, consider this case in which compactness fails. Suppose we allow infinite conjunctions in our language, such that, e.g., $\bigwedge\limits_{n \in \mathbb{N}} P_n$ is an infinite conjunction having, for every $n \in \mathbb{N}$, $P_n$ as a conjunct. Then the following set is finitely satisfiable, but not satisfiable:
$\Gamma = \{P_0, \neg Q, (\bigwedge\limits_{n \in \mathbb{N}} P_n \rightarrow Q)\} \cup \{P_n \rightarrow P_{n+1} \; | \; n \in \mathbb{N}\}$
It is not difficult to see that each finite subset of $\Gamma$ is satisfiable, but one cannot combine these valuations into a single one that makes the whole set satisfiable. In light of this, the surprising fact is that, in propositional (and also in first-order) logic, we can do this! After all, why could not there be an incompatibility between infinitely many sentences that only revealed itself when these are considered together?