¿Un conjunto no bien ordenado en el que se cumple el principio de inducción transfinita?

Question

Un teorema en mi libro de texto dice:

Dejemos que $(A, < )$ sea un conjunto totalmente ordenado. El conjunto A tiene un elemento mínimo y el principio de inducción transfinita se cumple en A si y sólo si A está bien ordenado.

Entiendo por qué se necesita la suposición de que A tiene un elemento mínimo para demostrar la implicación de izquierda a derecha en mi prueba de libro de texto de este teorema. Pero no encuentro un ejemplo de conjunto no bien ordenado donde se cumpla el principio de inducción transfinita... Obviamente, ese conjunto no tiene un mínimo elemento, pero esa ''pista'' no me llevó muy lejos.

Entonces, ¿alguien puede ayudarme?

EDIT: (Debido a Brian M. Scott)

Enunciamos el principio de inducción transfinita como sigue:

Dejemos que $(A, <)$ sea un conjunto totalmente ordenado y $B \subseteq A$ que satisface:

$$ (\forall x \in A) (p_A(x) \subseteq B \implies x \in B) $$

Entonces B = A.

( donde $p_A(x) = \{ a \in A : a < x \}$ )

Answer 1

Usted está planteando el principio como esencialmente $$ (\forall x)[(\forall y < x) P(y) \to P(x)] \to (\forall x) P(x) $$ donde los cuantificadores abarcan un conjunto ordenado $A$ .

Afirmo que si el conjunto no tiene ningún elemento mínimo entonces el principio no se cumple. Tomemos $P(z)$ para ser $z \not = z$ . Arreglar cualquier $x \in A$ . Porque $x$ no es mínimo, hay algo de $y < x$ y $P(y)$ es falso, por lo que $(\forall y < x)P(y)$ es falso. También $P(x)$ es falso. Así, $(\forall x)[(\forall y < x) P(y) \to P(x)]$ es cierto. Pero $P(x)$ es falso para todos los $x$ por lo que el principio da un resultado incorrecto.

Así, por contraposición, si el principio de inducción transfinito se mantiene entonces $A$ tiene un elemento mínimo. La suposición de un elemento mínimo en el teorema mencionado en la pregunta es superflua.

Si el conjunto tuviera un elemento mínimo $x_0$ entonces $(\forall y < x_0) Q(y)$ sería cierto independientemente de lo que $Q$ es. Esa es la forma en que el principio de inducción transfinito es capaz de evitar demostrar afirmaciones idénticamente falsas como la $P$ Yo elegí arriba. La intuición que hay que tener es que cuando miramos elementos no mínimos, la parte "inductiva" del principio de inducción matemática o el principio de inducción transfinita siempre por los enunciados falsos.

Answer 2

Supongo que tu versión del principio de inducción transfinita es algo así:

Si $(\forall y<x)P(y)$ implica $P(x)$ para cada $x\in X$ entonces $(\forall x\in X)P(x)$ .

Si es así, intente tomar $X=\Bbb Z$ . También he incluido una pista protegida por spoiler para una propiedad $P(x)$ que funcione. (Hay muchos.) Pase el ratón para verlo.

Para $P(x)$ puedes probar $x=x+1$ .