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