¿Podemos expandir el "principio de inducción" a una orden parcial$(X, \leq)$?

Question

Sabemos que cada infinita puede ser hecho bien-le ordenó con un desconocido de la orden. También podemos ampliar el principio de la inducción en cualquier conjunto infinito en el sentido de que puede hacerse bien ordenado. Ahora parcialmente conjunto ordenado no puede ser un conjunto ordenado con respecto a la orden parcial. Vamos a un conjunto parcialmente ordenado $(X, \leq)$ con respecto a este particular el fin de $'\leq'$ y supongamos que este orden parcial $'\leq '$ no hacer el set $X$ bien ordenada.

Mi pregunta es-

Podemos ampliar "principio de inducción" a la parte de el fin de establecer $(X,\leq)$mantener en cuenta que $(X,\leq)$ no está bien ordenado?

Tengo una gran confusión aquí.

Answer 1

La inducción se puede realizar a través de cualquier relación $R$ a través de un conjunto $X$, siempre que la relación está bien fundada: cualquier subconjunto $S \subseteq X$ debe tener un mínimo elemento con respecto a $R$. Un mínimo elemento de $S$ es un elemento $m \in S$ tal que no es $x \in S$ con $x R m$.

Para el total de los pedidos, de estar bien fundado es equivalente a estar bien-le ordenó.

Nota: Asumiendo el axioma de dependiente de la elección (una forma más débil del axioma de elección), uno puede mostrar que una relación está bien fundada, si y sólo si no hay ninguna infinito descendente de la cadena de elementos en $X$ (con respecto a la relación $R$).

Nota 2: El Axioma de Elección es equivalente a decir que todo conjunto puede ser bien ordenado. Así, uno podría, en principio, hacer (transfinito) la inducción a través de cualquier conjunto.

El problema es que el Axioma de Elección no es constructivo, lo que significa que nadie sabe nada acerca de lo que el buen orden dada por el axioma parece. Por lo tanto, es en la práctica imposible el uso de ese bien ordenar.

Answer 2

Ni siquiera podemos hacer inducción sobre un total de un pedido si no es bien ordenado. Como en $\Bbb Q$ o $\Bbb R$ con el estándar de la orden. Así que, en general, un orden parcial es fuera de la cuestión.

Uno podría imponer un orden como requisito en el orden parcial (todos los no-vacío subconjunto de $X$ tiene un mínimo elemento), y entonces es llamado un bien fundado de orden parcial. En ese caso se puede introducir en un orden parcial.

Answer 3

Una forma de ver el principio de inducción es una forma de mostrar que no puede haber contraejemplos a la proposición a ser probada. En general, el conjunto de valores para que una proposición falla puede ser cualquier subconjunto. Así que si usted quiere ser capaz de demostrar una proposición es válida, al establecer que no hay un mínimo de contraejemplos, que es lo que el principio de la fuerte inducción hace, entonces uno necesita un orden con la propiedad de que cada conjunto no vacío tiene un mínimo elemento. Para el total de la compra, que es la propiedad de ser un bien de pedidos. Por parciales de orden, es la propiedad de ser fundada. Así que si quieres emplear un argumento inductivo de la fuerte inducción tipo (mostrando que la validez de una proposición para todos los $y<x$ implica la validez de $x$), entonces no hay nada más débil que la de tener una bien fundada orden parcial permitirá un principio de inducción para ser válido.

Para ver por qué, tome un orden parcial por la cual algunas conjunto no vacío $S$ no tiene un mínimo elemento. Entonces, por la proposición $P$ para que $P(x)$ dice $x\notin S$ es cierto que $\forall x: (\forall y: (y<x\to P(y))\to P(x)$ (porque es equivalente a la negación de la "$S$ tiene un mínimo elemento"), pero la conclusión de que el principio de la inducción, es decir, $\forall x:P(x)$, es falso. Por lo tanto, el fuerte principio de la inducción no es válido en una situación semejante.