Löwenheimovo číslo - Löwenheim number

v matematická logika the Löwenheimovo číslo z abstraktní logika je nejmenší základní číslovka pro které slabý směrem dolů Löwenheim – Skolemova věta drží.^[1] Jsou pojmenovány po Leopold Löwenheim, který dokázal, že existují pro velmi širokou třídu logik.

Abstraktní logika

Abstraktní logika pro účely Löwenheimových čísel se skládá z:

• Sbírka „vět“;
• Sbírka „modelů“, z nichž každému je přiřazena mohutnost;
• Vztah mezi větami a modely, který říká, že určitá věta je „uspokojena“ konkrétním modelem.

Věta nevyžaduje žádné zvláštní vlastnosti vět nebo modelů nebo vztahu spokojenosti a nemusí být stejné jako v běžných logika prvního řádu. Platí tedy pro velmi širokou sbírku logik, včetně logika prvního řádu, logiky vyššího řádu, a nekonečná logika.

Definice

Löwenheimovo číslo logiky L je nejmenší kardinál κ takový, že pokud je libovolná věta L má jakýkoli model, věta má model mohutnosti ne větší než κ.

Löwenheim dokázal existenci tohoto kardinála pro jakoukoli logiku, ve které sbírka vět tvoří množinu, pomocí následujícího argumentu. Vzhledem k takové logice, pro každou větu φ, nechť κ_φ být nejmenší mohutností modelu φ, pokud má φ nějaký model, a nechat κ_φ jinak 0. Pak sada kardinálů

{κ_φ : φ je věta v L }

existuje axiom nahrazení. Vrcholem této sady je podle konstrukce počet Löwenheimů L. Tento argument není konstruktivní: dokazuje existenci Löwenheimova čísla, ale neposkytuje okamžitý způsob jeho výpočtu.

Rozšíření

Byly zváženy dvě rozšíření definice:^[2]

• The Löwenheim – Skolem číslo abstraktní logiky L je nejmenší kardinál κ takový, že pokud existuje množina vět T ⊆ L má model, pak má model o velikosti ne větší než max (|T|, κ).
• The Löwenheim – Skolem – Tarski číslo z L je nejmenší kardinál takový, že pokud A je libovolná struktura pro L tady je základní konstrukce z A o velikosti ne větší než κ. To vyžaduje, aby logika měla vhodný pojem „základní podstruktury“, například pomocí normální definice „struktury“ z predikátové logiky.

Pro každou logiku, pro kterou čísla existují, nebude číslo Löwenheim – Skolem – Tarski menší než číslo Löwenheim – Skolem, které zase nebude menší než Löwenheimovo číslo.

Příklady

• The Löwenheim – Skolemova věta ukazuje, že Löwenheim – Skolem – Tarski počet logiky prvního řádu je ℵ₀. To zejména znamená, že pokud je věta logiky prvního řádu uspokojivá, pak je věta splnitelná v spočetném modelu.
• Je známo, že počet Löwenheim – Skolem logika druhého řádu je větší než první měřitelný kardinál, pokud existuje měřitelný kardinál.^[3] (A totéž platí pro jeho Hanfovo číslo.) Löwenheimovo číslo univerzální (fragmentu) logiky druhého řádu je však menší než první superkompaktní kardinál (za předpokladu, že existuje).

Poznámky

Reference

• Menachem Magidor a Jouko Väänänen. "Na Löwenheim-Skolem-Tarski čísla pro rozšíření logiky prvního řádu ", Zpráva č. 15 (2009/2010) institutu Mittag-Leffler.
• Yi Zhang Logika a algebra 2002. ISBN  0-8218-2984-X