1
$\begingroup$

In the book Philosophical and Mathematical Logic, the following proof of the compactness theorem is presented:

Theorem 2.3 (Compactness theorem). Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model. Then $\Gamma$ has a model

Proof. Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model. We will define an interpretation $i$ of the atomic propositional formulas $P_1,P_2,P_3,\cdots$ such that for every natural number $n$, $\Phi(n)$, where $\Phi(n)$ := every finite subset of $\Gamma$ has a model in which $P_1,\cdots,P_n$ take the values $i(P_1),i(P_2),\cdots,i(P_n)$. Once having shown this, it follows that $i(A) = 1$ for every formula $A$ in $\Gamma$ . For given a formula $A$ in $\Gamma$ , take $n$ so large that all atomic formulas occurring in $A$ are among $P_1,\cdots,P_n$. Since $\{A\}$ is a finite subset of $\Gamma$ and because of $\Phi(n)$, $A$ has a model in which $P_1,\cdots,P_n$ take the values $i(P_1),...,i(P_n)$. So, $i(A) = 1$.

After that the existence of this interpretation is demonstrated by induction, the details are not important.

It seems like this proof works only if the set of all atomic formulas that are used in $\Gamma$ is at most countable. If it's uncountable then we can't denote all the atomic formulas by $P_1, P_2, \cdots$ and and induction proof wouldn't work. Am I missing something or do you agree with me? Did you see this proof before, do you know from where it comes from originally?

$\endgroup$

1 Answer 1

2
$\begingroup$

As you said, this proof assumes that there are only countably many atomic propositions. It is one of the standard proofs for this countable case. It can be extended to prove the general case of compactness, by using transfinite induction. But that extended proof involves a little more work, to handle the limit steps of the transfinite induction.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .