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
Previous Page Next Page