Conjuntos, relaciones y funciones

El lenguaje del curso

La clase siguiente define los números naturales mediante una función, el sucesor, que es inyectiva y no alcanza al $1$. La unidad siguiente construye los enteros y los racionales como clases de una relación de equivalencia; la clase de combinatoria define el número de elementos mediante biyecciones; el orden de los naturales es una relación de orden; y la tercera unidad compone e invierte funciones reales. Todas estas palabras pertenecen a un mismo lenguaje, que conviene fijar antes de usarlo, junto con los primeros teoremas que el curso invocará después.

Conviene advertir qué se anticipa. Los ejemplos usan números naturales pequeños con su orden, su suma, su producto, la divisibilidad y el resto de una división, tal como se aprenden en la escuela. La clase siguiente define los naturales mediante los axiomas de Peano, y las clases de la unidad definen esas operaciones y demuestran sus propiedades sin usar ningún ejemplo de esta, de modo que no hay círculo. Ningún teorema de esta clase depende de los ejemplos: los números solo sirven para ver los teoremas en acción.

Lo que se admite

Un conjunto es una colección de objetos, sus elementos; se escribe $a \in A$ para decir que $a$ pertenece a $A$, y $a \notin A$ para negarlo. Conjunto y pertenencia no se definen: son nociones primitivas, como el $1$ y el sucesor en la aritmética. Ahora bien, no toda propiedad define un conjunto. Si existiera el conjunto $R$ de todos los conjuntos que no se pertenecen a sí mismos, la pregunta de si $R$ pertenece a $R$ no tendría respuesta, porque por la definición de $R$ se tendría $R \in R \leftrightarrow R \notin R$. Esta contradicción, descubierta por Russell en 1901, obliga a restringir la formación de conjuntos: una propiedad solo selecciona elementos de un conjunto ya dado.

Hecho admitido (reglas de la teoría intuitiva de conjuntos). Se admiten sin demostración las reglas de la teoría intuitiva de conjuntos que esta clase usa: dos conjuntos con los mismos elementos son iguales; de un conjunto dado $A$ y una propiedad $P$ se forma el conjunto $\{ x \in A : P(x) \}$ de los elementos de $A$ que la cumplen; y existen el conjunto vacío, el conjunto $\{a, b\}$ cuyos únicos elementos son $a$ y $b$, la unión de los elementos de un conjunto de conjuntos y el conjunto de los subconjuntos de un conjunto. La existencia de un conjunto con las propiedades del conjunto de los naturales se admite en la clase siguiente.

Estas reglas forman parte de los axiomas de Zermelo y Fraenkel, cuyo estudio pertenece a la teoría de conjuntos y excede este curso; por eso se admiten, y se declaran para que se sepa exactamente qué se usa.

Lógica de los cuantificadores

Las demostraciones combinan enunciados con los conectivos $\neg$, $\wedge$, $\vee$, $\rightarrow$ y $\leftrightarrow$, cuyas leyes se estudian en el curso complementario Lógica Matemática I: Lógica Proposicional, a partir de su lenguaje; aquí basta recordar que la implicación $p \rightarrow q$ solo es falsa cuando $p$ es verdadera y $q$ falsa, que equivale a su contrapositiva $\neg q \rightarrow \neg p$, y que las leyes de De Morgan niegan una conjunción o una disyunción:

Para hablar de conjuntos hacen falta, además, enunciados sobre todos los elementos o sobre alguno. Si $P(x)$ es una propiedad de los elementos de $A$, el enunciado $(\forall x \in A)\,P(x)$, que se lee «para todo $x$ de $A$, $P(x)$», afirma que todos los elementos de $A$ la cumplen; el enunciado $(\exists x \in A)\,P(x)$, «existe un $x$ de $A$ tal que $P(x)$», afirma que al menos uno la cumple; y $(\exists! x \in A)\,P(x)$ afirma que exactamente uno la cumple. Los signos $\forall$ y $\exists$ se llaman cuantificadores, universal y existencial.

Hecho admitido (negación de los cuantificadores). Negar que todos los elementos cumplen una propiedad es afirmar que alguno no la cumple, y negar que alguno la cumple es afirmar que ninguno la cumple:

Estas reglas, propias de la lógica de primer orden, se admiten; extienden las leyes de De Morgan, porque si $A = \{a, b\}$ el universal es $P(a) \wedge P(b)$ y el existencial es $P(a) \vee P(b)$. El orden de los cuantificadores importa: el enunciado $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ dice que todo natural tiene otro mayor, y es verdadero; el enunciado $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ dice que hay un natural mayor que todos, también mayor que sí mismo, y es falso.

La forma lógica de un enunciado dicta la manera de demostrarlo. Las estrategias que esta clase usa son las siguientes; su justificación lógica se estudia en la clase sobre las técnicas de deducción.

• Para demostrar $(\forall x \in A)\,P(x)$, se toma un elemento $x$ de $A$ cualquiera, sin suponer de él nada más que su pertenencia a $A$, y se demuestra $P(x)$.
• Para demostrar $(\exists x \in A)\,P(x)$, se exhibe un elemento concreto de $A$ que cumple $P$; para refutar $(\forall x \in A)\,P(x)$, basta un contraejemplo, un elemento que no la cumple.
• Para demostrar $p \rightarrow q$, se supone $p$ y se deduce $q$; o bien se demuestra la contrapositiva $\neg q \rightarrow \neg p$; o bien se supone $p \wedge \neg q$ y se llega a una contradicción.
• Para demostrar $p \leftrightarrow q$, se demuestran las dos implicaciones $p \rightarrow q$ y $q \rightarrow p$.

Conjuntos

Pertenencia, igualdad e inclusión

Un conjunto se describe por extensión, enumerando sus elementos entre llaves, como $\{1, 2, 3\}$, o por comprensión, mediante una propiedad, como $\{ n \in \mathbb{N} : n \leq 3 \}$, que es el mismo conjunto. La regla de extensionalidad dice que un conjunto queda determinado por sus elementos:

De ello se sigue que en una descripción por extensión no importan ni el orden ni las repeticiones: $\{1, 2, 2\}$ y $\{2, 1\}$ son el mismo conjunto, porque tienen los mismos elementos. Se sigue también que hay un solo conjunto sin elementos, el conjunto vacío $\emptyset$: dos conjuntos sin elementos tienen los mismos elementos, es decir, ninguno.

Definición (inclusión). Un conjunto $A$ está contenido en un conjunto $B$, o es un subconjunto de $B$, cuando todo elemento de $A$ es elemento de $B$:

Si además $A \neq B$, se dice que $A$ es un subconjunto propio de $B$.

El conjunto vacío está contenido en todo conjunto $A$, porque la implicación $x \in \emptyset \rightarrow x \in A$ tiene siempre el antecedente falso y es, por tanto, verdadera. Conviene distinguir la pertenencia de la inclusión: $1 \in \{1, 2\}$ y $\{1\} \subseteq \{1, 2\}$ son verdaderos, mientras que $\{1\} \in \{1, 2\}$ es falso, porque los únicos elementos de $\{1, 2\}$ son $1$ y $2$, y el conjunto $\{1\}$ no es igual a ninguno de ellos: $\{1\} \neq 1$, porque el conjunto que tiene por único elemento al $1$ no se confunde con el $1$, y $\{1\} \neq 2$.

Unión, intersección y diferencia

Definición (operaciones con conjuntos). La unión de $A$ y $B$ es el conjunto de los elementos que pertenecen a alguno de ellos; la intersección, el de los que pertenecen a ambos; y la diferencia $A \setminus B$, el de los que pertenecen a $A$ y no a $B$:

Si $B \subseteq A$, la diferencia $A \setminus B$ se llama complemento de $B$ relativo a $A$. Dos conjuntos son disjuntos cuando su intersección es vacía.

Cada operación traduce un conectivo: la unión, la disyunción; la intersección, la conjunción; la diferencia, la conjunción con una negación. Si esto es así, cada ley lógica produce una ley de los conjuntos: la unión y la intersección son conmutativas, asociativas y distributivas una respecto de la otra porque lo son los conectivos, y todas estas leyes se demuestran como el teorema siguiente. El complemento se toma siempre respecto de un conjunto de referencia, porque un conjunto de todo lo que no está en $B$ reconstruiría la paradoja de Russell.

El conjunto de partes

Los subconjuntos de un conjunto forman a su vez un conjunto, cuya existencia se admitió al comienzo. El conjunto de partes de $A$, que se denota $\mathcal{P}(A)$, es el conjunto cuyos elementos son los subconjuntos de $A$:

Por ejemplo, el conjunto de partes de $\{1, 2, 3\}$ tiene ocho elementos: el vacío, tres conjuntos de un elemento, tres de dos elementos y el propio $\{1, 2, 3\}$.

Para todo conjunto $A$, el vacío y el propio $A$ son elementos de $\mathcal{P}(A)$, y para cada $a$ de $A$ se tiene $\{a\} \in \mathcal{P}(A)$, mientras que $a$ no es, en general, elemento de $\mathcal{P}(A)$. En la clase sobre combinatoria se demostrará que un conjunto de $n$ elementos tiene $2^n$ subconjuntos.

Pares ordenados y producto cartesiano

Un punto del plano, una fracción o una resta pendiente se describen con dos objetos en un orden determinado: el par $(3, 5)$ no es el par $(5, 3)$. El conjunto $\{3, 5\}$ no sirve para representarlo, porque es igual a $\{5, 3\}$. Lo único que se exige de un par ordenado es su propiedad característica: dos pares son iguales si y solo si tienen la misma primera componente y la misma segunda componente. Kuratowski observó en 1921 que basta la noción de conjunto para construir un objeto con esa propiedad.

Definición (par ordenado). El par ordenado de primera componente $a$ y segunda componente $b$ es el conjunto

Demostrada la propiedad característica, la construcción de Kuratowski puede olvidarse: todo lo que el curso dice de los pares se deduce de ella.

Definición (producto cartesiano). El producto cartesiano de $A$ y $B$ es el conjunto de los pares cuya primera componente pertenece a $A$ y cuya segunda componente pertenece a $B$:

La escritura $\{ (a, b) : a \in A \wedge b \in B \}$ no es por sí sola una de las reglas admitidas, que solo permiten separar elementos de un conjunto ya formado. Ahora bien, ese conjunto existe: si $a \in A$ y $b \in B$, los conjuntos $\{a\}$ y $\{a, b\}$ están contenidos en $A \cup B$, y por tanto son elementos de $\mathcal{P}(A \cup B)$; de ello se sigue que el par $(a, b) = \{ \{a\}, \{a, b\} \}$ está contenido en $\mathcal{P}(A \cup B)$, es decir, es un elemento de $\mathcal{P}(\mathcal{P}(A \cup B))$. Por tanto, el producto cartesiano se forma por separación dentro de ese conjunto, que existe por las reglas admitidas: $A \cup B$ es la unión de los elementos de $\{A, B\}$, y se toma dos veces el conjunto de partes.

El nombre recuerda a Descartes: el plano de la geometría analítica es $\mathbb{R} \times \mathbb{R}$. El producto no es conmutativo: $\{1\} \times \{2\}$ contiene solo a $(1, 2)$, y $\{2\} \times \{1\}$ solo a $(2, 1)$, que es distinto por la propiedad característica.

Relaciones

Decir que $2$ divide a $6$, que $3$ es menor que $5$ o que dos días caen en el mismo día de la semana es afirmar que ciertos pares de objetos están relacionados. Si esto es así, una relación queda determinada por los pares que relaciona, y puede definirse como un conjunto de pares.

Definición (relación). Una relación de $A$ en $B$ es un subconjunto $R$ del producto $A \times B$; una relación en $A$ es una relación de $A$ en $A$. Si $(a, b) \in R$, se dice que $a$ está relacionado con $b$ por $R$.

Por ejemplo, la relación «menor o igual que» en $\{1, 2, 3\}$ es el conjunto de pares $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Para las relaciones de uso frecuente se escribe un signo entre los términos, como $a \leq b$ o $a \mid b$, en lugar de $(a, b) \in R$. Cuatro propiedades de una relación en un conjunto se repiten en todo el curso.

Definición (propiedades de las relaciones). Una relación $R$ en $A$ es reflexiva, simétrica, antisimétrica o transitiva cuando cumple, respectivamente, las condiciones siguientes.

• Es reflexiva si todo elemento está relacionado consigo mismo: $(\forall a \in A)\,((a, a) \in R)$;
• Es simétrica si la relación de $a$ con $b$ implica la de $b$ con $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• Es antisimétrica si dos elementos relacionados en ambos sentidos son iguales: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• Es transitiva si la relación de $a$ con $b$ y la de $b$ con $c$ implican la de $a$ con $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

En la cuadrícula de $A \times A$, una relación es un conjunto de puntos. Es reflexiva cuando contiene toda la diagonal, la de los pares $(a, a)$; es simétrica cuando su dibujo es simétrico respecto de la diagonal; y es antisimétrica cuando ningún punto fuera de la diagonal tiene a su simétrico en la relación. Antisimétrica no significa «no simétrica»: la igualdad es ambas cosas, y el problema propuesto 1 pide una relación que no sea ninguna de las dos.

Relaciones de equivalencia

La relación «tener la misma paridad» se comporta como una igualdad parcial: identifica los números que coinciden en un aspecto, su paridad, y olvida los demás. Las tres propiedades que la hacen comportarse así reciben un nombre.

Definición (relación de equivalencia). Una relación en $A$ es una relación de equivalencia cuando es reflexiva, simétrica y transitiva. Se escribe entonces $a \sim b$, y se dice que $a$ es equivalente a $b$. La clase de $a$ es el conjunto de los elementos equivalentes a $a$, y cada uno de ellos es un representante de la clase:

El conjunto de todas las clases se llama conjunto cociente y se denota $A/{\sim}$.

Son relaciones de equivalencia la igualdad, cuyas clases tienen un solo elemento; la misma paridad, con dos clases; tener el mismo resto al dividir por $3$, con tres; y caer en el mismo día de la semana, con siete, que es el problema resuelto 3. En general, si $g$ es una función definida en $A$, la relación $g(x) = g(y)$ hereda de la igualdad las tres propiedades, y el problema resuelto 5 muestra que toda equivalencia es de esta forma.

Las clases dividen, por tanto, el conjunto en bloques que no se solapan. Este modo de dividir un conjunto merece una definición propia.

Definición (partición). Una partición de un conjunto $A$ es un conjunto de subconjuntos de $A$, llamados bloques, que no son vacíos, que son disjuntos dos a dos y cuya unión es $A$; equivalentemente, cada elemento de $A$ pertenece a exactamente un bloque.

Dar una equivalencia en $A$ y dar una partición de $A$ son, por tanto, dos maneras de decir lo mismo; el problema resuelto 4 lo aprovecha para contar equivalencias. El conjunto cociente es la partición vista como un conjunto nuevo: al pasar de $A$ a $A/{\sim}$, los elementos equivalentes se funden en uno solo.

Del mismo modo, en la clase sobre los números racionales dos fracciones $(p, q)$ y $(r, s)$ son equivalentes cuando $ps = qr$, y un racional es una clase; y en la clase sobre las congruencias, los restos módulo $n$ son las clases de una equivalencia entre enteros.

Relaciones de orden

La divisibilidad del ejemplo anterior no es simétrica sino antisimétrica: en lugar de identificar elementos, los ordena. Las relaciones de este tipo reciben un nombre propio.

Definición (orden). Una relación en $A$ es una relación de orden, u orden parcial, cuando es reflexiva, antisimétrica y transitiva; se escribe entonces $a \preceq b$, y se dice que $a$ precede a $b$. El orden es total cuando dos elementos cualesquiera son comparables, es decir, cuando para todos $a$ y $b$ se tiene $a \preceq b$ o $b \preceq a$.

Son órdenes la relación $\leq$ entre naturales, que es total por la tricotomía demostrada en la clase sobre las operaciones con números naturales; la inclusión, por el teorema de sus propiedades, que no es total, porque $\{1\}$ y $\{2\}$ no son comparables; y la divisibilidad entre naturales, cuya antisimetría se demuestra en la clase sobre la divisibilidad, que no es total, porque ni $2 \mid 3$ ni $3 \mid 2$. Un orden finito se dibuja con un diagrama de Hasse: un punto por elemento, con $b$ más arriba que $a$ cuando $a$ precede a $b$, y un segmento cuando entre ambos no hay ningún otro elemento; la transitividad permite omitir los demás segmentos.

Definición (cotas y elementos extremos). Sean $\preceq$ un orden en $A$ y $X$ un subconjunto de $A$. Las cotas y los elementos extremos de $X$ se definen como sigue.

• Un elemento $c$ de $A$ es una cota inferior de $X$ si precede a todos los elementos de $X$, y una cota superior si todos los elementos de $X$ lo preceden.
• Un mínimo de $X$ es una cota inferior de $X$ que pertenece a $X$, y un máximo es una cota superior que pertenece a $X$.
• Un elemento $m$ de $X$ es minimal si ningún elemento de $X$ distinto de él lo precede, y maximal si él no precede a ningún elemento de $X$ distinto de sí mismo.
• El ínfimo de $X$ es el máximo del conjunto de sus cotas inferiores, y el supremo es el mínimo del conjunto de sus cotas superiores, cuando existen.