5 Principio de inducción. Conjuntos finitos y numerables.

5.1 El principio de inducción

Proposición 5.1 (Propiedad del buen orden de ℕ\displaystyle\mathbb{N}).

Todo subconjunto no vacío de ℕ\displaystyle\mathbb{N} tiene un elemento menor.

Proposición 5.2 (Principio de inducción matemática).

Sea S\displaystyle S un subconjunto de ℕ\displaystyle\mathbb{N} que tenga las dos propiedades:

  1. 1.
    ​

    El numero 1∈S\displaystyle 1\in S

  2. 2.
    ​

    Para toda k∈ℕ\displaystyle k\in\mathbb{N}, si k∈S\displaystyle k\in S, entonces k+1∈S\displaystyle k+1\in S.

Entonces se tiene que S=ℕ\displaystyle S=\mathbb{N}.

El principio de induccion matematica suele exponerse en el contexto de propiedades relativas a numeros naturales.

En este contexto, el principio de induccion matematica puede formularse de la manera siguiente.

Para cada n∈ℕ\displaystyle n\in\mathbb{N}, sea P⁢(n)\displaystyle P(n) una proposicion acerca de n\displaystyle n. Suponer que:

  1. 1.
    ​

    P⁢(1)\displaystyle P(1) es verdadera

  2. 2.
    ​

    Para cualquier k∈ℕ\displaystyle k\in\mathbb{N}, si P⁢(k)\displaystyle P(k) es verdadera, entonces P⁢(k+1)\displaystyle P(k+1) es verdadera.

Entonces P⁢(n)\displaystyle P(n) es verdadera para toda n∈ℕ\displaystyle n\in\mathbb{N}.

5.2 Conjuntos finitos y numerables

Se dice que dos conjuntos A\displaystyle A y B\displaystyle B son equipotentes o coordinables si es posible definir una funcion biyectiva f:A→B\displaystyle f\colon A\to B entre dichos conjuntos. Si un conjunto A\displaystyle A es equipotente con el subconjunto de los numeros naturales {1,2,3,…,n}\displaystyle\{1,2,3,\ldots,n\} se dice que el cardinal de A\displaystyle A es n\displaystyle n y se escribe |A|=n\displaystyle|A|=n. Si A\displaystyle A es equipotente con {1,2,3,…,n}\displaystyle\{1,2,3,\ldots,n\} se dice que A\displaystyle A es finito. Por otra parte, si A\displaystyle A es coordinable con el conjunto ℕ\displaystyle\mathbb{N}, se dice que A\displaystyle A es numerable.

Tambien se podra demostrar que el conjunto ℚ\displaystyle\mathbb{Q} de los numeros racionales es numerable.