Matematické Fórum

Mihulik

Ahoj,
zadání příkladu zní:
Pro funkci $f$ a $n\in N$ definujeme induktivně funkci $f^n$ takto: $f^1 = f$ a $f^n = f\circ f^{n-1}$ .
Nechť X je konečná množina a $f: X\rightarrow X$ je funkce. Dokažte, že existují dvě různá přirozená čísla r, s taková, že $f^r = f^s$ .

Intuitivně si nějak umím představit, že to platí (definuji si nějakou konečnou množinu, určim si vztahy mezi prvky této množiny a pak je vidět, že z jednoho prvku na jiný se dokážu dostat ve dvou různých počkech kroků), ale jak formálně do důkazu vůbec netuším.

Mohl by mi prosím někdo poradit, jak vůbec začít?

Děkuji:)

vanok · 18. 10. 2011 21:28 — Editoval vanok (18. 10. 2011 22:00)

↑ Mihulik:
Je to lahko vidiet,
X je konecna mnozina , oznacim k pocet jej prvkov.
Aby sa to lahsie vyjadrilo budem pracovat na mnozine $\{1, 2, ...,k\}$
Je jasne ze obraz $(1; 2; ...;k)$ je $$ f(1); f(2);...; f(k)$$ a na to mame $k^k$ moznosti
preto najneskor po $k^k +1$ krokoch musi byt opakovanie.

Autor skryl část textu. Zobrazit/skrýt!

Srdecne Vanok

Mihulik · 19. 10. 2011 20:41

vanok napsal(a):
↑ Mihulik:
X je konecna mnozina , oznacim k pocet jej prvkov.
Aby sa to lahsie vyjadrilo budem pracovat na mnozine $\{1, 2, ...,k\}$
Je jasne ze obraz $(1; 2; ...;k)$ je $$ f(1); f(2);...; f(k)$$ a na to mame $k^k$ moznosti

Děkuji za radu. Do této chvíle to plně chápu, ovšem toto

vanok napsal(a):
preto najneskor po $k^k +1$ krokoch musi byt opakovanie.

už nějak nemůžu pochopit:-/ Nevím, jak z toho plyne, že takové r a s existují... Mohl bys mi to prosím ještě trošku zkusit rozepsat?

děkuji:)

Rumburak

↑ Mihulik:

Nechť $X$ je pevně daná $k$ -prvková množina (kde $k$ je přirozené číslo) a $F$ je množina všech funkcí tvaru $f: X\rightarrow X$ .
Víme, že množina $F$ má $k^k$ prvků (s hlediska středoškolské kombinatoriky je $F$ množina všech variací $k$ -té třídy z $k$ prvků s opakováním).
Tedy množina $F$ má pouze konečně mnoho prvků .
Zvolme pevně $g \in F$ a sestrojme funkční posloupnost $G :=(g^n, n \in \mathbb N)$ podle dané rekurentní formule. Pro každý její člen je $g^n \in F$ ,
tudíž množina $G^* := \{g^n, n \in \mathbb N\}$ jakožto část konečené množiny $F$ je rovněž konečná. Takže posloupnost $G$ nemůže být prostá,
protože v takovém případě by množna $G^*$ musela být nekonečná.

Poznámka: Způsob, jak byla sestrojena posloupnost G, aby jejími členy byly pouze prvky množiny F, nebyl vůbec podstatný. Z předchozích úvah je
jistě zřejmé, že žádná taková posloupnost by nemohla být prostá.

vanok · 20. 10. 2011 10:13 — Editoval vanok (20. 10. 2011 19:42)

↑ Mihulik:
Co sa tyka Dirichlevovho principu, ktory ma po anglicky nadherne meno <<Pigeonhole principle>>
je ozaj nutne ho dobre pochopit, lebo moze zjednodusit mnoho dokazov a nemysli si ze je to folklor co nema miesto v matematike
Ked pocitas 1/7, preco od urciteho miesta sa zacnu opakovat podiely?
Uz aj v beznom zivote ak ma sadnut 11 ludi na 10 stoliciek; co prve ti napadne?

A na ceskej wikipedii, co som ti dal vysie si mohol citat ( a skus to tento weekend sa spytat tvojich spolocnikov pri nedelnom obede) najdes <<Ačkoliv zní princip jednoduše, může být použit k dokázání na první pohled nečekaných výsledků. Můžeme např. dokázat, že v Praze žijí dva lidé, kteří mají přesně stejný počet vlasů. Uvážíme-li, že počet vlasů jednoho člověka nikdy nepřesahuje 1 000 000 a v Praze žije více než 1 000 000 lidí – pak musí být alespoň dva, kteří mají stejný počet vlasů.>>

Mozno ti niekto bude namietat ze na dokaz tohto principu treba AXIOMU VYBERU, ale v beznej matematike je prijata ...

Srdecne Vanok

check_drummer · 20. 10. 2011 19:22

vanok napsal(a):
↑ Mihulik:
Mozno ti niekto bude namietat ze na dokaz tohto principu treba AXIOMU VYBERU, ale v beznej matematike je prijata ...

Myslím, že pokud se pohybujeme v množinách s konečnou mohutností, tak axiom výběru není potřeba.

vanok · 20. 10. 2011 19:41

↑ check_drummer:

To mas pravdu, ale som myslel na vsetki mozne generalizacie principu. Mal som skor explicitne napisat <<Mozno ti niekto bude namietat ze na dokaz tohto principu treba AXIOMU VYBERU, ale v beznej matematike je prijata ...alebo aj niekedy nepotrebna>>
Ale vsetci uzuvatelia mozu tento Dirchlet-ov princip pouzivat bez problemu.

Mihulik · 21. 10. 2011 09:53

Děkuji vám všem. Teď už je mi to, po chvíli zamyšlení, jasné.:)

Dirchletův princip je intuitivně jasný, ale že ho lze formulovat i formálněji, jsem nevěděl - pořádně si to prostuduji.

Ještě jednou děkuji.:)

Matematické Fórum

#1 18. 10. 2011 21:00 — Editoval Mihulik (18. 10. 2011 21:01)

Induktivně zadaná funkce

#2 18. 10. 2011 21:28 — Editoval vanok (18. 10. 2011 22:00)

Re: Induktivně zadaná funkce

#3 19. 10. 2011 20:41

Re: Induktivně zadaná funkce

vanok napsal(a):

vanok napsal(a):

#4 20. 10. 2011 09:43 — Editoval Rumburak (20. 10. 2011 13:45)

Re: Induktivně zadaná funkce

#5 20. 10. 2011 10:13 — Editoval vanok (20. 10. 2011 19:42)

Re: Induktivně zadaná funkce

#6 20. 10. 2011 19:22

Re: Induktivně zadaná funkce

vanok napsal(a):

#7 20. 10. 2011 19:41

Re: Induktivně zadaná funkce

#8 21. 10. 2011 09:53

Re: Induktivně zadaná funkce

Zápatí