Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

Mihulik
Příspěvky: 175
Škola: MFF UK - Matematická analýza, Nav. Mag.
Pozice: student
Reputace:   
 

Induktivně zadaná funkce

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:)

Offline

 

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

vanok
Příspěvky: 14322
Reputace:   740 
 

Re: Induktivně zadaná funkce

↑ 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. 



Srdecne Vanok


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#3 19. 10. 2011 20:41

Mihulik
Příspěvky: 175
Škola: MFF UK - Matematická analýza, Nav. Mag.
Pozice: student
Reputace:   
 

Re: Induktivně zadaná funkce

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:)

Offline

 

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

Rumburak
Místo: Praha
Příspěvky: 8691
Reputace:   502 
 

Re: Induktivně zadaná funkce

↑ 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á.

Offline

 

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

vanok
Příspěvky: 14322
Reputace:   740 
 

Re: Induktivně zadaná funkce

↑ 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


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#6 20. 10. 2011 19:22

check_drummer
Příspěvky: 3867
Reputace:   91 
 

Re: Induktivně zadaná funkce

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.


Ve 21. století i vzdělaní lidé učili své děti, že látka je tvořená z atomů.

Offline

 

#7 20. 10. 2011 19:41

vanok
Příspěvky: 14322
Reputace:   740 
 

Re: Induktivně zadaná funkce

↑ 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.


Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT

Offline

 

#8 21. 10. 2011 09:53

Mihulik
Příspěvky: 175
Škola: MFF UK - Matematická analýza, Nav. Mag.
Pozice: student
Reputace:   
 

Re: Induktivně zadaná funkce

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.:)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson