2
$\begingroup$

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.

Thanks in advance!

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

2 Answers 2

3
$\begingroup$

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<j\le n}x_i=x_j)].$$ 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}\}$.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user400188
    Commented Apr 19, 2021 at 0:05
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Apr 19, 2021 at 0:14
  • $\begingroup$ @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. $\endgroup$ Commented Apr 19, 2021 at 0:15
  • $\begingroup$ 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! $\endgroup$
    – idlatva
    Commented Apr 20, 2021 at 10:36
3
$\begingroup$

Suppose that an infinitely long disjunction (1) exists.

\begin{equation}\tag{1}a_1\lor a_2\lor a_3\lor\dots\end{equation}

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

\begin{equation}\tag{2}\{\lnot a_1,\lnot a_2,\lnot a_3,\dots\}\end{equation}

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.

$\endgroup$
2
  • $\begingroup$ 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)$? $\endgroup$
    – idlatva
    Commented Apr 20, 2021 at 10:33
  • $\begingroup$ @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. $\endgroup$
    – user400188
    Commented Apr 20, 2021 at 22:54

You must log in to answer this question.

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