Conjuntos, relaciones y funciones (Parte 1)

• Capítulo 1 trata sobre conjuntos, relaciones y funciones.*

Conjuntos

• Un conjunto es una colección de objetos llamados elementos.
• La propiedad definitoria es que se puede determinar si un objeto pertenece o no al conjunto.
• Ejemplos de conjuntos incluyen:
  • A = {1, 2, 3}
  • B = {∆, □}
  • C = {1, {1}, {2, 3}}
• N = {1, 2, 3, 4, ...} es el conjunto de números naturales.
• Z = {..., -2, -1, 0, 1, 2, ...} es el conjunto de números enteros.
• Q = {a/b; a ∈ Z, b ∈ N} es el conjunto de números racionales.
• R es el conjunto de números reales.
• C es el conjunto de números complejos.
• Ø o {} representa el conjunto vacío.

Observaciones sobre conjuntos

• El orden de los elementos no es relevante.
• No se consideran repeticiones de elementos.
• Si un elemento 'a' pertenece al conjunto A, se denota a ∈ A.
• Si un objeto 'b' no pertenece al conjunto A, se denota b ∉ A.

Pertenencia y no pertenencia

• Sea A = {1, 2, 3}:
  • 1 ∈ A
  • 2 ∈ A
  • 4 ∉ A
  • {1, 2} ∉ A
  • Ø ∉ A
• Sea B = {2, {1}, {2, 3}}:
  • {1} ∈ B
  • {2, 3} ∈ B
  • 1 ∉ B
  • 3 ∉ B

Cardinal de un conjunto

• El cardinal de un conjunto A, denotado #A, es la cantidad de elementos distintos que tiene A.
• Si el conjunto no tiene un número finito de elementos, se dice que es infinito, y se denota #A = ∞.
• #Ø = 0
• #{a, b, c} = 3 = #{1, 2, 3}
• #N = ∞
• Si A es finito, #A ∈ N ∪ {0}.

Definiciones de conjuntos

• Por extensión (listando elementos entre llaves), aplicable a conjuntos finitos.
• Por comprensión (a través de una propiedad), usualmente requiere la noción de subconjunto y un conjunto referencial.
• Los conjuntos infinitos N y Z pueden presentarse informalmente con puntos suspensivos, aunque es menos riguroso.

Diagramas de Venn

• Los conjuntos se representan gráficamente mediante diagramas de Venn.

Subconjuntos e inclusión

• Un conjunto B está contenido en A (B ⊆ A) si todo elemento de B es también un elemento de A.
• Si B no es un subconjunto de A, se nota B ⊈ A.
• Sea A = {1, 2, 3}:
  • {1} ⊆ A
  • {2, 3} ⊆ A
  • Ø ⊆ A
  • A ⊆ A
  • {3, 4} ⊈ A
• N ⊆ Z ⊆ Q ⊆ R ⊆ C.
• A ⊆ A y Ø ⊆ A para cualquier conjunto A.

Inclusión y pertenencia

• B ⊆ A si ∀b, b ∈ B ⇒ b ∈ A.
• B ⊈ A si ∃b ∈ B : b ∉ A.

Símbolos lógicos

• ∀ significa "para todo."
• ∃ significa "existe."
• ⇒ significa "implica."

Conjuntos por comprensión

• A = {x ∈ R : x ≥ -2}
• B = {k ∈ Z : k > -2}
• P = {n ∈ N : n es par}
• I = {k ∈ Z : k es impar}

Igualdad de conjuntos

• A = B ⇔ A ⊆ B y B ⊆ A.
• A y B tienen los mismos elementos, sin importar orden o repeticiones.

Combinatoria

• Si A es finito y B ⊆ A, entonces #B ≤ #A.

Conjunto de partes

• El conjunto de partes de A, P(A), contiene todos los subconjuntos de A.
• P(A) = {B : B ⊆ A}
• B ∈ P(A) ⇔ B ⊆ A.
• Si A = {1, 2, 3}, entonces P(A) = {Ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}.
• Para cualquier A, Ø ∈ P(A) y A ∈ P(A).
• P(Ø) = {Ø}.

Operaciones entre conjuntos

• Se asume que los conjuntos A, B, C... son subconjuntos de un conjunto referencial U.

Complemento

• El complemento de A (en U), A', son los elementos de U que no están en A:
  • A' = {b ∈ U : b ∉ A}
  • b ∈ U, b ∈ A' ⇔ b ∉ A
• Si U = {1, 2, 3} y A = {2}, entonces A' = {1, 3}.
• Si U = N y A = {2}, entonces A' = {n ∈ N, n ≠ 2}.
• Depende de U.
• Si U = N y P = {n ∈ N: n es par }, entonces P' = {n ∈ N: n es impar }.
• Ø' = U y U' = Ø
• (A')' = A

Unión

• La unión de A y B, A ∪ B, contiene los elementos de U que están en A o en B:
  • A ∪ B = {c ∈ U : c ∈ A o c ∈ B}
  • c ∈ U, c ∈ A ∪ B ⇔ c ∈ A o c ∈ B
• El "o" es no excluyente.
• Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10} ⊆ U = {1, ..., 10}, entonces A ∪ B = {1, 2, 3, 4, 5, 8, 10}.
• Si I = {x ∈ R : x ≤ 2} = (-∞, 2] y J = {x ∈ R : -10 < x < 10} = [-10, 10) ⊆ U = R, entonces I ∪ J = {x ∈ R : x < 10} = (-∞, 10).
• A ∪ B = B ∪ A (conmutatividad).
• A ∪ Ø = A
• A ∪ U = U
• A ∪ A' = U

Inclusión prueba

• A ∪ A' ⊆ U: Si a ∈ (A ∪ A'), entonces a ∈ A o a ∈ A', lo que implica que a ∈ U.
• U ⊆ A ∪ A': Si a ∈ U, entonces a ∈ A o a ∉ A. Si a ∈ A, entonces a ∈ (A ∪ A'). Si a ∉ A, entonces a ∈ A' y luego a ∈ (A ∪ A').

Intersección

• La intersección de A y B (A ∩ B) contiene los elementos de U que están tanto en A como en B:
  • A ∩ B = {c ∈ U : c ∈ A y c ∈ B}
  • c ∈ (A ∩ B) ⇔ c ∈ A y c ∈ B
• Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10} ⊆ U = {1, ..., 10}, entonces A ∩ B = {3, 5}.
• Si I = {x ∈ R : x ≤ 2} = (-∞, 2] y J = {x ∈ R : -10 < x < 10} = [-10, 10) ⊆ U = R, entonces I ∩ J = {x ∈ R : -10 < x ≤ 2} = [-10, 2].
• A ∩ B = B ∩ A (conmutatividad).
• A ∩ Ø = Ø
• A ∩ U = A
• A ∩ A' = Ø

Conjuntos disjuntos

• Cuando A ∩ B = Ø, A y B son conjuntos disjuntos.

Unión, intersección y complemento

• La unión y la intersección no dependen del conjunto referencial U.

Leyes y operaciones

• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C): Se demuestra mostrando la doble inclusión.
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Leyes de De Morgan

• (A ∪ B)' = A' ∩ B'
• (A ∩ B)' = A' ∪ B'

Diferencia

• A - B son los elementos de A que no son elementos de B:
  • A - B = {a ∈ A : a ∉ B}
  • a ∈ (A - B) ⇔ a ∈ A y a ∉ B.
• A - Ø = A
• A - U = Ø
• A - A = Ø
• A - A' = A
• A ∩ B = B ∩ A, pero A - B ≠ B - A en general.

Diferencia simétrica

• A ∆ B son los elementos pertenecen a A o a B, pero no a ambos:
  • A ∆ B = {c ∈ U : (c ∈ A y c ∉ B) o (c ∈ B y c ∉ A)}
• A ∆ B = (A - B) ∪ (B - A) = (A ∩ B') ∪ (B ∩ A') = (A ∪ B) - (A ∩ B).
• Si A = {1, 2, 3, 5, 8} y B = {3, 4, 5, 10} ⊆ U = {1, ..., 10}, entonces A △ B = {1, 2, 4, 8, 10}.
• Si I = (-∞, 2] y J = [-10, 10) ⊆ U = R, entonces I △ J = (-∞, -10) ∪ (2, 10].
• A △ B = B △ A (simetría).
• A △ Ø = A
• A △ U = A'
• A △ A = Ø
• A △ A' = U

Combinatoria: Cardinal de la unión y el complemento

• A, B conjuntos finitos dentro de U.
• Si A y B son disjuntos, entonces #(A ∪ B) = #A + #B.
• En general:
  • #(A ∪ B) = #A + #B - #(A ∩ B)
• Si U es finito, #(A') = #U - #A.
• #(A - B) = #A - #(A ∩ B)
• #(A △ B) = #A + #B - 2#(A ∩ B)

Conectores lógicos:

• ¬ (“no”, o “NOT”).
• ∨ (“o” no excluyente, u “OR”).
• ∧ (“y”, o “AND”).
• "W" (“o excluyente”, u “XOR”).

Producto cartesiano

• Dados A y B, el producto cartesiano A × B es el conjunto de pares ordenados:
  • A × B := {(a, b) : a ∈ A, b ∈ B}
• Si A = {1, 2, 3} y B = {a, b}, entonces A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)} y B × A = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}.
• Si A = B = R, R × R es el espacio euclídeo R².
• A ≠ B entonces A × B ≠ B × A.
• A × Ø = Ø, Ø × B = Ø.
• Si A ⊆ U, B ⊆ V, entonces A × B ⊆ U × V.
• El producto cartesiano de n conjuntos A₁, ..., Aₙ es el conjunto de n-uplas ordenadas:
  • A₁ × ... × Aₙ := {(a₁, ..., aₙ) : a₁ ∈ A₁, ..., aₙ ∈ Aₙ}

Combinatoria

1. Si A y B son conjuntos finitos, #(A × B) = #A · #B.
2. Si A₁, ..., Aₙ son conjuntos finitos, #(A₁ × ... × Aₙ) = #A₁ · ... · #Aₙ.
3. Si A es un conjunto finito, #(P(A)) = 2#A.

• A cada subconjunto B de A = {a₁, ..., aₙ} se le asocia un elemento del producto cartesiano {0, 1}ⁿ.

Relaciones

• Un subconjunto R del producto cartesiano A × B se llama una relación de A en B:
  • R ⊆ P(A × B)

Ejemplos de relaciones

Sean A = {a, b, c} y B = {1, 2}:

• R₁ = {(a, 1), (b, 1), (b, 2)}
• R₂ = {(a, 2), (b, 2), (c, 1), (c, 2)} son ejemplos de relaciones de A en B.
• R₃ = Ø
• R₄ = A × B
• R₅ = {(1, c), (2, a)} es un ejemplo de relación de B en A. Sean A = B = R:
• R₆ = {(x, y) ∈ R² : x² = y²}
• R₇ = {(x, y) ∈ R² : x = y²}
  son relaciones de R en R.

Pertenencia Relacionada

• Dados a ∈ Ay b ∈ B y una relación R de A en B, se dice que a está relacionado con b (por la relación R) si (a, b) ∈ R, en ese caso se escribe a R b. Si a no está relacionado con b, (a, b) ∉ R, se escribe a R b.
• El número de relaciones de A = {a, b, c} en B = {1, 2} es 2^6 (64)

Proposición Combinatoria

• Dados conjuntos finitos Am y Bn con m y n elementos respectivamente, el número de posibles relaciones desde Am a Bn es 2^(m*n)

Relaciones en un conjunto

• Una relación R en un conjunto A es un subconjunto de A × A, es Cuando RCAXA

Ejemplos de relaciones

• Dados conjuntos finitos Am y Bn con m y n elementos respectivamente, el número de posibles relaciones desde Am a Bn es 2(m⋅n). En un conjunto, toda la igualdad de elementos siempre es una relación en cualquier conjunto A: R{(a, α)a ∈ A}, es decir Va, b: aRb⇔ a = b
• Dado conjunto es una relación en R, y < es una relación en P(A), cualquiera sea el conjunto A.

Relaciones

• una relacion R_en A se puede representar en la el A(vertice) y los arcos(son graficas dirigidas) se representan dependiendo elemtnos estan relacionados

Definición de tipos de Relaciones

Reflexiva

• una relacion REFLEXIVA si para todo elemento {α, α) ∈ A ,Va∈ A (para otro, aRa, Va e A).

Simetrica

• si cada vez que un par {α, B} ∈R entones {B, α) ∈R Tambien o "Vα, b ∈ A, αRb⇒ B, α)

Antisimetrica

• Si cada que un par (a,b) ∈ r con a!=b , entonces el par (B, a) e R (dicho de otra menera Va, b ∈ A, aRb y bRa => a ==b

Transitiva

para trios de elementos a , b y c tal que {a,B}∈R y (B,C)ER → (a,c) ER tambien (dicho de otra manera, Va, b, c∈a, aRb y bRc → aRc).

Relaciones de equivalencia

• La relación de equivalencia cuando es una REFLEXIVA, SIMETRICA, y Transitiva ###Relaciones en una de orden
• Reflexiva
• Antisimetrica
• Transitiva