Aritmetická sada - Arithmetical set

v matematická logika, an aritmetická množina (nebo aritmetická sada) je soubor z přirozená čísla které lze definovat a vzorec z první objednávka Peano aritmetika. Aritmetické množiny jsou klasifikovány podle aritmetická hierarchie.

Definici lze rozšířit na libovolné spočetná sada A (např. sada n-n-tice z celá čísla, soubor racionální čísla, sada vzorců v některých formální jazyk atd.) pomocí Gödelova čísla reprezentovat prvky množiny a deklarovat a podmnožina z A být aritmetický, pokud je sada odpovídajících čísel Gödel aritmetická.

A funkce ${ displaystyle f: subseteq mathbb {N} ^ {k} to mathbb {N}}$ je nazýván aritmeticky definovatelné pokud graf z ${ displaystyle f}$ je aritmetická množina.

A reálné číslo je nazýván aritmetický pokud je množina všech menších racionálních čísel aritmetická. A komplexní číslo se nazývá aritmetický, pokud je skutečné a imaginární části jsou obě aritmetické.

Formální definice

Sada X přirozených čísel je aritmetický nebo aritmeticky definovatelné pokud existuje vzorec φ (n) v jazyce Peano aritmetika tak, že každé číslo n je v X právě když φ (n) platí ve standardním modelu aritmetiky. Podobně, a k-ary vztah ${ displaystyle R (n_ {1}, ldots, n_ {k})}$ je aritmetické, pokud existuje vzorec ${ displaystyle psi (n_ {1}, ldots, n_ {k})}$ takhle ${ displaystyle R (n_ {1}, ldots, n_ {k}) iff psi (n_ {1}, ldots, n_ {k})}$ platí pro všechny k- n-tice ${ displaystyle (n_ {1}, ldots, n_ {k})}$ přirozených čísel.

A konečný funkce na přirozených číslech se nazývá aritmetická, pokud její graf je aritmetický binární vztah.

Sada A se říká, že je aritmetický v sada B -li A je definovatelný aritmetickým vzorcem, který má B jako nastavený parametr.

Příklady

Sada všech prvočísla je aritmetický.
Každý rekurzivně vyčíslitelná množina je aritmetický.
Každý vypočítatelná funkce je aritmeticky definovatelný.
Sada kódující Zastavení problému je aritmetický.
Chaitinova konstanta Ω je aritmetické reálné číslo.
Tarskiho věta o nedefinovatelnosti ukazuje, že množina skutečných vzorců aritmetiky prvního řádu není aritmeticky definovatelná.

Vlastnosti

The doplněk aritmetické množiny je aritmetická množina.
The Turingův skok aritmetické množiny je aritmetická množina.
Sbírka aritmetických množin je spočetná, ale sekvence aritmetických množin není aritmeticky definovatelný. Neexistuje tedy žádný aritmetický vzorec φ (n,m) to je pravda právě tehdy m je členem naritmetické predikáty.

Ve skutečnosti by takový vzorec popsal rozhodovací problém pro všechny konečné Turing skoky, a proto patří k 0^(ω), který nelze formalizovat v aritmetika prvního řádu, tak jako nepatří do aritmetické hierarchie prvního řádu.

Sada reálných aritmetických čísel je počitatelný, hustý a řádově izomorfní do množiny racionálních čísel.

Implicitně aritmetické množiny

Každá aritmetická sada má aritmetický vzorec, který určuje, zda jsou konkrétní čísla v sadě. Alternativní pojem definovatelnosti umožňuje vzorec, který neřekne, zda jsou konkrétní čísla v množině, ale řekne, zda množina sama splňuje nějakou aritmetickou vlastnost.

Sada Y přirozených čísel je implicitně aritmetické nebo implicitně aritmeticky definovatelné pokud je definovatelný aritmetickým vzorcem, který lze použít Y jako parametr. To znamená, že pokud existuje vzorec ${ displaystyle theta (Z)}$ v jazyce Peano aritmetiky bez volných číselných proměnných a nového nastaveného parametru Z a nastavit vztah členství ${ displaystyle in}$ takhle Y je jedinečná sada Z takhle ${ displaystyle theta (Z)}$ drží.

Každá aritmetická množina je implicitně aritmetická; -li X je aritmeticky definována φ (n) pak je implicitně definován vzorcem

{ displaystyle forall n [n in Z Leftrightarrow phi (n)]}

.

Ne každá implicitně aritmetická množina je však aritmetická. Zejména sada pravd aritmetiky prvního řádu je implicitně aritmetická, ale ne aritmetická.

Viz také

Další čtení

Rogers, H. (1967). Teorie rekurzivních funkcí a efektivní vypočítatelnost. McGraw-Hill. OCLC 527706

Číslo systémy
Počítatelné sady	Přirozená čísla ( ${ displaystyle mathbb {N}}$ ) Celá čísla ( ${ displaystyle mathbb {Z}}$ ) Racionální čísla ( ${ displaystyle mathbb {Q}}$ ) Konstruktivní čísla Algebraická čísla ( ${ displaystyle mathbb {A}}$ ) Období Vyčíslitelná čísla Definovatelná reálná čísla Aritmetická čísla Gaussova celá čísla
Složení algebry	Divize algebry: Skutečná čísla ( ${ displaystyle mathbb {R}}$ ) Složitá čísla ( ${ displaystyle mathbb {C}}$ ) Čtveřice ( ${ displaystyle mathbb {H}}$ ) Octonions ( ${ displaystyle mathbb {O}}$ )
Rozdělit typy	přes ${ displaystyle mathbb {R}}$ : Split-komplexní čísla Split-čtveřice Split-octonions přes ${ displaystyle mathbb {C}}$ : Dvojkomplexní čísla Biquaternions Bioktoniony
jiný hyperkomplex	Duální čísla Duální čtveřice Dvojkomplexní čísla Hyperbolické čtveřice Sedeniony ( ${ displaystyle mathbb {S}}$ ) Split-biquaternions Multikomplexní čísla Geometrická algebra Algebra fyzického prostoru Časoprostorová algebra
Jiné typy	Kardinální čísla Iracionální čísla Fuzzy čísla Hyperrealistická čísla Pole Levi-Civita Neskutečná čísla Transcendentní čísla Řadové číslovky p-adic čísla (p-adic solenoidy ) Nadpřirozená čísla Superrealistická čísla
Klasifikace Seznam