Saltar al contenido principal
LibreTexts Español

2.2: Números Naturales. Inducción

  • Page ID
    114129
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    El elemento 1 se introdujo en Axioma 4 (b). Dado que la adición también se asume conocida, podemos usarla para definir, paso a paso, los elementos

    \[2=1+1,3=2+1,4=3+1, \text{ etc.}\]

    Si este proceso se continúa indefinidamente, obtenemos lo que se llama el conjunto\(N\) de todos los elementos naturales en el campo dado\(F .\) En particular, los elementos naturales de\(E^{1}\) se denominan números naturales. Tenga en cuenta que

    \[(\forall n \in N) \quad n+1 \in N\]

    *Un enfoque más preciso de los elementos naturales es el siguiente. \(A\)subconjunto\(S\) de un campo\(F\) se dice que es inductivo iff

    \[\begin{align} (i)& \hskip 4pt 1 \in S \text{ and } \\ (ii)& \hskip 4pt (\forall x \in S) \hskip 4pt x+1 \in S \end{align}\]

    Tales subconjuntos ciertamente existen; por ejemplo, todo el campo\(F\) es inductivo ya que

    \[1 \in F \text{ and } (\forall x \in F) \hskip 4pt x+1 \in F.\]

    Definir\(N\) como la intersección de todos los conjuntos inductivos en\(F\).

    Teorema\(\PageIndex{1}\)

    El conjunto\(N\) así definido es inductivo en sí mismo. De hecho, es el subconjunto inductivo “más pequeño” de\(F\) (es decir, contenido en cualquier otro subconjunto de este tipo).

    Prueba

    Tenemos que demostrar que

    \[\begin{align} (i)& \hskip 4pt 1 \in N, \text{ and } \\ (ii)& \hskip 4pt (\forall x \in N) \hskip 4pt x+1 \in N. \end{align}\]

    Ahora, por definición, la unidad 1 está en cada conjunto inductivo; de ahí que también pertenezca a la intersección de tales conjuntos, es decir, a\(N .\) Así\(1 \in N,\) como se reivindica.

    A continuación, tomar cualquier\(x \in N .\) Entonces, por nuestra definición de\(N, x\) está en cada conjunto inductivo\(S ;\) así, por propiedad\((i i)\) de tales conjuntos, también\(x+1\) está en cada uno de tales\(S\); de ahí\(x+1\) está en la intersección de todos los conjuntos inductivos, es decir,

    \[x+1 \in N\]

    y así\(N\) es inductivo, en efecto.

    Finalmente, por definición,\(N\) es la parte común de todos esos conjuntos y por lo tanto contenida en cada uno. \(\square\)

    Para aplicaciones, el Teorema 1 generalmente se expresa de la siguiente manera.

    Teorema\(\PageIndex{1'}\)

    (primera ley de inducción). Una proposición\(P(n)\) que involucra una retención\(n\) natural para todos\(n \in N\) en un campo\(F\) si

    \[\begin{align} (i)& \text{ it holds for } n=1,\text{ i.e., } P(1) \text{ is true; and } \\ (ii)& \text{ whenever } P(n) \text{ holds for } n=m, \text{ it holds for } n=m+1, \text{ i.e., } \end{align} \]

    \[P(m) \Longrightarrow P(m+1).\]

    Prueba

    \(S\)Sea el conjunto de todos aquellos\(n \in N\) para los que\(P(n)\) es cierto,

    \[S=\{n \in N | P(n)\}\]

    Tenemos que demostrar que en realidad cada uno\(n \in N\) está en\(S,\) i.e.,\(N \subseteq S\)

    Primero, mostramos que\(S\) es inductivo.

    En efecto, por suposición\((\mathrm{i}), P(1)\) es cierto; entonces 1\(\in S\).

    Siguiente, vamos\(x \in S .\) Esto significa que eso\(P(x)\) es cierto. Por supuesto (ii), sin embargo, esto implica\(P(x+1),\) i.e.,\(x+1 \in S .\) Así

    \[ 1 \in S \text{ and } (\forall x \in S) \hskip 4pt x+1 \in S\]

    \(S\)es inductivo.

    Entonces, por el Teorema 1 (segunda cláusula),\(N \subseteq S,\) y todo está probado. \(\square\)

    Este teorema se utiliza para probar diversas propiedades de\(N\) "por inducción”.

    Ejemplo\(\PageIndex{1}\)

    (a) Si\(m, n \in N,\) entonces también\(m+n \in N\) y\(m n \in N\).

    Para probar la primera propiedad, arreglar cualquier\(m \in N .\) Let\(P(n)\) mean

    \[m+n \in N \quad(n \in N)\]

    Entonces

    (i)\(P(1)\) es cierto, pues como\(m \in N,\) la definición de\(N\) rendimientos\(m+1 \in N\), es decir,\(P(1)\).

    ii)\(P(k) \Rightarrow P(k+1)\) para\(k \in N .\) Indeed,

    \[\begin{align} P(k) \Rightarrow& m+k \in N \Rightarrow(m+k)+1 \in N\ \\ \Rightarrow& m+(k+1) \in N \Rightarrow P(k+1) \end{align}\]

    Así, por Teorema\(1^{\prime}, P(n)\) sostiene para todos\(n ;\) es decir,

    \((\forall n \in N) \quad m+n \in N\)

    para cualquier\(m \in N\).

    Para probar lo mismo para dejar\(m n,\) que\(P(n)\) signifique

    \(m n \in N \quad(n \in N)\)

    y proceder de manera similar.

    b) Si\(n \in N,\) entonces\(n-1=0\) o\(n-1 \in N\).

    Para una prueba inductiva,\(P(n)\) digamos

    \[n-1=0 \text{ or } n-1 \in N \quad(n \in N)\]

    Después proceder como en (a).

    (c) En un campo ordenado, todos los naturales son\(\geq 1\).

    En efecto,\(P(n)\) digamos que

    \[n \geq 1 \quad(n \in N).\]

    Entonces

    (i)\(P(1)\) mantiene desde\(1=1\)
    (ii)\(P(m) \Rightarrow P(m+1)\) para\(m \in N,\) desde

    \[P(m) \Rightarrow m \geq 1 \Rightarrow(m+1)>1 \Rightarrow P(m+1)\]

    Así el teorema\(1^{\prime}\) arroja el resultado.

    (d) En un campo ordenado,\(m, n \in N\) e\(m>n\) implica\(m-n \in N\)
    Para una prueba inductiva, fijar cualquiera\(m \in N\) y dejar que\(P(n)\) signifique

    \[m-n \leq 0 \text{ or } m-n \in N \quad(n \in N).\]

    Uso (b).

    (e) En un campo ordenado,\(m, n \in N\) e\(m<n+1\) implica\(m \leq n\)
    For, por\((\mathrm{d}), m>n\) implicaría de\(m-n \in N,\) ahí\(m-n \geq 1,\) o\(m \geq n+1,\) contrario a\(m<n+1\).

    Nuestro siguiente teorema afirma la llamada propiedad bien ordenada de\(N\).

    Teorema\(\PageIndex{2}\) (well-ordering of N)

    En un campo ordenado, cada conjunto no vacío\(A \subseteq N\) tiene un miembro mínimo (es decir, uno que no exceda ningún otro elemento de\(A )\).

    Prueba

    Lo siguiente es solo un esquema de una prueba:

    Dada\(\emptyset \neq A \subseteq N,\) dejó\(P(n)\) ser la proposición “Cualquier subconjunto de elementos\(A\) que contienen\(\leq n\) tiene un miembro menor”\((n \in N) .\) Use Teorema\(1^{\prime}\) y Ejemplo (e). \(\square\)

    Este teorema arroja una nueva forma de la ley de inducción.

    Teorema\(\PageIndex{2'}\) (second induction law)

    Una propuesta\(P(n)\) es para todos\(n \in N\)

    (i')\(P(1)\) sostiene y
    (ii') siempre que se\(P(n)\) mantenga para todos los naturales menos de algunos\(m \in N,\) entonces\(P(n)\)
    también se sostiene para\(n=m\).

    Prueba

    Asumir\(\left(\mathrm{i}^{\prime}\right)\) y\(\left(\mathrm{ii}^{\prime}\right) .\) Buscando una contradicción, supongamos que hay algunos los\(n \in N(\) llaman “malos”) para lo cual\(P(n)\) falla. Entonces estos naturales “malos” forman un subconjunto no vacío de\(N,\) llamarlo\(A\).

    Por teorema\(2, A\) tiene menos miembro\(m .\) Así\(m\) es el menos natural para el que\(P(n)\) falla. De ello se deduce que todos\(n\) menos que\(m\) satisfacer\(P(n) .\) Pero entonces, por nuestra suposición (ii'),\(P(n)\) también sostiene para\(n=m,\) lo cual es imposible porque, por construcción,\(m\) es “malo” (es en\(A ) .\) Esta contradicción demuestra que no hay naturales “malos”. Así todo está probado. \(\square\)

    Nota 1: Todos los argumentos precedentes se mantienen también si, en nuestra definición de\(N\) y todas las formulaciones, la unidad 1 es reemplazada por 0 o por alguna\(k( \pm k \in N)\). Entonces, sin embargo, se deben cambiar las conclusiones para decir que se\(P(n)\) mantiene para todos los enteros\(n \geq k\) (en lugar de “n\ geq 1 “). Entonces decimos que “la inducción empieza con\(k .\)

    También se aplica una ley de inducción análoga a las definiciones de conceptos\(C(n)\).

    \(A\)noción\(C(n)\) que implica un natural\(n\) se considera como definido para cada uno\(n \in N\)\(\left(i n E^{1}\right)\) si

    (i)\(i t\) se define para\(n=1\) y

    (ii) se da alguna regla que expresa\(C(n+1)\) en términos de\(C(1), \ldots, C(n)\).

    (La nota 1 también se aplica aquí.)

    \(C(n)\)en sí no necesita ser un número; puede ser de naturaleza bastante general.

    Adoptaremos este principio como una especie de axioma lógico, sin pruebas (aunque se pueda probar de manera similar a Teoremas\(1^{\prime}\) y\(2^{\prime} ) .\) La idea intuitiva subyacente es un proceso “paso a paso” - primero, definimos\(C(1) ;\) luego, como\(C(1)\) se sabe, podemos usarlo para definir\(C(2) ;\) siguiente, una vez que se conocen ambos, podemos utilizarlos para definir\(C(3) ;\) y así sucesivamente, ad infinitum. Las definiciones basadas en ese principio se denominan inductivas o recursivas. Los siguientes ejemplos son importantes.

    Ejemplo\(\PageIndex{1}\) (continued)

    (f) Para cualquier elemento\(x\) de un campo, definimos su\(n^{th}\) poder\(x^{n}\) y su\(n\) - múltiplo\(n x\) por

    i)\(x^{1}=1 x=x\)
    ii)\(x^{n+1}=x^{n} x\) (respectivamente,\((n+1) x=n x+x )\).

    Podemos pensarlo como una definición paso a paso:

    \[x^{1}=x, x^{2}=x^{1} x, x^{3}=x^{2} x, \text{ etc.}\]

    (g) Para cada número natural\(n,\) definimos su factorial\(n !\) por

    \[1 !=1,(n+1) !=n !(n+1);\]

    ej.\(, 2 !=1 !(2)=2,3 !=2 !(3)=6,\) etc. También definimos\(0 !=1\).

    h) La suma y el producto de n elementos de campo\(x_{1}, x_{2}, \dots, x_{n},\) denotados por

    \[\sum_{k=1}^{n} x_{k} \text{ and } \prod_{k=1}^{n} x_{k}\]

    o

    \[x_{1}+x_{2}+\cdots+x_{n} \text{ and } x_{1} x_{2} \cdots x_{n}, \text{ respectively}\]

    se definen recursivamente.

    Las sumas se definen por

    \[ \begin{align} (i)& \hskip 4pt \sum_{k=1}^{1} x_{k}=x_{1} \\ (ii)& \hskip 4pt \sum_{k=1}^{n+1} x_{k}=\left(\sum_{k=1}^{n} x_{k}\right)+x_{n+1}, n=1,2, \ldots \end{align}\]

    Así

    \[x_{1}+x_{2}+x_{3}=\left(x_{1}+x_{2}\right)+x_{3}\]

    \[x_{1}+x_{2}+x_{3}+x_{4}=\left(x_{1}+x_{2}+x_{3}\right)+x_{4}, \text{ etc.}\]

    Los productos están definidos por

    \[ \begin{align}(i)& \hskip 4pt \prod_{k=1}^{1} x_{k}=x_{1} \\ (ii)& \hskip 4pt \prod_{k=1}^{n+1} x_{k}=\left(\prod_{k=1}^{n} x_{k}\right) \cdot x_{n+1} \end{align}\]

    (i) Dado cualquier objeto\(x_{1}, x_{2}, \dots, x_{n}, \ldots,\) de la n-tupla ordenada

    \[\left(x_{1}, x_{2}, \ldots, x_{n}\right)\]

    se define inductivamente por

    (i)\(\left(x_{1}\right)=x_{1}\) (es decir, la “tupla única” ordenada\(\left(x_{1}\right)\) es\(x_{1}\) en sí misma\()\) y

    ii)\(\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\left(\left(x_{1}, \ldots, x_{n}\right), x_{n+1}\right),\) es decir, la\((n+1)-\) tupla ordenada es un par\(\left(y, x_{n+1}\right)\) en el que el primer término\(y\) es en sí mismo una\(n\) tupla ordenada,\(\left(x_{1}, \ldots, x_{n}\right) ;\) por ejemplo,

    \[\left(x_{1}, x_{2}, x_{3}\right)=\left(\left(x_{1}, x_{2}\right), x_{3}\right), \text{ etc.}\]


    This page titled 2.2: Números Naturales. Inducción is shared under a CC BY 3.0 license and was authored, remixed, and/or curated by Elias Zakon (The Trilla Group (support by Saylor Foundation)) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.