4.1: Ordenamientos de bienestar

Última actualización
Guardar como PDF

Page ID: 118577

Bob Dumas and John E. McCarthy
University of Washington and Washington University in St. Louis

\( \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}}\)

En este capítulo discutimos el principio de inducción matemática. Tenga en cuenta que la palabra inducción tiene un significado diferente en matemáticas que en el resto de la ciencia. El principio de inducción matemática depende de la estructura de orden de los números naturales, y nos da una técnica poderosa para probar afirmaciones matemáticas universales.

DEFINICIÓN. Bien ordenado Let\(X\) ser un conjunto, y\(\preceq\) un orden lineal en\(X\). Decimos que\(X\) está bien ordenado con respecto a\(\preceq\) (o\(\preceq\) es un wellordering de\(X\)) si cada subconjunto no vacío de\(X\) tiene un elemento mínimo con respecto a\(\preceq\). Es decir, para cualquier subconjunto no vacío\(Y\) de\(X\)\[(\exists a \in Y)(\forall y \in Y) a \preceq y .\] En general, los ordenamientos lineales no necesitan ser ordenamientos bien. El ordenamiento adecuado es una propiedad universal: un conjunto\(X\) con un orden\(\preceq\) está bien ordenado si cada subconjunto no vacío de\(X\) tiene un elemento mínimo con respecto a\(\preceq\). Si hay algún subconjunto no vacío que no tenga un elemento mínimo, entonces\(\preceq\) no se ordena bien\(X\).

EJEMPLO 4.1. \(\mathbb{Z}\)no está bien ordenado por\(\leq\). Los enteros no tienen un elemento mínimo, lo que basta para demostrar que no\(\mathbb{Z}\) está bien ordenado por\(\leq\).

EJEMPLO 4.2. Vamos\(X=\{x \in \mathbb{R} \mid x \geq 2\}\). Let\(\leq\) be the usual order on\(\mathbb{R} . X\) is linealmente ordenado por\(\leq\), pero no\(X\) es bien ordenado por\(\leq\). En este ejemplo,\(X\) tiene un elemento mínimo, pero cualquier intervalo abierto contenido en no\(X\) podrá tener un elemento mínimo. Las propiedades clave del orden\(\mathbb{N}\) son que está bien ordenado y cada elemento de\(\mathbb{N}\), excepto 0, es el sucesor de un número natural:

PRINCIPIO DE BIENESTAR PARA LOS NUMEROS NATURALES: El conjunto\(\mathbb{N}\) está bien ordenado\(\leq\)

PROPIEDAD SUCESORA PARA LOS NÚMEROS NATURALES: Si\(n \in \mathbb{N}\) y\(n \neq 0\), entonces hay\(m \in \mathbb{N}\) tal que\(n=m+1\).

Si uno acepta una comprensión intuitiva de los números naturales, estos principios son más o menos obvios. En efecto, dejemos\(Y\) ser cualquier subconjunto no vacío de\(\mathbb{N}\). Como no está vacío, hay algunos\(m\) adentro\(Y\). Ahora, considere cada uno de los números\(0,1,2, \ldots, m\) finitamente muchos a su vez. Si\(0 \in Y\), entonces 0 es el elemento menor. Si 0 no está en\(Y\), proceda a 1. Si esto está en\(Y\), debe ser el elemento menor; de lo contrario proceder a 2. Continúa de esta manera, y encontrarás algún número menor o igual que\(m\) ese es el menor elemento de\(Y\).

Este argumento, aunque convincente, sí se basa en el hecho de que tenemos una idea de lo que\(\mathbb{N}\) “es”. Si queremos definir\(\mathbb{N}\) en términos de operaciones de conjunto, como hacemos en el Capítulo 8, esencialmente tenemos que incluir como axioma el principio bien ordenado para los números naturales.