Alexander counter-attacking Bahamut
Suspended on silver wings...

Publications

Yuna during sending ritual Yuna with Rikku and Payne

Fregeho teoréma

Stručne zo života Fregeho

FregeFriedrich Ludwig Gottlob Frege (nar. 1848, zom. 1925) bol nemecký matematik, logik a filozof, pracoval na univerzite v Jena. Frege sa zaoberal konštrukciou formálneho systému, v ktorom by ukázal, že matematika sa dá redukovať na logiku. Formalizoval pojem “dôkaz” v podobe, aký je aj v súčasnosti akceptovaný. Bohužiaľ jedna z jeho axióm (základné pravidlo V), ktorá bola pridaná, aby mohol z logiky odvodiť podstatnú časť matematiky, spôsobila nekonzistentnosť. Napriek tomu boli jeho definície (relácia predchodcov a koncept prirodzeného čísla) a metódy veľkým pokrokom. Fregeho cieľ ukázať, že matematika sa dá redukovať na logiku ostal nenaplnený.

Poznámka: Fregeho notáciou sa nebudem zaoberať, nakoľko je rozsiahla a nie je predmetom tejto práce. Taktiež dôkazy budú len spomenuté, prípadne iba naznačené.

Príčiny paradoxu a snahy o opravu

Väčšina filozofov tvrdí, že dôvod, prečo Fregeho druhorádová logika (second order logic) a teória rozšírení (theory of extensions) sú nekonzistentné, je nesplniteľná požiadavka - musí platiť, aby doména konceptov bola ostro väčšia ako doména rozšírení a súčasne, aby doména rozšírení bola aspoň taká veľká ako doména konceptov. Táto situácia vedie k podobnému sporu ako pri dôkaze Kantorovej vety (potenčná množina P(A) má ostro väčšiu kardinalitu ako množina A).

Bolo veľa pokusov ako opraviť Fregeho systém. Klasický prístup bol obmedziť axiómu, ktorá nekonzistenciu vyvolala, prípadne zmeniť chápanie príncípu konceptov. Boolos prišiel s nápadom ako upraviť chybnú axiómu bez toho aby sme opustili druhorádovú logiku a jej chápanie princípu konceptov. Na druhej strane bolo veľa nápadov ako zmeniť princíp konceptov, niektoré navrhovali dokonca úplne upustiť od druhorádovej logiky a aj od princípu konceptov. Schroeder-Heister (1987) tvrdil, že prvorádová časť Fregeho systému (teda systém, ktorý vznikne, ak do prvorádového predikátového kalkulu pridáme základné pravidlo V) je konzistentná. Toto tvrdenie dokázali už v 1987 T. Parsons, neskôr Heck a Wehmeier, ktorí použili menej drastický dôkaz.

Napriek problémom s nekonzistentnou axiómou, čím nedosiahol svoj cieľ, Frege urobil chválihodný kus práce. Dokázal veľa vlastností prirodzených čísel, a ukázal aj fakt, že Dedekindove/Peánove axiómy sa dajú odvodiť v druhorádovej logike s pomocou jediného dodatočného princípu. Tento princíp je známy ako Humov Princíp. C. Parsons (1965) a Wright (1983), si všimli, že Humov princíp bol sám o sebe dosť silný na odvodenie Dedekindovych/Peánových axióm. Heck (1993) ukázal, že aj napriek tomu, že Frege použil nekozistnentnú axiómu na odvodenie Humovho princípu, jeho (Fregeho) ďalšie odvodenia Dedekindových/Peánových axióm v teórii čísel z Humovho princípu sa nikdy príliš neodvolávali na nekozistnentnú axiómu. Keďže Humov princíp je sám o sebe konzistentný s druhorádovou logikou, znamená to, že Frege správne odvodil základné pravidlá teórie čísel.

Fregeho analýza kardinálych čísel

Kardinálne čísla sú čísla, ktoré sa dajú použiť ako odpoveď na otázku “Koľko?”. Frege zistil, že tieto čísla majú zaujímavý vzťah s prirodzenými číslami. Prvé pozorovanie bolo, že jednu vec môžeme počítať rôznymi spôsobmi. Keď si zoberieme ako príklad vojsko, obsahuje (napríklad) 5 divízií, 25 regimentov, 120 rôt, 400 čát alebo 4000 ľudí. Otázka “Koľko?” teda nie je dosť presná. Treba sa pýtať “Koľko F-iek?”, kde F je koncept. Z pohľadu Fregeho číslo, ktoré je odpoveďou, nám hovorí čosi o koncepte, ktorý bol v otázke. Napríklad “V slnečnej sústave je osem planét” (Pluto nedávno zrušili) nám hovorí, že prvoúrovňový koncept planéta spadá pod druhoúrovňový koncept slnečná sústava, pod ktorý ich spadá osem.

Z tohto pozorovania vidno, že kardinálne číslo akýmsi spôsobom spája prvoúrovňové a druhoúrovňové koncepty. Frege zaviedol operátor kardinality, ktorý sa aplikuje na koncepty. Tento operátor priraďuje konceptu F jeho kadinálne číslo, teda počet objektov, ktoré spadajú pod F. Označujeme ho #, teda ak F je koncept tak #F je jeho kardinálne číslo.

Ekvinumerozita (Equinumerosity)

Frege zaviedol vzťah, ktorý nazval ekvinumerozita, pod ktorým chápal reláciu, v ktorej sú dve množiny, ak majú rovnaký počet prvkov. Trocha formálnejšie povedané:

F a G sú ekvinumerické (prvky F a G sú jeden-ku-jednému korešpondujúce) iba ak existuje relácia R, taká že

  1. každý objekt spadajúci pod F má pomocou R priradený unikátny prvok z G
  2. každý objekt spadajúci pod G je taký, že existuje jediný prvok z F, ktorý ho má pomocou R priradený.

Ukážeme si použitie definície na príkladoch. V prvom príklade (obrázok 1) sme našli reláciu (R1 = [λxy (x=a & y=f) v (x=b & y=g) v (x=c & y=e)] ), teda koncepty F a G su ekvinumerické.

Obrázok 1

1-1 relation

Obrázok 2

not 1-1 relation

V druhom príklade (obrázok 2) neexistuje relácia, ktorá by spĺňala podmienky z definície. Je zrejmé, že koncepty F a G sú ekvinumerické, vždy vtedy, keď počet objektov, ktoré do každého z nich spadajú, je rovnaký.

Niektoré vlastnosti ekvinumerozity

  1. ak sú dva koncepty materiálne ekvivalentné (identické), sú aj ekvinumerické
  2. ekvinumerozita je reflexívna
  3. ekvinumerozita je symetrická
  4. ekvinumerozita je tranzitívna

Humov princíp

“Počet objektov spadajúcich pod F je rovnaký ako počet objektov spadajúcich pod G, ak F a G sú ekvinumerické.” Toto je slovná formulácia Humovho princípu, formálnejšie môžeme zapísať ako:

#F = #G ≡ F ≈ G

No tomto princípe Frege budoval vývoj teórie o prirodzených číslach. Frege načrtol odvodenie základných vlastností teórie čísel z Humovho princípu. Z týchto náčrtov neskôr vznikli seriózne dôkazy.

Keď mal Frege definíciu #F, potom definoval kardinálne číslo ako objekt, ktorý je číslom nejakého konceptu, formálnejšie:

x is a cardinal number =df (exists)F(x = #F)

Treba si všimnúť podobnosť Humovho princípu a základného pravidla V. Oba hovoria o vzťahu konceptov a objektov. V prípade Humovho princípu, každé F má priradené #F. Základné pravidlo V problematicky tvrdí, že vzťah medzi konceptami a rozšíreniami má povahu jeden-na-jeden. Humov princíp iba tvrdí, že vzťah konceptov a čísel je povahovo viacero-ku-jednému. Humov princíp často viaže viacero konceptov k jednému číslu. Teda Humov princíp narozdiel od základného pravidla V, nevyžaduje mať doménu čísel aspoň tak veľkú ako doménu konceptov. Humov princíp sa ukázal byť konzistentný s druhorádovou logikou. Toto ukázali Burgess (1984) a Hazen (1985), nezávisle od seba.

Fregeho analýza predchodcov, predkov a prirodzených čísel

Teraz predpokladajme, že Humov princíp nahradil nekonzistnetnú axiómu (základné pravidlo V) vo Fregeho druhorádovom systéme.

Výsledok Fregeho analýzy prirodzených čísel bolo, že si uvedomil, že môžeme definovať konečné kardinálne čísla pomocou takto definovaných konceptov:

C0 = [λx x≠x]

C1 = [λx x = #C0]

C2 = [λx x = #C0 v x = #C1]

C3 = [λx x = #C0 v x = #C1 v x = #C2]

... atď

Frege si uvedomil, že tieto koncepty môžeme použiť na definovanie konečných kardinálnych čísel takto:

0 = #C0

1 = #C1

2 = #C2

... atď

Toto pozorovanie bol iba prvý krok Fregeho plánu. Uvedomil si, že toto vyzeralo ako definícia postupnosti čísel, pomocou ktorých by sme vedeli identifikovať prirodzené čísla, ale ešte sme nedefinovali, čo je to prirodzené číslo, takže to môžeme aplikovať len na kardinálne čísla.

Dedekindove/Peánove axiómy teórie čísel

  • 0 je prirodzené číslo
  • 0 nie je nasledovníkom hocijakého prirodzeného čísla
  • Žiadne dve rôzne prirodzené čísla nemajú rovnakého nasledovníka
    • 0 spadá pod F
    • pre ľubovoľné dve prirodzené čísla n a m, také že m je nasledovníkom n, platí, že ak n spadá pod F, tak m spadá pod F, tak každé prirodzené číslo spadá pod F (pricíp indukcie)
  • Každé prirodzené číslo má nasledovníka

Naviac, Frege si uvedomil potrebu použiť princíp indukcie v dôkaze, že každé prirodzené číslo má nasledovníka. Nedá sa dokázať tvrdenie, že každé prirodzené číslo má nasledovníka, iba vytvorením postupnosti výrazov pre kardinálne čísla. Táto formulácia nám na dôkaz nestačí.

Definícia prirodzeného čísla

Nula

Na zadefinovanie prirodzeného čísla potrebujeme niekoľko ďalších definícií. Frege definoval 0 ako kardinálne číslo konceptu nebyť identický sám so sebou, formálnejšie:

0 =df #[λx x≠x]

Keďže identita nám zabezpečuje, že každý objekt je identický sám so sebou, nič nespadá pod koncept nebyť identický sám so sebou.

Teraz sformulujeme lemu o nule, ktorá sa nám neskôr bude hodiť.

Lema: #F = 0 ≡ ¬(exists)xFx

Táto lema tvrdí dosť intuitívnu vec. Ak má koncept F priradené kardinálne číslo 0, tak do neho nič nespadá. Celý dôkaz lemy.

Predchodca

Predchodcu definoval nasledovne:

x predchádza (bezprostredne) y práve vtedy, keď existuje koncept F a objekt w tak, že w spadá pod F a y je kardinálne číslo F a x je číslo konceptu objektov spadajúcich pod F okrem w.

Formálnejšie:

Precedes(x,y) =df (exists)F(exists)w(Fw & y = #F & x = #[λz Fz & z≠w]).

Predok

Predok je predchodca, ale nielen bezprostredný, patrí tam aj predchodca predchodcu a tak ďalej... Takto môžeme zadefinovať reláciu predkov. Oslabením tejto relácie dostaneme jej slabšiu verziu, kde netrváme na tom, aby tam boli len predkovia, ale aj východiskový prvok. Formálne zapísané:

R+(x,y) =df R*(x,y) v x=y.

Prirodzené číslo

Frege definuje prirodzené číslo takto:

x je prirodzené číslo práve vtedy, keď x je členom postupnosti predchodcov začínajúcou 0.

Formálnejšie:

Nx =df Precedes+(0,x).

Fregeho teoréma

Fregeho teoréma tvrdí, že päť Dedekindovych/Peánových axióm môže byť odvodených z Humovho princípu v druhorádovej logike. Prejdime si každú z nich. U niektorých si prejdeme aj dôkazy.

“0 je prirodzené číslo.”

Ľahko vyplýva z definície prirodzeného čísla. Keďže máme slabú verziu relácie predkov, tak platí Precedes+(0,0).

“0 nie je nasledovníkom hocijakého prirodzeného čísla.”

Formálnejšie zapísané:

¬(exists)x(Nx & Precedes(x,0)).

Predpokladajme, že existuje objekt b, taký, že platí Precedes(b,0). Potom podľa definície predchodcu, existuje koncept Q a objekt c také, že Qc & 0=#Q & b=#[λz(exists)Qz & z≠c]. Ale podľa lemy o nule z 0=#Q vyplýva, že ¬(exists)xQx, čo je v spore s predpokladom Qc. Teda nič nepredchádza nulu. Keďže nič nepredchádza nulu, ani žiadne prirodzené číslo nepredchádza nulu.

“Žiadne dve rôzne prirodzené čísla nemajú rovnakého nasledovníka.”

Formálne zapísané:

(all)m(all)n(all)o[Precedes(m,o) & Precedes(n,o) → m = n]

Inak povedané, táto veta tvrdí, že predchodca je v jedna-ku-jednej vzťahu s prirodzenými číslami. Na dokázanie vety stačí ukázať tento fakt. Dokážeme to pomocou Humovho princípu a pomocou lemy o ekvinumerozite. Hlavná myšlienka dôkazu je využiť fakt, že táto lema tvrdí, že ak sú F a G ekvinumerické a x spadá pod F a y spadá pod G, tak koncept F bez x je ekvinumerický s koncpetom G bez y.

equinumrosity lemma

Dôkaz lemy o ekvinumerozite.

“Princíp indukcie”

Frege dokazuje princíp indukcie pomocou všeobecnejšieho tvrdenia tzv. všobecný princíp indukcie.

“Každé prirodzené číslo má nasledovníka.”

Frege toto tvrdenie dokazuje pomocou princípu matematickej indukcie. Formálnejšie zapísané:

(all)x[Nx → (exists)y(Ny & Precedes(x,y))]

Aby sme pochopili dôkaz tejto vety, treba si spomenúť na oslabenú reláciu predkov Precedes+(x,y), ktorá hovorí asi toľko, že x patrí do série predchodcov končiacich y. Frege zavádza pojem série predchodcov končiacich s n [λz Precedes+(z,n)], kde n je prirodzené číslo. Frege potom ukazuje indukciou, že každé prirodzené číslo n predchádza číslo koncpetu “člen série predchodcov končiacej s n”. Teda ukazuje, že každé prirodzené číslo má nasledovníka dokázaním tejto lemy indukciou:

(all)n Precedes(n, #[λz Precedes+(z,n)])

Lema tvrdí, že každé číslo n predchádza počet čísel v sérii predchodcov končiacej s n.

Význam Fregeho teorémy

Z Fregeho teorémy sa dá odvodiť aritmetika. Priamym dôsledkom predchodcu je to, že každé číslo má jedinečného nasledovníka. Teda môžeme zadefinovať funkciu nasledovníkov takto:

n'=df x such that Precedes(n,x)

Postupnosť prirodzených čísel môžeme zadefinovať takto:

1 = 0'

2 = 1'

3 = 2'

atď...

Naviac, rekurzívny spôsobom môžeme zadefinovať ščítanie:

n + 0 = n

n + m' = (n + m)'

Taktiež vieme zadefinovať relácie ostrú a neostrú nerovnosť

n < m=df Precedes*(n,m)

n <= m=df Precedes+(n,m)

Tieto definície sú zakladom pre aritmetiku.

Záver

Aj keď nahradíme nekonzistentnú axiómu (základné pravidlo V) Humovým princípom, Fregeho dielo stále necháva dve otázky otvorené. Ako vieme, že čísla existujú? Ako presne špecifikujeme objekty, ktoré im náležia? Prvá otázka je spôsobená faktom, že Humov princíp sa nezdá byť úplne čisto analytická pravda logiky. Ako vieme, že čísla existujú? Čo ak Humov princíp nie je analyticky správny? Druhá otázka vyplýva z faktu, že Fregeho dielo nijak nešpecifikuje nejakú všeobecnú podmienku, ktorá ak platí tak vieme priradiť zadanému číslu nejaký objekt x. Teda otázky ohľadom existencie a identity čísel stále zatemňujú Fregeho dielo.

Literatúra

Standford encyclopedia of philosophy