A logician wants to write a single first-order sentence (in standard finitary FOL) that is true in exactly the structures whose underlying graph is connected. This is:
APossible using careful universal and existential quantification over paths
BImpossible, because expressing connectivity requires an infinite disjunction over all possible path lengths
CPossible by applying the compactness theorem to generate an equivalent finite sentence
DPossible if second-order quantifiers are included within the finitary FOL framework
Connectivity requires saying 'for every pair of nodes, there exists a path of some finite length connecting them' — but paths can be of any length 1, 2, 3, ..., requiring an infinite disjunction. Finitary FOL only allows finite formulas, so this disjunction cannot be collapsed into a single sentence. This is a canonical example of an expressibility gap that motivates infinitary logics. Second-order quantifiers (option D) are a different extension that does capture connectivity, but they are not part of finitary FOL.
Question 2 Multiple Choice
Why does the compactness theorem of finitary FOL fail in L_{ω₁,ω}?
ABecause infinite conjunctions in L_{ω₁,ω} can impose constraints that no finite subset of the conjunction captures
BBecause L_{ω₁,ω} has no semantics — it lacks a model theory
CBecause L_{ω₁,ω} formulas cannot be recursively enumerated and thus resist compactness arguments
DBecause the completeness theorem must be proved before compactness, and L_{ω₁,ω} lacks completeness
Compactness says: if every finite subset of a theory has a model, the whole theory has a model. In finitary FOL, every formula is finite, so 'every finite subset' covers all the relevant constraints. But in L_{ω₁,ω}, a single formula can be an infinite conjunction φ_0 ∧ φ_1 ∧ φ_2 ∧ ... — and the whole conjunction may fail to have a model even if every finite fragment {φ_0,...,φ_n} does. The infinite conjunction enforces a property that only emerges in the limit, defeating the compactness argument.
Question 3 True / False
In L_{ω₁,ω}, it is possible to characterize the structure of the natural numbers up to isomorphism, whereas finitary FOL cannot do so.
TTrue
FFalse
Answer: True
This is a key demonstration of infinitary logic's greater expressive power. In finitary FOL, the compactness theorem guarantees non-standard models of arithmetic exist (models that satisfy all first-order sentences true of ℕ but contain 'infinite' elements). L_{ω₁,ω} can write an infinite conjunction that pins down the natural numbers categorically — up to isomorphism, there is only one model. This expressiveness comes at the cost of losing compactness and completeness.
Question 4 True / False
Gaining expressive power in infinitary logics like L_{ω₁,ω} comes with no significant cost — the beautiful theorems of finitary FOL are preserved.
TTrue
FFalse
Answer: False
The tradeoff is severe. Compactness fails: a theory can have a model for every finite subset yet no model overall. Completeness also fails: there is no effective proof system that derives exactly the L_{ω₁,ω} validities — some semantic consequences are not provable by any finite proof. These are not minor technical losses; they are the theorems that make finitary FOL mechanically checkable and practically useful for automated reasoning. The gain in expressiveness is real but comes at the cost of proof-theoretic tractability.
Question 5 Short Answer
What does it mean for a logic to be 'complete,' and why does allowing infinitely long formulas make completeness harder to achieve?
Think about your answer, then reveal below.
Model answer: Completeness means that every sentence which is semantically valid (true in all models) is also syntactically provable (derivable from the axioms via inference rules). In finitary FOL, Gödel's completeness theorem guarantees this: every valid sentence has a finite proof. In infinitary logics, a valid formula may be an infinite conjunction that requires infinitely many steps to 'prove' — but proofs are required to be finite sequences of steps. There is no finite proof system that captures all L_{ω₁,ω} validities because infinite formulas can impose constraints that resist reduction to any finite derivation. The gap between semantic truth and finite provability widens as formula complexity grows without bound.
The core tension is that proof systems operate finitely (finite derivations) while infinitary formulas can encode constraints that only emerge in infinite combinations.