# Show that the compactness theorem does not apply to infinite logic

I am trying to understand why the compactness theorem does not apply in infinite logic and I wonder if anyone has a good example and explanation for this?

Edit: By infinite logic I mean logic that allows infinitely many conjunctions and disjunctions. More exactly:

• $$M \models \bigvee \Gamma$$ iff $$M \models \varphi$$ for some set of sentences $$\varphi \in \Gamma$$.
• $$M \models \bigwedge \Gamma$$ iff $$M \models \varphi$$ for some set of sentences $$\varphi \in \Gamma$$.

The compactness theorem:

The compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model.

• What do you mean by "infinite logic", precisely? Apr 18, 2021 at 23:28
• Hi @EricWofsey, I have updated the question now with an exact explanation of what I mean by infinite logic. Apr 18, 2021 at 23:50

This is called "infinitary logic." For every pair of infinite cardinals $$\kappa\ge\lambda$$ there is a logic $$\mathcal{L}_{\kappa,\lambda}$$ gotten by closing first-order logic under conjunctions and disjunctions of size $$<\kappa$$ and universal and existential quantification over tuples of length $$<\lambda$$. The most common infinitary logics are of the form $$\mathcal{L}_{\kappa,\omega}$$ - so only finitary quantification is allowed, although we permit "big" Boolean combinations.

The logic $$\mathcal{L}_{\omega,\omega}$$ is just first-order logic itself. The first infinitary logic is $$\mathcal{L}_{\omega_1,\omega}$$, where we expand first-order logic by allowing countably infinite conjunctions and disjunctions. Here we already see a failure of compactness: consider the sentence $$(*)\quad\bigvee_{n\in\mathbb{N}}[\forall x_1,...,x_n(\bigvee_{1\le i This is true in a structure iff that structure is finite. But this yields a counterexample to compactness (think about the proof that every first-order theory with arbitrarily large finite models has an infinite model):

Consider the theory $$\{(*)\}\cup\{\mbox{"There are at least n elements"}: n\in\mathbb{N}\}$$.

• I am struggling to find the counterexample. Thinking about arbitrarily large finite models with an infinite model just reminds me of the Upward Löwenheim-Skolem theorem, and shows that this wont hold in infinitary logic. But I can't see how this line of thought leads to a failure of the compactness theorem. Apr 19, 2021 at 0:05
• @user400188 Upward Lowenheim-Skolem is only relevant if you already have an infinite model. It's compactness that lets you go from "arbitrarily large finite" to "infinite" - go back to the first-order case. Apr 19, 2021 at 0:14
• @user400188 And if you look at the end of my answer (behind the "spoiler hider") you'll see an explicit failure of compactness: an infinite theory with no model, every finite subtheory of which has a model. Apr 19, 2021 at 0:15
• Thank you very much for your answer and for the clarification that it is called infinitary logic! I will use your example to find the counterexample, this was very helpful! Apr 20, 2021 at 10:36

Suppose that an infinitely long disjunction (1) exists.

$$$$\tag{1}a_1\lor a_2\lor a_3\lor\dots$$$$

Then consider an infinite collection of formulae (2), consisting of the negation of each instance of the disjunction.

$$$$\tag{2}\{\lnot a_1,\lnot a_2,\lnot a_3,\dots\}$$$$

A theory $$T$$ consisting of (1) and all the formulae in (2) will necessarily be unsatisfiable, as each negated propositional atom $$a_i$$, cannot be satisfied unless the atom is false.

However, every finite subset of formulae in $$T$$ will be satisfiable, (e.g. $$\lnot a_1$$ and $$a_1\lor a_2\lor a_3\lor\dots$$). If the compactness theorem applied, then the set comprising all formulae in the theory will be satisfiable.

This is a contradiction, so it is not the case that the compactness theorem applies in what you have called infinite logic.

• Thanks you so much! But I have a question, if you have the assumption with infinite disjunctions. How do you get a conjunction into the subset, $\neg a_1 \wedge (a_1 \vee a_2 \vee ... \vee a_n)$? Apr 20, 2021 at 10:33
• @idlatva That was a typo. It was meant to end in an ellipsis, and not finish after some finite number of disjunctions. Thank you for pointing it out. Apr 20, 2021 at 22:54