Kanamori–McAloons teorem

Inom matematisk logik ger Kanamori –McAloon-satsen , på grund av Kanamori & McAloon (1987), ett exempel på en ofullständighet i Peano-arithmetiken , liknande den i Paris–Harrington-satsen . De visade att en viss finitistisk teorem i Ramsey-teorin inte är bevisbar i Peano-arithmetik (PA).

Påstående

Givet en mängd $s\subseteq \mathbb {N}$ av icke-negativa heltal, låt $min(s)$ beteckna minimielementet av $s$ . Låt $[X]^{n}$ beteckna mängden av alla n - elementundermängder av $X$ .

En funktion $f:[X]^{n}\rightarrow \mathbb {N}$ där $X\subseteq \mathbb {N}$ sägs vara regressiv om $f(s)<min(s)$ för alla $s$ som inte innehåller 0.

Kanamori–McAloon-satsen säger att följande proposition, betecknad med $(*)$ i den ursprungliga referensen, inte är bevisbar i PA:

För varje ${\displaystyle n,k\in \mathbb {N} } ,$ finns det en $m\in \mathbb {N}$ så att för alla regressiva ${\displaystyle f:[\{0,1,\ldots ,m-1\}]^{n}\rightarrow \mathbb {N} } ,$ det finns en uppsättning $H\in [\{0,1,\ldots ,m-1\}]^{k}$ så att för alla $s,t\in [H]^{n}$ med $min(s)=min(t)$ , vi har $f(s)=f(t)$ .

Se även

• Paris–Harringtons sats
• Goodsteins teorem
• Kruskals trädsats

•    Kanamori, Akihiro ; McAloon, Kenneth (1987), "On Gödel incompleteness and finite combinatorics", Annals of Pure and Applied Logic , 33 (1): 23–41, doi : 10.1016/0168-0072(87)90074-1 , ISSN 07128-07168-07168 MR 0870685 _