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