¿Un principio de inducción matemática para conjuntos parcialmente ordenados con infima?

Question

Recientemente aprendí que hay un análogo útil de la inducción matemática sobre $\mathbb{R}$ (más precisamente, sobre intervalos de la forma $[a,\infty)$ o $[a,b]$ ). Resulta que esta es una idea antigua: se remonta a Khinchin y Perron, pero por alguna razón nunca se ha puesto de moda y por lo tanto se sigue redescubriendo. Un buen artículo reciente es

http://alpha.math.uga.edu/~pete/Kalantari07.pdf

[Como nota al margen, hace dos días di una charla en el Seminario de Posgrado VIGRE de la UGA -esencialmente, un coloquio para estudiantes de posgrado, con charlas que se supone que son accesibles a los estudiantes de primer y segundo año- sobre la inducción sobre los números reales con aplicaciones a pruebas rápidas de esencialmente todos los "teoremas duros" básicos del cálculo de honores / análisis real elemental. Fue un éxito rotundo: los estudiantes disfrutaron de esta nueva forma de inducción y apreciaron la aplicación a pruebas consolidadas de teoremas que, en su memoria reciente, no eran tan rápidos o fáciles de demostrar].

La forma en que me gusta plantear el principio es un poco diferente del enfoque de Kalantari. [De hecho, me confundí con los "axiomas para la inducción" de Kalantari cuando los vi por primera vez y tuve la impresión de que eran erróneos. De hecho I estaba equivocado, y rápidamente respondió a mi correo electrónico sobre el tema, aclarándome y, amablemente, mencionando que otros habían cometido el mismo error]. Esta es mi versión preferida:

Dejemos que $(X,\leq)$ sea un conjunto totalmente ordenado con un elemento mínimo, que podemos llamar también $0$ .

Digamos que $X$ tiene infima si... todo subconjunto no vacío $S$ de $X$ tiene un infimo.

Digamos que $S \subset X$ es un subconjunto inductivo si se cumplen todas las condiciones siguientes:
(POI1) $0 \in S$ .
(POI2) Para todos los $x \in S$ si existe $z \in X$ tal que $x < z$ -- en otras palabras, si $x$ no es un elemento máximo de $X$ -- entonces existe $y > x$ tal que el intervalo $[x,y]$ está contenida en $S$ .
(POI3) Para todos los $x \in X$ , si $[0,x) \subset S$ entonces $x \in S$ .

Por último, decimos que $X$ satisface el principio de inducción ordenada si el único subconjunto inductivo de $X$ es $X$ sí mismo.

Teorema: Para un conjunto totalmente ordenado $X$ con un elemento mínimo, TFAE:
(i) $X$ tiene infima.
(ii) $X$ satisface el principio de inducción ordenada.

La prueba es sencilla. Si se aplica a intervalos semicerrados como los anteriores, se obtiene una inducción real. Además, aplicándolo a un conjunto bien ordenado se recupera la inducción transfinita exactamente como se suele plantear, es decir, con un axioma extra para los "elementos límite", aunque formalmente se podrían combinar (PDI2) y (PDI3) en un solo caso.

Este tema surgió el martes en nuestro sitio hermano math.SE -- alguien preguntó si existía la inducción real -- y yo respondí, oui , como en el caso anterior. Entonces alguien comentó mi respuesta: ¿qué pasa con las generalizaciones a conjuntos parcialmente ordenados?

Existe un conocido principio de inducción sobre conjuntos parcialmente ordenados que satisfacen la condición de cadena descendente o, lo que es lo mismo, en los que todo subconjunto no vacío tiene un mínimo. Esto se llama, por matemáticos de diversas tendencias, inducción bien fundada o inducción noetheriana. (Por lo que veo, debería llamarse Inducción artiniana . ¿Alguien quiere abordar esto? Editar : Me satisface el comentario de Dave Anderson más abajo).

Obsérvese que un conjunto parcialmente ordenado con DCC no necesita tener un elemento mínimo, lo que sí es necesario para la configuración anterior en conjuntos totalmente ordenados. Pero esto no es un gran problema: si $(X,\leq)$ es un poset que satisface DCC, el poset $X_0$ que se obtiene al unir un elemento mínimo $0$ sigue satisfaciendo el DCC, y nada se pierde aquí.

[ Editar Como señala François Dorais, no basta con añadir un mínimo; aún así, un conjunto parcialmente ordenado que satisfaga DCC no tiene por qué tener infimos. Así que lo que estoy preguntando es realmente diferente de la inducción noetheriana].

Después de pensarlo un poco, fui optimista al pensar que debería haber una versión de inducción de conjuntos parcialmente ordenados con un elemento mínimo. Incluso pensé que la definición correcta de subconjunto inductivo debería ser esencialmente la dada anteriormente, con (PDI2) modificada ligeramente a

(POI2'): para cada $x \in S$ y $z \in X$ con $x < z$ existe $y \in (x,z]$ tal que todo el intervalo $[x,y]$ está contenida en $S$ .

Y luego traté de demostrar que cualquier poset con un mínimo y que tenga infimos satisface el principio de inducción ordenada. Y no pude. Finalmente encontré el siguiente contraejemplo: dejemos que $A$ sea un conjunto infinito y $X = 2^A$ sea su conjunto de potencias, parcialmente ordenado por inclusión. Por supuesto $X$ tiene infima: toma la intersección. Sea $S$ sea la colección de todos los subconjuntos finitos de $A$ . Entonces $S$ satisface (PDI1), (PDI2') y (PDI3) pero es propia.

Tampoco se me ocurre alguna pequeña modificación de (PDI2') que evada este ejemplo. Sigo pensando que debería haber algún tipo del principio de inducción en conjuntos parcialmente ordenados con infima, pero no sé qué hacer. ¿Puede alguien enunciar un principio de este tipo que recupere como casos especiales como caso especial el principio de inducción ordenada y el principio de inducción noetheriana ?

Answer 1

Algo muy parecido a las condiciones de François logra la versión deseada del teorema de si y sólo si para las ordenaciones parciales proporcionando una caracterización por inducción de los órdenes parciales completos, al igual que el teorema de Pete caracteriza los órdenes totales completos.

Supongamos que $(P,\lt)$ es un orden parcial. Decimos que es completa si cada subconjunto $A$ tiene un límite superior mínimo $sup(A)$ y un límite inferior mayor $inf(A)$ . Esto implica que $(P,\lt)$ tiene un elemento menor y mayor, y en este caso, es fácil ver que la completitud es equivalente a la afirmación de que todo conjunto tiene un límite inferior mayor (el límite superior menor de un conjunto con límites superiores es el límite inferior mayor de sus límites superiores). Los órdenes parciales completos completos son exactamente los completa entramados .

A los efectos de esta pregunta, definamos que $S\subset P$ es inductivo si ocurre lo siguiente:

• (1) $S$ está cerrado hacia abajo: $y\lt x\in S\to y\in S$ ;
• (2) $S$ no tiene ningún elemento mayor, excepto posiblemente el elemento mayor de $P$ ;
• (3) Si $d=sup(A)$ para algunos $A\subset S$ entonces $d\in S$ .

En (2), por un más grande me refiero a un elemento que es más grande que todos los demás elementos (a diferencia de máximo elemento, un concepto más débil). Las condiciones (2) y (3) son ligeramente más débiles que las condiciones de François. La diferencia en (2) es que ya no suponemos que una condición $x\in S$ puede ampliarse en cualquier dirección, y la diferencia en (3) es que aquí no estamos asumiendo que $P$ es completa, pero sólo que $S$ contiene los supremos de sus subconjuntos, cuando estos supremos existen.

Por último, definir que una orden parcial $(P,\lt)$ tiene inducción de orden parcial si el único conjunto inductivo es todo de $P$ .

Teorema. Para cualquier orden parcial $(P,\lt)$ , los siguientes son equivalentes:

• $(P,\lt)$ está completo.
• $(P,\lt)$ tiene elementos menores y mayores y satisface la inducción de orden parcial.

Prueba. Para la implicación directa, supongamos $(P,\lt)$ es completa. De ello se desprende que $(P,\lt)$ tiene el menor y el mayor elementos, ya que estos son el sup y el inf del conjunto vacío. Supongamos que $S\subset P$ es inductivo. Por (3) sabemos $sup(S)\in S$ , lo que lo convertiría en el mayor elemento de $S$ (2), a menos que $sup(S)$ es mayor en $P$ , en cuyo caso $S=P$ por (1). Así que $(P,\lt)$ tiene una inducción de orden parcial.

A la inversa, supongamos que $(P,\lt)$ tiene el menor y el mayor y satisface la inducción de orden parcial. Queremos demostrar la exhaustividad. Supongamos que $B\subset P$ no es vacío y no tiene el mayor límite inferior. Sea $S$ sea el conjunto de los menores de $B$ . Se cierra hacia abajo, por lo que (1) se mantiene. Como $B$ no tiene un límite inferior mayor, se deduce que $S$ no tiene ningún elemento mayor, por lo que (2) se cumple. Por último, si $A\subset S$ y $sup(A)$ existe en $P$ , entonces sigue siendo un límite inferior de $B$ ya que cada elemento de $B$ es una parte superior límite superior de $A$ y $sup(A)$ es el límite superior mínimo de $A$ . Por lo tanto, (3) se mantiene y así $S$ es inductiva, al contrario que la hecho de que no contiene elementos de $B$ . Así, $B$ debe tener un límite inferior mayor después de todo, y así $(P,\lt)$ es completa. QED

Tenga en cuenta que cuando $(P,\lt)$ es un orden total, entonces estos conceptos se reducen a las condiciones que Pete menciona en la pregunta (añadiendo un elemento menor y mayor si necesario). Por lo tanto, este teorema parece ser la generalización deseada.

(He borrado mi otra respuesta a la pregunta, ya que era basada en un malentendido de la pregunta).

Answer 2

En mi humilde opinión, el principio general debería tener una prueba muy similar al principio original para ser considerado una generalización adecuada. Después de reconstruir una prueba de su principio original, obtuve la siguiente generalización.

Teorema. Dejemos que $X$ sea un poset en el que cada conjunto no vacío tiene un inf. (Nótese que $X$ tiene un elemento mínimo $0$ y que todo conjunto acotado por encima tiene un sup). Si $S \subseteq X$ es tal que:

1. Si $x \in S$ y $y < x$ entonces $y \in S$ .
2. Si $x \in S$ y $x < y$ entonces hay algo de $z \in S$ tal que $x < z \leq y$ .
3. Cada subconjunto de $S$ que está acotado por encima (en $X$ ) tiene su sup en $S$ .

Entonces $S = X$ . (Nótese que 3 implica formalmente que $0 \in S$ desde $0$ es el sup del conjunto vacío).

Esto es ligeramente diferente al principio original, pero se recupera el principio original aplicando el teorema anterior al subconjunto $S' = \{x \in X : [0,x] \subseteq S\}$ en lugar de $S$ .

---

Después de escribir la prueba que tenía en mente, me di cuenta de que la condición 1 no es necesaria.

Prueba del teorema. Supongamos que $y \notin S$ . Sea $x = \sup\{z \in S : z \leq y\}$ . Por 3, $x \in S$ y así $x < y$ . Por 2, hay un $z \in S$ tal que $x < z \leq y$ lo que contradice la definición de $x$ . QED

Answer 3

Esta es una respuesta a la pregunta de Cam.

No, no basé mi charla directamente en el artículo de Kalantari, aunque creo que sería posible hacerlo. En su lugar, escribí algunas notas de la conferencia antes de la misma (y las pulí un poco después, cuando me di cuenta de que estaba en algo). Véase

http://alpha.math.uga.edu/~pete/realinduction.pdf

Este documento no está destinado a ser publicado. Por favor, siéntase libre de utilizarlo como considere oportuno.

Answer 4

Una muy buena generalización de la indexación por un conjunto bien ordenado y el uso de la inducción para demostrar algo es proporcionada por la noción de $\kappa$ -buen árbol para $\kappa$ un cardinal regular (normalmente infinito) ver esta pregunta de MO . Para ver su uso en la teoría de la homotopía, eche un vistazo a la obra de Lurie Teoría de los topos superiores A.1.5, A.2.8 y A.3.3, donde se utiliza para demostrar (indirectamente) que las categorías de funtores (y las categorías de funtores simplificadas) A^C donde A es una categoría modelo combinatoria (resp. combinatoria simplicial) admiten funtores de sustitución fibrantes y cofibrantes (esto se deduce por el argumento del objeto pequeño una vez que demostramos que A^C es en sí misma combinatoria).

La clave aquí es el regularidad del cardenal $\kappa$ lo que nos permite tomar cierres descendentes de $\kappa$ -subconjuntos pequeños con impunidad, así como ampliar subconjuntos hasta que ciertos diagramas conmuten (es decir, dados algunos diagramas que conmutan en el límite, podemos encontrar $k$ -subconjunto pequeño B para el que el diagrama conmuta en el límite de B.