[Math] “tree-like” proof of compactness theorem in the case of uncountably many variables

compactnesslogicset-theorytrees

I like proofs using trees and König's lemma, since they are very visual.

One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, which says that a set of formula is satisfiable if and only if every finite subset is satisfiable.

In this proof you have to order the statements in your theory into a sequence and order the variables accordingly.
Then you construct a tree in which each vertex corresponds to truth values of a variables from the statements $T_1,\dots,T_n$ and then infinite branch gives you interpretation of all variables which is consistent with the whole theory.

In this way you can prove the compactness theorem under the assumption that the set of variables is countable.

Is there a proof in the similar spirit which works for arbitrary sets of variables too? (Or some technique which can be used to obtain uncountable version if we already have countable version?)

I am interested mainly in the proofs avoiding the use of completeness theorem.

Best Answer

I don't know a way to make the proof of propositional compactness, for uncountable sets of formulas, look like a tree argument. But if you go back to how König's Lemma is usually proved and apply that argument to the particular tree that you described, then the resulting argument for propositional compactness generalizes quite directly, to the following argument.

Given a set $S$ of propositional formulas, well-order the set of propositional variables occurring in these formulas, and proceed by (transfinite) induction over this well-ordering. When your inductive process arrives at a variable $p$, you assign a truth value to $p$, so as to preserve the following inductive hypothesis:

(*) For any finite subset $F$ of $S$, there exists a truth assignment that makes $F$ true and agrees with all the values assigned so far in your inductive process.

The hypothesis of the compactness theorem is that (*) holds at the beginning of your process, before you've assigned values to any of the variables. If (*) holds when you're about to assign a value to $p$, then you can choose that value so as to maintain (*). The reason is that if the value "true" for $p$ fails to work because of a finite $F_1\subseteq S$ and "false" fails because of $F_2$, then (*) already failed before you gave $p$ any truth value, because of $F_1\cup F_2$. You also have to check that (*) continues to hold at limit stages, but that is easy because any failure at a limit stage, involving a finite $F$ and thus only finitely many variables, would have already been a failure at an earlier stage.

After your transfinite induction is complete, (*) says that the specific truth values you've assigned to the variables satisfy all finite subsets of $S$ and therefore satisfy $S$.

Related Question