An son conjuntos, definimos
Si el lector está leyendo este primer capítulo, cabe la posibilidad de que no esté demasiado habituado a probar teoremas, habilidad que solo se adquiere con práctica, y leyendo muchas demostraciones. Probamos nuestro primer teorema.
Teorema 1.1 (Leyes de Morgan) Supongamos que X, I y Ai para i ∈ I son conjuntos. Entonces
Demostración. Probamos (a), por ejemplo. Queremos probar que dos conjuntos son iguales. Por tanto, debemos probar que X − (⋃i∈I Ai) está contenido en ⋂i∈I (X − Ai), y la inclusión contraria. Sea x ∈ X − (⋃i∈I Ai). Esto significa que x ∈ X y que x ∉ ⋃i∈I Ai. Por la definición de unión de una colección de conjuntos, tenemos que x ∉ Ai para todo i ∈ I. Así, x ∈ X − Ai para todo i ∈ I, y por la definición de intersección de una colección de conjuntos, concluimos que x ∈ ⋂i∈I (X − Ai). Recíprocamente, si x ∈ ⋂i∈I (X − Ai), tenemos que x ∈ X y x ∉ Ai para todo i. Entonces x ∈ X y x ∉ ⋃i∈I Ai, y por tanto x ∈ X − (⋃i∈I Ai).
2
Los conjuntos se relacionan mediante aplicaciones. Si A y B son conjuntos, una aplicación o función de A en B, que escribimos
es una correspondencia (regla o criterio) que asigna a cada elemento a ∈ A un único elemento f(a) de B. A f(a) se le llama la imagen de a mediante f. El conjunto A se llama el dominio o conjunto inicial de f. El conjunto B se llama el codominio o conjunto final de f. El conjunto imagen
f(A) = {f(a) | a ∈ A}
es el subconjunto de B formado por todas las imágenes mediante f de los elementos de A.
Podemos imaginar una función como una máquina cuyos inputs son los elementos de A. Damos a ∈ A a la máquina y esta produce un output perfectamente determinado que es f(a) ∈ B. Para el lector riguroso que no esté satisfecho ni con la definición ni con la idea de la máquina, podemos definir una función f : A → B como un subconjunto X ⊆ A × B tal que X ∩ ({a} × B) tiene exactamente un elemento para todo a ∈ A; pero esto es innecesariamente complicado. Si pensamos un momento sobre esta última definición, observamos que X es el grafo de la función f.
El lector está seguramente acostumbrado a tratar con funciones entre números reales como las aplicaciones f : ℝ → ℝ dada por f(x) = x2 + 1, o g : ℝ → ℝ dada por g(x) = sen(x). O incluso con funciones h : ℝ × ℝ → ℝ definidas por
Ejercicio 1.1 Sean A y B conjuntos. Sea BA el conjunto de las aplicaciones de A en B. Si A tiene n elementos y B tiene m elementos, probar que BA tiene mn elementos.
Dos funciones f : A → B, g : C → D son iguales si A = C, B = D y f(a) = g(a) para todo a ∈ A. Por ejemplo, las funciones f : ℤ → ℤ y g : ℤ → ℕ dadas por f(z) = g(z) = z2 no son iguales porque sus conjuntos finales son distintos.
Para todo conjunto A, tenemos definida la función identidad 1A : A → A con 1A(a) = a para todo a ∈ A.
Con frecuencia, lo primero que nos preguntamos sobre una aplicación f es si es inyectiva o suprayectiva; estos dos adjetivos se asocian de forma natural a las funciones. Una aplicación f : A → B es inyectiva si f(a1) = f(a2) solo si a1 = a2, para a1, a2 ∈ A. En otras palabras, f es inyectiva si elementos distintos de A tienen imágenes distintas en B. Si queremos comprobar que una función f es inyectiva, escribimos la igualdad f(a1) = f(a2) y tratamos de averiguar si a1 es necesariamente igual a a2 o no. Informalmente, si f es una aplicación inyectiva, pensamos que B contiene un subconjunto (f(A)) que tiene las mismas propiedades que A.
Ejercicio 1.2 Si A tiene n elementos, B tiene m elementos, y f : A → B es injectiva, probar que n ≤ m.
Una aplicación f : A → B es suprayectiva si f(A) = B. En otras palabras, si para todo b ∈ B existe a ∈ A tal que f(a) = b. Si queremos comprobar si una función f es suprayectiva, elegimos un elemento b ∈ B arbitrario y lo intentamos expresar como f(a) para algún a de A.
Ejercicio 1.3 Si A tiene n elementos, B tiene m elementos, y f : A → B es suprayectiva, probar que n ≥ m.
Teorema 1.2 Supongamos que A y B tienen n elementos, y sea f : A → B. Entonces f es inyectiva si y solo si f es suprayectiva.
Demostración. Esta es la primera vez en este libro que probamos un teorema si y solo si, por lo que hacemos una pausa para explicar lo que significa. Cuando tengamos que probar que un enunciado P es verdadero si y solo si un enunciado Q es verdadero, tenemos que probar que P implica Q (esto es, suponiendo P demostramos Q) y que Q implica P (suponiendo Q demostramos P).
Escribamos
