Semana 1 - Conjuntos y Relaciones

Conjuntos, relaciones y funciones

Hilo conductor: los conjuntos dicen qué elementos hay; las relaciones, qué pares se conectan; las funciones, una salida única para cada entrada.

1. Conjuntos

Un conjunto es una colección de elementos donde no importan el orden ni las repeticiones. Para cualquier objeto debe poder decidirse si pertenece o no.

Pertenencia: $x \in A$ / $x \notin A$ .
No confundir con inclusión: $2 \in {1, 2}$ , pero ${2} \subseteq {1, 2}$ .
Por extensión: $A = {1, 2, 3}$ . Por comprensión: $A = {x \in Z : x > 0}$ .
Vacío: $\emptyset = {}$ .
Inclusión: $A \subseteq B ⟺ \forall x (x \in A \Rightarrow x \in B)$ .
Igualdad: $A = B ⟺ A \subseteq B \land B \subseteq A$ .

Operaciones

Operación	Traducción mental	Definición
$A \cup B$	o (inclusive)	${x : x \in A \lor x \in B}$
$A \cap B$	y	${x : x \in A \land x \in B}$
$A ∖ B$	en $A$ , no en $B$	${x : x \in A \land x \notin B}$
$A △ B$	o exclusivo	$(A ∖ B) \cup (B ∖ A)$
$A^{c}$ (en $U$ )	fuera de $A$	$U ∖ A$

Memoria: complemento = no; unión = o; intersección = y.
Si $A, B, C \subseteq U$ :

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cup B^{c}

A \cap (B \cup C) = (A \cap B) \cup (A \cap C), A \cup (B \cap C) = (A \cup B) \cap (A \cup C) .

Además, $A ∖ B = A \cap B^{c}$ solo al fijar el universo $U$ .

Conjunto de partes y producto cartesiano

$P (A) = {X : X \subseteq A}$ : el conjunto de todos los subconjuntos de $A$ .
$X \in P (A) ⟺ X \subseteq A$ . Siempre $\emptyset, A \in P (A)$ .
Si $| A | = n$ , entonces $| P (A) | = 2^{n}$ .
$A \times B = {(a, b) : a \in A, b \in B}$ ; son pares ordenados. Si son finitos, $| A \times B | = | A | | B |$ .

2. Lógica: el diccionario de conjuntos

Para un elemento fijo $x$ , tomar $p : x \in A$ y $q : x \in B$ permite leer las operaciones como lógica:

Conjuntos	Lógica	Cuándo falla
$A^{c}$	$\neg p$	$p$ es verdadera
$A \cup B$	$p \lor q$	ambas son falsas
$A \cap B$	$p \land q$	alguna es falsa
$A △ B$	$p \oplus q$	tienen el mismo valor
$A \subseteq B$	$p \Rightarrow q$	$p$ verdadera y $q$ falsa
$A = B$	$p \Leftrightarrow q$	tienen distinto valor

$\forall$ : para todo. $\exists$ : existe al menos uno. $\exists!$ : existe uno y solo uno.
Al negar, cambia el cuantificador y niega el predicado:

\neg \forall x P (x) ⟺ \exists x \neg P (x), \neg \exists x P (x) ⟺ \forall x \neg P (x) .

3. Relaciones

Una relación de $A$ en $B$ es un subconjunto $R \subseteq A \times B$ .
$x R y$ significa $(x, y) \in R$ . Una relación en $A$ cumple $R \subseteq A \times A$ .

Propiedad	Fórmula	Imagen mental
Reflexiva	$\forall x \in A, x R x$	cada uno se apunta a sí mismo
Simétrica	$x R y \Rightarrow y R x$	flecha de vuelta
Antisimétrica	$x R y \land y R x \Rightarrow x = y$	no hay ida y vuelta entre distintos
Transitiva	$x R y \land y R z \Rightarrow x R z$	los caminos de dos pasos se cierran

Ojo: antisimétrica $\neq$ “no simétrica”. Una relación puede ser ambas (por ejemplo, la igualdad).

Dos familias clave

Equivalencia = reflexiva + simétrica + transitiva. Agrupa elementos “equivalentes”.
La clase de $a$ es $[a] = {x \in A : x \sim a}$ . Dos clases son iguales o disjuntas; todas juntas forman una partición de $A$ . El conjunto cociente es $A / \sim = {[a] : a \in A}$ .
Orden = reflexiva + antisimétrica + transitiva. Compara o jerarquiza.
Es total si para todo $a, b \in A$ , $a R b$ o $b R a$ ; si no, es parcial. Ejemplos: $\leq$ es total en $R$ ; $\subseteq$ es parcial en $P (A)$ .

4. Funciones

Una función $f : A \to B$ es una relación que a cada $x \in A$ le asigna un único $y \in B$ :

\forall x \in A \exists! y \in B : f (x) = y .

$A$ : dominio (todas las entradas deben tener flecha).
$B$ : codominio (puede contener elementos sin flecha).
$Im (f) = {f (x) : x \in A} \subseteq B$ : valores que realmente se alcanzan.

Tipo	Criterio	En flechas hacia $B$
Inyectiva	$f (a) = f (b) \Rightarrow a = b$	a cada $y$ llega a lo sumo una
Sobreyectiva	$Im (f) = B$	a cada $y$ llega al menos una
Biyectiva	inyectiva y sobreyectiva	a cada $y$ llega exactamente una

Chequeo rápido: una función no puede tener una entrada sin imagen ni una entrada con dos imágenes. Varias entradas sí pueden compartir imagen: eso impide inyectividad, no que sea función.

Composición e inversa

Si $f : A \to B$ y $g : B \to C$ , primero va $f$ y después $g$ :

(g \circ f) (x) = g (f (x)) .

$f$ tiene inversa $f^{- 1} : B \to A$ si y solo si es biyectiva. Entonces

f^{- 1} \circ f = {id}_{A}, f \circ f^{- 1} = {id}_{B} .

Mantra final: función = “cada entrada, una salida”; biyectiva = “cada llegada, una sola entrada”.