1  Preliminares

En este capítulo, repasamos los conceptos previos que el lector debe conocer para poder afrontar con garantías un curso de Estructuras algebraicas.

1.1 Teoría de conjuntos

En el corazón de las matemáticas, en la base misma sobre la que se erige gran parte del edificio lógico, encontramos la noción fundamental de conjunto. Un conjunto, en su esencia más simple, es una colección bien definida de objetos, que llamamos elementos. Aunque esta idea pueda parecer trivial a primera vista, su poder radica en su asombrosa generalidad y en la capacidad de formalizar la idea de “agrupar” entidades, ya sean números, letras, ideas abstractas o cualquier otra cosa que podamos imaginar. Los conjuntos son los ladrillos básicos con los que construimos estructuras matemáticas más complejas, desde los sistemas numéricos hasta los espacios abstractos, y su estudio constituye el punto de partida de la teoría de conjuntos, una rama esencial de las matemáticas modernas.

La relación primordial que define la interacción entre conjuntos y elementos es la pertenencia. Decimos que un objeto pertenece a un conjunto si está incluido dentro de la colección que define el conjunto. Esta relación, simbolizada por el signo \(\in\), es binaria: se da entre un elemento y un conjunto. Así, escribimos \(x \in A\) para indicar que el elemento \(x\) pertenece al conjunto \(A\), y \(x \notin A\) para indicar que \(x\) no pertenece a \(A\). La pertenencia es una relación fundamental, ya que define la esencia misma de un conjunto: un conjunto está completamente determinado por sus elementos. Dos conjuntos son iguales si y solo si tienen exactamente los mismos elementos.

Definición 1.1  

• Un conjunto es una colección bien definida de objetos.
• Los objetos que componen un conjunto se denominan elementos o miembros del conjunto.
• La relación de pertenencia se denota por \(\in\). Escribimos \(x \in A\) para indicar que \(x\) es un elemento del conjunto \(A\), y \(x \notin A\) para indicar que \(x\) no es un elemento de \(A\).

Los conjuntos pueden definirse de diversas maneras. Una forma común es la extensión, enumerando explícitamente todos sus elementos, encerrados entre llaves. Por ejemplo, \(A = \{1, 2, 3\}\) define el conjunto \(A\) cuyos elementos son los números 1, 2 y 3. Otra forma es la comprensión, especificando una propiedad que caracteriza a los elementos del conjunto. Por ejemplo, \(B = \{x \in \mathbb{N} \mid x \text{ es par}\}\) define el conjunto \(B\) de todos los números naturales pares. Esta notación se lee como “el conjunto de todos los \(x\) que pertenecen a los números naturales \(\mathbb{N}\) tales que \(x\) es par”.

Dentro del universo de los conjuntos, existen algunos conjuntos especiales que juegan un papel fundamental por su ubicuidad y propiedades particulares. Entre ellos destacan el conjunto vacío y el conjunto universal.

Definición 1.2  

• El conjunto vacío, denotado por \(\varnothing\) o \(\{\}\), es el conjunto que no contiene ningún elemento. Es único, y es subconjunto de cualquier otro conjunto.

• El conjunto universal, denotado por \(U\) (o a veces \(\mathcal{U}\) o \(E\)), es un conjunto que contiene a todos los elementos del contexto o universo de discurso considerado. El conjunto universal no es único, y depende del contexto en el que se esté trabajando.

El conjunto vacío puede parecer un concepto abstracto y poco útil a primera vista, pero su introducción es crucial para la coherencia y completitud de la teoría de conjuntos. Piensa en él como el “cero” de los conjuntos: así como el cero es esencial en la aritmética, el conjunto vacío lo es en la teoría de conjuntos. Por ejemplo, si consideramos el conjunto de los números naturales pares mayores que 5 y menores que 4, este conjunto es vacío, ya que no existe ningún número natural que cumpla ambas condiciones simultáneamente.

El conjunto universal, por otro lado, actúa como el “contenedor” de todos los conjuntos que nos interesan en un contexto dado. Su naturaleza depende del problema que estemos abordando. Si trabajamos con números naturales, el conjunto universal podría ser \(\mathbb{N}\). Si trabajamos con números reales, podría ser \(\mathbb{R}\). En lógica proposicional, el conjunto universal podría ser el conjunto de todas las proposiciones posibles. El conjunto universal nos proporciona un marco de referencia para definir operaciones como el complemento de un conjunto.

Una de las mayores fortalezas de la teoría de conjuntos reside en la posibilidad de combinar y manipular conjuntos mediante operaciones. Estas operaciones nos permiten construir nuevos conjuntos a partir de conjuntos dados, explorando las relaciones entre ellos y desvelando patrones y estructuras. Las operaciones básicas con conjuntos son la unión, la intersección, la diferencia y el complemento.

Definición 1.3 Sean \(A\) y \(B\) dos subconjuntos de un conjunto universal \(U\).

• La unión de \(A\) y \(B\), denotada por \(A \cup B\), es el conjunto que contiene todos los elementos que pertenecen a \(A\) o a \(B\) (o a ambos). Formalmente, \(A \cup B = \{x \in U \mid x \in A \text{ o } x \in B\}\).

• La intersección de \(A\) y \(B\), denotada por \(A \cap B\), es el conjunto que contiene todos los elementos que pertenecen tanto a \(A\) como a \(B\). Formalmente, \(A \cap B = \{x \in U \mid x \in A \text{ y } x \in B\}\).

• La diferencia de \(A\) y \(B\), denotada por \(A \setminus B\) o \(A - B\), es el conjunto que contiene todos los elementos que pertenecen a \(A\) pero no pertenecen a \(B\). Formalmente, \(A \setminus B = \{x \in U \mid x \in A \text{ y } x \notin B\}\).

• El complementario o complemento de \(A\) (respecto al conjunto universal \(U\)), denotado por \(A^c\) o \(\overline{A}\) o \(A'\), es el conjunto que contiene todos los elementos del conjunto universal \(U\) que no pertenecen a \(A\). Formalmente, \(A^c = \{x \in U \mid x \notin A\} = U \setminus A\).

La unión de conjuntos corresponde a la idea de “juntar” o “combinar” los elementos de dos o más conjuntos en uno solo. Si pensamos en conjuntos como colecciones de objetos, la unión sería como reunir todos los objetos en una única colección, sin repetir los que puedan estar presentes en más de un conjunto. Por ejemplo, si \(A = \{1, 2, 3\}\) y \(B = \{3, 4, 5\}\), entonces \(A \cup B = \{1, 2, 3, 4, 5\}\).

La intersección, por otro lado, representa los elementos “comunes” a dos o más conjuntos. Es decir, la intersección contiene aquellos elementos que están presentes en todos los conjuntos que se intersectan. Siguiendo con el ejemplo anterior, \(A \cap B = \{3\}\), ya que el único elemento que pertenece tanto a \(A\) como a \(B\) es el número 3.

La diferencia nos permite “restar” elementos de un conjunto a otro. \(A \setminus B\) contiene los elementos que están en \(A\) pero no en \(B\). En nuestro ejemplo, \(A \setminus B = \{1, 2\}\), ya que 1 y 2 están en \(A\) pero no en \(B\). Notemos que la diferencia no es simétrica, en general \(A \setminus B \neq B \setminus A\). En este caso, \(B \setminus A = \{4, 5\}\).

El complemento es una operación unaria que se aplica a un solo conjunto, y siempre se define con respecto a un conjunto universal \(U\). El complemento de \(A\) contiene todos los elementos de \(U\) que “faltan” en \(A\). Si consideramos \(U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) y \(A = \{1, 2, 3\}\), entonces \(A^c = \{4, 5, 6, 7, 8, 9, 10\}\).

Estas operaciones con conjuntos no son arbitrarias, sino que obedecen a una serie de propiedades algebraicas que facilitan su manipulación y simplificación de expresiones. Estas propiedades son análogas a las propiedades de las operaciones aritméticas (suma y producto) y de las operaciones lógicas (conjunción, disyunción, negación), lo que subraya la profunda conexión entre la teoría de conjuntos, la lógica y el álgebra.

Teorema 1.1 Sean \(A\), \(B\) y \(C\) subconjuntos de un conjunto universal \(U\). Se cumplen las siguientes propiedades:

• Conmutatividad:
  • \(A \cup B = B \cup A\)
  • \(A \cap B = B \cap A\)
• Asociatividad:
  • \((A \cup B) \cup C = A \cup (B \cup C)\)
  • \((A \cap B) \cap C = A \cap (B \cap C)\)
• Distributividad:
  • \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
  • \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
• Idempotencia:
  • \(A \cup A = A\)
  • \(A \cap A = A\)
• Identidad:
  • \(A \cup \varnothing = A\)
  • \(A \cap U = A\)
  • \(A \cup U = U\)
  • \(A \cap \varnothing = \varnothing\)
• Complemento:
  • \(A \cup A^c = U\)
  • \(A \cap A^c = \varnothing\)
  • \((A^c)^c = A\)
  • \(\varnothing^c = U\)
  • \(U^c = \varnothing\)
• Leyes de De Morgan:
  • \((A \cup B)^c = A^c \cap B^c\)
  • \((A \cap B)^c = A^c \cup B^c\)
• Leyes de absorción:
  • \(A \cup (A \cap B) = A\)
  • \(A \cap (A \cup B) = A\)

Estas propiedades pueden demostrarse formalmente utilizando las definiciones de las operaciones de conjuntos y las reglas de la lógica proposicional. También pueden visualizarse intuitivamente mediante Diagramas de Venn, una herramienta gráfica muy útil para representar conjuntos y sus relaciones.

Los Diagramas de Venn son representaciones visuales de conjuntos mediante círculos (u otras formas cerradas) dentro de un rectángulo que representa el conjunto universal \(U\). Cada círculo representa un conjunto, y la posición relativa de los círculos muestra las posibles relaciones de intersección y unión entre ellos. La región dentro de un círculo representa los elementos que pertenecen al conjunto, mientras que la región fuera del círculo (pero dentro del rectángulo \(U\)) representa los elementos que no pertenecen al conjunto (su complemento).

Los Diagramas de Venn son especialmente útiles para:

• Visualizar las operaciones con conjuntos: La unión de dos conjuntos se representa sombreando la región que cubre ambos círculos. La intersección se representa sombreando la región donde se superponen los círculos. La diferencia \(A \setminus B\) se representa sombreando la parte de \(A\) que no está superpuesta con \(B\). El complemento \(A^c\) se representa sombreando la región fuera del círculo de \(A\) dentro del rectángulo \(U\).

• Verificar propiedades de las operaciones: Las propiedades algebraicas de las operaciones con conjuntos, como las leyes de De Morgan o la distributividad, pueden verificarse visualmente mediante Diagramas de Venn, sombreando las regiones correspondientes a cada lado de la igualdad y comprobando si coinciden.

• Resolver problemas de conjuntos: Los Diagramas de Venn pueden utilizarse para resolver problemas que involucran conjuntos, como determinar cardinalidades de uniones e intersecciones, o analizar relaciones de inclusión y exclusión.

1.1.1 Relaciones

Imagina por un momento el mundo que te rodea: personas que son amigas, números que son mayores que otros, conjuntos que se contienen mutuamente, tareas que deben preceder a otras. En cada uno de estos escenarios, y en muchísimos más, subyace la idea fundamental de una relación, un vínculo que especifica cómo interactúan o se asocian dos elementos. Las relaciones binarias son la formalización matemática de esta noción intuitiva de conexión, proporcionando un lenguaje preciso y muy potente para describir y analizar patrones de interrelación en cualquier dominio imaginable.

Definición 1.4 Una relación binaria \(\mathcal{R}\) definida en un conjunto \(A\) es un subconjunto del producto cartesiano \(A \times A\), es decir, \(\mathcal{R} \subseteq A \times A\).

Si \((a, b) \in \mathcal{R}\), decimos que \(a\) está relacionado con \(b\) mediante \(\mathcal{R}\), y lo denotamos por \(a \mathcal{R} b\). En caso contrario, si \((a, b) \notin \mathcal{R}\), decimos que \(a\) no está relacionado con \(b\) mediante \(\mathcal{R}\).

Esta definición, aparentemente sencilla, encierra una enorme generalidad. Si consideramos el caso particular donde \(A = B\), obtenemos las relaciones binarias en un conjunto, que son el foco de atención en muchas áreas de las matemáticas.

La ubicuidad de las relaciones binarias en matemáticas es asombrosa. Desde las operaciones aritméticas básicas como la suma y la multiplicación, que en esencia son relaciones entre tríos de números (por ejemplo, \(a + b = c\) define una relación entre \(a\), \(b\) y \(c\)), hasta conceptos más abstractos como la equivalencia y el orden, las relaciones binarias son la columna vertebral de numerosas teorías y construcciones matemáticas. La relación “ser igual a”, simbolizada por \(=\), es quizás la relación binaria más fundamental, estableciendo un vínculo de identidad entre objetos matemáticos. La relación “ser menor que”, \(<\), ordena los números y nos permite compararlos. La relación “ser congruente módulo \(n\)” (de la que hablaremos más adelante, en Sección 1.3) clasifica los enteros en categorías basadas en su resto al dividir por \(n\). Incluso la noción de función puede reinterpretarse bajo la lente de las relaciones binarias, como un tipo especial de relación que asocia a cada elemento de un conjunto de partida a lo sumo un elemento de un conjunto de llegada.

Algunas relaciones binarias notables que se dan en diversos contextos matemáticos incluyen:

• Relación de inclusión (\(\subseteq\)) entre conjuntos: Dados dos conjuntos \(A\) y \(B\), decimos que \(A \subseteq B\) si todo elemento de \(A\) es también elemento de \(B\). Esta relación se define en el conjunto potencia de cualquier conjunto \(S\), \(\mathcal{P}(S)\).

• Relación de divisibilidad (\(\mathbin{|}\)) entre números enteros: Dados dos números enteros \(a\) y \(b\), decimos que \(a \mathbin{|} b\) si existe un entero \(k\) tal que \(b = k \cdot a\). Esta relación se define en el conjunto de los números enteros \(\mathbb{Z}\) (o en subconjuntos como los números naturales \(\mathbb{N}\)).

• Relación de orden habitual (\(\leq\)) entre números: Dados dos números reales \(x\) e \(y\), decimos que \(x \leq y\) si \(x\) es menor o igual que \(y\). Esta relación se define en los conjuntos numéricos \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\).

• Relaciones geométricas: En geometría, el paralelismo (\(\parallel\)) y la perpendicularidad (\(\perp\)) entre rectas en el plano son ejemplos de relaciones binarias. Dadas dos rectas \(r\) y \(s\), podemos decir que \(r \parallel s\) (son paralelas) o \(r \perp s\) (son perpendiculares).

Propiedades de las relaciones binarias

Las relaciones binarias pueden satisfacer diversas propiedades que las clasifican y les otorgan características específicas. A continuación, recordamos las propiedades más relevantes en el estudio de las relaciones de orden.

Sea \(\mathcal{R}\) una relación binaria definida en un conjunto \(A\).

Reflexividad: \(\mathcal{R}\) es reflexiva si para todo \(a\in A\), se cumple que \(a \mathcal{R} a\).

Ejemplo 1.1 La relación “\(\leq\)” en \(\mathbb{R}\) es reflexiva, ya que para todo \(x \in \mathbb{R}\), \(x \leq x\).

La relación de divisibilidad en \(\mathbb{Z}^+\) también es reflexiva, ya que todo número natural se divide a sí mismo.

La relación entre rectas en el plano “ser perpendicular a” no es reflexiva (una recta no es perpendicular a sí misma).

Simetría: \(\mathcal{R}\) es simétrica si para todo \(a, b \in A\), se cumple que si \(a \mathcal{R} b\), entonces \(b \mathcal{R} a\).

Ejemplo 1.2 La relación “ser paralelo” (\(\parallel\)) entre rectas es simétrica, ya que si la recta \(r\) es paralela a la recta \(s\), entonces \(s\) es paralela a \(r\).

La relación “ser menor estrictamente” (\(<\)) dentro de los números reales no es simétrica. Por ejemplo, \(2<3\) pero \(3\not< 2\).

Antisimetría: \(\mathcal{R}\) es antisimétrica si para todo \(a, b \in A\), se cumple que si \(a \mathcal{R} b\) y \(b \mathcal{R} a\), entonces \(a = b\).

Ejemplo 1.3 La relación “\(\leq\)” en \(\mathbb{R}\) es antisimétrica, ya que si \(x \leq y\) e \(y \leq x\), entonces \(x = y\).

La relación de inclusión “\(\subseteq\)” entre conjuntos también es antisimétrica, ya que si \(A \subseteq B\) y \(B \subseteq A\), entonces \(A = B\).

La relación \(\mathcal R\) entre conjuntos “tener el mismo número de elementos” no es antisimétrica: los conjuntos \(L = \{a, b, c\}\) y \(N = \{1, 2, 3\}\) verifican la relación en ambos sentidos (\(L\mathcal R N\) y \(N\mathcal R L\)), pero, evidentemente, \(L\neq N\).

Transitividad: \(\mathcal{R}\) es transitiva si para todo \(a, b, c \in A\), se cumple que si \(a \mathcal{R} b\) y \(b \mathcal{R} c\), entonces \(a \mathcal{R} c\).

Ejemplo 1.4 La relación “\(\leq\)” en \(\mathbb{R}\) es transitiva, ya que si \(x \leq y\) e \(y \leq z\), entonces \(x \leq z\).

La relación de divisibilidad en \(\mathbb{Z}^+\) es también transitiva, ya que si \(a \mathbin{|} b\) y \(b \mathbin{|} c\), entonces \(a \mathbin{|} c\).

Conexión: \(\mathcal{R}\) es conexa (o total) si para todo \(a, b \in A\), se cumple que o bien \(a \mathcal{R} b\), o bien \(b \mathcal{R} a\) (o ambas). Es decir, cualesquiera dos elementos de \(A\) son comparables mediante la relación \(\mathcal{R}\).

Ejemplo 1.5 La relación “\(\leq\)” en \(\mathbb{R}\) es conexa, ya que para cualesquiera dos números reales \(x, y\), o bien \(x \leq y\), o bien \(y \leq x\).

La relación de divisibilidad en \(\mathbb{Z}^+\) no es conexa, ya que, por ejemplo, \(2 \mathbin{\not|} 3\) y \(3 \mathbin{\not|} 2\).

El estudio sistemático de las relaciones binarias nos permite identificar propiedades comunes, clasificar diferentes tipos de relaciones y desarrollar herramientas generales para manipularlas y comprender sus implicaciones. Preguntas como “¿es simétrica esta relación?”, “¿es transitiva?”, “¿define un orden?” nos llevan a profundizar en la estructura subyacente de las relaciones y a desentrañar patrones ocultos.

Dependiendo de las propiedades que una relación verifique, recibirá un nombre especial. Las relaciones más usadas dentro del álgebra son las relaciones de orden y de equivalencia.

Las relaciones de orden son un tipo especial de relación binaria que formaliza la idea de comparación y ordenación dentro de un conjunto. Existen dos tipos principales: las relaciones de orden parcial y las relaciones de orden total.

Definición 1.5 Sea \(\mathcal{R}\) una relación binaria definida sobre un conjunto no vacío \(A\).

• Se dice que \(\mathcal{R}\) es una relación de orden parcial si \(\mathcal{R}\) es reflexiva, antisimétrica y transitiva. En este caso, el par \((A,\mathcal{R})\) se denomina conjunto parcialmente ordenado (poset, por sus siglas en inglés).

• Si \(\mathcal{R}\) es una relación de orden parcial y, además, es conexa, se dice que \(\mathcal{R}\) es una relación de orden total (o lineal). En este caso, el par \((A,\mathcal{R})\) se denomina conjunto totalmente ordenado (o conjunto linealmente ordenado o cadena).

Las relaciones de orden, que serán el objeto central del Capítulo 2, nos proporcionan el marco conceptual para formalizar la idea de jerarquía, precedencia y comparación, abriendo la puerta a un mundo rico en aplicaciones y resultados teóricos. Desde la organización de datos hasta la optimización de algoritmos, las relaciones de orden son una herramienta indispensable en la caja de herramientas del matemático y del científico de la computación.

Las relaciones de equivalencia, por otro lado, representan una de las herramientas más potentes y ubicuas en matemáticas, permitiéndonos agrupar objetos en “familias” o “clases” basadas en alguna propiedad compartida. Imagina que tienes una colección de formas geométricas: círculos, cuadrados, triángulos, etc. Podrías clasificarlas según su color, su tamaño, o su forma. Si eliges la forma como criterio, agruparás todos los círculos juntos, todos los cuadrados juntos, y así sucesivamente. Esta idea de clasificación por características comunes es la esencia de las relaciones de equivalencia. En lugar de considerar objetos individuales aislados, las relaciones de equivalencia nos invitan a pensar en términos de categorías o clases, simplificando la complejidad y revelando estructuras subyacentes.

Definición 1.6 Sea \(\mathcal{R}\) una relación binaria definida en un conjunto \(A\). Se dice que \(\mathcal{R}\) es una relación de equivalencia si cumple las siguientes propiedades:

• Reflexiva: Para todo \(a \in A\), \(a \mathcal{R} a\).
• Simétrica: Para todo \(a, b \in A\), si \(a \mathcal{R} b\), entonces \(b \mathcal{R} a\).
• Transitiva: Para todo \(a, b, c \in A\), si \(a \mathcal{R} b\) y \(b \mathcal{R} c\), entonces \(a \mathcal{R} c\).

La reflexividad asegura que todo elemento está relacionado consigo mismo, estableciendo una “auto-pertenencia” a su clase. La simetría garantiza que la relación es “bidireccional”: si \(a\) está relacionado con \(b\), entonces \(b\) también está relacionado con \(a\). La transitividad, quizás la propiedad más crucial, establece la “herencia” de la relación: si \(a\) está relacionado con \(b\), y \(b\) está relacionado con \(c\), entonces \(a\) también está relacionado con \(c\). Estas tres propiedades, trabajando en armonía, son las que confieren a las relaciones de equivalencia su capacidad única para generar particiones.

Las relaciones de equivalencia abundan en matemáticas, proporcionando herramientas esenciales en diversas áreas.

Ejemplo 1.6  

• Igualdad: La relación de igualdad (=) en cualquier conjunto \(A\) es una relación de equivalencia trivial. Es reflexiva (\(a = a\)), simétrica (si \(a = b\), entonces \(b = a\)) y transitiva (si \(a = b\) y \(b = c\), entonces \(a = c\)). En este caso, cada elemento está relacionado únicamente consigo mismo.

• Equivalencia de fracciones: En el conjunto de pares \(\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})\), definimos la relación \((a, b) \sim (c, d)\) si y solo si \(ad = bc\). Esta relación define la equivalencia entre fracciones \(\frac{a}{b} = \frac{c}{d}\).

• Semejanza de triángulos: En el conjunto de todos los triángulos planos, la relación “ser semejante a” es una relación de equivalencia. Es reflexiva (todo triángulo es semejante a sí mismo), simétrica (si el triángulo \(T_1\) es semejante a \(T_2\), entonces \(T_2\) es semejante a \(T_1\)) y transitiva (si \(T_1\) es semejante a \(T_2\) y \(T_2\) es semejante a \(T_3\), entonces \(T_1\) es semejante a \(T_3\)).

Ejercicio 1.1 Demuestra que la relación \(\sim\) que define la equivalencia entre fraccionaes es realmente una relación de equivalencia.

Ejercicio 1.2 Define formalmente la semejanza de dos triángulos \(ABC\) y \(A'B'C'\), y demuestra detalladamente que es una relación de equivalencia.

Definición 1.7 Sea \(\mathcal R\) una relación de equivalencia dentro de un conjunto \(A\), y sea \(a\in A\). Denominamos clase de equivalencia de \(a\) al conjunto \[ [a]_{\mathcal R} = \{x\in A\mid a\mathcal R x\}. \] De la misma forma, el conjunto de todas las clases de equivalencia se denomina conjunto cociente: \[ A/\mathcal{R} = \{ [a]_{\mathcal{R}} \mid a \in A \} \]

La propiedad más destacada de una relación de equivalencia es su capacidad para dividir un conjunto en clases de equivalencia disjuntas, formando lo que se conoce como una partición. Una partición de un conjunto \(A\) es una colección de subconjuntos no vacíos de \(A\) que son mutuamente disjuntos y cuya unión es todo \(A\). Cada relación de equivalencia induce naturalmente una partición, donde cada “pieza” de la partición es un conjunto de elementos equivalentes entre sí.

Definición 1.8 Una partición de un conjunto \(A\) es una colección \(\mathcal{P} = \{C_i\}_{i \in I}\) de subconjuntos de \(A\) que satisfacen las siguientes condiciones:

• No vacíos: Para todo \(i \in I\), \(C_i \neq \varnothing\).
• Disjuntos dos a dos: Para todo \(i, j \in I\) con \(i \neq j\), \(C_i \cap C_j = \varnothing\).
• Cubren \(A\): \(\bigcup_{i \in I} C_i = A\).

El siguiente teorema fundamental establece la conexión biunívoca entre relaciones de equivalencia y particiones: toda relación de equivalencia induce una partición, y recíprocamente, toda partición proviene de una relación de equivalencia. Este resultado subraya la profunda dualidad entre estos dos conceptos, mostrando que son esencialmente dos caras de la misma moneda.

Teorema 1.2  

• (Relación \(\Rightarrow\) Partición): Si \(\mathcal{R}\) es una relación de equivalencia en un conjunto \(A\), entonces el conjunto cociente \(A/\mathcal{R}\) es una partición de \(A\).

• (Partición \(\Rightarrow\) Relación): Si \(\mathcal{P} = \{C_i\}_{i \in I}\) es una partición de un conjunto \(A\), entonces la relación \(\mathcal{R}_{\mathcal{P}}\) definida por \(a \mathcal{R}_{\mathcal{P}} b\) si y solo si existe algún \(i \in I\) tal que \(a, b \in C_i\), es una relación de equivalencia en \(A\). Además, las clases de equivalencia de \(\mathcal{R}_{\mathcal{P}}\) son precisamente los conjuntos en la partición \(\mathcal{P}\).

Las relaciones de equivalencia nos permiten “identificar” elementos equivalentes, tratándolos como si fueran el mismo objeto en un nuevo nivel de abstracción, lo que simplifica el análisis y revela propiedades esenciales. Desde la construcción de los números racionales a partir de pares de enteros, hasta la definición de espacios vectoriales cociente en álgebra lineal, las relaciones de equivalencia son un pilar fundamental en la construcción y comprensión de las matemáticas modernas.

Ejemplo 1.7 Como ejemplo ilustrativo de la potencia de las relaciones de equivalencia, consideremos la construcción formal del conjunto de los números racionales \(\mathbb{Q}\) a partir de los números enteros \(\mathbb{Z}\). Intuitivamente, un número racional es una “fracción” \(\frac{a}{b}\), donde \(a\) y \(b\) son enteros y \(b \neq 0\). Sin embargo, diferentes fracciones pueden representar el mismo número racional, por ejemplo, \(\frac{1}{2} = \frac{2}{4} = \frac{3}{6}\), etc. Para construir \(\mathbb{Q}\) de manera rigurosa, utilizamos relaciones de equivalencia para identificar estas fracciones equivalentes como representantes del mismo número racional.

Comenzamos definiendo el conjunto \(A = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})\), que consiste en todos los pares ordenados \((a, b)\) donde \(a\) es un entero y \(b\) es un entero no nulo. Cada par \((a, b)\) podemos pensar que representa formalmente la fracción \(\frac{a}{b}\). Ahora, definimos la relación \(\sim\) en \(A\) como en el Ejemplo 1.6: \[ (a, b) \sim (c, d) \quad \text{si y solo si} \quad ad = bc. \]

Como se habrá demostrado en el Ejercicio 1.1, esta relación \(\sim\) es una relación de equivalencia en \(A\).

Dado que \(\sim\) es una relación de equivalencia en \(A\), induce una partición de \(A\) en clases de equivalencia. Cada clase de equivalencia \([(a, b)]_{\sim} = \{ (c, d) \in A \mid (c, d) \sim (a, b) \}\) contiene todos los pares que representan la misma “fracción” que \(\frac{a}{b}\).

Definimos formalmente el conjunto de los números racionales \(\mathbb{Q}\) como el conjunto cociente de \(A\) por \(\sim\): \[ \mathbb{Q} = A / \sim = (\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})) / \sim = \{ [(a, b)]_{\sim} \mid (a, b) \in A \}. \]

Cada número racional \(q \in \mathbb{Q}\) es, por definición, una clase de equivalencia de pares de enteros. Por ejemplo, el número racional “un medio”, que denotamos usualmente como \(\frac{1}{2}\), se define formalmente como la clase de equivalencia: \[ \frac{1}{2} = [(1, 2)]_{\sim} = \{ (1, 2), (2, 4), (3, 6), (-1, -2), (-2, -4), \dots \}. \]

Para operar con los números racionales así construidos, definimos las operaciones de suma y producto en el conjunto cociente \(\mathbb{Q}\) a partir de las operaciones en \(\mathbb{Z}\):

• Suma: \([(a, b)]_{\sim} + [(c, d)]_{\sim} = [(ad + bc, bd)]_{\sim}\).
• Producto: \([(a, b)]_{\sim} \cdot [(c, d)]_{\sim} = [(ac, bd)]_{\sim}\).

Es crucial verificar que estas operaciones están bien definidas, es decir, que el resultado no depende de los representantes elegidos para las clases de equivalencia. Una vez verificada la buena definición, se puede demostrar que con estas operaciones, \(\mathbb{Q}\) se convierte en un cuerpo (como veremos en el Capítulo 3), que extiende las propiedades aritméticas de los números enteros \(\mathbb{Z}\).

Esta construcción formal de los números racionales a través de relaciones de equivalencia ilustra cómo este concepto matemático abstracto permite construir nuevos objetos matemáticos a partir de otros más básicos, formalizando nociones intuitivas y resolviendo ambigüedades. En este caso, las relaciones de equivalencia nos permiten tratar las fracciones equivalentes como un único objeto matemático, el número racional, proporcionando una base sólida para la aritmética racional.

Ejercicio 1.3 Demuestra que las operaciones suma y producto de números racionales (definidos como las clases de equivalencia en el ejemplo anterior) están bien definidas. Ayuda: Por ejemplo, para la suma, si elegimos otros representantes \((a', b') \in [(a, b)]_{\sim}\) y \((c', d') \in [(c, d)]_{\sim}\), debemos asegurarnos de que \([(a'd' + b'c', b'd')]_{\sim} = [(ad + bc, bd)]_{\sim}\).

1.1.2 Aplicaciones

En el entramado de las matemáticas, las aplicaciones, también conocidas como funciones, se erigen como uno de los conceptos más centrales y versátiles. Si las relaciones binarias actúan como los hilos que conectan objetos, las aplicaciones son transformaciones que toman elementos de un conjunto de partida y los envían, de manera precisa y unívoca, a elementos de un conjunto de llegada. Desde las funciones más elementales que aprendemos en la escuela, como \(f(x) = x^2\) o \(g(x) = \sin(x)\), hasta las transformaciones más abstractas que encontramos en ramas avanzadas como el análisis funcional o la topología, las aplicaciones son herramientas omnipresentes para modelar dependencias, procesos y transformaciones en el mundo matemático y más allá. En esencia, una aplicación encapsula la idea de asignación o correspondencia entre conjuntos, proporcionando un mecanismo fundamental para establecer conexiones y estudiar las propiedades de estas correspondencias.

Definición 1.9 Sean \(A\) y \(B\) dos conjuntos. Una aplicación (o función) de \(A\) en \(B\) es una relación \(f \subseteq A \times B\) tal que para todo \(x \in A\), existe un único \(y \in B\) con \((x, y) \in f\). Escribimos \(f \colon A \to B\) para denotar una aplicación de dominio \(A\) y codominio \(B\).

• El conjunto \(A\) se denomina dominio de \(f\).
• El conjunto \(B\) se denomina codominio de \(f\).
• Para cada \(x \in A\), el único elemento \(y \in B\) tal que \((x, y) \in f\) se denota por \(f(x)\), y se llama imagen de \(x\) por \(f\).
• La imagen de \(f\) (o rango de \(f\)) es el conjunto de todas las imágenes de los elementos de \(A\): \[ \mathop{\mathrm{Im}}(f) = f(A) = \{ y \in B \mid \exists x \in A \text{ con } f(x) = y \} \subseteq B. \]

Para especificar una aplicación, es necesario definir su dominio, su codominio y la regla de asignación que determina la imagen de cada elemento del dominio. La regla de asignación puede expresarse mediante una fórmula, una descripción verbal, un algoritmo o cualquier otro método que defina de manera unívoca la imagen de cada elemento.

Ejemplo 1.8  

• Función identidad: Sea \(A\) un conjunto cualquiera. La función identidad en \(A\), denotada por \(\mathop{\mathrm{id}}_A \colon A \to A\), se define por \(\mathop{\mathrm{id}}_A(x) = x\) para todo \(x \in A\). El dominio y el codominio son ambos \(A\), y la imagen es también \(A\).

• Función constante: Sean \(A\) y \(B\) conjuntos, y sea \(b_0 \in B\) un elemento fijo de \(B\). La función constante \(f \colon A \to B\) con valor \(b_0\) se define por \(f(x) = b_0\) para todo \(x \in A\). El dominio es \(A\), el codominio es \(B\), y la imagen es el conjunto unitario \(\{b_0\}\) (o vacío si \(A\) es vacío).

• Función cuadrática: La función \(f \colon \mathbb{R} \to \mathbb{R}\) definida por \(f(x) = x^2\) es una aplicación de los números reales en los números reales. El dominio y el codominio son \(\mathbb{R}\). La imagen es el conjunto de los números reales no negativos, \(\mathop{\mathrm{Im}}(f) = [0, +\infty) = \{ y \in \mathbb{R} \mid y \geq 0 \} \subsetneq \mathbb{R}\).

• Función sucesor en los naturales: La función \(s \colon \mathbb{N} \to \mathbb{N}\) definida por \(s(n) = n + 1\) es una aplicación de los números naturales en los números naturales. El dominio y el codominio son \(\mathbb{N}\). La imagen es el conjunto de los números naturales mayores que 1, \(\mathop{\mathrm{Im}}(s) = \{ 1, 2, 3, \dots \} = \mathbb{N} \setminus \{0\} \subsetneq \mathbb{N}\).

• Proyección en el primer componente: Dados conjuntos \(A\) y \(B\), la proyección en el primer componente \(\pi_1 \colon A \times B \to A\) se define por \(\pi_1(x, y) = x\) para todo \((x, y) \in A \times B\). El dominio es el producto cartesiano \(A \times B\), el codominio es \(A\), y la imagen es \(A\) (siempre que \(B \neq \varnothing\)).

Dentro de la vasta familia de aplicaciones, algunas poseen propiedades adicionales que las hacen especialmente relevantes en diversos contextos. Recordamos ahora las definiciones de aplicación inyectiva y aplicación sobreyectiva, que clasifican las aplicaciones según cómo relacionan los elementos del dominio y el codominio.

Definición 1.10 Sean \(A\) y \(B\) dos conjuntos, y sea \(f \colon A\to B\) una aplicación.

• \(f\) se dice inyectiva si elementos distintos del dominio tienen imágenes distintas en el codominio. Formalmente: \[ \text{Para todo } x, y \in A, \quad f(x) = f(y) \quad \Longrightarrow \quad x = y. \] Equivalentemente, \(f\) es inyectiva si para todo \(x, y \in A\), con \(x \neq y\), se cumple \(f(x) \neq f(y)\).

• \(f\) se dice sobreyectiva (o exhaustiva) si todo elemento del codominio es imagen de al menos un elemento del dominio. Formalmente: \[ \text{Para todo } y \in B, \quad \text{existe } x\in A \quad \text{tal que} \quad f(x) = y. \] Equivalentemente, \(f\) es sobreyectiva si la imagen de \(f\) coincide con el codominio, es decir, \(\mathop{\mathrm{Im}}(f) = B\).

• \(f\) se dice biyectiva si es inyectiva y sobreyectiva.

Las aplicaciones inyectivas “preservan la distinción” entre elementos del dominio, mapeando elementos diferentes a imágenes diferentes. Las aplicaciones sobreyectivas “cubren” todo el codominio, asegurando que cada elemento del codominio sea alcanzado por al menos un elemento del dominio. Las aplicaciones biyectivas combinan ambas propiedades, estableciendo una correspondencia “uno a uno” entre el dominio y el codominio.

Ejemplo 1.9  

• Función identidad \(\mathop{\mathrm{id}}_A \colon A \to A\) es biyectiva para cualquier conjunto \(A\). Es inyectiva: si \(\mathop{\mathrm{id}}_A(x) = \mathop{\mathrm{id}}_A(y)\), entonces \(x = y\). Es sobreyectiva: para todo \(y \in A\), existe \(x = y \in A\) tal que \(\mathop{\mathrm{id}}_A(x) = y\).

• Función constante \(f \colon \mathbb{R} \to \mathbb{R}\) definida por \(f(x) = 2\) no es inyectiva ni sobreyectiva. No es inyectiva ya que \(f(1) = f(2) = 2\) pero \(1 \neq 2\). No es sobreyectiva ya que no existe ningún \(x \in \mathbb{R}\) tal que \(f(x) = 3\) (por ejemplo).

• Función cuadrática \(f \colon \mathbb{R} \to \mathbb{R}\) definida por \(f(x) = x^2\) no es inyectiva ni sobreyectiva. No es inyectiva ya que \(f(2) = f(-2) = 4\) pero \(2 \neq -2\). No es sobreyectiva ya que no existe ningún \(x \in \mathbb{R}\) tal que \(f(x) = -1\) (por ejemplo). Sin embargo, si restringimos el codominio a la imagen, la función \(g \colon \mathbb{R} \to [0, +\infty)\) definida por \(g(x) = x^2\) no es inyectiva pero sí sobreyectiva. Si restringimos el dominio a los números no negativos, la función \(h \colon [0, +\infty) \to \mathbb{R}\) definida por \(h(x) = x^2\) es inyectiva pero no sobreyectiva. Finalmente, si restringimos tanto el dominio como el codominio, la función \(k \colon [0, +\infty) \to [0, +\infty)\) definida por \(k(x) = x^2\) es biyectiva.

• Función sucesor en los naturales \(s \colon \mathbb{N} \to \mathbb{N}\) definida por \(s(n) = n + 1\) es inyectiva pero no sobreyectiva. Es inyectiva: si \(s(n) = s(m)\), entonces \(n + 1 = m + 1\), luego \(n = m\). No es sobreyectiva ya que no existe ningún \(n \in \mathbb{N}\) tal que \(s(n) = 0\) (por ejemplo). Sin embargo, si consideramos la función \(s' \colon \mathbb{N} \to \mathbb{N} \setminus \{0\}\) definida por \(s'(n) = n + 1\), entonces \(s'\) es biyectiva.

• Función lineal \(l \colon \mathbb{R} \to \mathbb{R}\) definida por \(l(x) = ax + b\), con \(a,b\in\mathbb R\), \(a\neq 0\), es biyectiva. Es inyectiva: si \(l(x) = l(y)\), entonces \(ax + b = ay + b\), luego \(ax = ay\), y \(x = y\) (pues \(a\neq 0\)). Es sobreyectiva: para todo \(y \in \mathbb{R}\), existe \(x = \frac{y - b}{a} \in \mathbb{R}\) tal que \(l(x) = a(\frac{y - b}{a}) + b = y - b + b = y\).

Las propiedades de inyectividad, sobreyectividad y biyectividad son fundamentales en el estudio de las aplicaciones, y están relacionadas con la existencia de ciertas funciones “inversas” o “recíprocas”. En particular, las aplicaciones biyectivas son precisamente aquellas que admiten una función inversa.

Definición 1.11 Sea \(f \colon A \to B\) una aplicación biyectiva. La función inversa de \(f\), denotada por \(f^{-1} \colon B \to A\), es la aplicación que asigna a cada \(y \in B\) el único elemento \(x \in A\) tal que \(f(x) = y\).

La existencia de la función inversa para aplicaciones biyectivas es un resultado teórico importante, que establece una correspondencia “perfecta” entre los elementos del dominio y el codominio.

Teorema 1.3 Una aplicación \(f \colon A \to B\) es biyectiva si y solo si existe una función \(g \colon B \to A\) tal que \(g \circ f = \mathop{\mathrm{id}}_A\) y \(f \circ g = \mathop{\mathrm{id}}_B\). En este caso, la función \(g\) es única y se denota por \(f^{-1}\).

Otra operación fundamental con aplicaciones es la composición de funciones. La composición permite “encadenar” aplicaciones, aplicando una función después de otra, creando nuevas aplicaciones a partir de las existentes.

Definición 1.12 Sean \(f \colon A \to B\) y \(g \colon B \to C\) dos aplicaciones. La composición de \(g\) con \(f\), denotada por \(g \circ f \colon A \to C\), es la aplicación definida por \((g \circ f)(x) = g(f(x))\) para todo \(x \in A\).

La composición de funciones es una operación asociativa, es decir, \((h \circ g) \circ f = h \circ (g \circ f)\) para aplicaciones \(f \colon A \to B\), \(g \colon B \to C\) y \(h \colon C \to D\). Además, la composición preserva la inyectividad y la sobreyectividad en el siguiente sentido:

Teorema 1.4 Sean \(f \colon A \to B\) y \(g \colon B \to C\) dos aplicaciones.

• Si \(f\) y \(g\) son inyectivas, entonces \(g \circ f\) es inyectiva.
• Si \(f\) y \(g\) son sobreyectivas, entonces \(g \circ f\) es sobreyectiva.
• Si \(f\) y \(g\) son biyectivas, entonces \(g \circ f\) es biyectiva.
• Si \(g \circ f\) es inyectiva, entonces \(f\) es inyectiva.
• Si \(g \circ f\) es sobreyectiva, entonces \(g\) es sobreyectiva.

En resumen, las aplicaciones constituyen un concepto esencial en matemáticas, proporcionando un lenguaje y unas herramientas fundamentales para describir transformaciones, correspondencias y dependencias entre conjuntos. Las nociones de inyectividad, sobreyectividad, biyectividad y composición enriquecen aún más este concepto, permitiéndonos clasificar y manipular aplicaciones de manera efectiva, y construir estructuras matemáticas cada vez más complejas y sofisticadas. Desde el cálculo y el análisis hasta el álgebra y la topología, las aplicaciones son una piedra angular en el edificio de las matemáticas modernas.

1.1.3 Ejercicios

Ejercicio 1.4 Dados los conjuntos \(A = \{1, 2, 3, 4, 5\}\) y \(B = \{3, 5, 6, 7\}\), calcula: a) \(A \cup B\) b) \(A \cap B\) c) \(A \setminus B\) d) \(B \setminus A\) e) \(A^c\) (suponiendo un conjunto universal \(U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\))

Ejercicio 1.5 Determina si las siguientes afirmaciones son verdaderas o falsas. Justifica tu respuesta. a) \(\{1, 2\} \subseteq \{1, 2, 3\}\) b) \(\{1, 2\} \in \{1, 2, 3\}\) c) \(\varnothing \subseteq \{1, 2, 3\}\) d) \(\varnothing \in \{1, 2, 3\}\) e) \(\varnothing \subseteq \varnothing\) f) \(\varnothing \in \varnothing\)

Ejercicio 1.6 Representa mediante un Diagrama de Venn los conjuntos \(A\), \(B\) y \(C\) y sombrea la región correspondiente a la operación \((A \cap B) \cup C\).

Ejercicio 1.7 Considera la relación \(\mathcal{R} = \{(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)\}\) definida en el conjunto \(A = \{1, 2, 3\}\). Representa \(\mathcal{R}\) como una matriz y como un grafo dirigido.

Ejercicio 1.8 Para la relación \(\mathcal{R}\) del ejercicio anterior, determina si es reflexiva, simétrica, antisimétrica o transitiva. Justifica tus respuestas.

Ejercicio 1.9 Define una relación de equivalencia en el conjunto \(A = \{1, 2, 3, 4\}\) y escribe las clases de equivalencia correspondientes.

Ejercicio 1.10 Determina si las siguientes correspondencias son aplicaciones de \(A = \{1, 2, 3\}\) en \(B = \{a, b, c\}\). Justifica tu respuesta. a) \(f_1 = \{(1, a), (2, b), (3, c)\}\) b) \(f_2 = \{(1, a), (2, a), (3, a)\}\) c) \(f_3 = \{(1, a), (2, b)\}\) d) \(f_4 = \{(1, a), (2, b), (2, c), (3, a)\}\) e) \(f_5 = \{(1, a), (2, b), (3, a), (1, c)\}\)

Ejercicio 1.11 Para las aplicaciones del ejercicio anterior que sí lo sean, determina su dominio, codominio e imagen.

Ejercicio 1.12 🔴 Demuestra las Leyes de De Morgan utilizando las definiciones de las operaciones de conjuntos y las propiedades de la lógica proposicional.

Ejercicio 1.13 🔴🔴 Demuestra que si \(A\) y \(B\) son conjuntos finitos, entonces \(|A \cup B| = |A| + |B| - |A \cap B|\). Generaliza este resultado para la unión de tres conjuntos finitos \(A, B, C\). (Principio de inclusión-exclusión).

Ejercicio 1.14 🔴 En una encuesta a 100 personas sobre sus hábitos de lectura, se encontró que 40 leen revistas, 30 leen periódicos y 20 leen libros. Además, 15 leen revistas y periódicos, 10 leen revistas y libros, 8 leen periódicos y libros, y 5 leen revistas, periódicos y libros.

1. ¿Cuántas personas leen solo revistas?
2. ¿Cuántas personas leen periódicos o libros, pero no revistas?
3. ¿Cuántas personas no leen ninguno de los tres tipos de publicaciones? Resuelve este problema utilizando Diagramas de Venn y también utilizando el principio de inclusión-exclusión.

Ejercicio 1.15 🔴 Considera las aplicaciones \(f \colon \mathbb{R} \to \mathbb{R}\) definida por \(f(x) = 3x - 2\) y \(g \colon \mathbb{R} \to \mathbb{R}\) definida por \(g(x) = x^2 + 1\). a) Calcula \(g \circ f\) y \(f \circ g\). b) Determina si \(f\) y \(g\) son inyectivas, sobreyectivas o biyectivas. c) Determina si \(g \circ f\) y \(f \circ g\) son inyectivas, sobreyectivas o biyectivas. d) Halla la función inversa de \(f\), si existe.

Ejercicio 1.16 🔴 Sea \(f \colon \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\) definida por \(f(m, n) = 2m + n\). ¿Es \(f\) inyectiva? ¿Es \(f\) sobreyectiva? Justifica tus respuestas.

Ejercicio 1.17 🔴🔴 Demuestra las leyes distributivas para las operaciones de unión e intersección de conjuntos: a) \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) b) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)

Ejercicio 1.18 🔴🔴 Sea \(\mathcal{P}(A)\) el conjunto potencia de un conjunto \(A\). Demuestra que para cualesquiera \(X, Y \in \mathcal{P}(A)\):

1. \(\mathcal{P}(X \cap Y) = \mathcal{P}(X) \cap \mathcal{P}(Y)\)
2. \(\mathcal{P}(X) \cup \mathcal{P}(Y) \subseteq \mathcal{P}(X \cup Y)\)
3. Da un ejemplo donde \(\mathcal{P}(X) \cup \mathcal{P}(Y) \neq \mathcal{P}(X \cup Y)\). ¿Bajo qué condición se da la igualdad?

Ejercicio 1.19 🔴🔴 Sea \(\mathcal{R}\) una relación binaria en un conjunto \(A\). Define la relación clausura transitiva de \(\mathcal{R}\), denotada por \(\mathcal{R}^t\), como la menor relación transitiva que contiene a \(\mathcal{R}\). Demuestra que la clausura transitiva existe y es única. Describe un método para construir \(\mathcal{R}^t\).

Ejercicio 1.20 🔴🔴 Sea \(f \colon A \to B\) una aplicación. Demuestra que:

1. \(f\) es inyectiva si y solo si existe una aplicación \(g \colon B \to A\) tal que \(g \circ f = \mathop{\mathrm{id}}_A\). En este caso, \(g\) es una inversa izquierda de \(f\).
2. \(f\) es sobreyectiva si y solo si existe una aplicación \(h \colon B \to A\) tal que \(f \circ h = \mathop{\mathrm{id}}_B\). En este caso, \(h\) es una inversa derecha de \(f\).
3. Si \(f\) es biyectiva, entonces la inversa izquierda y la inversa derecha coinciden y son iguales a la función inversa \(f^{-1}\).

Ejercicio 1.21 🔴🔴 Sea \(f \colon A \to B\) una aplicación, y sean \(X, Y \subseteq A\) y \(W, Z \subseteq B\). Demuestra o da un contraejemplo para las siguientes afirmaciones:

1. \(f(X \cup Y) = f(X) \cup f(Y)\)
2. \(f(X \cap Y) = f(X) \cap f(Y)\)
3. \(f^{-1}(W \cup Z) = f^{-1}(W) \cup f^{-1}(Z)\)
4. \(f^{-1}(W \cap Z) = f^{-1}(W) \cap f^{-1}(Z)\)
5. \(f(f^{-1}(W)) = W\)
6. \(f^{-1}(f(X)) = X\) En los casos donde no se da la igualdad, determina si se da alguna inclusión.

Ejercicio 1.22 🔴🔴 Sea \(f \colon A \to B\) una aplicación. Define una relación \(\mathcal{R}_f\) en \(A\) por \(x \mathcal{R}_f y\) si y solo si \(f(x) = f(y)\).

1. Demuestra que \(\mathcal{R}_f\) es una relación de equivalencia en \(A\).
2. Describe las clases de equivalencia de \(\mathcal{R}_f\).
3. Define una aplicación inyectiva \(\tilde{f} \colon A/\mathcal{R}_f \to B\) relacionada con \(f\).

Ejercicio 1.23 🔴🔴 Sea \(B^A\) el conjunto de todas las aplicaciones de un conjunto \(A\) en un conjunto \(B\). Si \(B = \{0, 1\}\), entonces \(B^A\) se puede identificar con el conjunto potencia \(\mathcal{P}(A)\). Describe esta identificación explícitamente. ¿Cómo se traducen las operaciones de unión, intersección y complemento de subconjuntos de \(A\) en términos de operaciones con aplicaciones en \(B^A\) cuando \(B = \{0, 1\}\)?

1.2 Cardinalidad

Vamos a comenzar estableciendo los conceptos fundamentales que nos permitirán comparar la noción de “tamaño” entre conjuntos, generalizando la idea intuitiva de recuento que aplicamos a conjuntos finitos.

Definición 1.13 Sean \(A\) y \(B\) conjuntos cualesquiera.

• Decimos que el cardinal de \(A\) es menor o igual que el cardinal de \(B\) si existe una función inyectiva de \(A\) en \(B\); en tal caso escribimos \(|A| \le |B|\).

• Decimos que el cardinal de \(A\) es igual al cardinal de \(B\) o que \(A\) y \(B\) son equipotentes si existe una función biyectiva de \(A\) en \(B\); en tal caso escribimos \(|A| = |B|\).

• Decimos que el cardinal de \(A\) es estrictamente menor que el cardinal de \(B\), y lo denotamos \(|A| < |B|\), si \(|A| \le |B|\) y \(|A| \ne |B|\).

Ejemplo 1.10 Los conjuntos \[ A = \{ 000, 001, 010, 100, 011 , 101, 110, 111\}, \qquad\qquad B = \{0, 1, 2, 3, 4, 5, 6, 7\}, \] son equipotentes, y eso significa que “tienen el mismo número de elementos”. Es decir, en estos conjuntos el cardinal coincide con la idea intuitiva de “tamaño” del conjunto. Sin embargo, esto no ocurre siempre.

Ejemplo 1.11 Sea \(E = \{ x \in \mathbb{Z} \mid x \text{ es par }\}\). La función \[ \begin{array}{cclcl} f& \colon& \mathbb{Z} & \to & E\\ &&x & \mapsto & 2x \\ \end{array} \] es biyectiva y permite afirmar que \(\mathbb{Z}\) tiene el mismo cardinal que \(E\), aunque la intuición nos dice que \(E\) tiene la “mitad” de los elementos de \(\mathbb{Z}\).

Observa que la función \(f\) está bien definida, ya que la imagen de cualquier entero mediante \(f\) es un número par. Además, \(f\) es inyectiva, pues si \(f(x) = f(y)\), entonces \(2x = 2y\), de donde \(x=y\). Finalmente, \(f\) es sobreyectiva, pues para cualquier \(y \in E\), que es un entero par, existe un entero \(x = y/2\) tal que \(f(x) = 2(y/2) = y\). Por lo tanto, \(f\) es una biyección entre \(\mathbb{Z}\) y \(E\), lo que prueba que \(|\mathbb{Z}| = |E|\). Este ejemplo ilustra que nuestra intuición sobre el “tamaño” de conjuntos infinitos puede ser engañosa.

Es fácil ver que la relación \(<\) entre cardinales es una relación no reflexiva y transitiva y que la relación \(\le\) es una relación de orden, que además es de orden total, según establece el siguiente resultado.

Teorema 1.5 (Tricotomía de Zermelo) Para cualquier par de conjuntos \(A\) y \(B\), se verifica una y solo una de las siguientes relaciones: \[ |A| < |B|, \qquad |A| = |B|, \qquad |B| < |A| \]

Este teorema, también conocido como el principio del tricotomía para cardinales, es un resultado fundamental en la teoría de conjuntos. Aunque la demostración de este teorema está más allá del alcance de este capítulo, es importante conocer que siempre podemos comparar los cardinales de dos conjuntos cualesquiera.

Según la definición de equipotencia, demostrar que dos conjuntos tienen el mismo cardinal, supone encontrar una biyección entre ellos, el siguiente teorema facilita el trabajo.

Teorema 1.6 (Cantor-Schröder-Bernstein) Sean \(A\) y \(B\) dos conjuntos cualesquiera. Si se verifica que \(|A| \le |B|\) y \(|B| \le |A|\), entonces \(|A| = |B|\).

El Teorema de Cantor-Schröder-Bernstein es una herramienta muy potente para demostrar que dos conjuntos tienen el mismo cardinal. En lugar de construir una biyección directamente, que en ocasiones puede ser complicado, basta con encontrar una función inyectiva de \(A\) en \(B\) y otra función inyectiva de \(B\) en \(A\).

Ejemplo 1.12 (Cardinal de intervalos) Los intervalos de números reales \([0,1]\) y \((0,1)\) tienen el mismo cardinal, dado que la siguiente función es una biyección: \[ f\colon [0,1] \to (0,1),\qquad \begin{cases} f(0) = \dfrac{1}{2} & \\ f(\dfrac{1}{n}) = \dfrac{1}{n+2} & n \in \mathbb{Z}^+ \\ f(x) = x & \text{ en otros casos } \end{cases} \]

Para verificar que \(f\) es una biyección, debemos probar que es inyectiva y sobreyectiva. La inyectividad se puede comprobar analizando los distintos casos de la función. La sobreyectividad es algo más sutil. Para ver que \(f\) es sobreyectiva, tomemos \(y \in (0,1)\). Si \(y\) no es de la forma \(\frac{1}{n+2}\) para ningún \(n \in \mathbb{Z}^+\), ni \(y = \frac{1}{2}\), entonces \(f(y) = y\). Si \(y = \frac{1}{2}\), entonces \(f(0) = \frac{1}{2}\). Si \(y = \frac{1}{n+2}\) para algún \(n \in \mathbb{Z}^+\), entonces \(f(\frac{1}{n}) = \frac{1}{n+2} = y\). Por lo tanto, \(f\) es sobreyectiva.

Utilizando el teorema de Cantor-Schröder-Bernstein (Teorema 1.6) podemos definir funciones más simples para obtener la misma conclusión.

• \(f \colon (0,1) \to [0,1]\) definida \(f(x) = x\) es una función inyectiva y por lo tanto, \(\big|(0,1)\big| \le \big|[0,1]\big|\)

• \(g \colon [0,1] \to (0,1)\) definida \(g(x)= \dfrac{x}{2} + \dfrac{1}{4}\) también es inyectiva y por lo tanto \(\big|[0,1]\big| \le \big|(0,1)\big|\).

Como ambas desigualdades se verifican, por el Teorema de Cantor-Schröder-Bernstein, concluimos que \(\big|(0,1)\big| = \big|[0,1]\big|\). Para verificar que \(g\) es inyectiva, supongamos que \(g(x) = g(y)\). Entonces \(\dfrac{x}{2} + \dfrac{1}{4} = \dfrac{y}{2} + \dfrac{1}{4}\), lo que implica \(\dfrac{x}{2} = \dfrac{y}{2}\) y por lo tanto \(x=y\). Además, la imagen de \(g\) está contenida en \((0,1)\) ya que si \(x \in [0,1]\), entonces \(0 \le x \le 1\), de donde \(0 \le \dfrac{x}{2} \le \dfrac{1}{2}\), y por lo tanto \(\dfrac{1}{4} \le \dfrac{x}{2} + \dfrac{1}{4} \le \dfrac{3}{4}\), lo que implica que \(g(x) \in [\frac{1}{4}, \frac{3}{4}] \subset (0,1)\).

1.2.1 Conjuntos finitos e infinitos

El primer comentario debe ser sobre conjuntos que denominaremos “finitos”.

Definición 1.14 Diremos que un conjunto \(A\) es finito si existe un número natural \(n\in\mathbb N\) tal que se puede establecer una biyección entre el conjunto \(\mathbb{N}_n = \{ 1, 2,\dots,n\}\) y el conjunto \(A\). En tal caso, diremos que el cardinal de \(A\) es \(n\) y lo denotaremos por \(|A| = n\).

La definición de conjunto infinito la hacemos por oposición.

Definición 1.15 Se dice que un conjunto \(A\) es infinito si no es finito, es decir, si no existe un número natural \(n \in \mathbb{N}\) tal que se puede establecer una biyección entre el conjunto \(\{1, 2, ..., n \}\) y el conjunto \(A\)).

Por lo tanto, para probar que un conjunto \(A\) es infinito se debe demostrar que no es posible definir ninguna biyección entre \(\{ 1, 2, \dots , n\}\) y \(A\) para ningún \(n\), y esto puede ser complicado.

Ejemplo 1.13  

Para demostrar que \(\mathbb{N}\) es un conjunto infinito, vamos a ver que no existe ningún número natural \(n\) para el que se pueda establecer una biyección del conjunto entre \(\{1, 2, \dots ,n\}\) y \(\mathbb{N}\).

Sea \(n\) un número natural cualquiera y \(f\colon \{ 1, 2, \dots , n\}\to \mathbb{N}\) una función cualquiera. Si tomamos \(k = 1 + \max\{ f(1), \dots, f(n)\}\), es decir, \(k\) es mayor que las imágenes \(f(i)\) para todo \(i=1, 2,\ldots, n\), así que, claramente, \(f(x)\ne k\) para todo \(x \in \{1, 2, \dots, n\}\) y en consecuencia \(f\) no es sobreyectiva y por lo tanto no es biyectiva. En consecuencia, \(\mathbb{N}\) es infinito.

En este ejemplo, hemos probado que cualquier función de un conjunto finito \(\{1, 2, \dots, n\}\) a \(\mathbb{N}\) no puede ser sobreyectiva, y por lo tanto, no puede ser biyectiva. Esto demuestra, usando la definición, que \(\mathbb{N}\) es un conjunto infinito.

La definición de conjunto infinito como opuesto a conjunto finito no permite reconocer explícitamente los conjuntos infinitos. La caracterización dada por el siguiente teorema es más conveniente para establecer que un conjunto es efectivamente infinito.

Teorema 1.7 Un conjunto \(A\) es infinito si y solo si existe una función inyectiva \(f\colon A \to A\) tal que \(f(A) \subset A\) y \(f(A) \ne A\).

Es decir, un conjunto es infinito si y solo si existe una función inyectiva de \(A\) en sí mismo que no es sobreyectiva. Esto constrasta con la situación en conjuntos finitos, como se pone de manifiesto en el siguiente ejercicio.

Ejercicio 1.24 Sea \(A\) un conjunto finito y sea \(f\colon A\to A\) una aplicación de \(A\) en sí mismo. Demostrar que \(f\) es inyectiva si, y sólo si, \(f\) es sobreyectiva.

Ejemplo 1.14 Veamos que \(\mathbb{N}\) es un conjunto infinito, usando la caracterización.

La función \(f\colon\mathbb{N} \to \mathbb{N}\), definida por \(f(n) = 2n\), es trivialmente inyectiva y \(f(\mathbb{N}) \subsetneq \mathbb{N}\), ya que por ejemplo \(7\not\in f(\mathbb{N})\) (de hecho, ningún número impar está en la imagen de \(f\)). Por lo tanto, \(\mathbb{N}\) es un conjunto infinito.

En este caso, la función \(f(n) = 2n\) nos proporciona una forma sencilla de verificar que \(\mathbb{N}\) es infinito, utilizando la caracterización del Teorema anterior.

Ejemplo 1.15 El conjunto de todas las cadenas de elementos de \(\Sigma = \{ \mathrm a, \mathrm b\}\), denotado por \(\Sigma ^*\), es un conjunto infinito. La función \(f\colon \Sigma^* \to \Sigma ^*\) definida por \(f(w) = \mathrm a w\) es inyectiva y \(f(\Sigma^*)\) no coincide con \(\Sigma ^*\), ya que \(f(\Sigma^*)\) no incluye las cadenas que empiezan por \(\mathrm b\) (ni la cadena vacía, si la cadena vacía está incluida en \(\Sigma^*\)).

Aquí, la función \(f(w) = \mathrm a w\) añade el símbolo ‘a’ al principio de cada cadena. Esta función es inyectiva porque si \(f(w_1) = f(w_2)\), entonces \(\mathrm a w_1 = \mathrm a w_2\), y cancelando ‘a’ al principio (por la propiedad cancelativa de la concatenación de cadenas) obtenemos \(w_1 = w_2\). La imagen de \(f\) no es todo \(\Sigma^*\) porque ninguna cadena que comience con ‘b’ (o la cadena vacía) está en la imagen de \(f\).

Proposición 1.1 Si \(A\) es un conjunto infinito y \(A\subset B\), entonces \(B\) es infinito.

Prueba. Si \(A\) es infinito, existe un función \(f\colon A \to A\) inyectiva tal que \(f(A)\subset A\) y \(f(A) \ne A\). Consideramos entonces la función \(g\colon B \to B\) dada por \[ g(x) = \left\{ \begin{array}{cl} f(x) & \ \text{si} \ x \in A \\ x & \ \text{si} \ x \in B - A \end{array}\right. \] Entonces \(g\) es claramente inyectiva y la imagen de \(g\) no incluye el conjunto no vacío \(A - f(A)\).

Para verificar que \(g\) es inyectiva, consideremos \(x, y \in B\) tales que \(g(x) = g(y)\). Debemos analizar varios casos:

• Si \(x, y \in A\), entonces \(g(x) = f(x)\) y \(g(y) = f(y)\). Como \(g(x) = g(y)\), tenemos \(f(x) = f(y)\). Dado que \(f\) es inyectiva en \(A\), se sigue que \(x = y\).
• Si \(x \in A\) e \(y \in B - A\), entonces \(g(x) = f(x) \in A\) y \(g(y) = y \in B - A\). Como \(A\) y \(B - A\) son disjuntos, \(g(x) \ne g(y)\), por lo que este caso no puede ocurrir si \(g(x) = g(y)\).
• Si \(x, y \in B - A\), entonces \(g(x) = x\) y \(g(y) = y\). Como \(g(x) = g(y)\), tenemos \(x = y\). Por lo tanto, \(g\) es inyectiva. Además, la imagen de \(g\) no contiene elementos de \(A - f(A)\), que es no vacío porque \(f(A) \subsetneq A\). Por lo tanto, \(g(B) \subsetneq B\), y por el Teorema de Caracterización de Conjuntos Infinitos, \(B\) es infinito.

Teorema 1.8 (Cantor) Sea \(A\) un conjunto cualquiera. Entonces \(|A| < |\mathcal{P}(A)|\).

Este teorema, fundamental en la teoría de cardinalidad, establece que el conjunto potencia de cualquier conjunto \(A\), \(\mathcal{P}(A)\), tiene una cardinalidad estrictamente mayor que la de \(A\). Esto es cierto tanto para conjuntos finitos como infinitos.

1.2.1.1 Conjuntos numerables

Para los conjuntos finitos, los conjuntos \(\mathbb{N}_n=\{ 1, 2, ... , n\}\) juegan un papel fundamental como referencia para comparar otros conjuntos y definir su cardinalidad. Específicamente, un conjunto finito \(A\) tiene cardinal \(n\) si, y solo si, existe una biyección entre el conjunto \(\mathbb{N}_n = \{ 1, 2, ... , n\}\) y \(A\). Adicionalmente, por convención, el cardinal del conjunto vacío es 0, es decir, \(|\varnothing| =0\).

En el ámbito de los conjuntos infinitos, podemos adoptar una estrategia similar, utilizando conjuntos infinitos de referencia para discernir diferentes “tamaños” entre ellos. Comenzaremos considerando el conjunto de los números naturales, \(\mathbb{N} = \{0, 1, 2, 3, \dots \}\).

Definición 1.16 Se dice que un conjunto \(A\) tiene cardinal \(\aleph_0\) (álef-cero) si existe una función biyectiva entre el conjunto de los números naturales \(\mathbb{N}\) y \(A\). En tal caso, escribimos \(|A| = \aleph_0\).

La notación \(\aleph_0\) se utiliza para denotar el cardinal de los conjuntos que son equipotentes a los números naturales. Este símbolo, \(\aleph\), es la primera letra del alfabeto hebreo y es utilizado en teoría de conjuntos para representar cardinales infinitos.

La relación de “tener el mismo cardinal” (equipotencia) es una relación de equivalencia entre conjuntos. En este contexto, el cardinal \(\aleph_0\) puede entenderse como representante de la clase de equivalencia de todos los conjuntos equipotentes a \(\mathbb{N}\). Es decir, \(\aleph_0\) representa la “magnitud” común a todos los conjuntos que pueden ser puestos en biyección con los números naturales.

La existencia de una biyección entre un conjunto \(A\) y \(\mathbb{N}\) (o \(\mathbb{N}_n\) en el caso finito) sugiere la posibilidad de “contar” o “enumerar” los elementos de \(A\), aunque en el caso infinito este proceso sea, intrínsecamente, interminable. Por esta razón, introducimos la noción de conjunto numerable.

Definición 1.17 Un conjunto \(A\) se dice que es numerable si es finito o si tiene cardinal \(\aleph_0\). Si un conjunto tiene cardinal \(\aleph_0\), se dice que es infinito numerable. En la literatura matemática, es común utilizar indistintamente los términos numerable y contable.

Ejemplo 1.16 Recordemos que \(\mathbb{N} = \{0, 1, 2, 3, ..., n, ...\}\) y \(\mathbb{Z}^+=\{1, 2, 3, ..., n, ...\}\). Estos conjuntos son equipotentes, como se puede verificar considerando la aplicación \[ f\colon \mathbb{N} \to \mathbb{Z}^+,\qquad\quad f(n) = n+1. \] Esta función \(f\) es biyectiva:

• Inyectiva: Si \(f(n) = f(m)\), entonces \(n+1 = m+1\), lo que implica \(n=m\).
• Sobreyectiva: Para cualquier \(m \in \mathbb{Z}^+\), existe \(n = m-1 \in \mathbb{N}\) (ya que \(m \ge 1\)) tal que \(f(n) = (m-1)+1 = m\).

Por la existencia de esta biyección, concluimos que \(|\mathbb{N}| = |\mathbb{Z}^+| = \aleph_0\). Este ejemplo justifica que podamos utilizar indistintamente \(\mathbb{N}\) o \(\mathbb{Z}^+\) como conjunto de referencia para estudiar la numerabilidad de otros conjuntos.

Ejemplo 1.17 Consideremos el conjunto \(A = \{ 1, \dfrac{1}{2}, \dfrac{1}{3}, \dots \} = \{ \dfrac{1}{n} \mid n \in \mathbb{Z}^+\}\). Para demostrar que \(A\) es infinito numerable, definimos la función \(f\colon \mathbb{Z}^+ \to A\) como \(f(n) = \dfrac{1}{n}\). Esta función establece una biyección entre \(\mathbb{Z}^+\) y \(A\):

• Inyectiva: Si \(f(n) = f(m)\), entonces \(\dfrac{1}{n} = \dfrac{1}{m}\), lo que implica \(n=m\).
• Sobreyectiva: Para cualquier \(y \in A\), por la propia definición de \(A\), existe un entero positivo \(n\) tal que \(y = \dfrac{1}{n}\). Por lo tanto, \(y = f(n)\).

En consecuencia, \(|A| = |\mathbb{Z}^+| = \aleph_0\), y \(A\) es un conjunto numerable (infinito numerable).

Ejemplo 1.18 Sea \(k\) un entero positivo no nulo. Consideremos el conjunto de los múltiplos positivos de \(k\), \(k\mathbb{Z}^+ = \{k\cdot n \mid n\in \mathbb{Z}^+\} = \{k, 2k, 3k, \dots \}\). Para demostrar que \(k\mathbb{Z}^+\) es numerable, definimos la función \(f\colon\mathbb{Z}^+ \to k\mathbb{Z}^+\) como \(f(x) = kx\). Esta función es biyectiva:

• Inyectiva: Si \(f(x) = f(y)\), entonces \(kx = ky\). Como \(k \ne 0\), se deduce que \(x=y\).
• Sobreyectiva: Por definición, todo elemento de \(k\mathbb{Z}^+\) es de la forma \(kn\) para algún \(n \in \mathbb{Z}^+\). Por lo tanto, para cualquier \(y \in k\mathbb{Z}^+\), existe \(x = y/k \in \mathbb{Z}^+\) tal que \(f(x) = k(y/k) = y\).

Por lo tanto, \(|k\mathbb{Z}^+| = |\mathbb{Z}^+| = \aleph_0\), y \(k\mathbb{Z}^+\) es numerable.

La noción de “enumeración” proporciona una perspectiva intuitiva sobre los conjuntos numerables. Un conjunto se puede enumerar si sus elementos pueden ser organizados en una lista, ya sea finita o infinita. Formalmente, definimos enumeración de la siguiente manera:

Definición 1.18 Una enumeración de un conjunto \(A\) es una función sobreyectiva \(f\) cuyo dominio es \(\mathbb{N}_n\) para algún \(n \in \mathbb{N}\), o bien \(\mathbb{Z}^+\).

• Si \(f\) es además inyectiva (y por tanto, biyectiva), se dice que es una enumeración sin repeticiones.
• Si \(f\) no es inyectiva, se dice que es una enumeración con repeticiones.

Una enumeración \(f\) se especifica habitualmente listando la secuencia de valores \([f(1), f(2), \dots ]\).

Ejemplo 1.19 Consideremos el conjunto \(A = \{ a, b, c\}\). Entonces, \([ b, c, b, a ]\) y \([ c, b, a ]\) son enumeraciones de \(A\). La primera es una enumeración con repeticiones, mientras que la segunda es una enumeración sin repeticiones.

En el contexto de conjuntos numerables, la existencia de una enumeración es suficiente para determinar su cardinalidad. En particular, para demostrar que un conjunto es numerable, no es necesario construir explícitamente una biyección, sino que basta con encontrar una función sobreyectiva desde \(\mathbb{N}\) o \(\mathbb{Z}^+\).

Teorema 1.9 (Caracterización de conjuntos numerables) Un conjunto \(A\) es numerable si, y sólo si, existe una enumeración de \(A\).

Ejemplo 1.20 Dado cualquier alfabeto finito \(\Sigma\), el conjunto \(\Sigma^*\) de todas las cadenas finitas formadas con símbolos de \(\Sigma\) es infinito numerable. Para demostrar esto, podemos construir una enumeración de los elementos de \(\Sigma^*\) siguiendo un orden lexicográfico (similar al orden alfabético de un diccionario), primero por longitud de cadena y luego alfabéticamente dentro de las cadenas de la misma longitud.

Por ejemplo, para el alfabeto binario \(\Sigma = \{ 0, 1\}\), si consideramos que \(0\) precede a \(1\), podemos enumerar \(\Sigma^*\) de la siguiente manera: \[ [\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, \dots ] \] donde \(\epsilon\) representa la cadena vacía. Esta enumeración cubre todos los elementos de \(\Sigma^*\) y, por lo tanto, \(\Sigma^*\) es numerable.

Ejemplo 1.21 El conjunto de los números racionales positivos \(\mathbb{Q}^+\) es infinito numerable. Es claro que \(\mathbb{Q}^+\) no es finito, ya que contiene a los números naturales \(\mathbb{N}\) como subconjunto. Para demostrar que el conjunto de los números racionales positivos \(\mathbb{Q}^+\) es numerable, vamos a construir una enumeración explícita de sus elementos. Consideremos la siguiente tabla infinita: \[ \begin{array}{cccccc} \frac{1}{1} & \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \dots \\ \frac{2}{1} & \frac{2}{2} & \frac{2}{3} & \frac{2}{4} & \frac{2}{5} & \dots \\ \frac{3}{1} & \frac{3}{2} & \frac{3}{3} & \frac{3}{4} & \frac{3}{5} & \dots \\ \frac{4}{1} & \frac{4}{2} & \frac{4}{3} & \frac{4}{4} & \frac{4}{5} & \dots \\ \frac{5}{1} & \frac{5}{2} & \frac{5}{3} & \frac{5}{4} & \frac{5}{5} & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \]

En esta tabla, la fila \(i\)-ésima contiene las fracciones con numerador \(i\) y denominadores \(1, 2, 3, \dots\). Cada número racional positivo aparece en esta tabla al menos una vez (de hecho, infinitas veces, por ejemplo \(\frac{1}{1} = \frac{2}{2} = \frac{3}{3} = \dots\)).

Para enumerar los elementos de \(\mathbb{Q}^+\), podemos recorrer la tabla siguiendo un camino diagonal, como se indica a continuación:

1. Empezamos por la esquina superior izquierda, \(\frac{1}{1}\).
2. Seguimos diagonalmente hacia abajo y a la derecha, tomando \(\frac{1}{2}, \frac{2}{1}\).
3. Continuamos con la siguiente diagonal, tomando \(\frac{1}{3}, \frac{2}{2}, \frac{3}{1}\).
4. Seguimos este patrón diagonal, recorriendo cada diagonal completa antes de pasar a la siguiente.

Este proceso genera la siguiente enumeración: \[ \left[ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots \right] \]

En esta enumeración, debemos eliminar las fracciones que no estén en su forma irreducible (o, más simplemente, eliminar las repeticiones). Si eliminamos las repeticiones y consideramos solo los racionales positivos únicos, obtenemos una enumeración de \(\mathbb{Q}^+\). Por ejemplo, eliminando las fracciones repetidas en los primeros términos, obtenemos: \[ \left[ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots \right] \] (hemos eliminado \(\frac{2}{2} = \frac{1}{1}\) y \(\frac{3}{3} = \frac{1}{1}\), \(\frac{2}{4} = \frac{1}{2}\), \(\frac{4}{2} = \frac{2}{1}\), \(\frac{3}{6} = \frac{1}{2}\), etc.)

Este proceso diagonal asegura que cada fracción \(\frac{p}{q}\) con \(p, q \in \mathbb{Z}^+\) eventualmente será alcanzada en la enumeración, ya que estará en la diagonal correspondiente a la suma \(p+q = k\) para algún entero \(k \ge 2\). Por lo tanto, hemos construido una enumeración de \(\mathbb{Q}^+\), lo que demuestra que \(\mathbb{Q}^+\) es un conjunto numerable.

El siguiente resultado establece una propiedad fundamental del cardinal \(\aleph_0\): es el “menor” cardinal infinito.

Teorema 1.10 Todo conjunto infinito contiene un subconjunto infinito numerable. Equivalentemente, si \(A\) es un conjunto infinito, entonces \(\aleph_0 \le |A|\).

Este teorema implica que \(\aleph_0\) es el cardinal “más pequeño” entre todos los cardinales infinitos. Cualquier conjunto infinito tiene al menos la “misma cantidad de elementos” que los números naturales.

1.2.1.2 Conjuntos no numerables

Ahora, surge la pregunta de si existen conjuntos infinitos que no sean equipotentes a \(\mathbb{N}\). En otras palabras, ¿existen conjuntos infinitos cuyo “tamaño” sea estrictamente mayor que el de los números naturales? El siguiente teorema, fundamental en la teoría de cardinalidad, responde afirmativamente a esta pregunta, proporcionando un ejemplo crucial de conjunto no numerable.

Teorema 1.11 (Diagonal de Cantor) El intervalo de números reales \([0, 1]\) no es numerable.

La demostración de este teorema, que utiliza una técnica conocida como el método de la diagonal de Cantor, es un resultado clásico en teoría de conjuntos. Aunque no se presenta la demostración detallada en este curso, es importante destacar que este método es una herramienta poderosa con numerosas aplicaciones en diversas áreas de las matemáticas y la informática teórica, especialmente en teoría de la computabilidad.

Georg Cantor (1845-1918) fue un matemático alemán, creador de la teoría de conjuntos, un área fundamental en matemáticas. Su trabajo revolucionario introdujo los números transfinitos para describir el tamaño de los conjuntos infinitos, estableciendo la existencia de diferentes “infinitos” y definiendo conceptos como la numerabilidad y la no numerabilidad. A pesar de la importancia actual de su teoría, Cantor enfrentó fuertes críticas y oposición durante su vida, especialmente por parte de Kronecker, lo que contribuyó a periodos de depresión. Hoy en día, Cantor es reconocido como uno de los matemáticos más importantes e influyentes de la historia, y su teoría de conjuntos es un pilar esencial de las matemáticas modernas.

Anteriormente, hemos establecido el Teorema de Cantor, que afirma que para cualquier conjunto \(A\), se cumple la desigualdad \(|A| < |\mathcal{P}(A)|\). Aplicando este teorema al conjunto de los números naturales \(\mathbb{N}\), obtenemos que \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\). Como \(\mathbb{N}\) es numerable (de cardinal \(\aleph_0\)), se deduce que \(\mathcal{P}(\mathbb{N})\) tiene un cardinal estrictamente mayor que \(\aleph_0\), y por lo tanto, \(\mathcal{P}(\mathbb{N})\) no puede ser numerable.

Teorema 1.12 El conjunto potencia de los números naturales, \(\mathcal{P}(\mathbb{N})\), es no numerable.

Una vez establecido que existen conjuntos infinitos no numerables, podemos introducir un nuevo cardinal infinito para describir el “tamaño” de conjuntos como \(\mathcal{P}(\mathbb{N})\) y \([0, 1]\).

Definición 1.19 Se dice que un conjunto \(A\) tiene cardinal \(\aleph_1\) si existe una biyección entre el conjunto potencia de los números naturales \(\mathcal{P}(\mathbb{N})\) y \(A\).

Es importante notar que esta definición de \(\aleph_1\) no coincide con la definición original dada por Cantor en el contexto de los números ordinales. Sin embargo, para nuestros propósitos, esta definición simplificada es suficiente. El cardinal de \(\mathcal{P}(\mathbb{N})\) se denota también con los símbolos \(\mathfrak{c}\) (cardinal del continuo) o \(\beth_1\) (beth-uno). La Hipótesis del Continuo, una famosa conjetura en teoría de conjuntos (cuya demostración de independencia de los axiomas ZFC fue probada por Gödel y Cohen), postula que no existe ningún cardinal estrictamente intermedio entre \(\aleph_0\) y \(\mathfrak{c}\). Si se asume la Hipótesis del Continuo, se tiene que \(\aleph_1 = \mathfrak{c}\).

Utilizando la notación \(2^A\) para el conjunto potencia de \(A\), la relación entre \(\aleph_0\) y \(\aleph_1\) puede expresarse de forma análoga a la relación entre cardinales finitos y sus conjuntos potencia: \[ \aleph_1 = 2^{\aleph_0}. \] Esta expresión refuerza la idea de que \(\aleph_1\) representa un “tamaño” significativamente mayor que \(\aleph_0\).

En resumen, combinando los resultados que hemos visto hasta ahora, podemos establecer la siguiente jerarquía de cardinalidades: para cualquier conjunto finito \(A\), \[ |A| < \aleph_0 < \aleph_1. \] Esto significa que cualquier conjunto finito tiene un cardinal estrictamente menor que \(\aleph_0\), y \(\aleph_0\) es estrictamente menor que \(\aleph_1\).

De forma análoga a como \(\mathbb{N}\) (o \(\mathbb{Z}^+\)) son los conjuntos de referencia para la numerabilidad, el intervalo \([0,1] \subset \mathbb{R}\) se utiliza como conjunto estándar para caracterizar conjuntos de cardinal \(\aleph_1\). El siguiente teorema, cuya demostración omitimos, formaliza esta idea.

\[\Huge\aleph_1 \stackrel{?}{=} \mathfrak{c}\] La Hipótesis del Continuo, formulada por Cantor, establece que no existe ningún cardinal entre el cardinal de los números naturales (\(\aleph_0\)) y el cardinal de los números reales (el continuo, \(\mathfrak{c}\)). En otras palabras, no hay un “tamaño” de infinito estrictamente intermedio entre los conjuntos numerables y los conjuntos con la cardinalidad del continuo. Sorprendentemente, se demostró en el siglo XX que la Hipótesis del Continuo es indecidible dentro de los axiomas estándar de la teoría de conjuntos (ZFC), lo que significa que puede ser asumida como verdadera o falsa sin contradicción.

Teorema 1.13 El cardinal del intervalo \([0,1]\) como subconjunto de los números reales \(\mathbb{R}\) es \(\aleph_1\).

Ejemplo 1.22 El conjunto \(\mathbb{R}\) de todos los números reales tiene cardinal \(\aleph_1\). Esto se puede demostrar construyendo una biyección entre el intervalo \((0, 1)\) y \(\mathbb{R}\). Un ejemplo de tal biyección es la función \[ g\colon (0, 1) \to \mathbb{R}, \qquad\quad g(x) = \dfrac{1- 2x}{x(1-x)}. \] Como ya hemos visto previamente que los intervalos \([0,1]\) y \((0,1)\) tienen el mismo cardinal (es decir, \(\aleph_1\)), este ejemplo confirma que \(|\mathbb{R}| = \aleph_1\).

Como consecuencia del Teorema de Cantor, sabemos que \(|A| < |\mathcal{P}(A)|\) para cualquier conjunto \(A\). Aplicando iterativamente el operador conjunto potencia, obtenemos una jerarquía infinita de cardinales infinitos, todos ellos no numerables: \[ |\mathbb N| < |\mathcal{P}(\mathbb N)| < |\mathcal{P}(\mathcal{P}(\mathbb N))| < \dots \] Este resultado fundamental revela que no existe un cardinal infinito máximo. Sin embargo, como hemos demostrado, sí existe un cardinal infinito mínimo, \(\aleph_0\). Para los objetivos de este curso introductorio, nos centraremos principalmente en conjuntos con cardinales finitos, \(\aleph_0\) (numerable) o \(\aleph_1\) (cardinal del continuo).

1.2.2 Aplicaciones

Aunque pueda parecer que “medir” el tamaño de conjuntos es una actividad por puro placer matemático, tiene multitud de aplicaciones, como presentamos aquí.

1.2.2.1 Recuento

El concepto de cardinalidad surge directamente de la necesidad de generalizar la idea de “contar” más allá de los conjuntos finitos. En el ámbito de los conjuntos finitos, el cardinal simplemente coincide con el número de elementos, una noción intuitiva y familiar. Sin embargo, al enfrentarnos a conjuntos infinitos, la cardinalidad se convierte en la herramienta fundamental para comparar y clasificar el “tamaño” de estos conjuntos. Mientras que la intuición podría sugerir que todos los conjuntos infinitos son “igual de grandes”, la teoría de cardinalidad revela una jerarquía sorprendente de infinitos, cada uno estrictamente mayor que el anterior.

La cardinalidad nos permite establecer comparaciones precisas entre conjuntos infinitos, determinando si dos conjuntos infinitos tienen el mismo “número” de elementos (son equipotentes) o si uno es “más grande” que otro en términos de cardinalidad. Esta capacidad de comparación es esencial para entender la estructura y las propiedades de los conjuntos infinitos, y para extender las técnicas de recuento combinatorio a contextos más generales. Por ejemplo, al demostrar que el conjunto de los números racionales es numerable, esencialmente estamos mostrando que, aunque infinito, se puede “contar” en cierto sentido, al poder establecer una biyección con los números naturales.

1.2.2.2 Teoría de la probabilidad

La teoría de la probabilidad, especialmente en su formulación moderna basada en la teoría de la medida, se beneficia enormemente del concepto de cardinalidad, sobre todo cuando se trata de espacios de probabilidad continuos. En estos espacios, como el intervalo \([0, 1]\) utilizado para modelar variables aleatorias continuas, la cardinalidad permite entender y comparar la “probabilidad” de diferentes eventos. Aunque en espacios continuos la probabilidad de un punto individual es cero, la cardinalidad nos ayuda a comprender que no todos los conjuntos de probabilidad cero son “iguales”.

Alan Turing (1912-1954) fue un matemático y científico de la computación británico, considerado padre de la informática teórica y la inteligencia artificial. Turing formalizó los conceptos de algoritmo y computación con su máquina de Turing, un modelo computacional abstracto que sentó las bases de la informática moderna. Durante la Segunda Guerra Mundial, desempeñó un papel crucial en el descifrado de códigos nazis en Bletchley Park. Su trabajo influyó profundamente en el desarrollo de la computación y la inteligencia artificial, aunque su vida se vio truncada trágicamente debido a la persecución por su homosexualidad.

Por ejemplo, al considerar la distribución uniforme en el intervalo \([0, 1]\), tanto el conjunto de los números racionales como el conjunto de los números trascendentes son subconjuntos de \([0, 1]\). Ambos conjuntos son infinitos, pero tienen cardinalidades muy diferentes. El conjunto de los racionales es numerable (cardinal \(\aleph_0\)), mientras que el conjunto de los trascendentes es no numerable (cardinal \(\aleph_1\)). Esta diferencia en cardinalidad se refleja en la medida de Lebesgue (y por tanto, en la probabilidad): el conjunto de los racionales tiene medida cero, mientras que el conjunto de los trascendentes tiene medida uno. La cardinalidad, por lo tanto, proporciona un marco conceptual para distinguir entre diferentes “grados de infinidad” incluso dentro de conjuntos con medida cero o medida uno, enriqueciendo nuestra comprensión de la probabilidad en contextos continuos.

1.2.2.3 Computabilidad

En el campo de la computabilidad, la cardinalidad juega un papel crucial para establecer límites fundamentales sobre lo que se puede y no se puede computar. La teoría de la computabilidad se ocupa de estudiar qué problemas pueden ser resueltos mediante algoritmos y cuáles son inherentemente irresolubles. La noción de conjunto numerable e incontable es esencial en este contexto. Los conjuntos numerables, al poder ser “enumerados” o “listados”, guardan una relación más estrecha con la computación, que inherentemente se basa en procesos discretos y secuenciales.

Un resultado fundamental en computabilidad es que el conjunto de todos los programas posibles (en cualquier lenguaje de programación) es numerable, ya que cada programa puede representarse como una cadena finita de símbolos de un alfabeto finito. Sin embargo, el conjunto de todos los problemas posibles (por ejemplo, el conjunto de todas las funciones de \(\mathbb{N}\) en \(\mathbb{N}\)) es no numerable. Esta diferencia de cardinalidad implica que existen “muchos más” problemas que programas para resolverlos. En consecuencia, debe haber problemas que son inherentemente no computables, es decir, para los que no existe ningún algoritmo que los resuelva. La cardinalidad, en este sentido, nos ayuda a comprender las limitaciones intrínsecas de la computación y a identificar problemas que están más allá del alcance de cualquier algoritmo, como el famoso problema de la parada de Turing.

1.2.3 Ejercicios

Presentamos una serie de problemas y cuestiones principalmente teóricas para reforzar y recordar los conceptos de cardinalidad.

Ejercicio 1.25 Sea \(A\) un conjunto finito. Demuestra que todo subconjunto de \(A\) es finito.

Ejercicio 1.26 Demuestra que la unión de dos conjuntos finitos es un conjunto finito.

Ejercicio 1.27 Demuestra que el producto cartesiano de dos conjuntos finitos es un conjunto finito.

Ejercicio 1.28 Si \(A\) es infinito, entonces demuestra que \(A\cup B\) es infinito para cualquier conjunto \(B\).

Ejercicio 1.29 Si \(f\colon A\to B\) es una función inyectiva y \(A\) es infinito, demuestra que \(B\) es infinito.

Ejercicio 1.30 Si \(A\) es infinito y \(B\ne \varnothing\), demuestra que \(A\times B\) es infinito.

Ejercicio 1.31 Si \(A\) es infinito, demuestra que \(\mathcal{P}(A)\) es infinito.

Ejercicio 1.32 Sea \(U\) un conjunto infinito y \(A \subset U\) un conjunto finito. Demuestra que \(U \setminus A\) es infinito.

Ejercicio 1.33 Sea \(f: A \to B\) una función inyectiva. Si \(B\) es finito, demuestra que \(A\) es finito.

Ejercicio 1.34 Sea \(f: A \to B\) una función sobreyectiva. Si \(A\) es finito, demuestra que \(B\) es finito.

Ejercicio 1.35 🔴 Demuestra que los siguientes conjuntos son numerables estableciendo una biyección con \(\mathbb{Z}^+\). \[ A = \{10, 20, 30, 40, ... \} ; \quad B = \{ 6, 7, 8, 9, ... \} ; \] \[ \mathbb{Z}^{-} = \{-1, -2, -3, -4, ... \} ; \quad C= \{ 1/n \mid n \in \mathbb{Z}^+\} \]

Ejercicio 1.36 🔴 Demuestra que el conjunto de los números enteros \(\mathbb{Z}\) es numerable.

Ejercicio 1.37 🔴 Demuestra que el conjunto de los números racionales \(\mathbb{Q}\) es numerable.

Ejercicio 1.38 🔴 Demuestra que la unión de dos conjuntos numerables es numerable.

Ejercicio 1.39 🔴 Demuestra que si \(A\) es un conjunto numerable, entonces \(A \times \mathbb{N}\) es numerable.

Ejercicio 1.40 🔴 Demuestra que el conjunto de todos los pares de números naturales \((m, n)\) tales que \(m + n = 100\) es finito. Determina su cardinal.

Ejercicio 1.41 🔴 Demuestra que el conjunto de todos los pares de números naturales \((m, n)\) tales que \(m < n\) es numerable.

Ejercicio 1.42 🔴 Demuestra que cualquier intervalo abierto \((a, b)\) con \(a < b\) en \(\mathbb{R}\) es no numerable y tiene cardinal \(\aleph_1\).

Ejercicio 1.43 🔴 Demuestra que \(\mathbb{Z} \times \mathbb{Z}\) es numerable.

Ejercicio 1.44 🔴 Demuestra que \(\mathbb{Q} \times \mathbb{Q}\) es numerable.

Ejercicio 1.45 🔴 Demuestra que la unión numerable de conjuntos numerables es numerable. Es decir, si \(\{A_n\}_{n \in \mathbb{N}}\) es una familia numerable de conjuntos numerables, entonces \(\bigcup_{n=0}^{\infty} A_n\) es numerable.

Ejercicio 1.46 🔴 Demuestra que el producto cartesiano de un número finito de conjuntos numerables es numerable.

Ejercicio 1.47 🔴 Sean \(A\) y \(B\) conjuntos disjuntos. Si \(A \cup B\) es numerable, ¿son necesariamente \(A\) y \(B\) numerables? Demuéstralo o da un contraejemplo.

Ejercicio 1.48 🔴 Sea \(A\) un conjunto no numerable y \(B\) un subconjunto numerable de \(A\). ¿Cuál es el cardinal de \(A \setminus B\)?

Ejercicio 1.49 🔴 Determina el cardinal de \(\mathbb{N} \times \mathbb{Q}\).

Ejercicio 1.50 🔴🔴 Demuestra que el conjunto de polinomios con coeficientes racionales es numerable.

Ejercicio 1.51 🔴🔴 Demuestra que el conjunto de los números algebraicos es numerable. (Un número algebraico es un número real que es raíz de un polinomio con coeficientes enteros).

Ejercicio 1.52 🔴🔴 Demuestra que el conjunto de los números reales \(\mathbb{R}\) no es numerable utilizando el argumento de la diagonal de Cantor.

Ejercicio 1.53 🔴🔴 Determina el cardinal de \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\).

Ejercicio 1.54 🔴🔴 Determina el cardinal del conjunto de todas las funciones de \(\mathbb{R}\) en \(\mathbb{R}\), es decir, \(|\mathbb{R}^{\mathbb{R}}|\).

Ejercicio 1.55 🔴🔴 Determina el cardinal del conjunto de todas las sucesiones de números reales.

Ejercicio 1.56 🔴🔴 Determina el cardinal del conjunto de todas las funciones continuas de \(\mathbb{R}\) en \(\mathbb{R}\).

Ejercicio 1.57 🔴🔴 Determina el cardinal del conjunto de todas las sucesiones infinitas de 0s y 1s.

Ejercicio 1.58 🔴🔴 Determina el cardinal del conjunto de todas las funciones de \(\mathbb{N}\) en \(\{0, 1\}\).

Ejercicio 1.59 🔴🔴 Compara los cardinales de \(\mathcal{P}(\mathbb{N})\) y \(\mathcal{P}(\mathcal{P}(\mathbb{N}))\). ¿Cuál es mayor?

Ejercicio 1.60 🔴🔴 Sea \(A\) un conjunto no numerable y \(B\) un conjunto cualquiera. ¿Cuál es el cardinal de \(A \cup B\)?

Ejercicio 1.61 🔴🔴 Sea \(A\) un conjunto no numerable y \(B\) un conjunto no vacío cualquiera. ¿Cuál es el cardinal de \(A \times B\)?

Ejercicio 1.62 🔴🔴 Demuestra que para cualquier \(n \in \mathbb{Z}^+\), el cardinal de \(\mathbb{R}^n\) es \(\aleph_1\).

Ejercicio 1.63 🔴🔴 Determina el cardinal del conjunto de todas las sucesiones de números naturales \(\mathbb{N}^{\mathbb{N}}\).

Ejercicio 1.64 🔴🔴 Demuestra que el cardinal del conjunto de funciones continuas de \(\mathbb{R}\) en \(\mathbb{R}\) es \(\aleph_1\). (Pista: Una función continua queda determinada por sus valores en los racionales).

Ejercicio 1.65 🔴🔴 ¿Cuál es el cardinal del conjunto de funciones discontinuas de \(\mathbb{R}\) en \(\mathbb{R}\)?

Ejercicio 1.66 🔴🔴 Dados conjuntos \(A\) y \(B\) con \(|A| \le |B|\). Compara los cardinales de \(\mathcal{P}(A)\) y \(\mathcal{P}(B)\).

Ejercicio 1.67 🔴🔴 ¿Puede la intersección de dos conjuntos no numerables ser numerable? Justifica tu respuesta.

Ejercicio 1.68 🔴🔴 Sean \(A\) y \(B\) conjuntos disjuntos. Si \(A\) es no numerable, ¿es \(A \cup B\) necesariamente no numerable?

Ejercicio 1.69 🔴🔴 Sea \(A\) un conjunto no numerable y \(\sim\) una relación de equivalencia en \(A\) tal que cada clase de equivalencia es numerable. ¿Qué puedes decir sobre la cardinalidad del conjunto cociente \(A/\sim\)? ¿Es necesariamente no numerable?

Ejercicio 1.70 🔴🔴 Sean \(A\) y \(B\) conjuntos con \(|A| = \aleph_0\) y \(|B| = \aleph_1\). Determina el cardinal del conjunto de todas las funciones inyectivas de \(A\) en \(B\).

Ejercicio 1.71 🔴🔴 Sean \(A\) y \(B\) conjuntos con \(|A| = \aleph_1\) y \(|B| = \aleph_0\). Determina si existen funciones sobreyectivas de \(A\) en \(B\). En caso afirmativo, ¿cuántas existen? (Considera el cardinal del conjunto de funciones sobreyectivas).

1.3 Divisibilidad y aritmética modular

Divisores y múltiplos. Máximo común divisor y mínimo común múltiplo. Algoritmo de Euclides. Lema de Bezout. Ecuaciones diofánticas.

1.3.1 Congruencias

Relación de congruencia módulo n. Propiedades de las congruencias. Sistemas de congruencias. Teorema chino del resto.

1.3.2 Anillos de enteros módulo n

Operaciones en Z/nZ. Elementos inversibles.

1.3.3 Aplicaciones

Criptografía (RSA, Diffie-Hellman). Teoría de números.

1.3.4 Ejercicios