Fandom

Math Wiki

Principiul inducției transfinite

1.029pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Definiţie. Fie (A, \le) \! o mulțime total ordonată. Vom spune că (A, \le) \! este bine ordonată dacă pentru orice submulţime nevidă B din A, există un element b \in B \! cu proprietatea b \le x , \; \forall x \in B. \!

Elementul b \in B \! cu proprietatea b \le x , \; \forall x \in B. \! este numit cel mai mic element sau prim element din B. Orice mulţime (A, \le) \! bine ordonată, are un prim element şi acesta este unic.


Teorema 1 (Principiul inducţiei transfinite). Fie (A, \le) \! o mulţime bine ordonată. Dacă A' este o submulţime din A având proprietăţile:

1^{\circ} A' conţine primul element din A;

2^{\circ} Pentru orice segment A_a \subset A', \! avem a \in A', \!

atunci mulţimea A' coincide cu mulţimea A.

Demonstraţie Să presupunem prin absurd că submulţimea A' din A are proprietăţile 1^{\circ} şi 2^{\circ} din enunţul teoremei dar că A' \neq A. \! Atunci A \setminus A' \! este submulţime nevidă a mulţimii bine ordonate A. Ea are un prim element b care nu se găseşte în A'. Segmentul A_b \! este inclus în A'. După 2^{\circ} rezultă b \in A'. \! Absurd, QED.


Reciproc, avem:

Teorema 2. Fie (A, \le) \! o mulțime total ordonată cu prim element. Dacă singura submulţime A' a lui A ce satisface condiţiile 1^{\circ} şi 2^{\circ} din teorema 1 este A, atunci (A, \le) \! este bine ordonată.

Demonstraţie. Presupunem că B \neq \varnothing \! este o submulţime din A care nu are prim element. Atunci A' = A \setminus B \! este o submulţime a lui A care conţine primul element din A. Dacă A_a \! este un element din A', atunci a \in A'. \! În caz contrar, a ar fi primul element din B. Aplicând principiul inducţiei transfinite, rezultă A'=A. \! Adică A \setminus B=A, \! deci B = \varnothing, \! în contradicţie cu B \neq \varnothing, \! QED.


Aceste teoreme arată că principiul inducţiei trabsfinite este echivalent cu buna ordonare. Vom spune că teoremele care sunt demonstate cu ajutorul acestui principiu, sunt demonstrate "prin recurenţă".

Vezi şi Edit

Also on Fandom

Random Wiki