Un conjunto finito siempre tiene un máximo y un mínimo.

Question

Estoy bastante seguro de que esta afirmación es verdadera. Sin embargo, no estoy seguro de cómo demostrarlo. Cualquier sugerencia/idea/respuesta sería apreciada.

Answer 1

Sea $S = \{s_1, \ldots,s_n\}$ un conjunto finito no vacío de tamaño $n > 0$. Demostraremos por inducción en $n \in \mathbb N$ que existen algunos $m,M \in S$ tal que para todo $s \in S$, tenemos que $m \leq s \leq M.

Caso Base: Para $n=1$, tenemos $S = \{s_1\}$, por lo que tomando $m = s_1$ y $M=s_1$ satisface trivialmente la condición requerida.

Hipótesis de Inducción: Supongamos que la afirmación es cierta para $n=k$, donde $k \geq 1$.

Resta probar que la afirmación es verdadera para $n = k+1$. Para ello, elige cualquier conjunto $S$ con $k+1$ elementos, digamos $S = \{s_1 ,\ldots,s_k,s_{k+1}\}$. Ahora, por la hipótesis de inducción, el subconjunto: $$ S' = S \setminus \{s_{k+1}\} = \{s_1 ,\ldots,s_k\} $$ tiene un elemento mínimo y un elemento máximo. Es decir, sabemos que existen algunos $m',M' \in S'$ tal que para todo $s' \in S'$, tenemos que $m' \leq s' \leq M'$. Ahora observa que $s_{k+1}$ debe caer en $1$ de $3$ casos:

Caso 1: Supongamos que $s_{k+1} < m'$. Entonces toma $m = s_{k+1}$ y $M=M'$. Para ver por qué esto funciona, observa que cualquier elemento en $S$ es $s_{k+1}$ o algún $s' \in S'$, y: $$ m = s_{k+1} < m' \leq s' \leq M' = M $$

Caso 2: Supongamos que $m' \leq s_{k+1} \leq M'$. Entonces toma $m = m'$ y $M=M'$. Para ver por qué esto funciona, observa que cualquier elemento en $S$ es $s_{k+1}$ o algún $s' \in S'$, y: $$ m = m' \leq s_{k+1} \leq M' = M $$ $$ m = m' \leq s' \leq M' = M $$

Caso 3: Supongamos que $s_{k+1} > M'$. Entonces toma $m =m'$ y $M=s_{k+1}$. Para ver por qué esto funciona, observa que cualquier elemento en $S$ es $s_{k+1}$ o algún $s' \in S'$, y: $$ m = m' \leq s' \leq M' < s_{k+1} = M $$

Por lo tanto, hemos demostrado que $S$ tiene un elemento mínimo y máximo, como se deseaba.

Answer 2

Sea $F$ un conjunto finito. Si $F$ es $\{x\}$ entonces hemos terminado, ya que trivialmente tenemos $x \geq x$ y por lo tanto $x = \max \{x\}$. Si $F = \{ a_1 ,... a_n \}$. asumimos que son diferentes, de lo contrario volvemos al caso de un solo elemento. Ahora, tomamos $a_1$. Si $a_1$ es mayor que cualquier otro $a_i$ entonces establecemos $a_1 = \max F$ y hemos terminado. Si no, tomamos $a_2$ y repetimos el paso anterior. Continuamos de esta manera de forma inductiva. Eventualmente, obtenemos el máximo.

Answer 3

Uno debe ser cuidadoso sobre el conjunto en el que trabajar, y la definición del orden. Si el conjunto está bien ordenado, entonces la prueba anterior funciona bien. De lo contrario, puede suceder que haya un supremo, pero no un máximo. Podemos, por ejemplo, considerar el orden parcial en el conjunto de matrices de valores reales de $2\times 2$, donde dos matrices $A$ y $B$ son tales que $A\le B$ si y solo si todas las entradas de $B-A$ son no negativas.

Con la relación de orden y conjunto mencionados anteriormente, consideramos el subconjunto $$ E = \left\{ \begin{pmatrix} 1 & 0 \\ 0& 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0& 1 \end{pmatrix} \right\} .$$

Podemos ver que $E$ está acotado superiormente (por ejemplo, por $ \begin{pmatrix} 1 & 0 \\ 0& 1 \end{pmatrix}$), y inferiormente (por ejemplo, por $\begin{pmatrix} 0 & 0 \\ 0& 0 \end{pmatrix}$). Sin embargo, los dos elementos de $E$ no son comparables usando la relación de orden definida, así que ninguno de ellos es el máximo.

Answer 4

Solo diría basado en Suppes, que el uso de la inducción para demostrar esta conjetura plantea la cuestión por las siguientes razones:

1. La minimalidad o maximalidad de los elementos dentro de un conjunto, A, no se puede definir sin especificar una relación de orden, R, en A.
2. Diferentes R's darán diferentes elementos minimales, llamados elementos R-minimales.
3. El conjunto A solo tiene un elemento R-minimal único si todos sus subconjuntos no vacíos tienen elementos R-minimales únicos, R está conectado y R es asimétrico. (es decir, R es un buen orden)
4. Tener un elemento R-minimal único no garantiza un elemento R-maximal único a menos que A sea finito.

El conjunto A es finito si y solo si cada familia no vacía de subconjuntos de A tiene un elemento minimal [ordenado por inclusión estricta '$\subset$']- A. Tarski a través de Suppes

Además, si una familia de subconjuntos, F, tiene un elemento minimal, entonces también debe tener un elemento maximal según el siguiente argumento:

Si F tiene un elemento minimal, entonces construya G a partir de los elementos de F donde z es un elemento de G si y solo si para cierto y en F, z es Unión F - y. Si z es minimal en G, entonces y es maximal en F, y viceversa. Si F no tiene un elemento maximal, entonces G no puede tener un elemento minimal, pero G tiene un elemento minimal, por lo tanto contradicción, y se prueba el teorema.

Answer 5

Supongo que te refieres a un conjunto de números, $S=\{s_1,s_2,\dots,s_n\}$ y $n$ es el tamaño finito, solo deja que

$$ m=\min(s_1,s_2,\dots,s_n) $$ $$ M=\max(s_1,s_2,\dots,s_n) $$ Q.E.D.