Niepierwsze uporządkowanie

W logice formalnej niezgodność z pierwszym porządkiem jest niezdolnością wyrażenia w języku naturalnym do odpowiedniego uchwycenia przez formułę logiki pierwszego rzędu . Konkretnie, stwierdzenie nie jest możliwe do uporządkowania pierwszego rzędu, jeśli nie ma formuły logiki pierwszego rzędu, która byłaby prawdziwa w modelu wtedy i tylko wtedy, gdy stwierdzenie jest spełnione w tym modelu. Instrukcje, których nie można uporządkować w pierwszym rzędzie, są czasami przedstawiane jako dowód na to, że logika pierwszego rzędu nie jest odpowiednia do uchwycenia niuansów znaczeniowych w języku naturalnym.

Termin został ukuty przez George'a Boolosa w jego artykule „Być to być wartością zmiennej (lub być niektórymi wartościami niektórych zmiennych)”. Quine argumentował, że takie zdania wymagają drugiego rzędu , którą można interpretować jako kwantyfikację liczby mnogiej w tej samej domenie, której używają kwantyfikatory pierwszego rzędu, bez postulowania odrębnych „obiektów drugiego rzędu” ( właściwości , zbiory itp.).

Przykłady

Zdanie Geacha-Kaplana

Standardowym przykładem jest zdanie Geacha – Kaplana : „Niektórzy krytycy podziwiają tylko siebie nawzajem”. Jeśli Axy oznacza „ x podziwia y ”, a wszechświat dyskursu jest zbiorem wszystkich krytyków, to rozsądne tłumaczenie tego zdania na logikę drugiego rzędu wygląda następująco:

{\ Displaystyle \ istnieje X (\ istnieje x,y(Xx\land Xy\land Axy)\land \exists x\neg Xx\land \forall x\,\forall y(Xx\land Axy\rightarrow Xy))}

To, że ta formuła nie ma odpowiednika pierwszego rzędu, można zobaczyć, przekształcając ją w formułę w języku arytmetyki. Zastąp formułę ( y = x + 1 v x = y + 1) zamiast Axy . Wynik,

{\ Displaystyle \ istnieje X (\ istnieje x, y (Xx \ ziemia Xy \ ziemia (y = x + 1 \ lor x = y + 1)} \ ziemia \ istnieje x \ neg Xx \land \forall x\,\forall y(Xx\land (y=x+1\lor x=y+1)\rightarrow Xy))}

stwierdza, że istnieje zbiór

X

o następujących własnościach:

$X$ są co najmniej dwie liczby
Istnieje liczba, która nie należy do $X$ , tzn. $X$ nie zawiera wszystkich liczb.
Jeśli liczba $x$ należy do $X$ i $y$ to $x + 1$ lub $x - 1$ , $y$ również należy do $X$ .

Model formalnej teorii arytmetyki, taki jak arytmetyka Peano pierwszego rzędu , nazywany jest standardem , jeśli zawiera tylko znane liczby naturalne $0, 1, 2, ...$ jako elementy. W przeciwnym razie model nazywany jest niestandardowym . Dlatego powyższy wzór jest prawdziwy tylko w modelach niestandardowych, ponieważ w modelu standardowym zbiór $X$ musi zawierać wszystkie dostępne liczby $0, 1, 2, ...$ . Ponadto w każdym modelu niestandardowym istnieje zbiór $X spełniający formułę.$

Załóżmy, że istnieje pierwsze odwzorowanie powyższego wzoru o nazwie $E$ . Gdyby $Peano , oznaczałoby to, że nie$ niestandardowych modeli rozszerzonych aksjomatów. Jednak zwykły argument przemawiający za istnieniem niestandardowych modeli nadal byłby aktualny, dowodząc, że mimo wszystko istnieją niestandardowe modele. Jest to sprzeczność, więc możemy stwierdzić, że taka formuła $E nie$ istnieje w logice pierwszego rzędu.

Skończoność dziedziny

W logice pierwszego rzędu nie ma formuły $A z równością$ , która byłaby prawdziwa dla wszystkich i tylko modeli o skończonych domenach. Innymi słowy, nie ma formuły pierwszego rzędu, która mogłaby wyrazić „istnieje tylko skończona liczba rzeczy”.

Wynika to z twierdzenia o zwartości w następujący sposób. Załóżmy, że istnieje wzór $A$ , który jest prawdziwy we wszystkich i tylko modelach o skończonych dziedzinach. Dla dowolnej dodatniej liczby całkowitej $n$ możemy wyrazić zdanie „ w dziedzinie jest co najmniej $n elementów”.$ Dla danego $n$ wywołaj formułę wyrażającą, że jest co najmniej $n$ elementów $B n$ . Na przykład wzór $B 3$ to:

{\ Displaystyle \ istnieje x \ istnieje y \ istnieje z (x \ neq y \ klin x \ neq z \ klin y \ neq z)}

co wyraża, że istnieją co najmniej trzy różne elementy w domenie. Rozważ nieskończony zestaw formuł

{\ Displaystyle A, B_ {2}, B_ {3}, B_ {4}, \ ldots}

Każdy skończony podzbiór tych formuł ma model: mając podzbiór, znajdź największe

n

, dla którego wzór

B n

należy do podzbioru. Wtedy model z dziedziną zawierającą

n

elementów spełni

A

(ponieważ dziedzina jest skończona) i wszystkie formuły

B

w podzbiorze. Stosując twierdzenie o zwartości, cały zbiór nieskończony musi mieć również model. Ze względu na to, co założyliśmy o

A

, model musi być skończony. Jednak ten model nie może być skończony, bo jeśli model ma tylko

m

pierwiastków, nie spełnia wzoru

B m+1

. Ta sprzeczność pokazuje, że nie może istnieć formuła

A

o założonej przez nas własności.

Inne przykłady

Pojęcie tożsamości nie może być zdefiniowane w językach pierwszego rzędu, a jedynie nierozróżnialność.
Właściwość Archimedesa , której można użyć do identyfikacji liczb rzeczywistych wśród rzeczywistych pól zamkniętych .
Twierdzenie o zwartości implikuje, że spójność grafu nie może być wyrażona w logice pierwszego rzędu. ^{[ wymagane wyjaśnienie ]}

Zobacz też

Linki zewnętrzne

CSS przyjazny dla drukarki i nonfirstorderisability autorstwa Terence'a Tao