1.2. INFINITARY LOGIC 5
Kei71, Kue70, BF85]. We draw on a few of these results as needed. Here we
just fix the notation.
Notation 1.2.1. For cardinals 𝜅 and 𝜆 and a vocabulary 𝜏, 𝐿𝜅,𝜆(𝜏) is the
smallest collection Φ of formulas such that:
(1) Φ contains all atomic 𝜏-formulas in the variables 𝑣𝑖 for 𝑖 𝜆.
(2) Φ is closed under ¬.
(3) Φ is closed under
⋁
Ψ and
⋀
Ψ where Ψ is a set of fewer than 𝜅 formulas
that contain strictly less than 𝜆 free variables.
(4) Φ is closed under sequences of universal and existential quantifiers over
less than 𝜆 variables 𝑣𝑖.
Thus, the logic 𝐿𝜔1,𝜔 is obtained by extending the formation rules of first order
logic to allow countable conjunctions and disjunctions; each formula of 𝐿𝜔1,𝜔 only
finitely many free variable. 𝐿∞,𝜆 allows conjunctions of arbitrary length.
Definition 1.2.2. A fragment Δ of 𝐿𝜔1,𝜔 is a countable subset of 𝐿𝜔1,𝜔 closed
under subformula, substitutions of terms, finitary logical operations such that:
whenever Θ ⊂ Δ is countable and 𝜙,
⋁
Θ ∈ Δ then
⋁
{∃𝑥𝜃:𝜃 ∈ Θ},
⋁and
{𝜙∧𝜃:𝜃 ∈ Θ},
and
⋁
({𝜙} ∪ Θ) are all in Δ. Further, when dealing with theories with linearly
ordered models, we require that if 𝜙,
⋁
Θ ∈ Δ then
⋁
({for arb large 𝑥)𝜃:𝜃 ∈ Θ}.
The following semantic characterization of 𝐿𝜔1,𝜔 equivalence is an important
tool.
Definition 1.2.3. Two structures 𝐴 and 𝐵 are back and forth equivalent if
there is a nonempty set 𝐼 of isomorphisms of substructures 𝐴 onto substructures of
𝐵 such that:
(forth) For every 𝑓 ∈ 𝐼 and 𝑎 ∈ 𝐴 there is a 𝑔 ∈ 𝐼 such that 𝑓 ⊆ 𝑔 and 𝑎 ∈ dom 𝑔.
(back) For every 𝑓 ∈ 𝐼 and 𝑏 ∈ 𝐵 there is a 𝑔 ∈ 𝐼 such that 𝑓 ⊆ 𝑔 and 𝑏 ∈ rg 𝑔.
We write 𝐴 ≈𝑝 𝐵.
Proofs of the following theorem and related results can be found in e.g. [Bar73]
and [Kue70].
Fact 1.2.4 (Karp). The following are equivalent.
(1) 𝐴 ≈𝑝 𝐵
(2) 𝐴 and 𝐵 are 𝐿∞,𝜔-elementarily equivalent.
Either of these conditions implies that if 𝐴 and 𝐵 are both countable then 𝐴 ≈ 𝐵,
i.e. they are isomorphic.
𝐿(𝑄) or 𝐿𝜔1,𝜔(𝑄) is obtained by adding the further quantifier, ‘there exists un-
countably many’ to the underlying logic. Truth for 𝐿𝜔1,𝜔(𝑄) is defined inductively
as usual; the key point is that 𝑀 ∣ = (𝑄𝑥)𝜙(𝑥) if and only if ∣{𝑚:𝑀 ∣ = 𝜙(𝑚)}∣ ≥ ℵ1.
There are other semantics for this quantifier (see [BF85]). There are other inter-
pretations of the 𝑄-quantifier, requiring for example that 𝜙 has 𝜅 solutions for some
other infinite 𝜅.
Fact 1.2.5 (L¨ owenheim-Skolem theorems). Unlike first order logic, the exis-
tence of models in various powers of an 𝐿𝜔1,𝜔-theory is somewhat complicated. The
downward L¨ owenheim-Skolem to ℵ0 holds for sentences (not theories) in 𝐿𝜔1,𝜔. For
every 𝛼 𝜔1, there is a sentence 𝜙𝛼 that has no model of cardinality greater than
