Matematické Fórum

Mephisto · 22. 08. 2009 21:57

Jak vlastně definovat co nejjednodušeji přirozená čísla? :) Triviální, že? ;)

Na matice v Brně jsme je definovali několikrát:

1) N je nejmenší induktivní podmnožina R. Super, jenže využívat k definici N dosti netriviální axiomatickou konstrukci, jíž je definována R [ve zkratce nespočetné, spojité, uspořádané těleso, přičemž jeho uspořádání je slučitelné s operacemi + a * toho tělesa], se mi jeví jako použití moc těžkého kladiva. Tohle není jednoduché.

2) Z hlediska teorie množin:
(i) prázdná množina patří do N
(ii) A patří do N implikuje že i {A} patří do N.
(iii) do N nepatří nic, co není vynuceno (i) a (ii) (bohužel si nejsem jist, jak byla ta (iii) přesně :( )
Fajn, jenže to mi nedefinuje sčítání ani násobení. Taky se mi to nelíbí.

3) Peanova aritmetika. K té mám nějaký iracionální odpor :D Přijde mi strašně těžkopádná, prakticky nic v ní nejsem schopen dokázat, ... a spousta věcí v ní ani dokázat nejde (např. korektnost Ackermannovy fce). Prostě PA mi nepřijde ani jednoduchá, ani elegantní.

Má někdo nějaký další nápad? :)

Kondr · 22. 08. 2009 22:40 — Editoval Kondr (22. 08. 2009 22:50)

Ještě si vybavuju, že se dají definovat podobně jako ve 2), akorát následník definovat jako

$S(n)=\{n\}\cup n$

takže přirozená čísla pak jsou $\emptyset,\{\emptyset\},\{\{\emptyset\},\emptyset\},...$ a třeba relace $a<b$ pak má pěkné vyjádření $a\in b$ . Tahle definice dost úzce souvisí s ordinálními čísly. Sčítání a násobení se na takovéhle struktuře se pak dá definovat pomocí Peanových axiomů. Jak se ale dostat k Ackermanově funkci netuším.

A ještě sii vzpomínám na Churchovy číslovky, ale to je to samé co 2) akorát v řeči lambda kalkulu.

Lishaak · 23. 08. 2009 12:29

Ono zalezi hodne na tom, jake prostredky mas k dispozici. Kdyz uz mam realna cisla, tak zevedeni prirozenych je jednoduche. Horsi je to ve chvili, kdy zacinam takrikajic na zelene louce. Nejbeznejsim zpusobem jsou opravdu ty Peanovy axiomy, nevim, proc k nim mas odpor. Je jich par a definuji vsechno, co potrebujes. To s tou Ackermannovu funkci by me celkem zajimalo, mas odkaz na nejaky zdroj, odkuds tohle vycetl? Ja jsem pred rokem prosel prednaskou o rekurzivnich funkcich, takze o Ackermannovi neco vim, ale uz to hodne zamlzil cas.

Jinak pozor na jednu vec. To, ze mam aximoy, ktere popisujou nejakou strukturu jeste neznamena, ze takova struktura vubec existuje. Takze kdyz mam peanovy axiomy, stejne netusim, jestli vubec nejaka mnozina temhle axiomum vyhovuje. Musim dokazat bezespornost tech axiomu. Pokud bych chtel zacit celou matematiku primo s Peanovym axiomy, tak to nejde, to vime od pana Gǒdela. Kdyz mam teorii mnozin a uvnitr te si zavedu Peanovy axiomy, tak bezespornost dokazu treba tak, ze ta prirozena cisla zkostruuju. K tomu se pouziva prave ten pristup, ktery ukazal Kondr

$S(n)=\{n\}\cup n$

Takze jenom axiomy nestaci, musim jeste ta cisla nejak vyrobit.

Mephisto · 23. 08. 2009 13:10

Jasně že mám odkaz, tak např. teďka jsem narychlo vygooglil tohle:

http://en.wikipedia.org/wiki/Paris%E2%8 … on_theorem

Cituji: "The smallest number N that satisfies the strengthened finite Ramsey theorem is a computable function of n, m, k, but grows extremely fast. In particular it is not primitive recursive, but it is also far larger than standard examples of non primitive recursive functions such as the Ackermann function. Its growth is so large that Peano arithmetic cannot prove it is defined everywhere, although Peano arithmetic easily proves that the Ackermann function is well defined."

Čili s tou Ackermannovou funkcí jsem neměl pravdu, na ni je Peanova aritmetika silná dost (i když mám sakryš pocit, že jsem stejně četl přímo o Ackermanově fci... ještě zkusím pohledat) no nicméně na ty rychleji rostoucí funkce už PA nestačí - není schopna dokázat, že jsou pro každé n z N definovány korektně.

Mephisto · 23. 08. 2009 13:19

Co se týká těch přirozených čísel, mě napadlo, jestli by to nešlo zavést nějak že by se řeklo že
(Z,+) je nekonečná volná grupa s jediným generátorem ozn. 1
a
N pak bude pologrupa, generovaná pouze tou jedničkou, bez uvážení inverzí...

co myslíte?

Kondr · 23. 08. 2009 13:42

↑ Mephisto:Takto bych neměl násobení, potřeboval bych ho dodefinovat (tím se vracíme k Peanovým axiomům).

Mephisto · 23. 08. 2009 13:48

Jo, přesvědčil jsi mě :)

Sice, v PA nemám nejen násobení, ale ani sčítání, jenže u toho mého způsobu bych násobení musel dodefinovat právě tak, jako v PA dodefinováváme sčítání (a násobení), totiž že
x+1=S(x)
a
x+S(y) = S(x+y)

a pak
x*1 = x
a
x*S(y) = x*y+x

A přece jen, funkce následníka v PA je přece jen jednodušší a elegantnější, než struktura plynoucí s grupy s dodefinovaným násobením...

OK! :)

Matematické Fórum

#1 22. 08. 2009 21:57

Definice N :)

#2 22. 08. 2009 22:40 — Editoval Kondr (22. 08. 2009 22:50)

Re: Definice N :)

#3 23. 08. 2009 12:29

Re: Definice N :)

#4 23. 08. 2009 13:10

Re: Definice N :)

#5 23. 08. 2009 13:19

Re: Definice N :)

#6 23. 08. 2009 13:42

Re: Definice N :)

#7 23. 08. 2009 13:48

Re: Definice N :)

Zápatí