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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.