In mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

 the Löwenheim number of an abstract logic

Abstract logic

In mathematical logic, an abstract logic is a formal system consisting of a class of sentences and a satisfaction relation with specific properties related to occurrence, expansion, isomorphism, renaming and quantification....

 is the smallest cardinal number

Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

 for which a weak downward Löwenheim–Skolem theorem

Löwenheim–Skolem theorem

In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...

 holds. They are named after Leopold Löwenheim

Leopold Löwenheim

Leopold Löwenheim was a German mathematician, known for his work in mathematical logic. The Nazi regime forced him to retire because under the Nuremberg Laws he was considered only three quarters Aryan. In 1943 much of his work was destroyed during a bombing raid on Berlin...

, who proved that these exist for a very broad class of logics.

Abstract logic

An abstract logic, for the purposes 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

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. It thus applies to a very broad collection of logics, including first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

, higher-order logic

Higher-order logic

In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and a stronger semantics...

s, and infinitary logic

Infinitary logic

An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs. Some infinitary logics may have different properties from those of standard first-order logic. In particular, infinitary logics may fail to be compact or complete. Notions of compactness and...

s.

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:

• 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 .
• 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
  Elementary substructure
  In model theory, a field within mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences....
  
   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.

Examples

• The Löwenheim-Skolem theorem shows that the Löwenheim–Skolem–Tarski number of first-order logic is ℵ₀. 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
  Measurable cardinal
  - Measurable :Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of κ...
  
  , if there is a measurable cardinal.