Principio de buen orden

Afirmación de que todos los subconjuntos no vacíos de números positivos contienen un elemento mínimo

En matemáticas , el principio de buen orden establece que cada subconjunto no vacío de números enteros no negativos contiene un elemento menor . ^[1] En otras palabras, el conjunto de números enteros no negativos está bien ordenado por su orden "natural" o de "magnitud" en el que precede si y solo si es o la suma de y algún número entero no negativo (otros ordenamientos incluyen el orden ; y ). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle 2,4,6,...}$ ${\displaystyle 1,3,5,...}$

La frase "principio de buen orden" se toma a veces como sinónimo de " teorema de buen orden ". En otras ocasiones se entiende como la proposición de que el conjunto de los números enteros contiene un subconjunto bien ordenado , llamado los números naturales , en el que cada subconjunto no vacío contiene un elemento mínimo. ${\displaystyle \{\ldots ,-2,-1,0,1,2,3,\ldots \}}$

Propiedades

Dependiendo del marco en el que se introduzcan los números naturales, esta propiedad (de segundo orden) del conjunto de los números naturales es un axioma o un teorema demostrable. Por ejemplo:

• En la aritmética de Peano , la aritmética de segundo orden y sistemas relacionados, y de hecho en la mayoría de los tratamientos matemáticos (no necesariamente formales) del principio de buen orden, el principio se deriva del principio de inducción matemática , que se toma como básico.
• Considerando los números naturales como un subconjunto de los números reales, y suponiendo que ya sabemos que los números reales son completos (de nuevo, ya sea como un axioma o un teorema sobre el sistema de números reales), es decir, cada conjunto acotado (desde abajo) tiene un ínfimo, entonces también cada conjunto de números naturales tiene un ínfimo, digamos . Ahora podemos encontrar un entero tal que se encuentre en el intervalo semiabierto , y luego podemos demostrar que debemos tener , y en . ${\displaystyle A}$ ${\displaystyle a^{*}}$ ${\displaystyle n^{*}}$ ${\displaystyle a^{*}}$ ${\displaystyle (n^{*}-1,n^{*}]}$ ${\displaystyle a^{*}=n^{*}}$ ${\displaystyle n^{*}}$ ${\displaystyle A}$
• En la teoría axiomática de conjuntos , los números naturales se definen como el conjunto inductivo más pequeño (es decir, el conjunto que contiene 0 y está cerrado bajo la operación sucesora). Se puede (incluso sin invocar el axioma de regularidad ) demostrar que el conjunto de todos los números naturales tales que " está bien ordenado" es inductivo y, por lo tanto, debe contener todos los números naturales; a partir de esta propiedad se puede concluir que el conjunto de todos los números naturales también está bien ordenado. ${\displaystyle n}$ ${\displaystyle \{0,\ldots ,n\}}$

En el segundo sentido, esta frase se utiliza cuando se recurre a esa proposición con el fin de justificar pruebas que adoptan la siguiente forma: para demostrar que todo número natural pertenece a un conjunto especificado , supóngase lo contrario, lo que implica que el conjunto de contraejemplos no está vacío y, por lo tanto, contiene un contraejemplo más pequeño. Luego, demuestre que para cualquier contraejemplo hay un contraejemplo aún más pequeño, lo que produce una contradicción. Este modo de argumentación es el contrapositivo de la prueba por inducción completa . Se lo conoce con humor como el método del " criminal mínimo " ^{[ cita requerida ]} y es similar en su naturaleza al método de Fermat de " descenso infinito ". ${\displaystyle S}$

Garrett Birkhoff y Saunders Mac Lane escribieron en A Survey of Modern Algebra que esta propiedad, al igual que el axioma del límite superior mínimo para números reales, no es algebraica, es decir, no puede deducirse de las propiedades algebraicas de los números enteros (que forman un dominio integral ordenado ).

Ejemplos de aplicaciones

El principio de buen orden se puede utilizar en las siguientes demostraciones.

Factorización prima

Teorema: Todo número entero mayor que uno puede factorizarse como producto de primos. Este teorema forma parte del Teorema de Factorización Primaria .

Demostración (por el principio de buen orden). Sea el conjunto de todos los números enteros mayores que uno que no se pueden factorizar como producto de primos. Demostramos que está vacío. ${\displaystyle C}$ ${\displaystyle C}$

Supongamos por el bien de la contradicción que no está vacío. Entonces, por el principio de buen ordenamiento, hay un elemento mínimo ; no puede ser primo ya que un número primo en sí mismo se considera un producto de primos de longitud uno. Por la definición de números no primos, tiene factores , donde son números enteros mayores que uno y menores que . Como , no están en ya que es el elemento más pequeño de . Por lo tanto, se pueden factorizar como productos de primos, donde y , lo que significa que , un producto de primos. Esto contradice la suposición de que , por lo que la suposición de que no está vacío debe ser falsa. ^[2] ${\displaystyle C}$ ${\displaystyle n\in C}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a,b}$ ${\displaystyle a,b}$ ${\displaystyle n}$ ${\displaystyle a,b<n}$ ${\displaystyle C}$ ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle a,b}$ ${\displaystyle a=p_{1}p_{2}...p_{k}}$ ${\displaystyle b=q_{1}q_{2}...q_{l}}$ ${\displaystyle n=p_{1}p_{2}...p_{k}\cdot q_{1}q_{2}...q_{l}}$ ${\displaystyle n\in C}$ ${\displaystyle C}$

Suma de números enteros

Teorema: para todos los números enteros positivos . ${\displaystyle 1+2+3+...+n={\frac {n(n+1)}{2}}}$ ${\displaystyle n}$

Demostración . Supongamos, por razones de contradicción, que el teorema anterior es falso. Entonces, existe un conjunto no vacío de números enteros positivos . Por el principio de buen orden, tiene un elemento mínimo tal que cuando , la ecuación es falsa, pero verdadera para todos los números enteros positivos menores que . La ecuación es verdadera para , por lo que ; es un número entero positivo menor que , por lo que la ecuación se cumple para ya que no está en . Por lo tanto, lo que demuestra que la ecuación se cumple para , una contradicción. Por lo tanto, la ecuación debe cumplirse para todos los números enteros positivos. ^[2] ${\displaystyle C=\{n\in \mathbb {N} \mid 1+2+3+...+n\neq {\frac {n(n+1)}{2}}\}}$ ${\displaystyle C}$ ${\displaystyle c}$ ${\displaystyle n=c}$ ${\displaystyle c}$ ${\displaystyle n=1}$ ${\displaystyle c>1}$ ${\displaystyle c-1}$ ${\displaystyle c}$ ${\displaystyle c-1}$ ${\displaystyle C}$ $${\displaystyle {\begin{aligned}1+2+3+...+(c-1)&={\frac {(c-1)c}{2}}\\1+2+3+...+(c-1)+c&={\frac {(c-1)c}{2}}+c\\&={\frac {c^{2}-c}{2}}+{\frac {2c}{2}}\\&={\frac {c^{2}+c}{2}}\\&={\frac {c(c+1)}{2}}\end{aligned}}}$$ ${\displaystyle c}$

Referencias

1. Apostol, Tom (1976). Introducción a la teoría analítica de números . Nueva York: Springer-Verlag. pp. 13. ISBN. 0-387-90163-9.
2. Lehman, Eric; Meyer, Albert R; Leighton, F Tom. Matemáticas para la informática (PDF) . Consultado el 2 de mayo de 2023 .