Definición 1.3.1 En general, una sentencia que incluye una variable x se denota por p(x) y se denomina un predicado. Si la variable se sustituye por un valor, el predicado se convierte en una proposición.
El cuantificador universal
p(x) es verdadera para todos los valores de un dominio particular. Se denota ∀xp(x). El símbolo ∀ se le denomina cuantificador universal.
El cuantificador existencial de un predicado es la proposición:
Existe un elemento x en el dominio tal que p(x) es verdadera. Se denota por (∃ al revés)xp(x).
Las demostraciones
En las teorías matemáticas se tiene un conjunto de axiomas de las cuales deducimos las afirmaciones de la teoría que se denominan teoremas que derivan de deducciones lógicas (demostraciones) usando los teoremas lógicos i.e. las tautologías.
Un paso de una demostración muy usado es: p es cierto, p → q es cierto, entonces q es cierto. Se denomina modus ponens, término usado por la lógica escolástica.
Conjuntos y elementos
Un conjunto es una colección de objetos bien definida. Usualmente los denotamos con mayúsculas. Los miembros de los conjuntos son sus elementos y los representaremos por letras minúsculas. Así escribimos a ∈ C para indicar que el elemento a es miembro del conjunto C, en caso contrario escribimos a ∉ C.
Definición: Dos conjuntos son iguales, escribimos C = D si tienen los mismos elementos, todo elemento de C pertenece a D y todo elemento de D está en C (no importa el orden).
Subconjuntos
Definición: Sean C y D conjuntos, si todo miembro de C también pertenece a D, decimos que C es un subconjunto de D, escribimos C ⊆ D.
Cualquier conjunto es subconjunto de sí mismo, C ⊆ C.
Definición 2.1.3 Si C ⊆ D y C ≠ D decimos que C es un subconjunto propio, C ⊂ D.
Los subconjuntos de un conjunto se pueden definir usando predicados o funciones proposicionales. Así:
{x ∈ C | p(x)}
denota el subconjunto de C formado por aquellos elementos de C para los que p(x) se verifica.
Definición Dado un conjunto C se llama conjunto de las partes de C al conjunto formado por todos los subconjuntos de C.
Definición Sean C y D dos conjuntos, entonces la intersección de C y D, denotada C ∩ D, es el conjunto formado por los elementos que pertenecen a C y D simultáneamente.
Dos conjuntos cuya intersección es el conjunto vacío se llamarán disjuntos.
Definición Sean C y D dos conjuntos, entonces la unión de C y D, denotada C ∪ D, es el conjunto formado por los elementos que pertenecen a C o D.
Definición Si C ⊆ D definimos el complemento de C en D, denotado C, como el conjunto formado por los elementos de D que no están en C.
En muchas ocasiones consideraremos que todos nuestros conjuntos están contenidos en uno grande llamado conjunto universal, denotado por U. En este caso las operaciones de conjuntos se pueden relacionar con las operaciones lógicas.
C ∩ D = {x ∈ U | x ∈ C ∧ x ∈ D}
C ∪ D = {x ∈ U | x ∈ C ∨ x ∈ D}
C = {x ∈ U | x ∉ C}
Producto cartesiano
Definición Dados dos objetos x, y a la sucesión (x; y) le llamamos un par ordenado, entonces (x; y) = (z; u) si y solo si x = z e y = u.
Definición El producto cartesiano de dos conjuntos C y D, denotado C X D, es el conjunto formado por todos los pares ordenados (c; d) con c ∈ C y d ∈ D.
Aplicaciones
Definición Una correspondencia entre dos conjuntos C y D es una asignación a elementos de C de algunos de D. Formalmente se puede describir como un subconjunto del producto cartesiano.
Definición Una aplicación f entre dos conjuntos C y D, denotado f : C → D, es una correspondencia entre C y D con la condición que a cada elemento de c ∈ C le asociamos un único elemento de D, denotado f(c). A f(c) le denominamos la imagen de c o el valor de f en c.
C es el dominio de f y D el codominio. La imagen de f, denotado Imf = f(C), es el conjunto formado por todas las imágenes de los elementos de C, i.e.
f(C) = {f(c) | c ∈ C}.
Tipos de aplicaciones
- Una aplicación f : C → D se llama inyectiva si elementos distintos de C tienen imágenes distintas, i.e. c ≠ c’ implica f(c) ≠ f(c’).
- Una aplicación f : C → D se llama sobreyectiva si cada elemento de D es una imagen, i.e. f(C)= D.
- Una aplicación f : C → D se llama biyectiva si a cada elemento de C le corresponde un único elemento de D, y cada elemento de D es imagen de un único elemento de C.
Es claro que una aplicación es biyectiva si y solo si es inyectiva y sobreyectiva.
Composición de aplicaciones
Sean f : C → D y g : D → E dos aplicaciones, entonces podemos componerlas para obtener una aplicación h : C → E definida por
h(c) = (gf)(c) = g(f(c))
para cada c ∈ C. La aplicación h se denomina la composición de f y g.
Proposición La composición de aplicaciones es asociativa: para cualesquiera aplicaciones f : C → D; g : D → E y h : E → F se tiene que
h(gf) = (hg)f.
Demostración Para demostrarlo tomamos un elemento c ∈ C y aplicamos cada miembro de la igualdad a c.
[h(gf)](c) = h[(gf)(c)] = h(g(f(c)))
y
[(hg)f)](c) = (hg)(f(c)) = h(g(f(c)))
luego la igualdad se sigue.
Definición A cada conjunto C le podemos asociar la aplicación identidad 1C que aplica cada elemento c de C en el mismo, i.e. f(c) = c.
Definición Si f : C → D y C’ ⊆ C, llamamos restricción de f a C’ a la aplicación g = f|C’ : C’ → D definida por g(x) = f(x) para todo x ∈ C’.
Lema Sean f : C → D y g : D → C dos aplicaciones tales que gf = 1C, entonces f es inyectiva y g es sobreyectiva.
Demostración. Sean x, y ∈ C tales que f(x) = f(y), aplicando g se tiene que g(f(x)) = g(f(y)) luego (gf)(x) = (gf)(y) como gf = 1C se obtiene que x = y. Así f es inyectiva
Como g(f(x)) = x para cualquier x ∈ C, se sigue que todo elemento de C es imagen de alguno de D, concretamente de f(x), por tanto g es sobreyectiva.
Teorema Una aplicación f : C → D es biyectiva si y solo si existe una aplicación g : C → D tal que gf = 1C y fg = 1D.
Demostración. Supongamos que existe g : C → D verificando que gf = 1C y fg = 1D, aplicando el Lema, obtenemos que f es inyectiva y sobreyectiva, luego f es biyectiva. Recíprocamente, supongamos que f es biyectiva. Dado un d ∈ D existe un único x ∈ C tal que f(x) = d, podemos definir entonces g : D → C mediante la fórmula g(d) = x. Es claro que gf = 1C y fg = 1D
Lema Una aplicación inyectiva de un conjunto finito en sí mismo, f : C → C, es siempre sobreyectiva (y por tanto biyectiva).
Demostración. Tomemos c ∈ C, tenemos que encontrar un x ∈ C tal que f(x) = c. Aplicamos f a c, luego f a f(c), lo denotamos f^2(c), de nuevo aplicamos f, f^3(c) y así continuamos. Obtendremos una sucesión de elementos c; f(c); f^2(c); f^3(c),… pero en algún momento habrá repeticiones porque C es finito. Por tanto para algunos n > m se sigue que f^n(c) = f^m(c):
Como f es inyectiva podemos cancelar f de ambos miembros n-m veces. Se obtiene f^n-m(c) = c.
Así
f(f^n-m-1(c)) = c
tomando x = f^n-m-1(c) se sigue que f(x) = c como queramos demostrar.
Definición A cada conjunto finito C le asociamos un número natural, llamado cardinal de C, que cuenta sus elementos.
Relaciones de equivalencia
Relaciones
Definición Una relación en un conjunto C es una correspondencia de C es sí mismo.
Propiedades de las relaciones
Las relaciones que se consideran en matemáticas usualmente presentan algunas de las propiedades siguientes:
- Cada elemento está relacionado consigo mismo, xRx ∀x ∈ C (Reflexiva).
- Para todo x; y ∈ C, si xRy, entonces yRx (Simétrica).
- Para todo x; y; z ∈ C, si xRy e yRz entonces xRz (Transitiva).
Relaciones de equivalencia
La relación más importante es la relación de igualdad, por tanto es muy interesante generalizar este concepto.
Definición Una relación de equivalencia es una relación que verifica las propiedades reflexiva, simétrica y transitiva.
Clases de equivalencia
Sea R una relación de equivalencia en C.
Definición Para cada x en C, definimos la clase de equivalencia de x, denotada [x] como el subconjunto formado por todos los elementos relacionados con x, i.e.
[x] = {c ∈ C | xRc}.
Proposición Sea R una relación de equivalencia de C. Entonces
- C es la unión de todas las clases de equivalencia, i.e. {[c] | c ∈ C} = C:
- Si cRd, entonces [c] = [d].
- Si a no está relacionado con b, [a] ∩ [b] = ∅
Demostración. i) Puesto que es reflexiva, para todo c ∈ C c ∈ [c], luego la unión de todas las clases de equivalencia es C.
ii) Sea x ∈ [c], es decir xRc por hipótesis cRd, luego la propiedad transitiva nos da xRd, lo que es lo mismo que decir que x ∈ [d]. Hemos probado que [c] ⊆ [d]. La otra inclusión se obtiene de manera similar.
iii) Si x ∈ [a] ∩ [b] ≠ ∅, se sigue que xRa y xRb, luego aRx y xRb, la propiedad transitiva nos da que aRb que es una contradicción.
Teorema Sea C un conjunto y R una relación de equivalencia, entonces el conjunto de todas las clases de equivalencia es una partición del conjunto C. Recíprocamente, toda partición de C define una relación de equivalencia sobre C.
Demostración. Los apartados i) y iii) de la Proposición anterior prueban que el conjunto de las clases de equivalencia forman una partición del conjunto.
Supongamos ahora que en C tenemos una partición. Definimos una relación en el conjunto C mediante el criterio -pertenecer al mismo subconjunto de la partición-. Claramente es una relación de equivalencia y las clases de equivalencia coinciden con los subconjuntos de la partición.
Definición Al conjunto formado por todas las clases de equivalencia se denomina conjunto cociente.
Al conjunto cociente de un conjunto C por una relación de equivalencia R lo denotaremos C/R
Conjuntos ordenados
Otro tipo de relaciones que son básicas en matemáticas son las relaciones de orden.
Definición Una relación R en un conjunto C se dice que es un orden si verifica las propiedades:
reflexiva,
transitiva
y además la siguiente
Si xRy e yRx entonces x = y (Antisimétrica)
Definición Un orden en un conjunto A se dirá total, cuanto todos los elementos del conjunto se pueden comparar, i.e. si para todos a; b ∈ A o bien a ≤ b o bien b ≤ a, o parcial en caso contrario.
Elementos maximales: un elemento a ∈ A es maximal si no existe ningún otro elemento b ∈ A tal que a ≤ b.
Elementos minimales: dualmente, un elemento a ∈ A es minimal si no existe ningún otro elemento b ∈ A tal que b ≤ a.
Cotas superiores: las cotas superiores del conjunto B en A son todos los elementos de A que sean mayores o iguales que todos los elementos de B, i.e., el conjunto {a ∈ A; a ≥ b ∀b ∈ B}.
Cotas inferiores: el conjunto de cotas inferiores de B en A es {a ∈ A; a ≤ b ∀b ∈ B}.
Supremo: el supremo de B en A es la menor de todas las cotas superiores de B en A, si esta existe.
Ínfimo: el ínfimo de B en A es la mayor de todas las cotas inferiores de B en A, si esta existe.
Máximo: El máximo de A es el mayor de todos los elementos de A, si este existe.
Mínimo: El mínimo de A es el menor de todos los elementos de A, si este existe.
