Definovatelná sada - Definable set

V matematické logiky , je definovatelná sada je n -ary vztah k doméně části struktury , jejíž prvky jsou právě ty prvky, které splňují určité vzorec v prvního řádu jazyk z této struktury. Sada může být definován s nebo bez parametrů , které jsou prvky domény, které mohou být odkazované ve vzorci definující vztah.

Definice

Podívejme se nejprve-objednávat jazyk -structure s doménou , pevnou dílčí části , a přirozené číslo . Pak:

  • Sada je definovatelná pomocí parametrů od právě tehdy, když existuje vzorec a prvky takové, že pro všechny ,
kdyby a jen kdyby
Poznámky v závorkách zde označují sémantické vyhodnocení volných proměnných ve vzorci.
  • Sada je definovatelná bez parametrů, pokud je definovatelná pomocí parametrů z prázdné sady (tj. Bez parametrů v definujícím vzorci).
  • Funkce je definovatelná v (s parametry), pokud je její graf definovatelný (s těmito parametry) v .
  • Prvek je definovatelný v (s parametry), pokud je singletonová sada definovatelná v (s těmito parametry).

Příklady

Přirozená čísla pouze s relačním řádem

Nechť je struktura skládající se z přirozených čísel s obvyklým uspořádáním. Pak je každé přirozené číslo definovatelné bez parametrů. Číslo je definováno vzorcem , který uvádí, že neexistují žádné prvky menší než x : a přirozené číslo je definováno vzorcem , který uvádí, že existují přesně prvky menší než x :

Naproti tomu nelze definovat žádné konkrétní celé číslo bez parametrů ve struktuře sestávající z celých čísel s obvyklým uspořádáním (viz níže část o automorfismech ).

Přirozená čísla s jejich aritmetickými operacemi

Dovolit být struktura prvního řádu skládající se z přirozených čísel a jejich obvyklých aritmetických operací a relace řádu. Sady definovatelné v této struktuře jsou známé jako aritmetické sady a jsou klasifikovány v aritmetické hierarchii . Pokud je struktura uvažována v logice druhého řádu namísto logiky prvního řádu, jsou definovatelné sady přirozených čísel ve výsledné struktuře klasifikovány v analytické hierarchii . Tyto hierarchie odhalují mnoho vztahů mezi definovatelností v této struktuře a teorií vypočítatelnosti a jsou také zajímavé pro deskriptivní teorii množin .

Pole reálných čísel

Dovolit je struktura skládající se z pole z reálných čísel . Ačkoli obvyklý vztah řazení není přímo zahrnut do struktury, existuje vzorec, který definuje množinu nezáporných real, protože to jsou jediné reality, které mají druhou odmocninu:

Libovolný tedy není záporný právě tehdy . Ve spojení se vzorcem, který definuje aditivní inverzní funkci reálného čísla v , lze definovat obvyklé řazení v : for , set if and only if is nonnegative. Zvětšená struktura s se nazývá definiční rozšíření původní struktury. Má stejnou expresivní sílu jako původní struktura v tom smyslu, že sada je definovatelná ve zvětšené struktuře ze sady parametrů právě tehdy, pokud je definovatelná nad původní strukturou ze stejné sady parametrů.

Teorie o má kvantifikátoru eliminaci . Definovatelné množiny jsou tedy booleovské kombinace řešení polynomiálních rovností a nerovností; tito se nazývají semi-algebraické množiny . Zobecnění této vlastnosti reálné linie vede ke studiu o-minimality .

Invariance za automorfismů

Důležitým výsledkem definovatelných množin je, že jsou zachovány pod automatickými tvary .

Dovolit být -structure s domény , a definovatelné v parametry z . Dovolme být automorfismem, jehož identitou je . Pak pro všechny ,
kdyby a jen kdyby

Tento výsledek lze někdy použít ke klasifikaci definovatelných podmnožin dané struktury. Například v případě výše je jakýkoli překlad výrazu automorfismus zachovávající prázdnou sadu parametrů, a proto není možné definovat žádné konkrétní celé číslo v této struktuře bez parametrů v . Ve skutečnosti, protože libovolná dvě celá čísla jsou navzájem přenášena překladem a jeho inverzí, jedinou sadou celých čísel definovatelných bez parametrů jsou prázdná množina a sama. Naproti tomu existuje nekonečně mnoho definovatelných sad párů (nebo dokonce n -tuplů pro jakékoli pevné n > 1) prvků , protože jakýkoli automorfismus (překlad) zachovává „vzdálenost“ mezi dvěma prvky.

Další výsledky

Test Tarski-Vaught se používá k charakterizaci základní konstrukcí z dané konstrukce.

Reference

  • Hinman, Peter. Základy matematické logiky , AK Peters, 2005.
  • Marker, David. Teorie modelu: Úvod , Springer, 2002.
  • Rudin, Walter. Principy matematické analýzy , 3. část. vyd. McGraw-Hill, 1976.
  • Slaman, Theodore A. a W. Hugh Woodin. Matematická logika: Vysokoškolský kurz v Berkeley . Jaro 2006.