Antes de los axiomas de Zermelo-Frankel, Russel y Whitehead intentaron axiomatizar la Teoría de Conjuntos y resolver sus paradojas introduciendo los postulados de tipos, pero distaba de ser axiomas sencillos. El sistema de Zermelo-Frankel proporcionó unos axiomas más evidentes.

Ahora introduciremos los axiomas de Zermelo-Frankel de la teoría de conjuntos. A la vez, construiremos parte de la maquinaria matemática necesaria para cuestionar estos axiomas en un sentido matemático más que en un contexto puramente lógico. Esto nos permitirá ver cómo parte de las matemáticas pueden ser construidas desde la teoría de conjuntos. Haremos esto mediante la discusión acerca de la maquinaria que desarrollemos cuidándonos de cualquier argumento circular.

1.   Axioma de Extensión

Iniciaremos nuestra discusión acerca de la Teoría de Conjuntos haciéndonos una pregunta un tanto filosófica: ¿qué significa que dos conjuntos sean iguales? Ahora bien, esto parece trivial y seguro tenemos una respuesta intuitiva. Sin embargo, necesitamos hacer explícita esta percepción mediante un argumento riguroso.

Axioma 1 (El Axioma de Extensión). Sean {A, B} conjuntos. Entonces {A = B} si, y sólo si, contienen los mismos elementos.

Una consecuencia inmediata de esta definición es la proposición

Proposición 2. Se cumple que {\{ a, a \} = \{ a \}} y {\{ a, b \} = \{ b, a \}}.

Demostración. Notar que {x \in \{ a, a \} \iff x \in \{ a \}} para la primera afirmación. La segunda se cumple por el mismo argumento.\Box

Esto quiere decir que los elementos repetidos son ignorados en los conjuntos, y así los conjuntos son colecciones no ordenadas. El Axioma 1 también nos permite garantizar la unicidad de conjuntos.

Ahora veamos la noción de subconjunto:

Definición 3 (Subconjuntos y subconjuntos propios). Sean {A, B} conjuntos. Si {x \in A \implies x \in B}, diremos que {A} es un subconjunto de {B} escribiendo {A \subseteq B} o {B \supseteq A}. Si {A \subseteq B} pero {A \ne B}, escribimos {A \subsetneq B} o {B \supsetneq A} y diremos que {A} es un subconjunto propio de {B}.

Con esta definición, se puede formular el axioma de extensión de la siguiente manera: {A = B \iff A \subseteq B \text{ y } B \subseteq A}.

Proposición 4 (Transitividad). Si {A \subseteq B} y {B \subseteq C}, entonces {A \subseteq C}.

Demostración. Ya que {A \subseteq B}, sabemos que {x \in A \implies x \in B}. Y ya que {B \subseteq C}, {x \in B \implies x \in C}. Así, trivialmente, {x \in A \implies x \in C}.\Box

🙂 Hola a todos.

Durante los últimos cinco meses otras actividades han pasado a ocupar mi tiempo. He decidido ampliar la temática. Estaré escribiendo sobre temas de desarrollo de software impulsado en parte por el trabajo que desempeño por ahora. También sobre otros variados.

Veremos como nos va. 😉

El lenguaje de la Teoría de Conjuntos consta de variable usualmente denotadas por {x}, {X}, {\mho}, {\mathcal M}, entre otros. También tenemos el predicado {\in} de pertenencia para denotar que {x} pertenece a {X} mediante {x \in X}. El predicado {=} de igualdad cuando {x} es igual a {y} denotado {x = y}. Incluimos la lógica de predicados: la negación ({\neg}, no), la conjunción ({\land}, y), la disyunción ({\lor}, o), la implicación ({\implies}) y la equivalencia ({\iff}, sí y sólo si). También, la lógica de cuantificadores: el cuantificador universal ({\forall}, para todo) y el cuantificador existencial ({\exists}, existe). Además, consideraremos los símbolos de ámbito como los paréntesis o corchetes.

Una sentencia estará caracterizada por las reglas siguientes: (1) sean {x, y} variables, de manera que {x \in y} es un sentencia y escribimos {S(x, y) = x \in y}; (2) si {S, T} son sentencias, tenemos que {\neg S}, {S \land T}, {S \lor T}, {S \implies T}, {S \iff T} y {S = T} son también sentencias; y (3) siendo {S(a)} una sentencia en {a}, tenemos que {\forall a [S(a)]} y {\exists a [S(a)]} son sentencias.

Observemos que no hemos sido rigurosos al elaborar estas afirmaciones. Por ejemplo, hemos usado ingenuamente la relación {=} al definir la sentencia {S(x, y)}, aunque bastarán para nuestros propósitos.

En ocasiones seremos breves con el cuantificador universal escribiendo {x \in A} en lugar de {\forall x \in A}. Para evitar ambigüedad, seremos explícitos con el cuantificador existencial.

En la próxima entrega, veremos la relación de los axiomas de Zermelo-Frankel y las matemáticas.

Disculpen mi inactividad. He vuelto con una pequeña serie sobre Teoría de Conjuntos a modo compensación. También habrán algunos cambios que mencionaré en pronta publicación. 🙂

En 1883, Georg Cantor proponía todo conjunto puede ser bien ordenado como una ley del pensamiento. Este Principio de Buen Ordenamiento se mantuvo en el corazón de los números cardinales de Cantor, los mismos que él había construido para investigar los conjuntos infinitos. Sin embargo, el Principio de Buen Ordenamiento se transformó en el problema del Buen Ordenamiento cuando Cantor anduvo buscando una demostración durante una década. En 1908, Ernst Zermelo produjo una solución. Zermelo formuló e hizo uso de una nueva y extremadamente poderosa herramienta matemática, El Axioma de Elección.

Exploraremos los axiomas de Zermelo-Frankel de la Teoría de Conjuntos, probaremos el Lema de Zorn y el Teorema del Buen Ordenamiento, además consideraremos algunas de las consecuencias de El Axioma de Elección.

— Introducción —

Un conjunto Bien Ordenado es un conjunto en el que todo subconjunto alcanza un mínimo. Un conjunto bien ordenado usual es el conjunto de los números naturales. El buen ordenamiento es una propiedad deseable porque tales conjuntos se parecen a los números naturales. Hay cierta esperanza de que podamos trabajar con tales conjuntos de la misma manera que lo hacemos con los números naturales. Hay muchas consecuencias estupendas de las cuales hay dos a continuación: extender el conteo más allá de los números naturales y extender el proceso de inducción matemática.

El Buen Ordenamiento no es una ley del pensamiento trivial como Cantor descubrió. El Teorema del Buen Ordenamiento, todo conjunto puede ser bien ordenado, es un resultado profundo en teoría de conjuntos. Esta es la razón por la que procuraremos un preámbulo sobre la teoría de conjuntos; en particular, la teoría axiomática de conjuntos.

Intuimos sobre los números, la aritmética, el conteo, entre otros. Pero, la idea de la teoría de conjuntos es construir una teoría en la que estas observaciones sean una consecuencia y en el que todas las otras entidades maravillosas puedan ser construidas rigurosamente. Parafraseando esto, podemos decir que la motivación de la teoría de conjuntos fue crear las matemáticas desde algo fundamental e incuestionable.

La primera de estas teoría fue la teoría ingenua de conjuntos en las que los conjuntos fueron considerados como objetos intuitivos. La necesidad de axiomatizar la teoría de conjuntos empezó con siglo veinte, cuando filósofos y matemáticos empezaron a hallar contradicciones en esta teoría de conjuntos; para ilustrarlo, consideremos el problema sugerido por Bertrand Russell en 1903. La Paradoja de Russell es la siguiente: si {\mho} es el conjunto que contiene a todos los conjuntos (el conjunto universal) y {\mathcal M = \{ A \in \mho : A \notin A \}}, ¿se cumple {\mathcal M \in \mathcal M}? Bueno, supongamos que {\mathcal M \in \mathcal M}; entonces tenemos que {\mathcal M \notin \mathcal M}. Si {\mathcal M \notin \mathcal M}, entonces {\mathcal M \in \mathcal M}. Esto es una clara inconsistencia: la existencia de un conjunto universal se dio por sentada en esta teoría. Es problema es grave pues las matemáticas son precisas en la teoría que es construida. La teoría que exploramos es la teoría de conjuntos de Zermelo-Frankel, la teoría en la que el análisis clásico se basa y de hecho la teoría aceptada para definir las matemáticas.

Idealmente, los axiomas deberían ser «verdades inobjetables». No obstante, por la misma naturaleza de los axiomas es siempre debatible. De hecho, ha habido siempre un axioma de la teoría de conjuntos sujeto de severas críticas: El Axioma de Elección. Este axioma puede ser usado para elaborar pruebas no constructivas sobre la existencia de objetos fantásticos, algunos de los cuales son aparentes paradojas. Consideraremos el axioma de la elección a cierto detalle y, de hechom probaremos que es equivalente al Teorema del Buen Ordenamiento.

   Esta publicación es la primera de una serie de ejemplos de optimización con programación lineal en los que dejaré el planteamiento de los ejercicios. Posteriormente desarrollaré la solución usando alguna herramienta que implemente el Método Simplex, por ejemplo.

   Empecemos.

Ejercicio 1. Tenemos un destacamento militar formado por {50} ingenieros, {36} zapadores, {22} fuerzas especiales, y {120} soldados de infantería. Han de transportarse hasta una posición estratégica importante. En la base se dispone de 4 tipos de vehículos, {A}, {B}, {C} y {D}, para el transporte de las tropas. Cada vehículo puede transportar es {10}, {7}, {6} y {9} como se detalla en la siguiente tabla:

\displaystyle  \begin{array}{lcccc} & \text{Ingenieros} & \text{Zapadores} & \text{Fuerzas especiales} & \text{Infantería} \\ \text{A} & 3 & 2 & 1 & 4 \\ \text{B} & 1 & 1 & 2 & 3 \\ \text{C} & 2 & 1 & 2 & 1 \\ \text{D} & 3 & 2 & 3 & 1 \end{array}

   El combustible necesario para que cada vehículo llegue hasta el punto de destino se estima en {160}, {80}, {40} y {120} litros respectivamente. Si queremos ahorrar combustible, ¿cuántos vehículos de cada tipo habrá que utilizar para que el consumo sea el mínimo posible?

   Usaremos {X_i} como variable de decisión para representar el número de vehículos de tipo {i}. Nos queda determinar las restricciones y expresarlas como ecuaciones o inecuaciones dependientes de las variables de decisión.

\displaystyle  \begin{array}{rrcrcrcrcr} \text{Ingenieros}\quad & 3X_A&+&X_B&+&2X_C&+&3X_D&\ge&50 \\ \text{Zapadores}\quad & 2X_A&+&X_B&+&X_C&+&2X_D&\ge&36 \\ \text{Fuerzas especiales}\quad & X_A&+&2X_B&+&2X_C&+&3X_D&\ge&22 \\ \text{Infantería}\quad & 4X_A&+&3X_B&+&X_C&+&X_D&\ge&120 \end{array}

   También se tienen que considerar las restricciones por la naturaleza del problema: {X_i\in\mathbf Z} y {X_i\ge0}.

   Finalmente nos queda determinar la función objetivo:

\displaystyle  \text{Minimizar } 160X_A+80X_B+40X_C+120X_D.

Hola a todos. Volviendo de una temporada de inactividad, leía sobre una duda sobre la aplicabilidad del axioma de elección sobre conjuntos finitos. (Espero retomar el ritmo de publicaciones pronto.) 😉

En la Wikipedia se expone que «informalmente, el axioma de elección dice que dada cualquier colección de contenedores, donde cada uno contiene al menos un objeto, es posible hacer una selección de exactamente un objeto de cada contenedor. En muchos casos dicha selección puede hacerse sin invocar el axioma de elección; en particular, cuando el número de contenedores es finito […]». Hasta aquí uno se pregunta cómo puede realizarse una selección (como la descrita) cuando los contenedores son finitos; incluso, cómo puede realizarse la selección de un contenedor.

Luego se da un ejemplo: […] para cualquier colección (que podría ser infinita) de pares de zapatos, se puede seleccionar el zapato izquierdo de cada par, pero para una colección infinita de pares de calcetines (asumiendo que no tienen una característica distintiva), dicha selección puede obtenerse sólo usando el axioma de elección. ¿Cómo se puede hacer una selección de un calcetín si estos no tienen alguna característica distintiva? ¿Estamos obviando otro axioma?

Vamos a recorrer postulados elementales de elección hasta llegar al Axioma de Elección. Lo que nos permitirá conducirnos en los expuesto por la Wikipedia.

Empezamos fijando uno de los axiomas de la Teoría de Conjuntos.

Axioma 1 (Conjunto vacío). Hay un conjunto {\emptyset} que no contiene ningún elemento, es decir, para cualquier objeto {x} tenemos {x\notin\emptyset}.

Ahora bien, este axioma es suficiente para probar que podemos «elegir» un elementos de un conjunto no vacío:

Lema 2 (Elección simple). Si {X} es un conjunto no vacío, hay un objeto {x} de manera que {x\in X}.

Demostración. Supongamos que no hay ningún objeto {x} que cumpla {x\in X}, es decir, tenemos {x\notin X} para cualquier objeto {x}. Además {x\notin\emptyset} por el Axioma 1. Luego {x\in X} si, y sólo si, {x\in\emptyset} (son equivalentemente falsas) y así {X=\emptyset} por la definición de igualdad de conjuntos; lo que es una contradicción.\Box

Con este lema, podemos ver que, dada una colección de conjuntos no vacíos, podemos elegir un elemento de cada uno y así obtener una colección de objetos seleccionados. Una versión de esta idea se da con la siguiente proposición:

Proposición 3 (Elección finita). Sea {n\ge1} un número natural y, para cada número natural {1\le i\le n}, sea {X_i} un conjunto no vacío. Entonces existe un tupla {n} {(x_i)_{1\le i\le n}} tal que {x_i\in X_i} para todo {1\le i\le n}. En otras palabras, si cada {X_i} no es vacío, el conjunto {\prod_{1\le i\le n}X_i} tampoco es vacío.

Demostración. Procedamos por inducción. Cuando {n=1}, se cumple por el Lema 2. Ahora, sea {X_1,\dotsc,X_{n^+}} una colección de conjuntos no vacíos. Por hipótesis hay una tupla {n} {(x_i)_{1\le i\le n}} tal que {x_i\in X_i} para todo {1\le i\le n}. Además, como {X_{n^+}} no es vacío, hay un {x} tal que {x\in X_{n^+}} por el Lema 2. Si definimos la tupla {n^+} {(y_i)_{1\le i\le n}} fijando {y_i=x_i} cuando {1\le i\le n} e {y_i=x} cuando {i=n^+}, evidentemente tenemos {y_i\in X_i} para todo {1\le i\le n^+}. Esto cierra la inducción.\Box

Como vemos, no ha sido necesario el Axioma de Elección para poder hacer una selección de una colección finita de conjuntos.

Lo que el Axioma de Elección asegura es que la Proposición 3 de elección finita también es verdadera para productos cartesianos infinitos.

Axioma 4 (Elección). Sea {I} un conjunto y, por cada {\alpha\in I}, sea {X_\alpha} un conjunto no vacío. Entonces {\prod_{\alpha\in I}X_\alpha} tampoco es vacío. En otras palabras, hay una función {(x_\alpha)_{\alpha\in I}} que asigna un elemento {x_\alpha\in X_\alpha} a cada {\alpha\in I}.

La idea detrás de este axioma es la misma que la elección finita: dada un colección (posiblemente infinita) de conjuntos no vacíos {X_\alpha}, podemos elegir un elemento simple {x_\alpha} de cada uno, y formar una tupla (posiblemente infinita) {(x_\alpha)_{\alpha\in I}} de todas las elecciones hechas. Por un lado, esto es muy intuitivo en el sentido que aplicamos el Lema 2 una y otra vez. Por otro lado, el hecho de generar elecciones arbitrarias infinitas veces, sin una regla explícita sobre cómo hacerlas, es un tanto desconcertante. De hecho, muchos teoremas afirman la existencia de algún objeto {x} con ciertas propiedades sin manifestar qué objeto es o cómo se construye. No hay un diferencia entre una afirmación de existencia no constructiva y una de existencia constructiva (que puede ser preferible pero no necesario en muchos casos), excepto a un nivel filosófico.

En ocasiones no se necesita toda la capacidad del Axioma de Elección. En su lugar, suele usarse el axioma de elección numerable que es lo mismo que el axioma de elección pero restringida a un conjunto a lo sumo numerable. Por ejemplo,

Proposición 5. Sea {E} un subconjunto no vacío de la recta real con {\sup(E)<\infty} (es decir, {E} está acotado superiormente). Entonces hay una sucesión {(a_n)_{n=1}^\infty} cuyos elementos {a_n} se encuentran en {E}, de manera que {\lim_{n\to\infty}a_n=\sup(E)}.

Demostración. Para cada número natural positivo {n}, {X_n} denota al conjunto

\displaystyle X_n:=\{x\in E:\sup(E)-1/n\le x\le\sup(E)\}.

Ya que {\sup(E)} es la mínima cota superior para {E}, {\sup(E)-1/n} no puede ser una cota superior para {E}, y así {X_n} no es vacío para cada {n}. Usando el axioma de elección (o el axioma de elección numerable), podemos hallar una sucesión {(a_n)_{n=1}^\infty} tal que {a_n\in X_n} para cualquier {n\ge1}. En particular {a_n\in E} para cualquier {n}, y {\sup(E)-1/n\le a_n\le\sup(E)} para cualquier {n}. Luego, tenemos {\lim_{n\to\infty}a_n=\sup(E)} por la prueba del sanguchito. 🙂\Box

Uno puede obtener esta proposición sin el axioma de elección en algunos casos especiales. Por ejemplo, si {E} es un conjunto cerrado, podemos definir {a_n} sin elección mediante {a_n:=\inf(X_n)}.

El axioma de elección tiene otras formulaciones, como que existe una función elección para cualquier colección de conjuntos no vacíos. La siguiente proposición es otra formulación del axioma de elección.

Proposición 6. Sean los conjuntos {X} e {Y}, y sea {P(x,y)} una propiedad perteneciente a los objetos {x\in X} e {y\in Y} de manera que, para cada {x\in X}, hay al menos un {y\in Y} tal que {P(x,y)} es verdadera. Entonces existe una función {f\colon X\to Y} tal que {P(x,f(x))} es verdadera para todo {x\in X}.