Matematické Fórum

Chanzy · 02. 10. 2012 09:00

Ahoj, poradil byste mi tu někdo prosím, jaký je rozdíl mezi slabou a silnou matematickou indukcí? Nejlépe na nějakém příkladu. Děkuju

vanok · 02. 10. 2012 10:13

Ahoj ↑ Chanzy:,
http://fr.wikipedia.org/wiki/Récurrence … ence_forte

Tu mas zaujimave citanie.
Staci maly slovnik ...

Rumburak

↑ Chanzy:

Ahoj.

S pojmy slabá resp. silná mat. indukce jsem se nesetkal, ale odhaduji, že jde o následující věc.

Označme $\mathbb{N} = \{ 0, 1, 2, ... \}$ množinu všech přirozených čísel (nulu mezi ně počítáme záměrně, důvod se objeví později).

Princip matematické indukce se nejčastěji používá v následujícím tvaru:

Nechť o množině $M$ platí

(0) $0 \in M$ ,
(1) $(\forall n \in \mathbb{N}) (n \in M \Rightarrow n+1 \in M)$ .

Potom $\mathbb{N} \subseteq M$ .

K pochopení alternativního tvaru tohoto principu nám pomůže množinová konstrukce přirozených čísel - naznačme ji.
O množině (obecněji o třídě) $J$ budeme říkat, že je induktivní (toto označení ber pro jistotu jen jako pracovní pro toto vlákno),
má-li vlastnost

(i) $j \subset J \Rightarrow j \in J$ ,

kde $j$ je množinová proměnná (nutno zdůraznit, že $\subset$ značí ostrou inklusi). Rozborem vlastnosti (i) postupně zjistíme,
že každá induktivní třída obsahuje jako své prvky množiny

(2) $\emptyset, \{\emptyset\}\!, \{ \emptyset, \{\emptyset\}\}\!, \{ \emptyset, \{\emptyset\}\!, \{\emptyset, \{\emptyset\}\}\}\!, ...$

(tato posloupnost tedy začíná členem $\emptyset$ a každý další člen je množinou všech členů předchozích).

Množinu složenou výhradně ze členů posloupnosti (2) považujeme v teorii množin za množinu všech přirozených čísel a značime
ji symbolem $\omega$ . Místo $\emptyset$ píšeme $0$ a je-li $n \in \omega$ , potom $n \cup \{n\}$ v (2) považujeme za $n+1$ .

Druhou versi principu matematické indukce pak můžeme zformulovat ve tvaru

Nechť o množině $M$ platí

(3) $(\forall n \in \omega) (n \subset M \Rightarrow n \in M)$ .

Potom $\omega \subseteq M$ .

Místo $n \subset M$ zde můžeme psát $(k\in \omega \wedge k < n) \Rightarrow k \in M$ .

Obě uvedené verse principu matematické indukce jsou spolu ekvivalentní.

Pro další souvislosti hledej hesla ordinální čísla, transfinitní indukce .

radekm · 02. 10. 2012 18:19 — Editoval radekm (02. 10. 2012 18:21)

↑ Rumburak:

Neboli: Pokud platí $M(0), \ldots, M(n-1) \Rightarrow M(n)$ pro každé $n \in \mathbb{N}$ , tak $M$ platí pro všechna přirozená čísla (tj. $\mathbb{N} \subseteq M$ ) - tento princip se nazývá silná MI.

Rumburak

↑ radekm:

Díky, tušil jsem, že to tak bude, ale příslušnou terminologii jsem neznal .

vanok · 02. 10. 2012 23:34

↑ Rumburak:
Pozdravujem,
V texte co som poslal vyssie su odpovede na polozene otazky ( a aj viac) a naviac su tam aj priklady na kazdu situaciu... ozaj maly slovnik staci.

Rumburak · 03. 10. 2012 09:30

↑ vanok:

Ahoj, máš pravdu.
Znalosti francouzštiny i francouzské kultury jsou bohužel u nás v úpadku (což je jistě škoda).

Matematické Fórum

#1 02. 10. 2012 09:00

Silná X slabá matematická indukce

#2 02. 10. 2012 10:13

Re: Silná X slabá matematická indukce

#3 02. 10. 2012 17:51 — Editoval Rumburak (03. 10. 2012 17:00)

Re: Silná X slabá matematická indukce

#4 02. 10. 2012 18:19 — Editoval radekm (02. 10. 2012 18:21)

Re: Silná X slabá matematická indukce

#5 02. 10. 2012 21:44 — Editoval Rumburak (02. 10. 2012 21:46)

Re: Silná X slabá matematická indukce

#6 02. 10. 2012 23:34

Re: Silná X slabá matematická indukce

#7 03. 10. 2012 09:30

Re: Silná X slabá matematická indukce

Zápatí