In
mathematical logic the Löwenheim number of an
abstract logic is the smallest
cardinal number for which a weak downward
Löwenheim–Skolem theorem holds.
[1] They are named after
Leopold Löwenheim, who proved that these exist for a very broad class of logics.
Abstract logic
An abstract logic, for the purpose of Löwenheim numbers, consists of:
- A collection of "sentences";
- A collection of "models", each of which is assigned a cardinality;
- A relation between sentences and models that says that a certain sentence is "satisfied" by a particular model.
The theorem does not require any particular properties of the sentences or models, or of the satisfaction relation, and they may not be the same as in ordinary
first-order logic. It thus applies to a very broad collection of logics, including
first-order logic,
higher-order logics, and
infinitary logics.
Definition
The Löwenheim number of a logic L is the smallest cardinal κ such that if an arbitrary sentence of L has any model, the sentence has a model of cardinality no larger than κ.
Löwenheim proved the existence of this cardinal for any logic in which the collection of sentences forms a
set, using the following argument. Given such a logic, for each sentence φ, let κφ be the smallest cardinality of a model of φ, if φ has any model, and let κφ be 0 otherwise. Then the set of cardinals
- { κφ : φ is a sentence in L }
exists by the
axiom of replacement. The
supremum of this set, by construction, is the Löwenheim number of L. This argument is non-constructive: it proves the existence of the Löwenheim number, but does not provide an immediate way to calculate it.
Extensions
Two extensions of the definition have been considered:
[2]
- The Löwenheim–Skolem number of an abstract logic L is the smallest cardinal κ such that if any set of sentences T ⊆ L has a model then it has a model of size no larger than max(|T|, κ).
- The Löwenheim–Skolem–Tarski number of L is the smallest cardinal such that if A is any structure for L there is an
elementary substructure of A of size no more than κ. This requires that the logic have a suitable notion of "elementary substructure", for example by using the normal definition of a "structure" from predicate logic.
For any logic for which the numbers exist, the Löwenheim–Skolem–Tarski number will be no less than the Löwenheim–Skolem number, which in turn will be no less than the Löwenheim number.
Note that versions of these definitions replacing "has a model of size no larger than" with "has a model smaller than" are sometimes used, as this yields a more fine-grained classification.
[2]
Examples
- The
Löwenheim–Skolem theorem shows that the Löwenheim–Skolem–Tarski number of first-order logic (with countable signatures) is ℵ0. This means, in particular, that if a sentence of first-order logic is satisfiable, then the sentence is satisfiable in a countable model.
- It is known that the Löwenheim–Skolem number of
second-order logic is larger than the first
measurable cardinal, if there is a measurable cardinal.
[2] (And the same holds for its
Hanf number.) The Löwenheim number of the universal (fragment of) second-order logic however is less than the first
supercompact cardinal (assuming it exists).
- The Löwenheim–Skolem–Tarski number of second-order logic is the supremum of all ordinals definable by a formula.
[3]Corollary 4.7
Notes
-
^ Zhang 2002 page 77
- ^
a
b
c Magidor and Väänänen 2009/2010
-
^ J. Väänänen, Sort logic and foundations of mathematics. In Infinity and Truth, Lecture Notes Series of the Institute for Mathematical Sciences of the National University of Singapore, vol. 25 (2014), World Scientific, pp.171--186.
References