Multi-Page Printing

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 and such that: whenever Θ ⊂ Δ is countable and 𝜙, ⋁ Θ ∈ Δ then ⋁ {∃𝑥𝜃:𝜃 ∈ Θ}, ⋁ {𝜙∧𝜃:𝜃 ∈ Θ}, 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