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. Estosconceptos son basicos en la construccion del lenguaje de las matematicas actuales. Tanto lasrelaciones como las funciones son de gran importancia en la informatica, pues muchos temasse deben tratar con este lenguaje. Uno de ellos es el de la cardinalidad, o sea el numero deelementos de un conjunto cuando no nos limitamos a conjuntos finitos. especıficamente alhablar de numerabilidad y sobre todo, de conjuntos no enumerables, obtenemos resultadossorprendentes y relevantes en cuanto a lo que puede ser computable.

1. Relaciones

1.1. Generalidades

Definicion 1. Siendo A y B conjuntos el producto cartesiano A× B esta definido por:

A× B = {(x, y) | x ∈ A, y ∈ B}

Definicion 2. Siendo A y B conjuntos una relacion de A en B es cualquier conjunto R quecumple R ⊆ A× B

Notacion. Cuando R es una relacion tambien se nota xRy en lugar de (x, y) ∈ R

Segun nuestra definicion una relacion es simplemente un conjunto de parejas, es conve-niente a veces asociar esas parejas a un predicado de dos variables, digamos p(x, y), ası larelacion sera {(x, y) | p(x, y)}. En cierto sentido el producto cartesiano es el universo paralas proposiciones de dos variables.

Definicion 3. Siendo A un conjunto y R una relacion de A en A, es decir una relacion sobreA, se dice que R es:

Reflexiva Si ∀x ∈ A ((x, x) ∈ R)

Simetrica 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)

Antisimetrica Si ∀x, y ∈ A (((x, y) ∈ R ∧ (y, x) ∈ R) ⇒ x = y)

*Profesor titular UIS

1

Antirreflexiva Si ∀x ∈ A ((x, x) /∈ R)

Definicion 4. Una relacion R sobre un conjunto A se dice que es de equivalencia sobre Asi es reflexiva, simetrica y transitiva

Notacion. Las relaciones de equivalencia se notan con signos simetricos como ∼,≡,≃,≈,∼=.

Definicion 5. Dada una relacion de equivalencia ∼ sobre el conjunto A, se define para cadaa ∈ A la clase de equivalencia de a segun ∼ que se nota [a]∼ ası:

[a]∼ = {x ∈ A | a ∼ x}

cuando no hay lugar a confusion se nota simplemente [a]. El conjunto de todas las diferentesclases de equivalencia as formadas se nota A/ ∼.

Ejemplo 1.1. Sea m un entero positivo. La relacion de congruencia entre enteros modulo mes siempre una relacion de equivalencia para cualquier entero m ≥ 1. Dado cualquier enteron la clase de equivalencia segun la relacion de congruencia modulo m consiste en todos losenteros que tiene el mismo residuo que n al ser divididos por m, o lo que es lo mismo, losenteros de la forma km+ n. Se tiene:

[n] = {x ∈ Z | n ≡ x (mod m)} = {km+ n | k ∈ Z}

se tiene entonces m− 1 clases de equivalencia, todas infinitas.

Lema 1. Sea ∼ es una relacion de equivalencia sobre el conjunto A y a, b ∈ A, las siguientesafirmaciones son equivalentes:

i) a ∼ b

ii) a ∈ [b]∼

iii) b ∈ [a]∼

iv) [a]∼ = [b]∼

v) [a]∼ ∩ [b]∼ 6= ∅

Demostracion. De la definicion de [a]∼ y la simetrica 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]∼. Seapues x ∈ [a]∼ entonces a ∼ x y como a ∼ b aplicando transitiva y simetrica se tiene queb ∼ 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.

Proposicion 1. Dada una relacion de equivalencia ∼ sobre el conjunto A no vacıo, lasclases de equivalencia forman una particion de A.

2

Demostracion. 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 dosse sigue del lema.

Ahora bien, como para cada a ∈ A se tiene que [a]∼ ⊆ A por tanto⋃

a∈A[a]∼ ⊆ A. Porotra parte, si a ∈ A entonces a ∈ [a]∼ y por tanto a ∈ ⋃

a∈A[a]∼ y tenemos A ⊆ ⋃

a∈A[a]∼con lo que se concluye que

⋃

a∈A[a]∼ = A.

Definicion 6. Una relacion R sobre un conjunto A se dice que es de orden parcial sobreA si es reflexiva, antisimetrica y transitiva.

1.2. Representacion de Relaciones

Una relacion se puede “pintar” como un subconjunto del producto cartesiano, siempre ycuando dicho producto cartesiano se pueda representar. Por ejemplo la relacion R de R enR definida por R = {(x, y) | x2 + y2 ≤ 4} se representa un disco centrado en el origen y conradio 2 del plano cartesiano.

Tambien podemos utilizar flechas, especialmente cuando trabajamos relaciones finitas:Representamos los elementos de los conjuntos A y B por puntos y siempre que (x, y) ∈ Rtrazamos una flecha entre los respectivos puntos. Cuando A = B se pintan los puntos de Asolo una vez y se obtiene el digrafo o grafo dirigido de R1. Cuando se sabe de antemano quela relacion es simetrica, sobra poner sentido a las flechas y obtenemos el grafo (o la grafica)de la relacion.

0

1 3

4

2

Figura 1: Grafo de la relacion simetrica que contiene las parejas(0, 1), (1, 2), (1, 3), (2, 3), (3, 4) y (4, 0).

Desde el punto de vista informatico, ası como los conjuntos se representan por vectoresbooleanos, las relaciones conviene representarlas por matrices booleanas.

Definicion 7. Siendo A y B conjuntos finitos, digamos A = {a1, . . . an} y B = {b1, . . . bm},cualquier relacionR deA enB se puede representar por la matriz booleanaMR = (mi,j)i:1,...,n; j:1,...,mde n filas y m columnas donde mi,j = 1 ⇔ (ai, bj) ∈ R.

Observando la matriz de una relacion entre conjuntos finitos es inmediato saber si larelacion es reflexiva, simetrica y antisimetrica. Por una observacion mas de sencilla no esfacil ver si es transitiva.

1Los mexicanos hablan de graficas en lugar de grafos, tal vez mas castizo.

3

1.3. Composicion de Relaciones

Con las relaciones por ser conjuntos, podemos hacer uniones intersecciones, hablar de unarelacion contenida en otra, etc.. Hay ciertas operaciones y operadores entre relaciones que noprovienen de los conjuntos: el operador inverso y la operacion composicion entre relaciones,que introducimos enseguida.

Definicion 8. Siendo A y B conjuntos y R una relacion entre ellos se define

R−1 = {(y, x) | (x, y) ∈ R}

que es la relacion inversa de R y esta definida de B en A.

Definicion 9. Siendo A, B y C conjuntos, R una relacion de A en B, S una relacion de Ben C, definimos la relacion 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 inmediatade las definiciones y las omitimos.

Proposicion 2. La composicion entre relaciones ◦ es asociativa es decir (R ◦ S) ◦ T =R ◦ (S ◦ T )

Proposicion 3. (R ◦ S)−1 = S−1 ◦R−1

Proposicion 4. La relacion R es transitiva si y solo sı R ◦R ⊆ R

Definicion 10. Sea M = (mi,j) matriz booleana de orden n × m y N = (mj,k) matrizbooleana 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ı:

ci,k =

m∨

j=1

(mi,j ∧ nj,k)

Proposicion 5. Siendo A, B y C conjuntos finitos, R una relacion de A en B, S unarelacion de B en C, la matriz de la relacion S ◦R de A en C esta dada por:

M(S◦R) = MR ⊙MS

Demostracion. 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) ⇔m∨

j=1

(mi,j ∧ nj,k) = 1

4

1.4. Ejercicios

1. Explique por que si S, T,W son conjuntos no podemos asegurar que S × (T ×W ) =(S × T )×W . Determine en que 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 parejasde cada una de las siguientes relaciones sobre {a, b, c} y determine si son reflexivas,antirreflexivas, simetricas, antisimetricas o transitivas:

a) R

b) S

c) R ∪ S

d) R ∩ S

e) R ◦ Sf ) R−1 ∪ S

g) R ∩ R−1

h) S ◦R

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 relacion y exhibir su matriz:

a) R ∩ S.

b) R ∪ S

c) R ∩ S−1

d) S ◦Re) R ∩ S

4. ¿Cuantas relaciones hay de un conjunto con n elementos en un conjunto con m ele-mentos? Demuestre que si |A| = n hay exactamente 2n

2

sobre A y que de estas, 2n(n−1)

son reflexivas y 2n(n+1)/2 son simetricas.

5. Sea A el conjunto de todos los humanos y consideermos las relaciones P y M definidaspor:

(x, y) ∈ P sisi el padre de x es y.

(x, y) ∈ M sisi la madre de x es y

que significado tiene las siguientes relaciones sobre A?

a) P ◦ Pb) (P ∪M) ◦ (P ∪M)

c) P ◦ P−1

d) (P ∪M) ◦ (P ∪M)−1

e) (P ◦ P−1) ∪ (M ◦M−1)

6. Cuales de las siguientes relaciones sobre los naturales son reflexivas, antirreflexivas,simetricas, antisimetricas o transitivas, cuales son ordenes parciales (definicion 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 relacion Θ sobre Σ∗. Interpretequ significa cada relacion y decida si la relacion ası definida es reflexiva, antirreflexiva,simetrica, antisimetrica o transitiva:

a) i) Base: ∀α ∈ Σ∗(α, α) ∈ Θ.

ii) Paso inductivo: Si α, β ∈ Σ∗, x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ.

iii) Clausura: Θ se calcula unicamente aplicando i) y ii).

b) i) Base: (λ, λ) ∈ Θ.

ii) Paso inductivo: Si α, β ∈ Σ∗, x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ.

iii) Clausura: Θ se calcula unicamente aplicando i) y ii).

c) i) Base: ∀α ∈ Σ∗(α, α) ∈ Θ.

ii) Paso inductivo: Si α ∈ Σ∗, x ∈ Σ y (α, β) ∈ Θ entonces (α, βx) ∈ Θ y(α, xβ) ∈ Θ.

iii) Clausura: Θ se calcula unicamente aplicando i) y ii).

8. El conjunto ∅ es una relacion entre cualquier par de conjuntos A yB. ¿Que propiedadestiene?

9. Segun la proposicion 5 la matriz MR ⊙ MS tiene un 1 en el puesto i, j si y solo sii esta conectado con j por medio de R ◦ S, si no estan conectados habra un 0. Sihicieramos la multiplicacin deMR yMS de la manera usual, podramos obtener numerosmayores que 1. ¿Que significado tienen los numeros mayores que 1 en MRMS?

10. Sean R y S relaciones sobre el conjunto A. IA la identidad en A. En cada caso contestefalso o verdadero y justifique brevemente.

a) Si R es reflexiva entonces R ∩ S lo es.

b) Si R es simetrica entonces R = R−1.

c) Si R y S son antisimetricas entonces R ∪ S lo es.

d) Si R ∪ S es reflexiva entonces R y S lo son.

e) Si R es simetrica 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 simetricas sobre el conjunto {a, b, c} de tal forma que su com-puesta no sea simetrica.

12. Muestre dos relaciones transitivas sobre el conjunto {a, b, c} de tal forma que su com-puesta no sea transitiva.

13. Sean R = {(2, 1), (2, 3)} y S = {(2, 3), (4, 2)(2, 1), (4, 1)} relaciones sobre el conjuntoA = {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 relacion 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 relacion T sobre el conjunto A = {1, 2, 3, 4}que es de equivalencia y tal que R ⊆ T . (T es la clausura de equivalencia deR).

c) Cuales son las clases de equivalencia que forma T ?

15. A continuacion se define la relacion ∼ sobre el conjunto Z. Demuestre que en cada casola relacion es de equivalencia y determine cuantas clases de equivalencia se forman.

a) n ∼ m ⇔ n−m es par.

b) n ∼ m ⇔ n−m es divisible por 5.

c) n ∼ m ⇔ nm > 0 o n = m = 0.

d) n ∼ m ⇔ n/m o m/n son potencia de 2 o n = m = 0

16. A continuacion se define la relacion ∼ sobre C• el conjunto de los complejos sin el 0.Demuestre que en cada caso la relacion es de equivalencia y determine como son susclases de equivalencia.

a) z1 ∼ z2 ⇔ ∃α ∈ R(αz1 = z2)

b) z1 ∼ z2 ⇔ ∃α ∈ R, α > 0(αz1 = z2)

c) z1 ∼ z2 ⇔ (|z1| = |z2|)d) z1 ∼ z2 ⇔ (Re(z1) = Re(z2))

e) z1 ∼ z2 ⇔ (Im(z1) = Im(z2))

17. Probar que si una relacion R es reflexiva y transitiva entonces R ∩ R−1 es de equiva-lencia.

18. Probar que si las relaciones R y S son reflexivas y simetricas entonces las siguientescondiciones son equivalentes:

i) R ◦ S es simetrica.

ii) R ◦ S = S ◦R.

7

2. Funciones

Las funciones son un tipo especial de relaciones. Informalmente a cada elemento deldominio se le asocia un unico elemento del conjunto de llegada. Generalmente esta relacionse especifica por medio de una formula o algoritmo. El concepto de funcion es un conceptoclave en la matematica y en la informatica. Podemos decir que todo programa de computadores una funcion en cuanto dada una entrada especıfica, produce una salida.

Definicion 11. Sea R una relacion de A en B, se dice que R es una funcion de A en B sise 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 elrecorrido, la segunda exige que este sea unico. Realmente el concepto de funcion incluye trescosas: el dominio, el recorrido y el conjunto de parejas.

Notacion. Se acostumbra notar con las letras f, g, h las funciones. Cuando f es una funcionde A en B se nota f : A −→ B y si (x, y) ∈ f se escribe f(x) = y. Ası, f(x) se denomina laimagen de x.

Tal como las relaciones, las funciones pueden tener o no una formula, expresion o algo-ritmo que determine la imagen de cada elemento del dominio. Sin embargo las funciones quetienen dicha “formula, expresion o algoritmo”, como comprobaremos mas adelante, son unaparte muy pequena de todas las funciones. Por tanto no conviene confundir el concepto defuncion con una “formula, expresion o algoritmo”.

Realmente para hablar de funciones hay que tener en cuenta tres cosas: el conjunto deparejas, el conjunto de salida o dominio de la funcion, y el conjunto de llegada o recorrido dela funcion. El conjunto de parejas por sı mismo no forma una funcion. Un mismo conjuntode 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 aun la formula constituyenuna funcion. Por ejemplo si hablamos de la formula: x2 + y2 = 1 podrıamos referirnos alconjunto de parejas:

R = {(x, y) : x2 + y2 = 1}que visto como subconjunto de R×R no es una funcion. R es una funcion de [−1, 1] en R yotra funcion de [0, 1] en [−1, 1].

Ejemplo 2.2. La coleccion indicada de conjuntos {Ai}i∈I se puede entender como unafuncion f : I −→ P(X) donde Ai ⊆ X para todo i ∈ I.

Ejemplo 2.3. La funcion caracterıstica de un conjunto A donde A ⊆ X es una funcionχA : X −→ Z2 donde χA(x) = 0 ⇔ x /∈ A.

8

Ejemplo 2.4. La pareja (a, b) se puede ver como una funcion f : {1, 2} −→ X dondef(1) = a, f(2) = b y a, b ∈ X . El producto cartesiano A× B se puede ver como el conjuntode funciones {f : {1, 2} −→ A ∪B |f(1) ∈ A, f(2) ∈ B }. De aquı se generaliza el conceptode producto cartesiano para cualquier coleccion indicada de conjuntos {Ai}i∈I , ası:

∏

i∈IAi = {f : I −→

⋃

i∈IAi | f(i) ∈ Ai}.

Un caso especial es cuando Ai = A para todo i ∈ I se nota entonces∏

i∈I A = AI y se tiene:

AI = {f : I −→ A | f es funcion}.

Ejemplo 2.5. Una palabra de n letras sobre el alfabeto Σ se puede ver como una funcionw : {1, 2, . . . n} −→ Σ.

Ejemplo 2.6. La funcion parte entera f : R −→ R donde f(x) es el mayor entero menoro igual que x. Se nota ⌊x⌋

Ejemplo 2.7. La funcion exponencial f : R −→ R+ en base b definida por f(x) = bx.

Ejemplo 2.8. La funcion de Collatz f : N+ −→ N+ esta definida as:

f(n) =

1 si n = 1

f(n) = n2Si 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 naturalesse puede ver como una funcion S : N× N −→ N en donde S(x, y) se nota x+ y.

2.2. Composicion de funciones

La composicion de funciones se hace como la de las relaciones, toca sin embargo, asegu-rarnos que realmente se produce una nueva funcion.

Proposicion 6. Sean R ⊆ A×B y S ⊆ B×C, si R y S son funciones (de A en B y de Ben C,respectivamente) entonces S ◦R es funcion de A en C.

Notacion. Si f : A −→ B y g : B −→ C son funciones su compuesta se nota g◦f : A −→ Ces decir g ◦ f(x) = g(f(x))

Ejemplo 2.10. Si RES( ;m) : Z −→ Z es la funcion residuo al dividir entre m > 0entonces 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 queal aplicar sucesivamente la funcion a determinado numero se debe llegar a 1, esto sin embargono quiere decir, que la funcion de Collatz compuesta un determinado numero de veces seala constante 1.

9

Definicion 12. Sea f : A −→ B una funcion 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 biyeccion y A = B se dice que f es una permutacion de A.

Ejemplo 2.12. Si A ⊆ B se puede definir inA,B : A −→ B, la funcion inclusion, definidapor inA,B(a) = a para todo a ∈ A. Esta funcion inA,B siempre es inyectiva y si A = B setiene inA,B = IA la funcion identica que es la unica relacion que es a la vez de equivalenciay funcion. Se define ademas para cada f : B −→ C la restriccion de f a A como la funcionf ⇃A= f ◦ inA,B.

Proposicion 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.

Demostracion. 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 quedandoprobado que g es sobreyectiva.

iv) Demostraremos la contrarecıproca. Si f no es 1-1 entonces existen x1, x2 ∈ A conx1 6= x2 tal que f(x1) = f(x2) y aplicando g tenemos g(f(x1)) = g(f(x2)) entonces g ◦ f noes inyectiva.

Las funciones como las relaciones tienen inversa pero no siempre dicha inversa es unafuncion.

Proposicion 8. Sea f : A −→ B funcion. Condicion necesaria y suficiente para que f−1

sea funcion es que f sea biyeccion.

Demostracion. Traduzcamos la definicion de funcion 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 funcion exponencial f : R −→ R+ en base b > 0 definida por f(x) = bx

tiene como inversa la funcion g : R+ −→ R definida por g(x) = logb(x). Notese que siconsideramos f : R −→ R definida de manera igual, su inversa no es funcion.

10

Cuando una funcion tiene inversa (es decir cuando es biyectiva) al componerlas se pro-ducen las dos identicas y las unicas relaciones que cumplen esto son las biyecciones:

Proposicion 9. Sea f : A −→ B biyeccion. Entonces

f−1 ◦ f = IdA ∧ f ◦ f−1 = IdB

Por otra parte, si R ⊆ A× B cumple que

R−1 ◦R = IdA ∧ R ◦R−1 = IdB

entonces R es una biyeccion de A en B

Demostracion. Notese las siguientes “traducciones”:

a. R−1 ◦R ⊆ IdA ⇐⇒ ∀x ∈ A∃y ∈ B(xRy)

b. R−1 ◦R ⊇ IdA ⇐⇒ ∀x1, x2 ∈ A∀y ∈ B(x1Ry ∧ x2Ry ⇒ 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”:

Proposicion 10. Sea A 6= ∅ y f : A −→ B funcion.

1. Existe g : B −→ A tal que f ◦ g = IdB si y solo si f es sobreyectiva. Se dice que g esuna inversa a derecha de f .

2. Existe g : B −→ A tal que g ◦ f = IdA si y solo si f es inyectiva. Se dice que g es unainversa a izquierda de f .

Demostracion. • Veamos que si f tiene inversa a derecha entonces es sobreyectiva. Sea y ∈ Bentonces 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 . Paracada y ∈ B por ser f sobre existe algun 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 tantopara 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 izquierdaentonces

x1 = g(f(x1)) = g(f(x2)) = x2

por lo tanto f es 1-1.

2Realmente estamos usando el axioma de eleccion, este item de nuestra proposicion es una forma de

expresar tal axioma, sutil e importante que ha generado mucha literatura matematica. Por ahora anotemosque se puede hacer matematicas sin utilizarlo.

11

• Para construir g que sea inversa a izquierda de f sabiendo que f es 1-1, dado y ∈ B siexiste x tal que f(x) = y entonces hacemos g(y) = x, queda bien determinada x porser f inyectiva. Si no existe tal x, es decir si ∀x(f(x) 6= y) escogemos cualquier a0,∈ Ay definimos g(y) = a0. Aquı hemos usado que A 6= ∅. Se tiene g(f(x)) = x por laconstruccion.

Ejemplo 2.14. Hagamos f = {(1, a), (2, a)}, g = {(a, 1)} entonces tomando A = {1, 2} yB = {a} tenemos g : B −→ A y f : A −→ B y se cumple que f ◦ g = IdB por tanto f esinversa 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 cadafuncion.

2.3. Imagen Directa e Imagen Inversa

Las funciones operan en principio sobre elementos pero tambien es muy util verlas ope-rando sobre subconjuntos tanto del dominio como del recorrido.

Definicion 13. Sea f : A −→ B cualquier funcion 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 funcioninversa de f que probablemente no exista (como funcion).

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∈Zf−1({0}) = {kπ}k∈Zf({(2k + 1)π/2}k∈Z) = {1,−1}

Proposicion 11. Sea f : A −→ B una funcion, 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 solo 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 solo si f es sobreyectiva.

12

Proposicion 12. Sea f : A −→ B una funcion, si para todo i ∈ I tenemos Yi ⊆ B y Xi ⊆ Aentonces:

1. f−1(⋂

i∈I Yi) =⋂

i∈I f−1(Yi).

2. f−1(⋃

i∈I Yi) =⋃

i∈I f−1(Yi).

3. f(⋂

i∈I Xi) ⊆⋂

i∈I f(Xi)

4. f(⋃

i∈I Xi) =⋃

i∈I f(Xi)

5. f es inyectiva si y solo f(⋂

i∈I Xi) =⋂

i∈I f(Xi).

2.4. Contando funciones entre conjuntos finitos

Proposicion 13. El numero de funciones entre un conjunto con n elementos y otro con melementos esta dado por

mn

Demostracion. Hay tantas de estas funciones como palabras de n letras sobre un alfabetocon m letras.

Proposicion 14. El numero de funciones inyectivas entre un conjunto con n elementos yotro con m elementos, donde 0 < n ≤ m, esta dado por

mn = m(m− 1) . . . (m− n+ 1)

Demostracion. Notemos [n] = {1 . . . n} para cada n ∈ N+. Para n ≥ m calcularemos elnumero de funciones inyectivas de [n] en [m]. Hacemos induccion sobre n: Si n = 1 es claroque hay m funciones todas inyectivas (m ≥ n). Supongamos (hipotesis de induccion) m > ny que hay

mn = m(m− 1) . . . (m− n+ 1)

funciones de inyectivas de [n] en [m]. entonces para cada funcion f : [n] −→ [m] podemosconstruir f ′ : [n + 1] −→ [m] haciendo f ′(i) = f(i) si i ∈ [n] y escogiendo f ′(n + 1) en elconjunto [m] − f([n]); ası f ′ sera inyectiva y podramos escoger m − n funciones. Por otraparte, todas las funciones inyectivas se pueden construir ası y de manera unica. Por tantohay

mn+1 = m(m− 1) . . . (m− n+ 1)(m− n)

funciones f : {1, . . . , n, n+ 1} −→ {1, . . . , m} inyectivas.

Proposicion 15. El numero de permutaciones de un conjunto con n elementos es

n!

Demostracion. Este es un corolario de la proposicion anterior.

Para la demostracion de la siguiente proposicion se usa el principio de inclusion-exclusiony el cardinal del conjunto de funciones entre dos conjuntos (proposicion 13). Antes veamosun 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 queno son sobreyectivas. Entonces sea Ai = {f : {1, 2, 3, 4} −→{1,2,3} | i /∈ f({1, 2, 3, 4})} esdecir, aquellas cuya imagen esta contenida en {1, 2, 3} − {i} (hay 24) y ası las funciones nosobreyectivas son exactamente las del conjunto A1 ∪ A2 ∪ A3 y por el principio de inclusinexclusion (descontando las tres constantes) hay

(

3

2

)

24 − 3

funciones no sobreyectivas, es decir tenemos

34 −(

3

2

)

24 + 3 = 81− 3× 16 + 3 = 36

funciones sobreyectivas. Es bueno contarlas de otras maneras. Todas las funciones sobreyec-tivas tiene necesariamente dos elementos y unicamente dos, que tiene igual imagen. Si estaimagen es 1 hay 2

(

42

)

= 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

Proposicion 16. El numero de funciones sobreyectivas entre un conjunto con n elementosy otro con m elementos esta dado por

m∑

i=0

(−1)i(

m

i

)

(m− i)n

Demostracion. Notemos n = {1, 2, . . . , n}. Sabemos que el cardinal de M el conjunto de lasfunciones entre n y m es mn. Por cada j ∈ m sea

Mj = {f ∈ M | j /∈ f(n)}

es evidente que N =⋃

j∈nMj es el conjunto de todas las funciones de M que NO sonsobreyectivas. Por el principio de inclusion exclusion se tiene

|N | =∑

∅6=J⊆n

(−1)|J |−1 |AJ | , donde AJ =⋂

j∈JMj .

Pero AJ = {f ∈ M | f(n) ⊆ m− J} entonces |AJ | = (m− |J |)n. Si hacemos la suma sobrei = |J | como hay

(

mi

)

conjuntos J ⊆ n con esta condicion entonces

|N | =n

∑

i=1

(−1)i−1

(

m

i

)

(m− i)n

como nos interesa son las funciones sobreyectivas tenemos

|M −N | = mn −n

∑

i=1

(−1)i−1

(

m

i

)

(m− i)n =n

∑

i=0

(−1)i(

m

i

)

(m− i)n

14

2.5. Sucesiones definidas recursivamente

Una sucesion es una funcion cuyo dominio son los numeros naturales. Hemos visto muchassucesiones definidas recursivamente. En ellas se da los valores de el(los) primer(os) termino(s)y luego una regla para calcular el n-simo en terminos de uno o varios anteriores. Tambien sedefinen recursivamente funciones cuyo dominio son el conjunto de palabras (ver ejercicio 6).Trataremos ahora de sistematizar un metodo para hallar formulas explıcitas para algunassucesiones definidas recursivamente. Tal vez el caso mas conocido y motivante es la sucesionde Fibonacci que como se sabe es define recursivamente por Fn+1 = Fn + Fn−1 con F0 = 0

y F1 = 1. Se puede demostrar por induccion que siendo α = 1+√5

2y β = 1−

√5

2, el n-simo

termino de la sucesion de Fibonacci es:

Fn =1√5(αn − βn)

Es en principio sorprendente esta formula porque ademas de involucrar numeros relacio-nados por la proporcion aurea, patron de la belleza griega, a partir de numeros irracionalesproducimos numeros enteros. Nos interesa ver como se producen formulas explıcitas a partirde las definiciones recursivas. El caso mas sencillo lo dejamos como ejercicio. Estudiaremos lasdefiniciones recursivas homogeneas de segundo orden, en donde el termino general dependede los dos anteriores multiplicados por constantes y estan definidas ası:

Tn =

u, si n = 0;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 sucesion, mejor “ley derecurrencia” se le asocia el polinomio x2 − ax − b llamado caracterıstico. Sus raıces nosdan diran mucho de la solucion explıcita.

Proposicion 1. Cualquier sucesion de la forma sn = xαn + yβn donde α, β son solucionesa la ecuacion x2 = ax+ b, cumple la ley recursiva sn+1 = asn + bsn−1.

Demostracion. Supongamos que α, β son soluciones a la ecuacion 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−1y(aβ + b)

= αn−1xα2 + βn−1yβ2

= xαn+1 + yβn+1

= sn+1

Ejemplo 2.18. La ley recursiva

sn+1 = 5sn − 6sn−1

con ecuacion caracterıstica (x−3)(x−2) la cumplen todas las siguientes sucesiones: 3n, 3n+5,2n, 3n + 2n, 3n − 5× 2n, etc.

15

Proposicion 2. Sea sn la sucesion definida recursivamente ası:

s0 = u; s1 = v.

sn+1 = asn + bsn−1.

si α 6= β son soluciones a la ecuacion x2 = ax + b, entonces existen x, y ∈ R tales que paratodo n ∈ N se cumple sn = xαn + yβn.

Demostracion. Por la proposicion 1 se sabe la forma general, como sabemos los valorescuando n = 0, 1 entonces Conseguimos x, y ∈ R tales que se cumpla:

u = x+ y

v = αx+ βy

como α 6= β el sistema tiene una unica solucion.

La demostracion de la anterior proposicion nos determina un metodo para dar una formu-la explıcita de la sucesion siempre que el polinomio caracterıstico asociado tenga dos raıcesdiferentes. Cuando α = β en el ejercicio 21 se piede demostrar que para este caso se tiene:

Proposicion 3. Sea sn la sucesion definida recursivamente ası:

s0 = u; s1 = v.

sn+1 = asn + bsn−1.

si la ecuacion 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 relacion R sobre el conjunto A es una biyeccion si y solo si R◦R−1 =R−1 ◦R = IA

2. Si A tiene n elementos cuantas funciones hay de A en {1}?

3. Entre cuales conjuntos ∅ es una funcion?

4. A cada persona de una poblacion se le asocia su lugar de residencia. Que significa queesta relacion sea funcion? Que sea inyectiva? Que sea sobre?

5. Sean R ⊆ A×B una relacion y f : B −→ C una funcion demostrar que R ◦ f cumple

(x, y) ∈ R ⇒ (x, f(y)) ∈ (f ◦R)

6. Sea Σ = {a, b} en cada caso se define recursivamente la funcion f con dominioΣ∗.Decidir si la funcion queda bien definida, y en caso afirmativo si es inyectiva y/osobreyectiva:

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 unicamente 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 unicamente 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 unicamente aplicando i) y ii).

7. Sean R ⊆ A×A una relacion y f : A −→ B una biyeccion entonces f−1 ◦R ◦ f cumple

(x, y) ∈ R ⇔ (f(x), f(y)) ∈ (f−1 ◦R ◦ f)

8. Si {Ai}i∈I , es una coleccion de conjuntos para cada j ∈ I se define πj la j-esimaproyeccion ası: πj :

∏

i∈I Ai −→ Aj donde πj(f) = f(j) para cada f ∈ ∏

i∈I Ai.Demostrar que para cualesquier coleecion de funciones ρj : C −→ Aj existe un unicafuncion F : C −→ ∏

i∈I Ai de tal forma que para todo j ∈ I se tiene πj ◦ F = ρj .

9. Analice la funcion f : N −→ N× N definida recursivamente ası:

f(n) =

(0, 0) si n = 0

(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 funcion si tiene dos inversas a derecha diferentes entoncesno 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 ges uno a uno.

12. Sea f : A −→ B una funcion.

f es inyectiva si y solo para todas g1, g2 : B −→ C se cumple f ◦g1 = f ◦g2 ⇒ g1 = g2.

f es sobreyectiva si y solo para cualesquier g1, g2 : C −→ A se cumple g1◦f = g2◦f ⇒g1 = g2.

13. Probar la proposicion 11.

14. De cuantas maneras se pueden sentar 10 personas en una sala de 15 asientos?.

15. De cuantas maneras se pueden se pueden intercambiar los dgitos del sistema decimalsi 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. ¿Decuantas maneras se pueden distribuir?.

17. Pruebe por induccion que si Tn esta 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 definicion recursiva para f(n) encuentre una formula explıcita.

a) f(n) =

{

3 si n = 0

f(n− 1) + 2 con n > 0

b) f(n) =

{

4 si n = 0

3f(n− 1) con n > 0

c) f(n) =

{

3 si n = 0

= 2f(n− 1) + 5 con n > 0

19. Demuestre que si las sucesiones sn y tn cumplen la misma ley recursiva homogenea,entonces xsn + ytn tambien la cumple.

20. Demuestre que si an = an−1 + an−2 y a0 = u, a1 = v entonces para n ≥ 1 se tienean = uFn−1 + vFn donde Fn es la sucesion de Fibonacci.

21. Considere la sucesion definida recursivamente ası

an =

u si n = 0

v si n = 1

2ran−1 − r2an−2 con n > 1

(notese que aquı la ecuacion caracterıstica tiene sus dos raıces iguales). Demuestreseque existen x, y ∈ R tales que para todo n ∈ N se tiene an = xrn + ynrn.

22. Encontrar formulas explıcitas para el numero 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 numeros surgen ante la necesidad de contar los elementos que tiene un conjunto A.Ası los numeros naturales nos sirven para contar los elementos de conjuntos finitos. Se llegaa entender un conjunto finito como aquel que tiene un numero natural de elementos. Faltarıa

18

hablar de otro numero ∞ para contar los elementos de conjuntos infinitos. Pero ¡NO!. Enprimer lugar el ∞ con el que el lector debe estar familiarizado por sus cursos de calculo, esun infinito potencial por cuanto se refiere a una cantidad o variable que puede crecer tantocomo se quiera. George Cantor descubrio a finales del siglo XIX que se necesitan muchosnumeros de “otros” para contar los elementos de los conjuntos no finitos. Ası nacieron losnumeros transfinitos que no son los reales ni los complejos sino que conforman segunHilbert,“el paraıso que dejo Cantor para nosotros”. Intentaremos en esta seccion dar unabreve introduccion a este paraıso (del cual “nadie nos podra expulsar”). Bienvenidos!

Figura 2: George Cantor (1845-1918)

Definicion 14. Dos conjuntos A y B son equipotentes si existe una biyeccion f : A −→ B.Se nota A ∼ B y la relacion ∼ se llama equipotencia y es una relacion sobre la clase de todoslos conjuntos (que no es un conjunto).

Que dos conjuntos sean equipotentes significa intuitivamente que tienen igual cantidadde elementos.

Proposicion 17. La relacion de equipotencia es una relacion de equivalencia.

Demostracion. Por ser la funcion identica biyeccion la equipotencia es una relacion reflexiva.Por ser la inversa de una biyeccion biyeccion la equipotencia es una relacion simetrica. Por serla composicion de una biyecciones biyeccion la equipotencia es una relacion transitiva.

Definicion 15. Un cardinal es cualquier clase de equivalencia segun la relacion de equipo-tencia. Si A es un conjunto, el cardinal de A, que se nota |A|, ser entonces

|A| = {X | A ∼ X}

Ejemplo 3.1. El familiar numero dos 2 es como cardinal, la clase de todos los conjuntosque son equipotentes con, por ejemplo, {0, 1}.

Definicion 16. Un conjunto A es infinito si existe B ⊆ A tal que A 6= B y A ∼ B, casocontrario 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 elconjunto de los pares, se tiene que N ∼ 2N, en efecto f : N −→ 2N definida por f(n) = 2nes una biyeccion.

Ejemplo 3.3. El conjunto {1, 2} es finito. Esto se puede demostrar exhaustivamente: Tometodos los subconjuntos propios de {1, 2} que no son sino 3, y demuestre que ninguna delas funciones inyectivas de los subconjuntos en el (en total 5), es biyeccion. Este metodopuede resultar muy engorroso para demostrar que los conjuntos que conocemos son finitos.La siguiente proposicion 18 da una herramienta para demostrar que un conjunto es finito.

Proposicion 18. Si a un conjunto finito se le une un conjunto con un solo elemento launion es un conjunto finito.

19

Demostracion. Supongamos que A∪{x} es infinito y x /∈ A, sea B ⊆ A∪{x} con B 6= A∪{x}y f : B −→ A∪{x} una biyeccion. 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 Aequipotente 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 proposicion 18, {0} =∅ ∪ {0} es finito. Ası mismo {0, 1} y en general {0, 1, . . . n− 1} es finito. De esta manera seve que los cardinales finitos coinciden con lo numeros naturales.

Definicion 17. Un conjunto A es enumerable o numerable si A es ∅ o existe f : N −→ Aque es sobreyectiva.

Ejemplo 3.5. N × N es enumerable. En efecto por ejemplo la funcion f : N −→ N × N

definida recursivamente as

f(n) =

(0, 0) si n = 0

(i+ 1, j − 1) si f(n− 1) = (i, j) con j > 0

(0, i+ 1) si f(n− 1) = (i, 0).

Cual es la imagen de 5? Se recomienda calcular suficientes valores de f para convencerseque realmente es sobreyectiva (en realidad biyeccion). La demostracion formal sera algo masengorroso.

Que N×N sea numerable es sorprendente y permite demostrar que muchos otros conjuntosson numerables como Q,

Proposicion 19. Si A es un un conjunto numerable y existe de A en B una funcion sobre-yectiva entonces B es numerable.

Demostracion. Si A es vacıo entonces B tambien debe ser vacıo. Si A no es vacıo, el resultadose tiene porque la composicion de funciones sobreyectivas es sobreyectiva.

Proposicion 20. Union numerable de conjuntos numerables es numerable.

Demostracion. Sea {Ai}i∈N una coleccion de conjuntos numerables no vacıos. Entonces paracada 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 facil ver que F ası definida es sobreyectiva, como N×N esnumerable por la proposicion 19 tenemos que

⋃

i∈N Ai es enumerable. El caso en que algunosAi son vacıos es tambien muy sencillo.

Proposicion 21. Q es numerable.

Demostracion. Sea Z 1n

los multiplos de 1n, es decir Z 1

n= { z

n| z ∈ Z}. Entonces Q =

⋃

n∈N+ Z 1nes decir Q es la union numerable de conjuntos numerables.

Ejemplo 3.6. P(N) no es enumerable: Este importante resultado debido a Cantor se gene-raliza en el Teorema de Cantor (ejercicio 16) que nos permite construir cardinales cada vezmas grandes. Si existiera una funcion f : N −→ P(N) sobreyectiva, vale hacernos la preguntai ∈ f(i)? Construimos el conjunto A = {n ∈ N | n /∈ f(n)} que es como “el barbero queafeita a todos aquellos que no se afeitan a sı mismos”. Como f es sobreyectiva existir unj ∈ N tal que f(j) = A y nos preguntamos “quien afeita al barbero?”, es decir j ∈ f(j)? Lasdos posibles respuestas nos llevan a un absurdo, por lo tanto no podemos aceptar que existatal f sobreyectiva.

20

Definicion 18. Se dice que |A| ≤ |B| si existe una funcion f : A −→ B que es inyectiva.

Ejemplo 3.7. Para cualquier conjunto X se tiene |X| ≤ |P(X)|. En efecto, si a cadaelemento x ∈ X se le asocia el conjunto {x} ∈ P(X) se tiene una funcion inyectiva.

Proposicion 22. La relacion ≤ entre cardinales esta bien definida, es reflexiva y transitiva.

Demostracion. Esto se debe a que la funcion identidad es inyectiva y la composicion defunciones inyectivas es inyectiva

Proposicion 23. Un conjunto es enumerable sisi su cardinal es menor o igual que el de losnaturales.

3.1. Conjuntos efectivamente enumerables

Definicion 19. Un conjunto A es efectivamente enumerable si existe una funcion f : N −→A sobreyectiva que se puede calcular por un algoritmo.

La mayornia de los conjuntos infinitos numerables que conocemos son efectivamente enu-merables por cuanto para describirlos de alguna forma utilizamos un algoritmo. Pero estosolo indica lo poco que conocemos. Una idea de conjuntos enumerables pero no efectivamenteenumerables se tiene trabajando el ejercicio 14 de esta seccion.

Otra nocion mas fuerte es la de conjunto decidible que se da para un universo numerablepor ejemplo las palabras sobre un alfabeto finito. Se pide que dada una palabra se puedadecidir algorıtmicamente si esta pertenece o no al conjunto.

Definicion 20. Un lenguaje L sobre Σ es decidible si existe un algoritmo que dada unapalabra w ∈ Σ∗ decide si w ∈ L o w /∈ L.

Proposicion 24. Todo lenguaje decidible es efectivamente enumerable.

Demostracion. Como el conjunto de las palabras sobre Σ es efectivamente enumerable, hayun algoritmo para numerarlas. Sea S el lenguaje decidible, modificamos el algoritmo paranumerar todas las palabras preguntado si cada palabra producida pertenece o no a S, si larespuesta es positiva esta entra de la numeracion de S, si no, pues no entra. Ası obtenemosuna numeracion de S

3.2. Ejercicios

1. Exhibir funciones biyectivas entre los conjuntos A y B dados (lo cual nos demuestraque 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 funcion} y B = {a, b, c} × {a, b, c}.j ) A = {f : {0, 1} −→ X | f es funcion} y B = X × X donde X es cualquier

conjunto.

k) A = {X | X ⊆ U} y B = {f : U −→ {0, 1} | f es funcion} donde U = {a, b, c}.l) A = {X | X ⊆ U} y B = {f : U −→ {0, 1} | f es funcion} 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 solo 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 funcion f de {0, 1, . . . n − 1} en {0, 1, . . .m − 1} se puede representar por unarreglo 1-dimensional, digamos A(i), de n componentes de 0 hasta n − 1 en dondeA(i) = f(i). Elaborar algoritmos para:

a) Decidir si una funcion dada es inyectiva.

b) Decidir si una funcion dada es sobreyectiva.

9. Cada funcion f de {0, 1, . . . n − 1} en {0, 1, . . .m − 1} se puede representar por unarreglo 1-dimensional, digamos A(i), de n componentes de 0 hasta n − 1 en dondeA(i) = f(i). Elaborar algoritmos (o formulas 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 formulas recursivas) para enumerar:

22

a) N× {a, b}.b) N× {a, b, c}.c) Z.

d) N× N.

e) Z× N.

f ) 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

b) B −A

c) A ∩ B

d) A× B

12. Sea A y B conjuntos efectivamente enumerables, exhiba algoritmos (si existen) paraenumerar:

a) A ∪B

b) B −A

c) A ∩ B

d) A× B

13. Decidir de cada afirmacion si es falsa o verdadera y argumentar brevemente su res-puesta.

a) Todo subconjunto de un conjunto fi-nito es finito.

b) Todo subconjunto de un conjunto in-finito es infinito.

c) Todo subconjunto de un conjuntoenumerable es enumerable.

d) Todo subconjunto de un conjuntoefectivamente enumerable es efectiva-mente enumerable.

e) Todo subconjunto de un conjunto de-cidible es decidible.

f ) Todo conjunto efectivamente enume-rable es decidible.

g) Todo conjunto decidible es efectiva-mente enumerable.

h) Todo conjunto efectivamente enume-rable es enumerable.

i) Todo conjunto enumerable es efecti-vamente enumerable.

j ) Todo conjunto enumerable es efecti-vamente enumerable.

k) Cualquier union de conjuntos enume-rables es enumerable.

l) Interseccion de dos conjuntos decidi-bles es decidible.

m) El conjunto de las tautologas es deci-dible.

14. Sean a0a1a2 . . . las cifras de la expansion decimal de algun numero irracional. Acep-tamos que la sucesion de los ai es generada algorıtmicamente. Dar argumentos paradecidir si los siguientes conjuntos son finitos, enumerables, efectivamente enumerablesy 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 solo con 0’s y 2’s (Conjuntoternario de Cantor).

16. Teorema de Cantor Para cualquier cardinal α se tiene: α < 2α

24