1. No category

Relaciones, Funciones y Enumerabilidad
Rafael F. Isaacs G.
*
Fecha: 17 de abril de 2015
El lector debe tener familiaridad tanto con las relaciones como con las funciones. Estos
conceptos son básicos en la construcción del lenguaje de las matemáticas actuales. Tanto las
relaciones como las funciones son de gran importancia en la informática, pues muchos temas
se deben tratar con este lenguaje. Uno de ellos es el de la cardinalidad, o sea el número de
elementos de un conjunto cuando no nos limitamos a conjuntos finitos. especı́ficamente al
hablar de numerabilidad y sobre todo, de conjuntos no enumerables, obtenemos resultados
sorprendentes y relevantes en cuanto a lo que puede ser computable.
1.
Relaciones
1.1.
Generalidades
Definición 1. Siendo A y B conjuntos el producto cartesiano A × B está definido por:
A × B = {(x, y) | x ∈ A, y ∈ B}
Definición 2. Siendo A y B conjuntos una relación de A en B es cualquier conjunto R que
cumple R ⊆ A × B
Notación. Cuando R es una relación también se nota xRy en lugar de (x, y) ∈ R
Según nuestra definición una relación es simplemente un conjunto de parejas, es conveniente a veces asociar esas parejas a un predicado de dos variables, digamos p(x, y), ası́ la
relación será {(x, y) | p(x, y)}. En cierto sentido el producto cartesiano es el universo para
las proposiciones de dos variables.
Definición 3. Siendo A un conjunto y R una relación de A en A, es decir una relación sobre
A, se dice que R es:
Reflexiva Si ∀x ∈ A ((x, x) ∈ R)
Simétrica Si ∀x, y ∈ A ((x, y) ∈ R ⇒ (y, x) ∈ R)
Transitiva Si ∀x, y, z ∈ A (((x, y) ∈ R ∧ (y, z) ∈ R) ⇒ (x, z) ∈ R)
Antisimétrica Si ∀x, y ∈ A (((x, y) ∈ R ∧ (y, x) ∈ R) ⇒ x = y)
*
Profesor titular UIS
1
Antirreflexiva Si ∀x ∈ A ((x, x) ∈
/ R)
Definición 4. Una relación R sobre un conjunto A se dice que es de equivalencia sobre A
si es reflexiva, simétrica y transitiva
Notación. Las relaciones de equivalencia se notan con signos simétricos como ∼, ≡, ≃, ≈, ∼
=.
Definición 5. Dada una relación de equivalencia ∼ sobre el conjunto A, se define para cada
a ∈ A la clase de equivalencia de a según ∼ que se nota [a]∼ ası́:
[a]∼ = {x ∈ A | a ∼ x}
cuando no hay lugar a confusión se nota simplemente [a]. El conjunto de todas las diferentes
clases de equivalencia as formadas se nota A/ ∼.
Ejemplo 1.1. Sea m un entero positivo. La relación de congruencia entre enteros módulo m
es siempre una relación de equivalencia para cualquier entero m ≥ 1. Dado cualquier entero
n la clase de equivalencia según la relación de congruencia módulo m consiste en todos los
enteros que tiene el mismo residuo que n al ser divididos por m, o lo que es lo mismo, los
enteros de la forma km + n. Se tiene:
[n] = {x ∈ Z | n ≡ x (mód m)} = {km + n | k ∈ Z}
se tiene entonces m − 1 clases de equivalencia, todas infinitas.
Lema 1. Sea ∼ es una relación de equivalencia sobre el conjunto A y a, b ∈ A, las siguientes
afirmaciones son equivalentes:
i) a ∼ b
ii) a ∈ [b]∼
iii) b ∈ [a]∼
iv) [a]∼ = [b]∼
v) [a]∼ ∩ [b]∼ 6= ∅
Demostración. De la definición de [a]∼ y la simétrica de ∼ se sigue la equivalencia de i), ii)
y iii).
Demostremos que i) implica iv): es suficiente ver que si a ∼ b entonces [a]∼ ⊆ [b]∼ . Sea
pues x ∈ [a]∼ entonces a ∼ x y como a ∼ b aplicando transitiva y simétrica se tiene que
b ∼ x por tanto x ∈ [b]∼ y hemos demostrado [a]∼ ⊆ [b]∼ .
Que iv) implica v) se tiene, pues como ya se dijo, cada clase de equivalencia es no vacı́a.
Veamos que v) implica i): si [a]∼ ∩ [b]∼ 6= ∅ existe y ∈ A tal que y ∈ [a]∼ y y ∈ [b]∼
entonces a ∼ y y b ∼ y aplicando reflexiva y transitiva concluimos que a ∼ b.
Proposición 1. Dada una relación de equivalencia ∼ sobre el conjunto A no vacı́o, las
clases de equivalencia forman una partición de A.
2
Demostración. Es claro que {[a]∼ }a∈A es una familia no vacı́a de subconjuntos de A. Cada
[a]∼ es no vacı́o ya que a ∈ [a]∼ por ser ∼ reflexiva. Que {[a]∼ }a∈A son disjuntas dos a dos
se sigue del lema.
S
Ahora bien, como para cada a ∈ A se tiene que [a]∼ S
⊆ A por tanto a∈A [a]∼ ⊆
S A. Por
otra parte, si a ∈ A entonces
a
∈
[a]
y
por
tanto
a
∈
[a]
y
tenemos
A
⊆
∼
∼
a∈A
a∈A [a]∼
S
con lo que se concluye que a∈A [a]∼ = A.
Definición 6. Una relación R sobre un conjunto A se dice que es de orden parcial sobre
A si es reflexiva, antisimétrica y transitiva.
1.2.
Representación de Relaciones
Una relación se puede “pintar” como un subconjunto del producto cartesiano, siempre y
cuando dicho producto cartesiano se pueda representar. Por ejemplo la relación R de R en
R definida por R = {(x, y) | x2 + y 2 ≤ 4} se representa un disco centrado en el origen y con
radio 2 del plano cartesiano.
También podemos utilizar flechas, especialmente cuando trabajamos relaciones finitas:
Representamos los elementos de los conjuntos A y B por puntos y siempre que (x, y) ∈ R
trazamos una flecha entre los respectivos puntos. Cuando A = B se pintan los puntos de A
solo una vez y se obtiene el digrafo o grafo dirigido de R1 . Cuando se sabe de antemano que
la relación es simétrica, sobra poner sentido a las flechas y obtenemos el grafo (o la gráfica)
de la relación.
2
1
3
0
4
Figura 1:
Grafo de
la
relación
(0, 1), (1, 2), (1, 3), (2, 3), (3, 4) y (4, 0).
simétrica
que
contiene
las
parejas
Desde el punto de vista informático, ası́ como los conjuntos se representan por vectores
booleanos, las relaciones conviene representarlas por matrices booleanas.
Definición 7. Siendo A y B conjuntos finitos, digamos A = {a1 , . . . an } y B = {b1 , . . . bm },
cualquier relación R de A en B se puede representar por la matriz booleana MR = (mi,j )i:1,...,n; j:1,...,m
de n filas y m columnas donde mi,j = 1 ⇔ (ai , bj ) ∈ R.
Observando la matriz de una relación entre conjuntos finitos es inmediato saber si la
relación es reflexiva, simétrica y antisimétrica. Por una observación más de sencilla no es
fácil ver si es transitiva.
1
Los mexicanos hablan de gráficas en lugar de grafos, tal vez más castizo.
3
1.3.
Composición de Relaciones
Con las relaciones por ser conjuntos, podemos hacer uniones intersecciones, hablar de una
relación contenida en otra, etc.. Hay ciertas operaciones y operadores entre relaciones que no
provienen de los conjuntos: el operador inverso y la operación composición entre relaciones,
que introducimos enseguida.
Definición 8. Siendo A y B conjuntos y R una relación entre ellos se define
R−1 = {(y, x) | (x, y) ∈ R}
que es la relación inversa de R y está definida de B en A.
Definición 9. Siendo A, B y C conjuntos, R una relación de A en B, S una relación de B
en C, definimos la relación R ◦ S de A en C ası́:
(x, z) ∈ (R ◦ S) ⇔ ∃y ∈ B ((x, y) ∈ S ∧ (y, z) ∈ R)
Las demostraciones de las siguientes tres proposiciones son una consecuencia inmediata
de las definiciones y las omitimos.
Proposición 2. La composición entre relaciones ◦ es asociativa es decir (R ◦ S) ◦ T =
R ◦ (S ◦ T )
Proposición 3. (R ◦ S)−1 = S −1 ◦ R−1
Proposición 4. La relación R es transitiva si y solo sı́ R ◦ R ⊆ R
Definición 10. Sea M = (mi,j ) matriz booleana de orden n × m y N = (mj,k ) matriz
booleana de orden m × p, se define el producto booleano de M y N como la matriz M ⊙ N =
(ci,k ) de orden n × p ası́:
m
_
ci,k =
(mi,j ∧ nj,k )
j=1
Proposición 5. Siendo A, B y C conjuntos finitos, R una relación de A en B, S una
relación de B en C, la matriz de la relación S ◦ R de A en C está dada por:
M(S◦R) = MR ⊙ MS
Demostración. Sea A = {a1 , . . . , an }, B = {b1 , . . . , bm } y C = {c1 , . . . , cp } entonces
(ai , ck ) ∈ (S ◦ R) ⇔ ∃bj ∈ B ((ai , bj ) ∈ R ∧ (bj , ck ) ∈ S)
esto quiere decir que
(ai , ck ) ∈ (S ◦ R) ⇔ ∃j : 1, . . . m(mi,j = 1) ∧ (nj,k = 1)
que es lo mismo que
(ai , ck ) ∈ (S ◦ R) ⇔
4
m
_
(mi,j ∧ nj,k ) = 1
j=1
1.4.
Ejercicios
1. Explique por qué si S, T, W son conjuntos no podemos asegurar que S × (T × W ) =
(S × T ) × W . Determine en qué casos sı́ se tiene la igualdad.
2. Sean R = {(a, b), (a, a), (b, a), (c, a)} y S = {a, c)(c, c), (b, b)}. Enumere las parejas
de cada una de las siguientes relaciones sobre {a, b, c} y determine si son reflexivas,
antirreflexivas, simétricas, antisimétricas o transitivas:
e) R ◦ S
a) R
f ) R−1 ∪ S
b) S
g) R ∩ R−1
c) R ∪ S
h) S ◦ R
d) R ∩ S
3. Sean R y S las relaciones definidas sobre el conjunto {−5, −4, . . . , 0, 1, . . . , 4, 5} ası́:
nRm ⇔ a ≤ b.
nSm ⇔ a = −b.
Analizar cada relación y exhibir su matriz:
a) R ∩ S.
b) R ∪ S
c) R ∩ S −1
d) S ◦ R
e) R ∩ S
4. ¿Cuántas relaciones hay de un conjunto con n elementos en un conjunto con m ele2
mentos? Demuestre que si |A| = n hay exactamente 2n sobre A y que de estas, 2n(n−1)
son reflexivas y 2n(n+1)/2 son simétricas.
5. Sea A el conjunto de todos los humanos y consideermos las relaciones P y M definidas
por:
(x, y) ∈ P sisi el padre de x es y.
(x, y) ∈ M sisi la madre de x es y
qué significado tiene las siguientes relaciones sobre A?
d ) (P ∪ M) ◦ (P ∪ M)−1
a) P ◦ P
b) (P ∪ M) ◦ (P ∪ M)
c) P ◦ P −1
e) (P ◦ P −1) ∪ (M ◦ M −1 )
6. Cuáles de las siguientes relaciones sobre los naturales son reflexivas, antirreflexivas,
simétricas, antisimétricas o transitivas, cuáles son órdenes parciales (definición 6:
5
a) nRm ⇔ n + m es par.
b) nRm ⇔ n + m es impar.
c) nRm ⇔ n − m es par.
d ) nRm ⇔ n − m es impar.
e) nRm ⇔ n/m es potencia de 2.
f ) nRm ⇔ n/m es impar.
g) nRm ⇔ n − m es mltiplo de 5.
h) nRm ⇔ n divide a m
7. Sea Σ = {a, b} en cada caso se define recursivamente la relación Θ sobre Σ∗ . Interprete
qu significa cada relación y decida si la relación ası́ definida es reflexiva, antirreflexiva,
simétrica, antisimétrica o transitiva:
a) i) Base: ∀α ∈ Σ∗ (α, α) ∈ Θ.
ii) Paso inductivo: Si α, β ∈ Σ∗ , x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ.
iii) Clausura: Θ se calcula únicamente aplicando i) y ii).
b) i) Base: (λ, λ) ∈ Θ.
ii) Paso inductivo: Si α, β ∈ Σ∗ , x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ.
iii) Clausura: Θ se calcula únicamente aplicando i) y ii).
c) i) Base: ∀α ∈ Σ∗ (α, α) ∈ Θ.
ii) Paso inductivo: Si α ∈ Σ∗ , x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ y
(α, xβ) ∈ Θ.
iii) Clausura: Θ se calcula únicamente aplicando i) y ii).
8. El conjunto ∅ es una relación entre cualquier par de conjuntos A yB. ¿Qué propiedades
tiene?
9. Según la proposición 5 la matriz MR ⊙ MS tiene un 1 en el puesto i, j si y sólo si
i está conectado con j por medio de R ◦ S, si no están conectados habrá un 0. Si
hiciéramos la multiplicacin de MR y MS de la manera usual, podramos obtener números
mayores que 1. ¿Qué significado tienen los números mayores que 1 en MR MS ?
10. Sean R y S relaciones sobre el conjunto A. IA la identidad en A. En cada caso conteste
falso o verdadero y justifique brevemente.
a) Si R es reflexiva entonces R ∩ S lo es.
b) Si R es simétrica entonces R = R−1 .
c) Si R y S son antisimétricas entonces R ∪ S lo es.
d ) Si R ∪ S es reflexiva entonces R y S lo son.
e) Si R es simétrica entonces R ⊂ IA .
f ) Siempre R ∪ R−1 es reflexiva.
6
g) Si R y S son transitivas entonces R ∪ S lo es.
11. Muestre dos relaciones simétricas sobre el conjunto {a, b, c} de tal forma que su compuesta no sea simétrica.
12. Muestre dos relaciones transitivas sobre el conjunto {a, b, c} de tal forma que su compuesta no sea transitiva.
13. Sean R = {(2, 1), (2, 3)} y S = {(2, 3), (4, 2)(2, 1), (4, 1)} relaciones sobre el conjunto
A = {1, 2, 3, 4} enumere los elementos de las siguientes relaciones:
(a) R ∪ S −1
(b) R ◦ S −1
14. Sea R = {(2, 1), (2, 3), (4, 2)(2, 1), (4, 1)}.
a) Enumere los elementos de la menor relación S sobre el conjunto A = {1, 2, 3, 4}
que es transitiva y tal que R ⊆ S (S es la clausura transitiva de R).
b) Enumere los elementos de la menor relación T sobre el conjunto A = {1, 2, 3, 4}
que es de equivalencia y tal que R ⊆ T . (T es la clausura de equivalencia de
R).
c) Cuáles son las clases de equivalencia que forma T ?
15. A continuación se define la relación ∼ sobre el conjunto Z. Demuestre que en cada caso
la relación es de equivalencia y determine cuántas clases de equivalencia se forman.
a)
b)
c)
d)
n ∼ m ⇔ n − m es par.
n ∼ m ⇔ n − m es divisible por 5.
n ∼ m ⇔ nm > 0 o n = m = 0.
n ∼ m ⇔ n/m o m/n son potencia de 2 o n = m = 0
16. A continuación se define la relación ∼ sobre C• el conjunto de los complejos sin el 0.
Demuestre que en cada caso la relación es de equivalencia y determine cómo son sus
clases de equivalencia.
a)
b)
c)
d)
e)
z1
z1
z1
z1
z1
∼ z2
∼ z2
∼ z2
∼ z2
∼ z2
⇔ ∃α ∈ R(αz1 = z2 )
⇔ ∃α ∈ R, α > 0(αz1 = z2 )
⇔ (|z1 | = |z2 |)
⇔ (Re(z1 ) = Re(z2 ))
⇔ (Im(z1 ) = Im(z2 ))
17. Probar que si una relación R es reflexiva y transitiva entonces R ∩ R−1 es de equivalencia.
18. Probar que si las relaciones R y S son reflexivas y simétricas entonces las siguientes
condiciones son equivalentes:
i) R ◦ S es simétrica.
ii) R ◦ S = S ◦ R.
7
2.
Funciones
Las funciones son un tipo especial de relaciones. Informalmente a cada elemento del
dominio se le asocia un único elemento del conjunto de llegada. Generalmente esta relación
se especifica por medio de una fórmula o algoritmo. El concepto de función es un concepto
clave en la matemática y en la informática. Podemos decir que todo programa de computador
es una función en cuanto dada una entrada especı́fica, produce una salida.
Definición 11. Sea R una relación de A en B, se dice que R es una función de A en B si
se cumple
i) ∀x ∈ A∃y ∈ B((x, y) ∈ R)
ii) ∀x ∈ A∀y1 , y2 ∈ B(((x, y1 ) ∈ R ∧ (x, y2 ) ∈ R) ⇒ y1 = y2 )
La primera propiedad exige que cada elemento del dominio tenga uno relacionado en el
recorrido, la segunda exige que este sea único. Realmente el concepto de función incluye tres
cosas: el dominio, el recorrido y el conjunto de parejas.
Notación. Se acostumbra notar con las letras f, g, h las funciones. Cuando f es una función
de A en B se nota f : A −→ B y si (x, y) ∈ f se escribe f (x) = y. Ası́, f (x) se denomina la
imagen de x.
Tal como las relaciones, las funciones pueden tener o no una fórmula, expresión o algoritmo que determine la imagen de cada elemento del dominio. Sin embargo las funciones que
tienen dicha “fórmula, expresión o algoritmo”, como comprobaremos más adelante, son una
parte muy pequeña de todas las funciones. Por tanto no conviene confundir el concepto de
función con una “fórmula, expresión o algoritmo”.
Realmente para hablar de funciones hay que tener en cuenta tres cosas: el conjunto de
parejas, el conjunto de salida o dominio de la función, y el conjunto de llegada o recorrido de
la función. El conjunto de parejas por sı́ mismo no forma una función. Un mismo conjunto
de parejas forma diferentes fuciones cuando se varı́a su dominio y su recorrido
2.1.
Ejemplos de funciones
Ejemplo 2.1. Como ya se dijo el conjunto de parejas y menos aún la fórmula constituyen
una función. Por ejemplo si hablamos de la fórmula: x2 + y 2 = 1 podrı́amos referirnos al
conjunto de parejas:
R = {(x, y) : x2 + y 2 = 1}
que visto como subconjunto de R × R no es una función. R es una función de [−1, 1] en R y
otra función de [0, 1] en [−1, 1].
Ejemplo 2.2. La colección indicada de conjuntos {Ai }i∈I se puede entender como una
función f : I −→ P(X) donde Ai ⊆ X para todo i ∈ I.
Ejemplo 2.3. La función caracterı́stica de un conjunto A donde A ⊆ X es una función
χA : X −→ Z2 donde χA (x) = 0 ⇔ x ∈
/ A.
8
Ejemplo 2.4. La pareja (a, b) se puede ver como una función f : {1, 2} −→ X donde
f (1) = a, f (2) = b y a, b ∈ X. El producto cartesiano A × B se puede ver como el conjunto
de funciones {f : {1, 2} −→ A ∪ B |f (1) ∈ A, f (2) ∈ B }. De aquı́ se generaliza el concepto
de producto cartesiano para cualquier colección indicada de conjuntos {Ai }i∈I , ası́:
Y
[
Ai = {f : I −→
Ai | f (i) ∈ Ai }.
i∈I
i∈I
Un caso especial es cuando Ai = A para todo i ∈ I se nota entonces
AI = {f : I −→ A | f es función}.
Q
i∈I
A = AI y se tiene:
Ejemplo 2.5. Una palabra de n letras sobre el alfabeto Σ se puede ver como una función
w : {1, 2, . . . n} −→ Σ.
Ejemplo 2.6. La función parte entera f : R −→ R donde f (x) es el mayor entero menor
o igual que x. Se nota ⌊x⌋
Ejemplo 2.7. La función exponencial f : R −→ R+ en base b definida por f (x) = bx .
Ejemplo 2.8. La función de Collatz f : N+ −→ N+ está definida as:


1 si n = 1
f (n) = f (n) = n2 Si n es par


f (n) = 3n + 1 Si n es impar mayor que 1
Ejemplo 2.9.
Las operaciones son un tipo especial de funciones. Por ejemplo la suma entre naturales
se puede ver como una función S : N × N −→ N en donde S(x, y) se nota x + y.
2.2.
Composición de funciones
La composición de funciones se hace como la de las relaciones, toca sin embargo, asegurarnos que realmente se produce una nueva función.
Proposición 6. Sean R ⊆ A × B y S ⊆ B × C, si R y S son funciones (de A en B y de B
en C,respectivamente) entonces S ◦ R es función de A en C.
Notación. Si f : A −→ B y g : B −→ C son funciones su compuesta se nota g ◦ f : A −→ C
es decir g ◦ f (x) = g(f (x))
Ejemplo 2.10. Si RES( ; m) : Z −→ Z es la función residuo al dividir entre m > 0
entonces RES es idempotente pues al componerla consigo misma da ella misma.
Ejemplo 2.11. La conjetura de Collatz, que no se ha refutado ni comprobado, asegura que
al aplicar sucesivamente la función a determinado número se debe llegar a 1, esto sin embargo
no quiere decir, que la función de Collatz compuesta un determinado número de veces sea
la constante 1.
9
Definición 12. Sea f : A −→ B una función entonces:
f es inyectiva, o uno a uno (o 1-1) si ∀x, y ∈ A(f (x) = f (y) ⇒ x = y)
f es sobreyectiva, o simplemente sobre si ∀y ∈ B∃x ∈ A(f (x) = y)
f es biyectiva si es uno a uno y sobre.
Si f es biyección y A = B se dice que f es una permutación de A.
Ejemplo 2.12. Si A ⊆ B se puede definir inA,B : A −→ B, la función inclusión, definida
por inA,B (a) = a para todo a ∈ A. Esta función inA,B siempre es inyectiva y si A = B se
tiene inA,B = IA la función idéntica que es la única relación que es a la vez de equivalencia
y función. Se define además para cada f : B −→ C la restricción de f a A como la función
f ⇃A = f ◦ inA,B .
Proposición 7. Sean f : A −→ B, g : B −→ C funciones entonces:
i) Si f y g son inyectivas, g ◦ f : A −→ C es inyectiva.
ii) Si f y g son sobreyectivas, g ◦ f : A −→ C es sobreyectiva.
iii) g ◦ f : A −→ C sobreyectiva implica que g es sobreyectiva
iv) g ◦ f : A −→ C uno a uno implica que f es uno a uno.
Demostración. Solamente probaremos iii) y iv) dejando i) y ii) como ejercicio.
iii) Si g ◦ f : A −→ C es sobreyectiva para todo z ∈ C existe x ∈ A tal que g(f (x)) = z
por tanto para todo z ∈ C haciendo y = f (x) existe y ∈ B tal que g(y) = z quedando
probado que g es sobreyectiva.
iv) Demostraremos la contrarecı́proca. Si f no es 1-1 entonces existen x1 , x2 ∈ A con
x1 6= x2 tal que f (x1 ) = f (x2 ) y aplicando g tenemos g(f (x1 )) = g(f (x2 )) entonces g ◦ f no
es inyectiva.
Las funciones como las relaciones tienen inversa pero no siempre dicha inversa es una
función.
Proposición 8. Sea f : A −→ B función. Condición necesaria y suficiente para que f −1
sea función es que f sea biyección.
Demostración. Traduzcamos la definición de función para f −1 (de B en A):
i) ∀x ∈ B∃y ∈ A((x, y) ∈ f −1 ) esto significa que f es sobre.
ii) ∀x ∈ B∀y1 , y2 ∈ A(((x, y1 ) ∈ f −1 ∧ (x, y2 ) ∈ f −1 ) ⇒ y1 = y2 ) esto significa que f es 1-1.
Ejemplo 2.13. La función exponencial f : R −→ R+ en base b > 0 definida por f (x) = bx
tiene como inversa la función g : R+ −→ R definida por g(x) = logb (x). Nótese que si
consideramos f : R −→ R definida de manera igual, su inversa no es función.
10
Cuando una función tiene inversa (es decir cuando es biyectiva) al componerlas se producen las dos idénticas y las únicas relaciones que cumplen esto son las biyecciones:
Proposición 9. Sea f : A −→ B biyección. Entonces
f −1 ◦ f = IdA
∧
f ◦ f −1 = IdB
∧
R ◦ R−1 = IdB
Por otra parte, si R ⊆ A × B cumple que
R−1 ◦ R = IdA
entonces R es una biyección de A en B
Demostración. Nótese las siguientes “traducciones”:
a. R−1 ◦ R ⊆ IdA ⇐⇒ ∀x ∈ A∃y ∈ B(xRy)
b. R−1 ◦ R ⊇ IdA ⇐⇒ ∀x1 , x2 ∈ A∀y ∈ B(x1 Ry ∧ x2 Ry ⇒ x1 = x2 )
c. R ◦ R−1 ⊆ IdB ⇐⇒ ∀y ∈ B∃x ∈ A(xRy)
d. R ◦ R−1 ⊇ IdB ⇐⇒ ∀x ∈ A∀y1 , y2 ∈ B(xRy1 ∧ xRy2 ⇒ y1 = y2 )
Las afirmaciones de la derecha significan que R y R−1 son biyecciones.
En ciertos casos las funciones apenas alcanzan a tener “cuasi-inversas”:
Proposición 10. Sea A 6= ∅ y f : A −→ B función.
1. Existe g : B −→ A tal que f ◦ g = IdB si y sólo si f es sobreyectiva. Se dice que g es
una inversa a derecha de f .
2. Existe g : B −→ A tal que g ◦ f = IdA si y sólo si f es inyectiva. Se dice que g es una
inversa a izquierda de f .
Demostración. • Veamos que si f tiene inversa a derecha entonces es sobreyectiva. Sea y ∈ B
entonces y = f (g(y)) por ser g la inversa a derecha de f entonces haciendo x = g(y)
se tiene f (x) = y por tanto f es sobre.
• Ahora supongamos que f es sobre y construyamos g que es inversa a derecha de f . Para
cada y ∈ B por ser f sobre existe algún x ∈ A tal que f (x) = y entonces “escogemos”
2
uno de estos x como imagen de g. Tenemos que g(y) = x ⇒ f (x) = y y por tanto
para todo y ∈ B se tiene f (g(y)) = f (x) = y es decir f ◦ g = IdB .
• Veamos que si f tiene inversa a izquierda entonces es inyectiva. Si x1 , x2 ∈ A y f (x1 ) =
f (x2 ) entonces aplicamos g y tenemos g(f (x1 )) = g(f (x2)) pero g es inversa a izquierda
entonces
x1 = g(f (x1)) = g(f (x2)) = x2
por lo tanto f es 1-1.
2
Realmente estamos usando el axioma de elección, este item de nuestra proposición es una forma de
expresar tal axioma, sutil e importante que ha generado mucha literatura matemática. Por ahora anotemos
que se puede hacer matemáticas sin utilizarlo.
11
• Para construir g que sea inversa a izquierda de f sabiendo que f es 1-1, dado y ∈ B si
existe x tal que f (x) = y entonces hacemos g(y) = x, queda bien determinada x por
ser f inyectiva. Si no existe tal x, es decir si ∀x(f (x) 6= y) escogemos cualquier a0 , ∈ A
y definimos g(y) = a0 . Aquı́ hemos usado que A 6= ∅. Se tiene g(f (x)) = x por la
construcción.
Ejemplo 2.14. Hagamos f = {(1, a), (2, a)}, g = {(a, 1)} entonces tomando A = {1, 2} y
B = {a} tenemos g : B −→ A y f : A −→ B y se cumple que f ◦ g = IdB por tanto f es
inversa a izquierda de g mientras g es inversa a derecha de f :
√
Ejemplo 2.15. Si f (x) = x y g(x) = x2 entonces g es inversa a izquierda de f pero no
es inversa a derecha! Claro, esto depende del dominio y el recorrido especificados para cada
función.
2.3.
Imagen Directa e Imagen Inversa
Las funciones operan en principio sobre elementos pero también es muy útil verlas operando sobre subconjuntos tanto del dominio como del recorrido.
Definición 13. Sea f : A −→ B cualquier función y X ⊆ A, Y ⊆ B se define:
i) f (X) = {f (x) | x ∈ X} se llama imagen directa de X.
ii) f −1 (Y ) = {x ∈ A | f (x) ∈ Y } se llama imagen inversa de Y .
Estas definiciones se pueden expresar ası́:
u ∈ f (X) ⇔ ∃x(x ∈ X ∧ f (x) = u)
u ∈ f −1 (Y ) ⇔ f (u) ∈ Y )
Es conveniente aclarar que en estas definiciones f −1 no debe interpretarse como la función
inversa de f que probablemente no exista (como función).
Ejemplo 2.16. Sea f la funcion de R en R definida por f (t) = sen(t). Entonces:
f ([0, ∞)) = [−1, 1]
f −1 ([−1, 1)) = R − {(4k + 1)π/2}k∈Z
f −1 ({0}) = {kπ}k∈Z
f ({(2k + 1)π/2}k∈Z) = {1, −1}
Proposición 11. Sea f : A −→ B una función, entonces:
1. Para todo X ⊆ A siempre X ⊆ f −1 (f (X)).
2. Para todo X ⊆ A se tiene X = f −1 (f (X)) si y sólo si f es inyectiva.
3. Para todo Y ⊆ B siempre f (f −1 (Y )) ⊆ Y .
4. Para todo Y ⊆ A se tiene f (f −1(Y )) = Y si y sólo si f es sobreyectiva.
12
Proposición 12. Sea f : A −→ B una función, si para todo i ∈ I tenemos Yi ⊆ B y Xi ⊆ A
entonces:
T
T
1. f −1 ( i∈I Yi ) = i∈I f −1 (Yi ).
S
S
2. f −1 ( i∈I Yi ) = i∈I f −1 (Yi ).
T
T
3. f ( i∈I Xi ) ⊆ i∈I f (Xi )
S
S
4. f ( i∈I Xi ) = i∈I f (Xi )
T
T
5. f es inyectiva si y sólo f ( i∈I Xi ) = i∈I f (Xi ).
2.4.
Contando funciones entre conjuntos finitos
Proposición 13. El número de funciones entre un conjunto con n elementos y otro con m
elementos está dado por
mn
Demostración. Hay tantas de estas funciones como palabras de n letras sobre un alfabeto
con m letras.
Proposición 14. El número de funciones inyectivas entre un conjunto con n elementos y
otro con m elementos, donde 0 < n ≤ m, está dado por
mn = m(m − 1) . . . (m − n + 1)
Demostración. Notemos [n] = {1 . . . n} para cada n ∈ N+ . Para n ≥ m calcularemos el
número de funciones inyectivas de [n] en [m]. Hacemos inducción sobre n: Si n = 1 es claro
que hay m funciones todas inyectivas (m ≥ n). Supongamos (hipótesis de inducción) m > n
y que hay
mn = m(m − 1) . . . (m − n + 1)
funciones de inyectivas de [n] en [m]. entonces para cada función f : [n] −→ [m] podemos
construir f ′ : [n + 1] −→ [m] haciendo f ′ (i) = f (i) si i ∈ [n] y escogiendo f ′ (n + 1) en el
conjunto [m] − f ([n]); ası́ f ′ será inyectiva y podramos escoger m − n funciones. Por otra
parte, todas las funciones inyectivas se pueden construir ası́ y de manera única. Por tanto
hay
mn+1 = m(m − 1) . . . (m − n + 1)(m − n)
funciones f : {1, . . . , n, n + 1} −→ {1, . . . , m} inyectivas.
Proposición 15. El número de permutaciones de un conjunto con n elementos es
n!
Demostración. Este es un corolario de la proposición anterior.
Para la demostración de la siguiente proposición se usa el principio de inclusión-exclusión
y el cardinal del conjunto de funciones entre dos conjuntos (proposición 13). Antes veamos
un ejemplo.
13
Ejemplo 2.17. Calcularemos el cardinal del conjunto de funciones sobreyectivas de {1, 2, 3, 4}
en {1, 2, 3}. De las 34 funciones que hay de {1, 2, 3, 4} en {1, 2, 3}, debemos quitar las que
no son sobreyectivas. Entonces sea Ai = {f : {1, 2, 3, 4} −→{1,2,3} | i ∈
/ f ({1, 2, 3, 4})} es
4
decir, aquellas cuya imagen está contenida en {1, 2, 3} − {i} (hay 2 ) y ası́ las funciones no
sobreyectivas son exactamente las del conjunto A1 ∪ A2 ∪ A3 y por el principio de inclusin
exclusión (descontando las tres constantes) hay
3 4
2 −3
2
funciones no sobreyectivas, es decir tenemos
3 4
4
2 + 3 = 81 − 3 × 16 + 3 = 36
3 −
2
funciones sobreyectivas. Es bueno contarlas de otras maneras. Todas las funciones sobreyectivas tiene necesariamente
dos elementos y únicamente dos, que tiene igual imagen. Si esta
4
imagen es 1 hay 2 2 = 12 funciones sobreyectivas que van dos elementos a 1. Como lo mismo
sucede con 2 y con 3 tendremos 3 × 2 42 = 36 funciones sobreyectivas
Proposición 16. El número de funciones sobreyectivas entre un conjunto con n elementos
y otro con m elementos está dado por
m
X
i m
(m − i)n
(−1)
i
i=0
Demostración. Notemos n = {1, 2, . . . , n}. Sabemos que el cardinal de M el conjunto de las
funciones entre n y m es mn . Por cada j ∈ m sea
Mj = {f ∈ M | j ∈
/ f (n)}
S
es evidente que N = j∈n Mj es el conjunto de todas las funciones de M que NO son
sobreyectivas. Por el principio de inclusión exclusión se tiene
X
\
|N| =
(−1)|J|−1 |AJ | , donde AJ =
Mj .
j∈J
∅6=J⊆n
Pero AJ = {f ∈ M |f (n) ⊆ m − J} entonces |AJ | = (m − |J|)n . Si hacemos la suma sobre
i = |J| como hay mi conjuntos J ⊆ n con esta condición entonces
|N| =
n
X
(−1)
i−1
i=1
m
(m − i)n
i
como nos interesa son las funciones sobreyectivas tenemos
n
|M − N| = m −
n
X
i=1
(−1)
i−1
n
X
m
n
i m
(m − i)n
(m − i) =
(−1)
i
i
i=0
14
2.5.
Sucesiones definidas recursivamente
Una sucesión es una función cuyo dominio son los números naturales. Hemos visto muchas
sucesiones definidas recursivamente. En ellas se da los valores de el(los) primer(os) término(s)
y luego una regla para calcular el n-simo en términos de uno o varios anteriores. También se
definen recursivamente funciones cuyo dominio son el conjunto de palabras (ver ejercicio 6).
Trataremos ahora de sistematizar un método para hallar fórmulas explı́citas para algunas
sucesiones definidas recursivamente. Tal vez el caso más conocido y motivante es la sucesión
de Fibonacci que como se sabe es define recursivamente por Fn+1√= Fn + Fn−1
con F0 = 0
√
1− 5
1+ 5
y F1 = 1. Se puede demostrar por inducción que siendo α = 2 y β = 2 , el n-simo
término de la sucesión de Fibonacci es:
1
Fn = √ (αn − β n )
5
Es en principio sorprendente esta fórmula porque además de involucrar números relacionados por la proporción áurea, patrón de la belleza griega, a partir de números irracionales
producimos números enteros. Nos interesa ver como se producen fórmulas explı́citas a partir
de las definiciones recursivas. El caso más sencillo lo dejamos como ejercicio. Estudiaremos las
definiciones recursivas homogéneas de segundo orden, en donde el término general depende
de los dos anteriores multiplicados por constantes y están definidas ası́:

si n = 0;
 u,
Tn =
v,
si n = 1;

Tn = aTn−1 + bTn−2 , si n > 1.
donde u, v son los datos iniciales y a, b son constantes. A dicha sucesión, mejor “ley de
recurrencia” se le asocia el polinomio x2 − ax − b llamado caracterı́stico. Sus raı́ces nos
dan dirán mucho de la solución explı́cita.
Proposición 1. Cualquier sucesión de la forma sn = xαn + yβ n donde α, β son soluciones
a la ecuación x2 = ax + b, cumple la ley recursiva sn+1 = asn + bsn−1 .
Demostración. Supongamos que α, β son soluciones a la ecuación x2 = ax + b y sea sn =
xαn + yβ n entonces
asn + bsn−1 =
=
=
=
=
axαn + ayβ n + bxαn−1 + byβ n−1
αn−1x(aα + b) + β n−1 y(aβ + b)
αn−1xα2 + β n−1 yβ 2
xαn+1 + yβ n+1
sn+1
Ejemplo 2.18. La ley recursiva
sn+1 = 5sn − 6sn−1
con ecuación caracterı́stica (x−3)(x−2) la cumplen todas las siguientes sucesiones: 3n , 3n+5 ,
2n , 3n + 2n , 3n − 5 × 2n , etc.
15
Proposición 2. Sea sn la sucesión definida recursivamente ası́:
s0 = u; s1 = v.
sn+1 = asn + bsn−1 .
si α 6= β son soluciones a la ecuación x2 = ax + b, entonces existen x, y ∈ R tales que para
todo n ∈ N se cumple sn = xαn + yβ n.
Demostración. Por la proposición 1 se sabe la forma general, como sabemos los valores
cuando n = 0, 1 entonces Conseguimos x, y ∈ R tales que se cumpla:
u = x+y
v = αx + βy
como α 6= β el sistema tiene una única solución.
La demostración de la anterior proposición nos determina un método para dar una fórmula explı́cita de la sucesión siempre que el polinomio caracterı́stico asociado tenga dos raı́ces
diferentes. Cuando α = β en el ejercicio 21 se piede demostrar que para este caso se tiene:
Proposición 3. Sea sn la sucesión definida recursivamente ası́:
s0 = u; s1 = v.
sn+1 = asn + bsn−1 .
si la ecuación caracterı́stica x2 = ax + b tiene sus dos raı́ces iguales es decir x2 − ax − b =
(x − α)2 , entonces existen x, y ∈ R tal que para todo n ∈ N se cumple sn = xαn + ynαn .
2.6.
Ejercicios
1. Demostrar que la relación R sobre el conjunto A es una biyección si y sólo si R ◦ R−1 =
R−1 ◦ R = IA
2. Si A tiene n elementos cuántas funciones hay de A en {1}?
3. Entre cuáles conjuntos ∅ es una función?
4. A cada persona de una población se le asocia su lugar de residencia. Qué significa que
esta relación sea función? Que sea inyectiva? Que sea sobre?
5. Sean R ⊆ A × B una relación y f : B −→ C una función demostrar que R ◦ f cumple
(x, y) ∈ R ⇒ (x, f (y)) ∈ (f ◦ R)
6. Sea Σ = {a, b} en cada caso se define recursivamente la función f con dominioΣ∗ .
Decidir si la función queda bien definida, y en caso afirmativo si es inyectiva y/o
sobreyectiva:
16
a) i) Base: f (λ) = λ.
ii) Paso inductivo: Si v ∈ Σ∗ entonces f (va) = f (v)aa y f (vb) = f (v).
iii) Clausura: f se calcula nicamente aplicando i) y ii).
b) i) Base: f (λ) = λ.
ii) Paso inductivo: Si v ∈ Σ∗ entonces f (va) = f (v)b y f (vb) = f (v)a.
iii) Clausura: f se calcula únicamente aplicando i) y ii).
c) i) Base: f (λ) = 0.
ii) Paso inductivo: Si v ∈ Σ∗ entonces f (va) = f (v) + 1 y f (vb) = f (v) + 1.
iii) Clausura: f se calcula únicamente aplicando i) y ii).
d ) i) Base: f (λ) = λ.
ii) Paso inductivo: Si v ∈ Σ∗ entonces f (va) = af (v) y f (vb) = bf (v).
iii) Clausura: f se calcula únicamente aplicando i) y ii).
7. Sean R ⊆ A × A una relación y f : A −→ B una biyección entonces f −1 ◦ R ◦ f cumple
(x, y) ∈ R ⇔ (f (x), f (y)) ∈ (f −1 ◦ R ◦ f )
8. Si {Ai }i∈I , es una colección
de conjuntos para cada j ∈ I se define πj la j-ésima
Q
Q
proyección ası́: πj : i∈I Ai −→ Aj donde πj (f ) = f (j) para cada f ∈ i∈I Ai .
Demostrar que para
Q cualesquier coleeción de funciones ρj : C −→ Aj existe un única
función F : C −→ i∈I Ai de tal forma que para todo j ∈ I se tiene πj ◦ F = ρj .
9. Analice la función f : N −→ N × N definida recursivamente ası́:


(0, 0) si n = 0
f (n) = (i + 1, j − 1) si f (n − 1) = (i, j) con j > 0


(0, i) si f (n − 1) = (i, 0).
10. Demuestre que para cualquier función si tiene dos inversas a derecha diferentes entonces
no tiene inversa a izquierda. Enuncie y demuestre el resultado dual.
11. Mostrar funciones f y g tales que f ◦ g no es biyectiva, aunque f es sobreyectiva y g
es uno a uno.
12. Sea f : A −→ B una función.
f es inyectiva si y sólo para todas g1 , g2 : B −→ C se cumple f ◦ g1 = f ◦ g2 ⇒ g1 = g2 .
f es sobreyectiva si y sólo para cualesquier g1 , g2 : C −→ A se cumple g1 ◦f = g2 ◦f ⇒
g1 = g2 .
13. Probar la proposición 11.
14. De cuántas maneras se pueden sentar 10 personas en una sala de 15 asientos?.
15. De cuántas maneras se pueden se pueden intercambiar los dgitos del sistema decimal
si los pares se deben intercambiar con pares y los impares con impares?.
17
16. 6 personas ocupan 4 habitaciones sabiendo que ninguna puede quedar vacı́a. ¿De
cuántas maneras se pueden distribuir?.
17. Pruebe por inducción que si Tn está definido recursivamente ası́:
6,
si n=0;
Tn = 4Tn−1 + 2n , si n 6= 0.
entonces Tn = 7 · 4n − 2n .
18. En cada caso se da una definición recursiva para f (n) encuentre una fórmula explı́cita.
(
3 si n = 0
a) f (n) =
f (n − 1) + 2 con n > 0
(
4 si n = 0
b) f (n) =
3f (n − 1) con n > 0
(
3 si n = 0
c) f (n) =
= 2f (n − 1) + 5 con n > 0
19. Demuestre que si las sucesiones sn y tn cumplen la misma ley recursiva homogénea,
entonces xsn + ytn también la cumple.
20. Demuestre que si an = an−1 + an−2 y a0 = u, a1 = v entonces para n ≥ 1 se tiene
an = uFn−1 + vFn donde Fn es la sucesión de Fibonacci.
21. Considere la sucesión definida recursivamente ası́


u si n = 0
an = v si n = 1


2ran−1 − r 2 an−2 con n > 1
(nótese que aquı́ la ecuación caracterı́stica tiene sus dos raı́ces iguales). Demuéstrese
que existen x, y ∈ R tales que para todo n ∈ N se tiene an = xr n + ynr n .
22. Encontrar fórmulas explı́citas para el número de palabras de longitud n sobre el alfabeto
{a, b, c} que:
a) No contienen dos letras seguidas iguales.
b) No contienen la subpalabra aa.
c) No contienen la subpalabras aa ni bb.
3.
Cardinalidad
Los números surgen ante la necesidad de contar los elementos que tiene un conjunto A.
Ası́ los números naturales nos sirven para contar los elementos de conjuntos finitos. Se llega
a entender un conjunto finito como aquel que tiene un número natural de elementos. Faltarı́a
18
hablar de otro número ∞ para contar los elementos de conjuntos infinitos. Pero ¡NO!. En
primer lugar el ∞ con el que el lector debe estar familiarizado por sus cursos de cálculo, es
un infinito potencial por cuanto se refiere a una cantidad o variable que puede crecer tanto
como se quiera. George Cantor descubrió a finales del siglo XIX que se necesitan muchos
números de “otros” para contar los elementos de los conjuntos no finitos. Ası́ nacieron los
números transfinitos que no son los reales ni los complejos sino que conforman según
Hilbert,“el paraı́so que dejó Cantor para nosotros”. Intentaremos en esta sección dar una
breve introducción a este paraı́so (del cual “nadie nos podrá expulsar”). Bienvenidos!
Figura 2: George Cantor (1845-1918)
Definición 14. Dos conjuntos A y B son equipotentes si existe una biyección f : A −→ B.
Se nota A ∼ B y la relación ∼ se llama equipotencia y es una relación sobre la clase de todos
los conjuntos (que no es un conjunto).
Que dos conjuntos sean equipotentes significa intuitivamente que tienen igual cantidad
de elementos.
Proposición 17. La relación de equipotencia es una relación de equivalencia.
Demostración. Por ser la función idéntica biyección la equipotencia es una relación reflexiva.
Por ser la inversa de una biyección biyección la equipotencia es una relación simétrica. Por ser
la composición de una biyecciones biyección la equipotencia es una relación transitiva.
Definición 15. Un cardinal es cualquier clase de equivalencia según la relación de equipotencia. Si A es un conjunto, el cardinal de A, que se nota |A|, ser entonces
|A| = {X | A ∼ X}
Ejemplo 3.1. El familiar número dos 2 es como cardinal, la clase de todos los conjuntos
que son equipotentes con, por ejemplo, {0, 1}.
Definición 16. Un conjunto A es infinito si existe B ⊆ A tal que A 6= B y A ∼ B, caso
contrario se dice que A es finito.
Ejemplo 3.2. El conjunto N de los naturales es infinito ya que si 2N = {2n}n∈N es el
conjunto de los pares, se tiene que N ∼ 2N, en efecto f : N −→ 2N definida por f (n) = 2n
es una biyección.
Ejemplo 3.3. El conjunto {1, 2} es finito. Esto se puede demostrar exhaustivamente: Tome
todos los subconjuntos propios de {1, 2} que no son sino 3, y demuestre que ninguna de
las funciones inyectivas de los subconjuntos en él (en total 5), es biyección. Este método
puede resultar muy engorroso para demostrar que los conjuntos que conocemos son finitos.
La siguiente proposición 18 da una herramienta para demostrar que un conjunto es finito.
Proposición 18. Si a un conjunto finito se le une un conjunto con un solo elemento la
unión es un conjunto finito.
19
Demostración. Supongamos que A∪{x} es infinito y x ∈
/ A, sea B ⊆ A∪{x} con B 6= A∪{x}
y f : B −→ A ∪ {x} una biyección. Entonces B − f −1 (x) es equipotente con A, si B − f −1 (x)
no es un subconjunto de A, es porque x ∈ B entonces B − {x} es subconjunto propio de A
equipotente con B − f −1 (x) y por tanto con A. Entonces A no puede ser finito.
Ejemplo 3.4. ∅ es finito, pues no tiene subconjuntos propios. Por la proposición 18, {0} =
∅ ∪ {0} es finito. Ası́ mismo {0, 1} y en general {0, 1, . . . n − 1} es finito. De esta manera se
ve que los cardinales finitos coinciden con lo números naturales.
Definición 17. Un conjunto A es enumerable o numerable si A es ∅ o existe f : N −→ A
que es sobreyectiva.
Ejemplo 3.5. N × N es enumerable. En efecto por ejemplo la función f : N −→ N × N
definida recursivamente as


(0, 0) si n = 0
f (n) = (i + 1, j − 1) si f (n − 1) = (i, j) con j > 0


(0, i + 1) si f (n − 1) = (i, 0).
Cuál es la imagen de 5? Se recomienda calcular suficientes valores de f para convencerse
que realmente es sobreyectiva (en realidad biyección). La demostración formal sera algo más
engorroso.
Que N×N sea numerable es sorprendente y permite demostrar que muchos otros conjuntos
son numerables como Q,
Proposición 19. Si A es un un conjunto numerable y existe de A en B una función sobreyectiva entonces B es numerable.
Demostración. Si A es vacı́o entonces B también debe ser vacı́o. Si A no es vacı́o, el resultado
se tiene porque la composición de funciones sobreyectivas es sobreyectiva.
Proposición 20. Unión numerable de conjuntos numerables es numerable.
Demostración. Sea {Ai }i∈N una colección de conjuntos numerables no vacı́os. Entonces
S para
cada i ∈ N existe fi : N −→ Ai que es sobreyectiva. Sea ahora F : N × N −→ i∈N Ai
definida por F (n, m) = fn (m). Es fácil ver queSF ası́ definida es sobreyectiva, como N × N es
numerable por la proposición 19 tenemos que i∈N Ai es enumerable. El caso en que algunos
Ai son vacı́os es también muy sencillo.
Proposición 21. Q es numerable.
Demostración. Sea Z n1 los múltiplos de n1 , es decir Z n1 = { nz | z ∈ Z}. Entonces Q =
S
1
n∈N+ Z n es decir Q es la unión numerable de conjuntos numerables.
Ejemplo 3.6. P(N) no es enumerable: Este importante resultado debido a Cantor se generaliza en el Teorema de Cantor (ejercicio 16) que nos permite construir cardinales cada vez
más grandes. Si existiera una función f : N −→ P(N) sobreyectiva, vale hacernos la pregunta
i ∈ f (i)? Construimos el conjunto A = {n ∈ N | n ∈
/ f (n)} que es como “el barbero que
afeita a todos aquellos que no se afeitan a sı́ mismos”. Como f es sobreyectiva existir un
j ∈ N tal que f (j) = A y nos preguntamos “quién afeita al barbero?”, es decir j ∈ f (j)? Las
dos posibles respuestas nos llevan a un absurdo, por lo tanto no podemos aceptar que exista
tal f sobreyectiva.
20
Definición 18. Se dice que |A| ≤ |B| si existe una función f : A −→ B que es inyectiva.
Ejemplo 3.7. Para cualquier conjunto X se tiene |X| ≤ |P(X)|. En efecto, si a cada
elemento x ∈ X se le asocia el conjunto {x} ∈ P(X) se tiene una función inyectiva.
Proposición 22. La relación ≤ entre cardinales está bien definida, es reflexiva y transitiva.
Demostración. Esto se debe a que la función identidad es inyectiva y la composición de
funciones inyectivas es inyectiva
Proposición 23. Un conjunto es enumerable sisi su cardinal es menor o igual que el de los
naturales.
3.1.
Conjuntos efectivamente enumerables
Definición 19. Un conjunto A es efectivamente enumerable si existe una función f : N −→
A sobreyectiva que se puede calcular por un algoritmo.
La mayorñia de los conjuntos infinitos numerables que conocemos son efectivamente enumerables por cuanto para describirlos de alguna forma utilizamos un algoritmo. Pero esto
solo indica lo poco que conocemos. Una idea de conjuntos enumerables pero no efectivamente
enumerables se tiene trabajando el ejercicio 14 de esta sección.
Otra noción más fuerte es la de conjunto decidible que se da para un universo numerable
por ejemplo las palabras sobre un alfabeto finito. Se pide que dada una palabra se pueda
decidir algorı́tmicamente si esta pertenece o no al conjunto.
Definición 20. Un lenguaje L sobre Σ es decidible si existe un algoritmo que dada una
palabra w ∈ Σ∗ decide si w ∈ L o w ∈
/ L.
Proposición 24. Todo lenguaje decidible es efectivamente enumerable.
Demostración. Como el conjunto de las palabras sobre Σ es efectivamente enumerable, hay
un algoritmo para numerarlas. Sea S el lenguaje decidible, modificamos el algoritmo para
numerar todas las palabras preguntado si cada palabra producida pertenece o no a S, si la
respuesta es positiva ésta entra de la numeración de S, si no, pues no entra. Ası́ obtenemos
una numeración de S
3.2.
Ejercicios
1. Exhibir funciones biyectivas entre los conjuntos A y B dados (lo cual nos demuestra
que en cada caso estos conjuntos son equipotentes):
a) A = N y B = {n ∈ N | n ≥ 5}.
b) A = Z y B = N.
c) A = {n2 | n ∈ N} y B = N.
d ) A = {2n + 1 | n ∈ N} y B = N.
e) A = {x ∈ R | 0 < x < 1} y B = {x ∈ R | 5 < x < 7}.
f ) A = {x ∈ R | 0 ≤ x < 1} y B = {x ∈ R | 5 ≤ x < 7}.
21
g) A = {x ∈ R | 0 ≤ x < 1} y B = {x ∈ R | 5 < x ≤ 7}.
h) A = {X | X ⊆ {a, b, c}} y B = {0, 1} × {0, 1} × {0, 1}.
i ) A = {f : {0, 1} −→ {a, b, c} | f es función} y B = {a, b, c} × {a, b, c}.
j ) A = {f : {0, 1} −→ X | f es función} y B = X × X donde X es cualquier
conjunto.
k ) A = {X | X ⊆ U} y B = {f : U −→ {0, 1} | f es función} donde U = {a, b, c}.
l ) A = {X | X ⊆ U} y B = {f : U −→ {0, 1} | f es función} donde U es cualquier
conjunto.
m) (!) A = {x ∈ R | 0 < x < 1} y B = {x ∈ R | 0 < x < 1} × {x ∈ R | 0 < x < 1}.
n) (!) A = {x ∈ R | 0 < x < 1} y B = {x ∈ R | 0 < x ≤ 1}.
2. Demostrar que si A es finito y B ⊆ A entonces B es finito.
3. Demostrar que si A es enumerable y B ⊆ A entonces B es enumerable.
4. Un conjunto contiene un subconjunto equipotente con N si y sólo si es infinito.
5. Si los conjuntos A y B son enumerables lo son A ∪ B,A ∩ B y A × B. Demostrar.
6. Demostrar que el conjunto de palabras sobre un alfabeto finito es enumerable infinito.
7. Elaborar en cada caso un algoritmo para numerar:
a) Las palabras sobre Σ = {a, b} de longitud n.
b) Las palabras sobre Σ = {a, b}.
c) Las palabras sobre Σ = {a, b} que no contienen la subpalabra aa.
8. Cada función f de {0, 1, . . . n − 1} en {0, 1, . . . m − 1} se puede representar por un
arreglo 1-dimensional, digamos A(i), de n componentes de 0 hasta n − 1 en donde
A(i) = f (i). Elaborar algoritmos para:
a) Decidir si una función dada es inyectiva.
b) Decidir si una función dada es sobreyectiva.
9. Cada función f de {0, 1, . . . n − 1} en {0, 1, . . . m − 1} se puede representar por un
arreglo 1-dimensional, digamos A(i), de n componentes de 0 hasta n − 1 en donde
A(i) = f (i). Elaborar algoritmos (o fórmulas recursivas) para enumerar:
a) Las funciones de {0, 1, . . . n − 1} en {0, 1, . . . m − 1} constantes.
b) Todas las funciones de {0, 1, . . . n − 1} en {0, 1, . . . m − 1}.
c) Las funciones inyectivas de {0, 1, . . . n − 1} en {0, 1, . . . m − 1}.
d ) Las funciones sobreyectivas de {0, 1, . . . n − 1} en {0, 1, . . . m − 1}.
e) Las funciones biyectivas de {0, 1, . . . n − 1} en {0, 1, . . . m − 1}.
10. Elaborar algoritmos (o fórmulas recursivas) para enumerar:
22
a)
b)
c)
d)
e)
f)
N × {a, b}.
N × {a, b, c}.
Z.
N × N.
Z × N.
Z × Z.
g) Q.
h) Palabras sobre un alfabeto finito Σ.
i ) Los subconjuntos de {0, 1, . . . n − 1}.
j ) Los subconjuntos finitos de N.
k ) Los polinomios con coeficientes en Z.
11. Sea A un conjunto finito y B efectivamente enumerable, exhiba algoritmos (si existen)
para enumerar:
a) A ∪ B
c) A ∩ B
b) B − A
d) A × B
12. Sea A y B conjuntos efectivamente enumerables, exhiba algoritmos (si existen) para
enumerar:
a) A ∪ B
c) A ∩ B
b) B − A
d) A × B
13. Decidir de cada afirmación si es falsa o verdadera y argumentar brevemente su respuesta.
a) Todo subconjunto de un conjunto finito es finito.
g) Todo conjunto decidible es efectivamente enumerable.
b) Todo subconjunto de un conjunto infinito es infinito.
h) Todo conjunto efectivamente enumerable es enumerable.
i ) Todo conjunto enumerable es efectivamente enumerable.
c) Todo subconjunto de un conjunto
enumerable es enumerable.
j ) Todo conjunto enumerable es efectivamente enumerable.
d ) Todo subconjunto de un conjunto
efectivamente enumerable es efectivamente enumerable.
k ) Cualquier unión de conjuntos enumerables es enumerable.
e) Todo subconjunto de un conjunto decidible es decidible.
l ) Intersección de dos conjuntos decidibles es decidible.
f ) Todo conjunto efectivamente enumerable es decidible.
m) El conjunto de las tautologas es decidible.
14. Sean a0 a1 a2 . . . las cifras de la expansión decimal de algún número irracional. Aceptamos que la sucesión de los ai es generada algorı́tmicamente. Dar argumentos para
decidir si los siguientes conjuntos son finitos, enumerables, efectivamente enumerables
y decidibles.
a) {n ∈ N | ∃k, l ∈ N ((ak . . . ak+l )10 = n)}
23
b) {n ∈ N | ∀N∃k > N, l ∈ N ((ak . . . ak+l )10 = n)}
15. Demostrar que los siguientes conjuntos no son enumerables:
a) {x ∈ R | 0 < x < 1}
b) {x ∈ R | 0 ≤ x ≤ 1}.
c) Todas las funciones de N en {0, 1}.
d ) Todas las funciones de N en {0, 1, . . . m − 1}.
e) Los subconjuntos de N.
f ) Los reales entre 0 y 1 que en base 3 se escriben sólo con 0’s y 2’s (Conjunto
ternario de Cantor).
16. Teorema de Cantor Para cualquier cardinal α se tiene: α < 2α
24