FANDOM


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