"Cualquier poset finito tiene un elemento máximo". ¿Cómo formalizar la prueba que se da?

Question

Para la diversión, estoy leyendo las Matemáticas de La Lógica, y el autor da el siguiente teorema

Teorema. Cualquier finito poset tiene un elemento maximal.

y una prueba de los mismos. Pero, yo no puedo entender cómo formalizar la prueba. Ayuda, alguien? Yo estaba pensando en usar un reductio ad absurdum.

Aquí está la prueba (he cortado un poco de la pelusa, pero su más o menos literal).

Prueba. Deje $X$ ser nuestro finito poset y deje $a_0 \in X$. Vamos a definir una secuencia de elementos $a_n \in X$ tal que $a_n < a_{n+1}$ por cada $n$. Dado $a_n \in X$, hay dos posibilidades. Cualquiera de las $a_n$ es máxima, en cuyo caso hemos terminado, o bien hay algo de $b \in X$ con $a_n < b$. En el último caso, elija $a_{n+1}$ una $b$.

Ahora el argumento en el párrafo anterior no puede dar una secuencia infinita de elementos de $X$. Esto es debido a que $X$ es finito y la secuencia de $a$ es estrictamente creciente, por lo tanto, todos los términos de $a$ son distintos. Por lo tanto, no podemos tener siempre la segunda opción en el párrafo anterior, así que en algún punto de la $a_n$ hemos obtenido será máxima. Es decir, nuestro finito poset tiene un elemento maximal, según sea necesario.

Observación. Estamos permitido el uso de Konig del lexema, ya que esto ya ha sido demostrado.

Answer 1

El dado prueba pasa por alto algunos detalles, pero básicamente completa.

Usted podría utilizar la inducción sobre la cardinalidad de $X$. Si $|X|=1$ no hay nada que demostrar. Así que supongamos $|X|=n+1$, y que el resultado vale para posets tener cardinalidad menos de $n$.

Escoger un elemento de $X$, se $a$; si $a$ es maximal, entonces hemos terminado. De lo contrario, existe al menos un elemento $b$ tal que $a<b$. Considere la posibilidad de $Y=\{x\in X: a<x\}$. A continuación,$Y$, con la inducida por el fin de la relación, es un finito poset y $a\notin Y$, por lo que el $|Y|<|X|$. Por la hipótesis de inducción, $Y$ tiene un elemento maximal $c$. Vamos a demostrar que $c$ también es máxima en $X$. Si $d\in X$ e $c<d$, luego tenemos a $a<c<d$, lo $a<d$ y, por tanto,$d\in Y$, contradiciendo el hecho de que $c$ es máxima en $Y$.

Answer 2

Los conjuntos finitos también permiten construcciones como "elemento superior de una cadena más larga" o "elemento con el mayor número de descendientes".

Answer 3

Deje que$n(x)$ sea la cardinalidad de$\{y \in X / x < y\}$. Como$X$ es finito, los$n(x)$ son números naturales, y hay un$x_0$ tal que$n(x_0)$ es mínimo. Supongamos que$n(x_0)>0$. Luego hay un$y \in X$ tal que$x_0<y$, y luego$n(y)$ es el tamaño de$\{z \in X / y< z\}$, que se incluye estrictamente en$\{z \in X / x_0 < z\}$. Por lo tanto,$n(y) < n(x_0)$, lo que contradice la minimalidad de$n(x_0)$. Por lo tanto,$n(x_0)=0$, lo que significa que$x_0$ fue un elemento máximo.