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.