Bloque de Colores

Funciones (Definiciones Básicas)

Icono de Post August 10 2009 :: Apuntes, Teoría de Conjuntos ::

Definición de Función.

Sea F una relación de A en B. F es una función si se cumple que:

F: A -> B <=> ∀a ∈ A( ∃b ∈ B ( (a, b) ∈ F ∧ ( (a, c) ∈ F => b = c)))

Coloquialmente para todo elemento de A existe un elemento de B tal que (a, b) ∈ F y este elemento es unico.

Considerando esto se suele expresar el valor de f  en a es b o en simbolos:

f(a) = b

Composición de Funciones

Sean f: A -> B y g: B -> C, entonces (g o f) (a) : A -> C es equivalente a g ( f (a) ) .

Funciones inyectivas (uno a uno)

f es inyectiva si se cumple que:

∀a1 ∈ A ( ¬∃ a2 ∈ A ( f(a1) = f(a2) )  

Funciones suryectivas

f : A -> B es suryectiva si se cumple que:

∀b ∈ B( ∃ a ∈ A( f(a) = b) )

Función inversa

Si f: A -> B es inyectiva y suryectiva se cumple que:

  • f-1: B -> A también es función.
  • (f o f-1) = IA
  • (f-1 o f) = IB

Donde IC es la función identidad de C, I: C -> C tal que ∀ c ∈ C ( I(c) = c) ).

Referencias

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Funciones (Definiciones Básicas)

Relaciones sobre conjuntos (Definiciones y Propiedades Básicas)

Icono de Post May 7 2009 :: Apuntes, Teoría de Conjuntos ::

Definiciones Iniciales

Producto Cartesiano de A × B
A × B = {(a, b) | a ∈ A ∧ b ∈ B }
En particular, si A = B, se escribe A2 = {(a, b) | a ∈ A ∧ b ∈ A}

Relación
Sean A, B Conjuntos entonces R ⊆ A × B es una relación de A a B.

Dominio de R
Dom(R) = {a ∈ A | ∃b ∈ B((a, b) ∈ R)}

Rango de R
Ran(R) = {b ∈ B | ∃a ∈ A((a, b) ∈ R)}

Inversa de R
R-1 = {(b, a) ∈ B × A | (a, b) ∈ R}

Composición de S con R
S o R = {(a, c) ∈ A × C | (a, b) ∈ R ∧ (b, c) ∈ S}

Propiedades Posibles de las relaciones

Reflexiva
∀x ∈ R (x R x )

Simétrica
∀x, y ∈ R ( x R y -> y R x)

Transitiva
∀x,y,z ∈ R ( x R y ∧ y R z -> x R z)

Antisimetrica
∀x,y ∈ R ( x R y ∧ y R x -> x = y)

Irreflexiva
∀x ∈ A ((x, x) ∉ R)

Tricotomia
∀x ∈ A, ∀y ∈ A ( x R y ∨ y R x ∨ x = y)

Relaciones de Orden

Sea R una relación sobre un conjunto A, si R es Reflexiva, Transitiva y Antisimétrica se dice que R es un orden parcial sobre A.
Sera un orden total si ademas cumple que:
∀x,y ∈ A( x R y ∨ y R x)

Si R es irreflexiva y transitiva, se la llama un orden parcial estricto. Si ademas cumple Tricotomia, es un orden total estricto.

Elementos menores y mínimos

Sea R un Orden parcial en un conjunto A, B ⊆ A y b ∈ B. b es el elemento menor en B para R si ∀x ∈ B(b R x ). b es un elemento mínimo en B para R si ∀x ∈ B( x R b -> x = b ).

Nota: Sea R es un orden parcial sobre A y B ⊆ A. Se cumple que si B tiene un elemento menor, entonces este elemento es único, es mínimo y es el único mínimo. ( Sin embargo un elemento puede ser mínimo pero no ser menor. ) Si R es un orden total se cumple que si b es un elemento mínimo de B entonces es el menor elemento de B.

Cotas Inferiores y Superiores

Sea R un orden parcial en A, B ⊆ A y a ∈ A. a es una cota inferior de B si ∀b ∈ B( a R b ). Es una cota superior si ∀b ∈ B( b R a).

Sea U el conjunto de todas las cotas superiores de A, Si U tiene un elemento menor entonces este elemento es la cota superior menor de B.
Sea U el conjunto de todas las cotas inferiores de A, Si U tiene un elemento mayor entonces este elemento es la cota inferior mayor de B.

Cerraduras ( Closures )

Sea R una Relación en A. Sea S ⊆ A x A, si se cumple que: R ⊆ S,  S es reflexiva, ∀T ⊆ A x A( R ⊆ T ∧ T es reflexiva -> S ⊆ T) entonces S es la cerradura reflexiva de R.
De forma equivalente se definen las cerraduras Transitiva y Simétrica..

Relaciones de Equivalencia

Sea R una relación en A. Si R es reflexiva, simétrica y transitiva, se la llama una relación de equivalencia en A.  

Supongamos que A es un conjunto y F ∈ P(A), si se cumple que ∀X ∈ F, Y ∈ F( X ≠ Y -> X ∩ Y = ∅ ) se dice que F es disjunto en pares (pairwise disjoint). Si F cumple que: ∪F = A, F es disjunto en pares, ∀X ∈ F( X ≠ ∅ ), entonces F es una partición de A.

Toda relación de equivalencia establece una partición sobre el conjunto sobre el que esta definida.

Sea R una relación de equivalencia sobre A, x ∈ A. La clase de equivalencia de x respecto a R es el conjunto:
[x]R = { y ∈ A | y R x}
Se define entonces el conjunto de todas las clases de equivalencia sobre A determinados por R como A / R ( A modulo R ) tal que:
A / R = { [x]R | x ∈ A } = { X ⊆ A | ∃x ∈ A(X = [x]R)}

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Relaciones sobre conjuntos (Definiciones y Propiedades Básicas)

Ejercicio 4.7 de THRTLMP

Icono de Post September 10 2008 :: Lógica, Teoría de Conjuntos ::

Se nos pide demostrar que siendo A un conjunto de conjuntos, el conjunto { x ∈ A | x ∉ x } ∉ A. Es interesante y por eso lo blogueo porque es una aplicación de la paradoja de Russell.

Demostración

Llamemos B al conjunto { x ∈ A | x ∉ x }. Supongamos que B ∈ A y consideremos a B con respecto a si mismo desde la relación ∈, o bien B ∈ B o bien B∉ B.

Supongamos que B ∈ B entonces por la propia definición de B, B ∉ B, lo cual es una contradicción. Ahora si B ∉ B también por la definición de B sigue que B ∈ B, lo cual también es una contradicción.

Dado que nuestra premisa original nos lleva siempre a una contradicción, debe ser falsa, por consiguiente B ∉ A.

Es interesante también como este ejercicio sirve de introducción a los tipos y clases de Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 4.7 de THRTLMP

Teoría de Conjuntos ( Definiciones y Formulas Básicas )

Icono de Post September 10 2008 :: Apuntes, Teoría de Conjuntos ::

Definiciones

Conjunto: Colección de Objetos. A, B, C..
Elemento: Objeto dentro de un conjunto. a, b, c.
Representación por extensión.
A = {a, b, c, d}
Representación por comprensión.
A = {x | x < 10 ∧ x > -100}
A = {x | Φ(x) }
∈ pertenece a, es elemento de

∪ Union
A ∪ B = {x | x ∈ A ∨ x ∈ B}
∩ Intersección
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Ac Complemento
Ac = {x | x ∉ A}

Equivalencias Basicas

Doble negación
A = (Ac)c

Idempotencia
A ∪ A = A
A ∩ A = A

De morgan
(A ∪ B)c = (Ac ∪ Bc)
(A ∩ B)c = (Ac ∩ Bc)

Conmutativa
(A ∪ B) = (B ∪ A)
(A ∩ B) = (B ∩ A)

Asociativa
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributiva
A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C)
A ∪ (B ∩ C) = (A ∩ B) ∪ (A ∩ C)

Absorción
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A

Universo, Conjunto Vacio

U Universo
∅ Conjunto Vacio

c = U
Uc = ∅

Dominancia
U ∪ A = U
∅ ∩ A = ∅

Identidad
U ∩ A = A
∅ ∪ A = A

Ley del medio excluido
A ∪ Ac = U

Contradicción
A ∩ Ac = ∅

Inclusión, Inclusión estricta, Equivalencia, Resta, Diferencia simetrica

Definiciones

⊆ Inclusión
A ⊆ B = {x | x ∈ A => x ∈ B}
⊂ Inclusión Estricta
A ⊂ B <=> ∀x (x ∈ A => x ∈ B) ∧ ∃y (y ∈ B ∧ y ∉ A)
= Equivalencia
A = B <=> A ⊆ B ∧ B ⊆ A
– Resta
A – B = {x | x ∈ A ∧ x ∉ B}
Δ Diferencia Simetrica
A Δ B = {x | x ∈ A ∨ x ∈ B ∧ ¬ (x ∈ A ∧ x ∈ B) } = A ∪ B -(A ∩ B)

A, B son Disjuntos <=> A ∩ B = ∅

Ac = U – A

Conjunto de Partes y Familias de Conjuntos

Definiciónes

P(A) Conjunto de Partes
X ∈ P(A) <=> X ⊆ A
P(A) = {X | X ⊆ A}

Nota: ∀A( {∅} ∈ P(A) )

F, G Se usan para representar Familias de Conjuntos o o Colecciones de Conjuntos
∪F = ∀x ( ∃y ( y ∈ F ∧ x ∈ y ) )
∩F = ∀x ( ∀y ( y ∈ F -> x ∈ y ) )

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Teoría de Conjuntos ( Definiciones y Formulas Básicas )