Matematické Fórum

Krokzakrokem · 25. 02. 2016 14:46

Dobrý den. Pořád se trápím s tímto příkladem a nejsem si jistá v hned několika bodech. Dokážete mi prosím někdo pomoci? Předem děkuji. Jde o následující příklad:

Pro libovolnou funkci f : X → X a pro každé číslo $n \in N$ jsou definovány mocniny funkce f následujícími vztahy:
$f^{0} := id_{x}, f^{n+1} := f \circ f^{n}$ . Funkce $id_{x} : X \rightarrow X$ je identita na množině X, tj,: $id_{x} (x) = x$ , platí proto $id_{x} \circ g = g \circ id_{x}$ pro libovolnou funkci g : X → X. Matematickou indukcí dokažte, že pro takto definované mocniny funkce f platí známé pravidlo pro počítání s mocninami $f^{m+n} = f^{m} \circ f^{n}$ pro všechna $m, n \in N$ .

a) Jasně definujte prvek, který dokazujete.
$f^{m+n} = f^{m} \circ f^{n}$ ; $m, n \in N$

b) Podle které proměnné indukci provádíte? Jasně vyznačte a dokažte základní krok matematické indukce.
Podle n. // Je vůbec možné ji dělat podle dvou parametrů - zde m a n?
$f^{0+1} := f \circ f^{0} := f \circ id_{x}$
$f^{1} := f$
To evidentně platí
// Nejsem si jistám jestli mohu použít nulu, ale nebylo u N zvýrazněno, že jde o množinu bez nuly a kdybych použila v ZK 1, musela bych pak počítat mat. indulkci se dvěma parametry (v IK m+1 a n+1).

c) Jasně zformulujte indukční krok a indukční předpoklad. Dokažte indukční, vyznačte dekompozici problému a indukčního předpokladu:
IP: $f^{m+n} = f^{m} \circ f^{n}$
IK: Chceme dokázat, že $f^{m+n+1} = f^{m} \circ f^{n} \circ f^{1}$ pro pevné libovloné $n\ge1$
Dekompozice: // netuším...
IK: $f^{m+n+1} = f^{m} \circ f^{n+1}$ ,
protože $f^{n+1} := f \circ f^{n}$ , tedy:
$f^{m+n+1} = f^{m} \circ f \circ f^{n}$
// Může být toto dekompozice?:
$f^{m+n+1} = f^{m} \circ f \circ id_{x} \circ f^{n}$
$f^{m+n+1} = f^{m} \circ f^{1} \circ f^{n}$
// Můžu to přepsat rovnou na následující krok?
$f^{m+n+1} = f^{m} \circ f^{n} \circ f^{1}$

d) Jaký princip matematické indukce používáte?
slabý princip

Rumburak

↑ Krokzakrokem:
Ahoj.

Udělejme si v tom nejdříve pořádek. Tvrzení

(1) $f^{m+n} = f^{m} \circ f^{n}$

má být dokázáno, proto ho nelze použít jako definici, tj. bod a) je pochybný. Definicí je rekurentní předpis

$f^{0} := id_{X}, f^{n+1} := f \circ f^{n}$ , kde $id_{X} (x) = x$ pro $x \in X$ .

Vztah (1) nutno dokázat v následujících krocích :

I. pro $m = 0 = n$ , tj. $f^{0+0} = f^{0} \circ f^{0}$ , což je vzhledem k definici $f^{0} := id_{X}$ triviální.

II. Indukční kroky budou dva, jeden pro proměnnou $m$ (při pevném $n$ ) a druhý pro proměnnou $n$ (při pevném $m$ ).
Tedy pomocí předpokladu $f^{m+n} = f^{m} \circ f^{n}$ (a dalších již známých faktů) dokazujeme platnost vztahů

$f^{m+1+n} = f^{m+1} \circ f^{n}$ , $f^{m+n+1} = f^{m} \circ f^{n+1}$ .

Stačí takto ?

Krokzakrokem · 25. 02. 2016 16:40

↑ Rumburak: Děkuji, základní krok jsem skutečně popletla.
S tím indukčním krokem je to zajímavé a jasnější. Jednou tedy provedeme indukci podle m, podruhé podle n. Mohu se však zeptat, co bude tou dekompozicí? Děkuji.

Rumburak

↑ Krokzakrokem:

S pojmem "dekomposice" se zde setkávám poprvé, patrně je tím míněn opak komposice, tedy vyjádření daného zobrazení $h$
ve tvaru $h = f \circ g$ , kde $f, g$ jsou nějaká - obecně jiná - zobrazení.

Odhaduji, že se snažíš postupovat podle nějakého "kuchařského receptu", který je ale podle mne formulován natolik složitě,
že je to na úkor přehlednosti. Princip mat. indukce je při tom poměrně jednoduchý, lze ho formulovat několika ekvivaletními způsoby,
například následovně.

Nejprve označme $P := \{0, 1, 2, 3, ... \}$ . Jak víme, na množině $P$ je definovana unární operace (tedy funkce o jedné proměnné)
"přičtení jedničky k danému číslu", obecněji operace "součtu dvou čísel" (tedy funkce o dvou proměnných), přičemž součet $m+n$
čísel $m, n \in P$ je rovněž prvkem množiny $P$ . Předpokládejme, že základní vlastnosti této operace jsou známy.

Nyní k vlastní formulaci principu indukce:

Nechť množina $M$ má následující dvě vlastnosti:
(1) $0 \in M$ ,
(2) pro každé $n \in M \cap P$ je $n + 1 \in M$ .
Potom $P \subseteq M$ .

Pokud bychom z množiny $P$ vyloučili nulu $0$ , pak bychom předpoklad (1) nahradili předpokladem $1 \in M$ .

To, co jsem posledně nabídl (využítí "dvojné" indukce), není jediná možnost. Lze vystačit i s "jednoduchou" indukcí, například důkazem
věty ve tvaru

Nechť $M$ je množína všech takových $k \in P$ , pro něž je splněna implikace
$(m, n \in P \wedge m \le k \wedge n \le k) \Rightarrow f^{m+n} = f^{m} \circ f^{n}$ .
Potom $P \subseteq M$ .

Indukce by se pak prováděla podle proměnné $k$ . Tento způsob bude možná efektivnější.

Ať si zvolíme tu či onu cestu, budeme nejspíše potřebovat pomocné tvrzení $f^{n} \circ f= f \circ f^{n}$ ,
které je možno dokázat rovněž indukcí.

Matematické Fórum

#1 25. 02. 2016 14:46

Matematická indukce - skládání funkcí

#2 25. 02. 2016 15:47 — Editoval Rumburak (25. 02. 2016 15:51)

Re: Matematická indukce - skládání funkcí

#3 25. 02. 2016 16:40

Re: Matematická indukce - skládání funkcí

#4 26. 02. 2016 10:39 — Editoval Rumburak (26. 02. 2016 14:18)

Re: Matematická indukce - skládání funkcí

Zápatí