Zasady indukcji, ograniczania i najmniejszych liczb - Induction, bounding and least number principles

W pierwszego rzędu arytmetyki , z zasady indukcji , zasad ograniczających oraz zasad najmniejszej liczbie trzy pokrewne rodziny zasad pierwszego rzędu, które mogą lub nie mogą posiadać w niestandardowych modeli arytmetyki . Zasady te są często używane w matematyce odwrotnej do kalibracji mocy aksjomatycznej twierdzeń.

Definicje

Nieformalnie, w przypadku formuły arytmetycznej pierwszego rzędu z jedną zmienną wolną, zasada indukcji for wyraża ważność indukcji matematycznej nad , podczas gdy zasada najmniejszej liczby dla zapewnia, że ​​jeśli ma świadka , to ma co najmniej jednego. Dla formuły z dwiema wolnymi zmiennymi zasada graniczna dla stanowi, że dla ustalonego ograniczenia , jeśli dla każdego jest takie, że , to możemy znaleźć granicę na 's. ${\ Displaystyle \ varphi (x)}$${\displaystyle \varphi}$${\displaystyle \varphi}$${\displaystyle \varphi}$${\displaystyle \varphi}$${\ Displaystyle \ psi (x, y)}$${\ Displaystyle \ psi}$ ${\displaystyle k}$${\displaystyle n<k}$${\displaystyle m_{n}}$${\ Displaystyle \ psi (n, m_ {n})}$${\displaystyle m_{n}}$

Formalnie zasadą indukcji${\displaystyle \varphi}$ jest zdanie:

${\displaystyle {\mathsf {ja}}\varphi :\quad {\duży [}\varphi (0)\land \forall x{\duży (}\varphi (x)\do \varphi (x+1){ \duży )}{\duży ]}\do \forall x\ \varphi (x)}$

Podobna zasada silnej indukcji${\displaystyle \varphi}$ :

${\ Displaystyle {\ mathsf {I}} '\ varphi : \ quad \ dla wszystkich x {\ duży [} \ dla \ varphi (x){\big ]}\to \forall x\ \varphi (x)}$

Zasada najmniejszej liczby${\displaystyle \varphi}$ to zdanie:

${\ Displaystyle {\ mathsf {L}} \ varphi : \ quad \ istnieje x \ \ varphi (x) \ do \ istnieje x '{\ duży (} \ varphi (x ') \ ziemi \ dla wszystkich y < x '\ \,\lnie \varphi (y){\big )}}$

Wreszcie zasadą graniczną dla${\ Displaystyle \ psi}$ jest zdanie:

${\displaystyle {\mathsf {B}}\psi :\quad \forall u{\duży [}{\duży (}\forall x<u\ \,\istnieje r\ \,\psi (x,y){ \big )}\to \exists v\ \,\forall x<u\ \,\exists y<v\ \,\psi (x,y){\big ]}}$

Częściej rozważamy te zasady nie tylko dla pojedynczej formuły, ale dla klasy formuł w hierarchii arytmetycznej . Na przykład jest schemat aksjomatu składający się z każdej formuły w jednej wolnej zmiennej. ${\ Displaystyle {\ mathsf {I}} \ Sigma _ {2}}$${\displaystyle {\mathsf {ja}}\varphi}$${\ Displaystyle \ Sigma _ {2}}$${\ Displaystyle \ varphi (x)}$

Modele niestandardowe

Wydawać by się mogło, że zasady , , , są trywialne i rzeczywiście obowiązują dla wszystkich formuł , w standardowym modelu arytmetyki . Jednak stają się bardziej odpowiednie w niestandardowych modelach. Przypomnijmy, że niestandardowy model arytmetyki ma postać pewnego porządku liniowego . Innymi słowy, składa się z początkowej kopii , której elementy nazywane są skończonymi lub standardowymi , a następnie z wielu kopii ułożonych w kształt , których elementy nazywane są nieskończonymi lub niestandardowymi . ${\displaystyle {\mathsf {ja}}\varphi}$${\displaystyle {\mathsf {ja}}'\varphi}$${\displaystyle {\mathsf {L}}\varphi}$${\displaystyle {\mathsf {B}}\psi}$${\displaystyle \varphi}$${\ Displaystyle \ psi}$ ${\ Displaystyle \ mathbb {N}}$${\ Displaystyle \ mathbb {N} + \ mathbb {Z} \ cdot K}$${\ Displaystyle K}$${\ Displaystyle \ mathbb {N}}$${\ Displaystyle \ mathbb {Z}}$${\ Displaystyle K}$

Teraz, biorąc pod uwagę zasady , , , w niestandardowym modelu , możemy zobaczyć, jak mogą zawieść. Na przykład hipoteza zasady indukcji zapewnia tylko, że obowiązuje dla wszystkich elementów w części standardowej - może nie obowiązywać dla elementów niestandardowych, do których nie można dotrzeć przez iterację operacji następnika od zera. Podobnie zasada ograniczenia może zawieść, jeśli powiązanie jest niestandardowe, ponieważ wtedy (nieskończona) kolekcja może być kofinalna w . ${\displaystyle {\mathsf {ja}}\varphi}$${\displaystyle {\mathsf {ja}}'\varphi}$${\displaystyle {\mathsf {L}}\varphi}$${\displaystyle {\mathsf {B}}\psi}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle {\mathsf {ja}}\varphi}$${\ Displaystyle \ varphi (x)}$${\ Displaystyle {\ Mathcal {M}}}$${\displaystyle {\mathsf {B}}\psi}$${\ Displaystyle u}$${\displaystyle y}$${\ Displaystyle {\ Mathcal {M}}}$

Relacje między zasadami

Relacje między zasadami indukcji, ograniczania i najmniejszych liczb.

Pomiędzy zasadami zachodzą następujące relacje (nad teorią słabej bazy ): ${\ Displaystyle {\ mathsf {PA}} ^ {-} + {\ mathsf {ja}} \ Sigma _ {0}}$

• ${\displaystyle {\mathsf {ja}}'\varphi \equiv {\mathsf {l}}\lnot \varphi}$dla każdej formuły ;${\displaystyle \varphi}$
• ${\ Displaystyle {\ mathsf {ja}} \ Sigma _ {n} \ równoważny {\ mathsf {ja}} \ pi _ {n} \ równoważny {\ mathsf {ja}} '\ Sigma _ {n} \ równoważny { \mathsf {I}}'\Pi _{n}\equiv {\mathsf {L}}\Sigma _{n}\equiv {\mathsf {L}}\Pi _{n}}$;
• ${\ Displaystyle {\ mathsf {ja}} \ Sigma _ {n + 1} \ implikuje {\ mathsf {B}} \ Sigma _ {n + 1} \ implikuje {\ mathsf {ja}} \ Sigma _ {n} }$, a obie implikacje są ścisłe;
• ${\ Displaystyle {\ mathsf {B}} \ Sigma _ {n + 1} \ równoważny {\ mathsf {B}} \ pi _ {n} \ równoważny {\ mathsf {L}} \ Delta _ {n + 1} }$;
• ${\ Displaystyle {\ mathsf {l}} \ delta _ {n} \ implikuje {\ mathsf {ja}} \ delta _ {n}}$, ale nie wiadomo, czy to się odwraca.

Powyżej , Slaman okazało się, że . ${\ Displaystyle {\ mathsf {PA}} ^ {-} + {\ mathsf {ja}} \ Sigma _ {0}+ {\ mathsf {wyraz}}}$${\ Displaystyle {\ mathsf {B}} \ Sigma _ {n} \ równoważny {\ mathsf {l}} \ Delta _ {n} \ równoważny {\ mathsf {I}} \ Delta _ {n}}$

Matematyka odwrotna

Zasady indukcji, ograniczenia i najmniejszych liczb są powszechnie stosowane w matematyce odwrotnej i arytmetyce drugiego rzędu . Na przykład jest częścią definicji podsystemu arytmetyki drugiego rzędu. Stąd też , i to wszystkie twierdzenia . Podsystem sprawdza wszystkie zasady , , , dla arytmetyki , . Nieskończona zasada szufladka jest znany jako równoważne i ponad . ${\ Displaystyle {\ mathsf {I}} \ Sigma _ {1}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\ Displaystyle {\ mathsf {I}} '\ Sigma _ {1}}$${\ Displaystyle {\ mathsf {L}} \ Sigma _ {1}}$${\ Displaystyle {\ mathsf {B}} \ Sigma _ {1}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathsf {ACA}}_{0}}$${\displaystyle {\mathsf {ja}}\varphi}$${\displaystyle {\mathsf {ja}}'\varphi}$${\displaystyle {\mathsf {L}}\varphi}$${\displaystyle {\mathsf {B}}\psi}$ ${\displaystyle \varphi}$${\ Displaystyle \ psi}$${\ Displaystyle {\ mathsf {B}} \ Pi _ {1}}$${\ Displaystyle {\ mathsf {B}} \ Sigma _ {2}}$${\displaystyle {\mathsf {RCA}}_{0}}$

Bibliografia