Zestaw arytmetyczny

W logice matematycznej zbiór arytmetyczny (lub zbiór arytmetyczny ) to zbiór liczb naturalnych , które można zdefiniować za pomocą wzoru arytmetyki Peano pierwszego rzędu . Zbiory arytmetyczne są klasyfikowane według hierarchii arytmetycznej .

Definicję można rozszerzyć na dowolny przeliczalny zbiór A (np. zbiór n - krotek liczb całkowitych , zbiór liczb wymiernych , zbiór formuł w jakimś języku formalnym , itp.) używając liczb Gödla do reprezentacji elementów zbioru i zadeklarowanie podzbioru A jako arytmetycznego , jeśli zbiór odpowiednich liczb Gödla jest arytmetyczny.

Funkcja ${\ Displaystyle f: \ subseteq \ mathbb {N} ^ {k} \ do \ mathbb {N}}$ jest nazywana arytmetycznie definiowalną , jeśli wykres jest arytmetyczny ${\ displaystyle f}$ ustawić.

Liczbę rzeczywistą nazywamy arytmetyczną , jeśli zbiór wszystkich mniejszych liczb wymiernych jest arytmetyczny. Liczbę zespoloną nazywamy arytmetyczną, jeśli jej części rzeczywista i urojona są arytmetyczne.

Definicja formalna

Zbiór liczb naturalnych X jest arytmetyczny lub definiowalny arytmetycznie , jeśli w języku arytmetyki Peano istnieje formuła pierwszego rzędu φ( n ) taka, że każda liczba n jest w X wtedy i tylko wtedy, gdy φ( n ) zachodzi w modelu standardowym arytmetyki. Podobnie k -ary relacja $_$ ${\ Displaystyle \ psi (n_ {1}, \ ldots, n_ {k})}$ _ takie, że ${\ Displaystyle R (n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})}$ zachodzi dla wszystkich k -krotek ${\ styl wyświetlania (n_{1},\ldots ,n_{k})}$ liczb naturalnych.

Funkcja ${\ Displaystyle f: \ subseteq \ mathbb {N} ^ {k} \ do \ mathbb {N}}$ nazywana jest arytmetyczną, jeśli jej wykres jest relacją arytmetyczną ( k + 1) -ary .

zbiór A jest arytmetyczny w zbiorze B , jeśli A można zdefiniować za pomocą wzoru arytmetycznego, w którym parametrem zestawu jest B.

Przykłady

Zbiór wszystkich liczb pierwszych jest arytmetyczny.
Każdy zbiór rekurencyjnie przeliczalny jest arytmetyczny.
Każda funkcja obliczalna jest definiowalna arytmetycznie.
Zbiór kodujący problem zatrzymania jest arytmetyczny.
Stała Chaitina Ω jest arytmetyczną liczbą rzeczywistą.
Twierdzenie Tarskiego o niedefiniowalności pokazuje, że zbiór (liczb Gödla) prawdziwych formuł arytmetyki pierwszego rzędu nie jest definiowalny arytmetycznie.

Nieruchomości

Dopełnieniem zbioru arytmetycznego jest zbiór arytmetyczny.
Skok Turinga zbioru arytmetycznego jest zbiorem arytmetycznym.
Zbiór zbiorów arytmetycznych jest policzalny, ale kolejność zbiorów arytmetycznych nie jest definiowalna arytmetycznie. Zatem nie ma wzoru arytmetycznego φ( n , m ), który byłby prawdziwy wtedy i tylko wtedy, gdy m należy do n -tego predykatu arytmetycznego.

W rzeczywistości taki wzór opisywałby problem decyzyjny dla wszystkich skończonych skoków Turinga , a zatem należy do 0 ^(ω) , którego nie można sformalizować w arytmetyce pierwszego rzędu , ponieważ nie należy do hierarchii arytmetycznej pierwszego rzędu .

Zbiór rzeczywistych liczb arytmetycznych jest przeliczalny , gęsty i rzędowo izomorficzny ze zbiorem liczb wymiernych.

Niejawnie zbiory arytmetyczne

Każdy zbiór arytmetyczny ma formułę arytmetyczną, która mówi, czy w zbiorze znajdują się określone liczby. Alternatywne pojęcie definiowalności pozwala na formułę, która nie mówi, czy określone liczby znajdują się w zbiorze, ale mówi, czy sam zbiór spełnia jakąś właściwość arytmetyczną.

Zbiór liczb naturalnych Y jest niejawnie arytmetyczny lub niejawnie definiowalny arytmetycznie , jeśli można go zdefiniować za pomocą wzoru arytmetycznego, który może użyć Y jako parametru. To znaczy, jeśli istnieje formuła $arytmetyki$ Peano bez wolnych zmiennych liczbowych i nowego ustawionego parametru i ustalonej relacji członkostwa $\ in}$ takie że Y $zachodzi$ unikalnym Z takim .

Każdy zbiór arytmetyczny jest implicite arytmetyczny; jeśli X jest arytmetycznie zdefiniowane przez φ( n ), to jest domyślnie zdefiniowane przez wzór

{\ Displaystyle \ forall n [n \ in Z \ Strzałka w lewo \ phi (n)]}

.

Jednak nie każdy niejawnie arytmetyczny zbiór jest arytmetyczny. W szczególności zbiór prawdy arytmetyki pierwszego rzędu jest niejawnie arytmetyczny, ale nie arytmetyczny.

Zobacz też

Dalsza lektura

Hartley Rogers Jr. (1967). Teoria funkcji rekurencyjnych i efektywnej obliczalności. McGraw-Hill. OCLC 527706

Systemy liczbowe
Zestawy definiowalnych liczb	Liczby naturalne ( ${\ Displaystyle \ mathbb {N}}$ ) liczby całkowite ( ${\ Displaystyle \ mathbb {Z}}$ ) Liczby wymierne ( ${\ Displaystyle \ mathbb {Q}}$ ) Konstruowalne liczby Liczby algebraiczne ( ${\ Displaystyle \ mathbb {A}}$ ) Liczby w formie zamkniętej Okresy Liczby obliczalne Liczby arytmetyczne Liczby definiowalne w teorii zbiorów Całkowite liczby Gaussa
Algebry kompozycji	Algebry dzielenia : liczby rzeczywiste ( ${\ displaystyle \ mathbb {R}}$ ) Liczby zespolone ( ${\ Displaystyle \ mathbb {C}}$ ) kwaterniony ( ${\ Displaystyle \ mathbb {H}}$ ) Octony ( ${\ Displaystyle \ mathbb {O}}$ )
Podział typów	przez ${\ Displaystyle \ mathbb {R}}: R {\ Displaystyle \ mathbb {R}}$ : Liczby rozdzielno-zespolone Czwartorzędy podzielone Split-octonions Over do ${\ displaystyle \ mathbb {$ }: Liczby dwuzespolone Biquaternions Bioktoniony
Inny hiperkompleks	Numery podwójne Podwójne kwaterniony Liczby podwójnie zespolone Kwaterniony hiperboliczne Sedenions ( ${\ Displaystyle \ mathbb {S}}$ ) Podzielone biquaternions Liczby wielozespolone Algebra geometryczna / algebra Clifforda Algebra przestrzeni fizycznej Algebra czasoprzestrzenna
Inne rodzaje	Liczby kardynalne Rozszerzone liczby naturalne Liczby niewymierne Rozmyte liczby Liczby hiperrzeczywiste Pole Levi-Civita Surrealistyczne liczby Liczby transcendentalne Liczby porządkowe liczby p -adyczne ( elektromagnesy p -adyczne ) Liczby nadprzyrodzone Liczby nadrzeczywiste Normalne liczby
Klasyfikacja Lista