Löwenheim number

Löwenheim number

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.

Contents

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. 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 TL 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.

Examples

  • The Löwenheim-Skolem theorem shows that the Löwenheim–Skolem–Tarski number of first-order logic 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.[3]

Notes

  1. ^ Zhang 2002 page 77
  2. ^ Magidor and Väänänen 2009/2010
  3. ^ Magidor and Väänänen 2009/2010.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • 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 κ. The… …   Wikipedia

  • Real number — For the real numbers used in descriptive set theory, see Baire space (set theory). For the computing datatype, see Floating point number. A symbol of the set of real numbers …   Wikipedia

  • metalogic — /met euh loj ik/, n. the logical analysis of the fundamental concepts of logic. [1835 45; META + LOGIC] * * * Study of the syntax and the semantics of formal languages and formal systems. It is related to, but does not include, the formal… …   Universalium

  • 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 (a less… …   Wikipedia

  • Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… …   Wikipedia

  • logic, history of — Introduction       the history of the discipline from its origins among the ancient Greeks to the present time. Origins of logic in the West Precursors of ancient logic       There was a medieval tradition according to which the Greek philosopher …   Universalium

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Countable set — Countable redirects here. For the linguistic concept, see Count noun. Not to be confused with (recursively) enumerable sets. In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of… …   Wikipedia

  • Second-order logic — In logic and mathematics second order logic is an extension of first order logic, which itself is an extension of propositional logic.[1] Second order logic is in turn extended by higher order logic and type theory. First order logic uses only… …   Wikipedia

  • List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”