レーヴェンハイム番号

数学論理学において、抽象論理のレーヴェンハイム数は、弱い下方レーヴェンハイム・スコレム定理が成り立つ最小の基数である。^{[ 1 ]}これらは、非常に広いクラスの論理に対してこれらが存在することを証明したレオポルド・レーヴェンハイム にちなんで名付けられている。

レーヴェンハイム数のための抽象論理は、以下から構成される。

• 「文章」の集まり。
• それぞれにカーディナリティが割り当てられた「モデル」の集合。
• ある文が特定のモデルによって「満たされる」ことを示す、文とモデル間の関係。

この定理は、文やモデル、あるいは充足関係の特定の性質を要求せず、それらは通常の1階述語論理における性質と同じである必要はない。したがって、この定理は、 1階述語論理、高階述語論理、無限論理など、非常に幅広い論理体系に適用できる。

論理Lのレーヴェンハイム数は、 Lの任意の文がモデルを持つ場合、その文のモデルの濃度がκ以下となるような最小の基数κである。

レーヴェンハイムは、文の集合が集合を形成する任意の論理に対して、次の議論を用いてこの基数の存在を証明した。そのような論理が与えられたとき、各文φに対して、φがモデルを持つ場合、κ _{φ を}φのモデルの最小基数とし、そうでない場合はκ _{φ を}0 とする。すると、基数の集合は

{ κ _φ  : φはLの文です}

置換公理により存在する。この集合の上限は、構成上、Lのレーヴェンハイム数である。この議論は非構成的である。レーヴェンハイム数の存在は証明するが、それを直接計算する方法は提供しない。

定義の2つの拡張が検討されている：^{[ 2 ]}

• 抽象論理Lのレーヴェンハイム・スコレム数は、文の集合T ⊆ L がモデルを持つ場合、そのモデルのサイズが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]

• The Löwenheim–Skolem theorem shows that the Löwenheim–Skolem–Tarski number of first-order logic (with countable signatures) 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, 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 $\displaystyle \Pi _{2}}$ formula.^{[3]Corollary 4.7}

• Menachem Magidor and Jouko Väänänen. "On Löwenheim-Skolem-Tarski numbers for extensions of first order logic", Report No. 15 (2009/2010) of the Mittag-Leffler Institute.
• Yi Zhang Logic and algebra 2002. ISBN 0-8218-2984-X