Conjuntos

Campus Fdo. May, Chillán

“Conjuntos Numerables y No Numerables,
Diagonalización”

Integrantes: Danilo Valle
Jorge Vásquez
Asignatura: Fundamentos de
Cs. de la Computación
Docentes: Juan Carlos Figueroa
Gilberto Gutiérrez

Chillán, 21 de Agosto de 2012

Índice

Introducción …………………………………………………………………………….. 3
Conjunto Numerable …………………………………………………………………... 4
Ejemplo de ConjuntoNumerables …………………………………………………… 7
Conjunto No Numerable ………………………………………………………………. 9
Ejemplos de Conjuntos No Numerables ……………………………………………. 9
Diagonal de Cantor …………………………………………………………………… 10
Ejemplo Método de la Diagonal …………………………………………………….. 12
Conclusión …………………………………………………………………………….. 14
Linkografía …………………………………………………………………………….. 15

“Conjuntos Numerables y No Numerables,Diagonalizacón”

Página 2

Introducción

El presente trabajo se basará principalmente en dos temas; los conjuntos
numerables y no numerables y la diagonalización.
Para comenzar a hablar de esto, echemos un vistazo rápido a lo que un
conjunto y a que corresponde la “Teoría de Conjuntos”, ya que será el pilar para
entender lo que se planteará posteriormente en este informe.
Un conjunto, como tal, es unacolección abstracta de elementos cualquiera
sea su naturaleza. Por otro lado, la teoría de conjun tos, es una rama que estudia
el comportamiento, cómo se relacionan entre si y las propiedades de los
conjuntos.
El desarrollo histórico de esta teoría, es atribuido a Georg Cantor, cuyas
investigaciones comenzaron en la segunda mitad del siglo XIX, preced ido por
algunas ideas de BernhardBolzano e influenciado por Richard Dedekind.

“Conjuntos Numerables y No Numerables, Diagonalizacón”

Página 3

Conjunto Numerable

Se dice que un conjunto A es numerable cuando A = Ø o existe una
aplicación inyectiva de A en N (dígase N el conjunto de todos los números
Naturales). Equivalentemente, A es numerable cuando es equipotente a un
subconjunto de N. En particular, todo subconjuntode N es numerable.
Para motivar una propiedad clave de los conjuntos numerables, pensemos
por ejemplo en el conjunto de los números pares, es decir, P = {2n : n ε N}. Es
evidente que la aplicación f : N → P, es definida por f(n) = 2n para todo n ε N, es
biyectiva, luego P es equipotente a N. Informalmente podríamos decir que “hay
tantos números pares como números naturales”, pero lo mismopodríamos decir
de los números impares. En realidad, vamos a ver enseguida que todo
subconjunto infinito de N es equipotente a N. Más concretamente, vamos a probar
lo siguiente:
Si A es un subconjunto infinito de N, existe una aplicación biyectiva
f : N → A, que tiene la siguiente propiedad:
n, m ε N, n < m entonces f(n) < f(m)

[*]

Un comentario previo ayudará a entender la demostración.Dicho de
manera

más

sencilla,

con

la

aplicación

de

f

pretendemos

enumerar

“consecutivamente” todos los elementos de A. La definición de f se hará por
inducción y es evidente que debemos tomar f(1) = mín(A), luego sólo queda
explicar la forma de obtener f(n + 1) a partir de f(n), para todo n ε N. La idea es
sencilla: conocido f(n), deberíamos detectar el “siguiente”elemento de A.
Consideramos el conjunto {a ε A : f(n) < a}, que no puede ser vacío, pues si
lo fuese tendríamos A Ĉ {x ε N : x ≤ f(n)} (entiéndase a „Ĉ‟ como subconjunto) y A
sería finito por ser subconjunto de un conjunto finito.

“Conjuntos Numerables y No Numerables, Diagonalizacón”

Página 4

El principio de buena ordenación nos per mite entonces definir:
f(n + 1) = mín{a ε A : f(n)< a}
Así pues, hemos definido por inducción una aplicación f : N → A y vamos a
comprobar que esta aplicación tiene las propiedades deseadas, empezando por la
condición [*].
Es claro que f(n) < f(n + k) para todo n ε N o dicho de otra forma
f(n) < f(n + k) para todo n ε N

[Pk]

es cierta para k = 1. Pero suponiendo que se cumple [Pk] para un k ε N, tenemos
obviamente f(n) < f(n +...