Tarskisova střední škola s algebrou - Tarskis high school algebra problem - Wikipedia

v matematická logika, Tarskiho problém střední školy s algebrou byla otázka, kterou položil Alfred Tarski. Ptá se, jestli existují identity zahrnující přidání, násobení, a umocňování přes kladná celá čísla, která nelze dokázat pomocí jedenácti axiomy o těchto operacích, které se vyučují v matematice na střední škole. V roce 1980 byla otázka vyřešena Alex Wilkie, který ukázal, že takové neprokazatelné identity skutečně existují.

Prohlášení o problému

Tarski považoval následujících jedenáct axiomů o sčítání ('+'), násobení ('·') a umocňování za standardní axiomy vyučované na střední škole:

1. X + y = y + X
2. (X + y) + z = X + (y + z)
3. X · 1 = X
4. X · y = y · X
5. (X · y) · z = X · (y · z)
6. X · (y + z) = X · y + X ·z
7. 1^X = 1
8. X¹ = X
9. X^y + z = X^y · X^z
10. (X · y)^z = X^z · y^z
11. (X^y)^z = X^y · z.

Těchto jedenáct axiomů, někdy nazývaných identity na střední škole,^[1] souvisí s axiomy a bikarteziánská uzavřená kategorie nebo exponenciální kruh.^[2] Tarskiho problém se pak stává: existují identity zahrnující pouze sčítání, násobení a umocňování, které platí pro všechna kladná celá čísla, ale které nelze dokázat pouze pomocí axiomů 1–11?

Příklad prokazatelné identity

Vzhledem k tomu, že se zdá, že axiomy uvádějí všechna základní fakta o dotyčných operacích, není okamžitě zřejmé, že by mělo existovat něco prokazatelně pravdivého, co lze říci pomocí pouze tří operací, ale nelze to u axiomů dokázat. Dokazování zdánlivě neškodných tvrzení však může vyžadovat dlouhé důkazy s použitím pouze výše uvedených jedenácti axiomů. Zvažte následující důkaz, že (X + 1)² = X² + 2 · X + 1:

${ displaystyle { begin {aligned} (x + 1) ^ {2} & = (x + 1) ^ {1 + 1} & = (x + 1) ^ {1} cdot (x + 1 ) ^ {1} && { text {o 9.}} & = (x + 1) cdot (x + 1) && { text {o 8.}} & = (x + 1) cdot x + (x + 1) cdot 1 && { text {o 6.}} & = x cdot (x + 1) + x + 1 && { text {o 4 a 3.}} & = x cdot x + x cdot 1 + x cdot 1 + 1 && { text {o 6. a 3.}} & = x ^ {1} cdot x ^ {1} + x cdot (1 + 1) +1 && { text {o 8. a 6.}} & = x ^ {1 + 1} + x cdot 2 + 1 && { text {o 9.}} & = x ^ {2} +2 cdot x + 1 && { text {o 4.}} end {zarovnáno}}}$

Zde jsou závorky vynechány, když nám axiom 2. říká, že nedochází k nejasnostem ohledně seskupování.

Délka důkazů není problém; důkazy podobné identity jako výše pro věci jako (X + y)¹⁰⁰ zabralo by mnoho řádků, ale ve skutečnosti by zahrnovalo jen o málo více než výše uvedený důkaz.

Historie problému

Seznam jedenácti axiomů lze nalézt výslovně zapsaný v pracích Richard Dedekind,^[3] i když je matematici znali a používali už dávno předtím. Dedekind byl však první, kdo se zřejmě ptal, zda jsou tyto axiomy nějak dostačující, aby nám řekly vše, co bychom mohli chtít vědět o celých číslech. Otázka byla postavena na pevný základ jako problém v logice a teorie modelů někdy v 60. letech Alfred Tarski,^[1][4] a v 80. letech se stal známým jako Tarskiho problém střední školy s algebrou.

Řešení

V roce 1980 Alex Wilkie dokázal, že ne každou dotyčnou identitu lze dokázat pomocí výše uvedených axiomů.^[5] Udělal to výslovným nalezením takové identity. Zavedením nových funkčních symbolů odpovídajících polynomům, které mapují kladná čísla na kladná čísla, dokázal tuto identitu a ukázal, že tyto funkce společně s výše uvedenými jedenácti axiomy jsou dostatečné a nezbytné k prokázání. Dotyčná identita je

${ displaystyle { begin {zarovnáno} & left ((1 + x) ^ {y} + (1 + x + x ^ {2}) ^ {y} right) ^ {x} cdot left ( (1 + x ^ {3}) ^ {x} + (1 + x ^ {2} + x ^ {4}) ^ {x} vpravo) ^ {y} = {} & vlevo (( 1 + x) ^ {x} + (1 + x + x ^ {2}) ^ {x} vpravo) ^ {y} cdot left ((1 + x ^ {3}) ^ {y} + (1 + x ^ {2} + x ^ {4}) ^ {y} vpravo) ^ {x}. End {zarovnáno}}}$

Tato identita se obvykle označuje Ž(X,y) a platí pro všechna kladná celá čísla X a y, jak je patrné z factoringu ${ displaystyle (1-x + x ^ {2}) ^ {xy}}$ z druhého termínu; přesto to nelze dokázat pomocí jedenácti středoškolských axiomů.

Intuitivně nelze identitu dokázat, protože středoškolské axiomy nelze použít k diskusi o polynomu ${ displaystyle 1-x + x ^ {2}}$. Úvahy o tom polynomu a podmnožině ${ displaystyle -x}$ vyžaduje koncept negace nebo odčítání a tyto nejsou přítomny ve středoškolských axiomech. Když to chybí, pak je nemožné použít axiomy k manipulaci s polynomem a k prokázání jeho skutečných vlastností. Výsledky Wilkieho z jeho článku ve formálnějším jazyce ukazují, že „jedinou mezerou“ v středních školních axiomech je neschopnost manipulovat s polynomy se zápornými koeficienty.

R. Gurevič v roce 1988 ukázal, že u platných rovnic pro kladná přirozená čísla s 1, sčítáním, násobením a umocněním neexistuje konečná axiomizace.^[6][7]

Zobecnění

Wilkie dokázal, že existují výroky o celých kladných číslech, které nelze dokázat pomocí výše uvedených jedenácti axiomů, a ukázal, jaké další informace jsou zapotřebí, než lze takové výroky dokázat. Použitím Teorie Nevanlinna bylo také prokázáno, že pokud člověk omezuje druhy exponenciální, pak stačí výše uvedených jedenáct axiomů k prokázání každého pravdivého tvrzení.^[8]

Dalším problémem vyplývajícím z výsledku Wilkie, který zůstává otevřený, je ten, který se ptá, co je nejmenší algebra je pro které Ž(X, y) není pravda, ale jedenáct axiomů výše je. V roce 1985 byla nalezena algebra s 59 prvky, která uspokojila axiomy, ale pro které Ž(X, y) byl falešný.^[4] Od té doby byly nalezeny menší algebry a nyní je známo, že ta nejmenší musí mít buď 11 nebo 12 prvků.^[9]

Poznámky

Reference

• Stanley N. Burris, Karen A. Yeats, Sága identit střední školy, Algebra Universalis 52 č. 2–3, (2004), s. 325–342, PAN2161657.