teoria de conjuntos

Teoría de Conjuntos I

CONJUNTOS FINITOS Definición. CANTOR, G. (1845-1918). En 1872 acepta el Infinito (Actual) de Facto, en contra de la idea que el Infinito es en Potencia. syss ∃n ∈  n  a.

a es Finito

a es Infinito syss a no es finito. Notación: 1). FIN 

x / x es finito .

2). INF 

x / x es infinito .

Observaciones: 1). ∀n ∈ , n ∈ FIN. 2). Si a ∈ FIN y b  a entonces b ∈ FIN. 3). a  0 syss a  ∅. Y ∅ ∈ FIN. Proposición 1 . (Lema de Finitud). Ningún natural es equipotente con un subconjunto propio. En símbolos: ∀n ∈  ∃x x  n & x  n Prueba. Sea n  ∃x x  n  n. Probaremos por inducción para  que ∀n ∈  n. 0 Trivialmente es cierto que ∃x x  0 & x  0. ∀n ∈  n  n   Sea n ∈  y supongamos que n   demostraremos que n. Supongamos que a  n  el cual n   f a. Tenemos dos casos: n∉a

Así, resulta que a ⊆ n y fn ∈ a ∖ n. Con esto, a ∖ fn  n. Ahora

bien, sea g  f ∖ 〈n, fn. Con lo que tenemos que n  g a ∖ fn. n∈a

En este caso a ∖ n  n y hay un k ∈ n  tal que fk  n. Así,

n  g a ∖ n, donde f∖ g

Si k  n

n, n

O f∖

n, fn

,

k, n

En cualquier caso tenemos que n.

Rafael Rojas Barbachano.



k, fn

Si k ∈ n †

Teoría de Conjuntos I

Conjuntos Finitos

Corolario 2 . 1). Ningún conjunto finito es equipotente a un subconjunto propio, ∀x x ∈ FIN  ∃y y  x & y  x 2). Cualquier conjunto equipotente a un subconjunto propio es infinito, ∀x ∃y y  x & y  x  x ∈ INF 3).  ∈ INF. (De hecho, como se verá, es el 1 er ordinal y cardinal infinito) 4). ℤ, , , ℂ ∈ INF. Definición. (DEDEKIND, R. (1831-1916) En 1888) a es D-Infinito syss ∃y y  a & y  a a es D-Finito

syss a no es D-Infinito syss ∀y y ⊆ a & y  a  y  a

Observación:  es D-infinito. Corolario 3 . 1) Si a es finito, entonces a es D-finito. 2) Si a es D-infinito, entonces a es infinito. ¿Qué puede decir de la conversa de esta proposición? (R: Depende del AE) Corolario 4 . Si n, m ∈ , entonces 1) a) n ≠ m  n ≁ m b) n  m  n  m 2) Si a  n y a  m entonces n  m Con este resultado podríamos dar una definición parcial de cardinalidad: Si a ∈ FIN, entonces el cardinal de a es el único natural con el cual es equipotente; en notación quedaría así: : FIN   ∀a ∈ FIN,

a





n∈ / na

Sin embargo, prescindiremos de esta definición y de la notación por el momento.

Rafael Rojas Barbachano.

2

Teoría de Conjuntos I

Conjuntos Finitos

Corolario 5 . (Principio del palomar para finitos). Sea n ∈ . Si n objetos son colocados en menos de n casillas, entonces habrá una casilla con más de un objeto. Proposición 6 . Si a ∈ FIN, entonces a  b ∈ FIN. De hecho, ∀a∀n ∈ ∀p a  n & p ∉ a  a  p  n  Proposición 7 . Al quitarle a un finito uno de sus elementos, sigue siendo finito. De hecho: ∀a∀n ∈ ∀p a  n  & p ∈ a  a ∖ p  n Prueba: Supongamos que a  f n  . Definimos g : a ∖ p  n, como sigue: fx

si fx ≠ n

fp

si fx  n

para x ∈ a ∖ p, gx  †

Así, a ∖ p  g n. Proposición 8 . 1). Los subconjuntos de un número natutal son finitos. 2). Los subconjuntos de un conjunto finito son finitos. Prueba 1): Sea n  ∀x x ⊆ n  x ∈ FIN Probaremos por inducción: ∀n ∈ , n. 0

∀xx ⊆ 0  x ∈ FIN es obviamente cierto.

∀n ∈  n  n  

Sea n ∈  y supongamos inductivamente que n. Sea

b ⊆ n  . Tenemos dos casos: Si n ∉ b, entonces b ⊆ n y por la H.I. tenemos que b ∈ FIN. Ahora veamos cuando n ∈ b; aquí b ∖ n ⊆ n y nuevamente por la H.I., b ∖ n ∈ FIN. Finalmente, como b  b ∖ n  n, por la proposición anterior, tenemos que b ∈ FIN. La prueba de 2) se sigue de 1). † Otra forma de probar la proposición anterior es demostrando 2) (ya que 1) es un caso particular) y esta se puede hacer por inducción sobre la “cardinalidad del conjunto”: ∀n ∈  ∀x x  n  ∀y y ⊆ x  y ∈ FIN dejamos al lector, dicha prueba.

Rafael Rojas Barbachano.

3

Teoría de Conjuntos I

Conjuntos Finitos

Corolario 9 . a). Si a ∈ FIN entonces a ∖ b ∈ FIN. b). Si a ∈ FIN entonces a ∩ b ∈ FIN. Proposición 10 . La unión de dos conjuntos finitos es finita. Prueba. Por inducción sobre la cardinalidad de uno de ellos: Supongamos que a ∈ FIN y sea n  ∀x x  n  a  x ∈ FIN probemos que ∀n ∈  n. 0 Si b  0, entonces b  ∅ y de aquí que a  b  a  ∅  a ∈ FIN. ∀n ∈  n  n   Sea n ∈  y supongamos inductivamente n. Sean b, f y p tales que b  f n  y p  f −1 n ∈ b. Así, por la Proposición 7 , b ∖ p  n. Ahora, de la H.I. a  b ∖ p ∈ FIN, pero entonces, por la Proposición 6 , a  b  a  b ∖ p  p ∈ FIN. † Proposición 11 . La unión finita (e.d. la unión de un conjunto finito) de conjuntos finitos es finita. Prueba. Por inducción sobre la cardinalidad del conjunto: Sea  la fórmula: n  ∀x n  x & ∀y ∈ x y ∈ FIN   x ∈ FIN probemos que ∀n ∈  n. 0 Si a  0, entonces a  ∅ y de aquí que  a   ∅  ∅ ∈ FIN. ∀n ∈  n  n   Sea n ∈  y supongamos inductivamente n. También supongamos que a y f son tales que n   f a y ∀y ∈ a y ∈ FIN. Así fn ∈ a y por tanto, gracias a la Proposición 7 , a ∖ fn  n. De la H.I. tenemos que a ∖ fn ∈ FIN. Ahora bien, puesto que fn ∈ a, tenemos que fn ∈ FIN y de aqui que, por la proposición anterior,  a  a ∖ fn  fn ∈ FIN. † Proposición 12 . 1. El producto cartesiano de conjuntos finitos es finito. 2. Si a  n y b  m, con n, m ∈ , entonces a  b  n  m Prueba de 1. Por un lado, tomando en cuenta que ab  y por otro, que a  z  a y que

Rafael Rojas Barbachano.



a  z / z ∈ b

a  z / z ∈ b

 b. Finalmente, si a y b son 4

Teoría de Conjuntos I

Conjuntos Finitos

finitos, entonces a  b resulta ser la unión finita de conjuntos finitos.

†

Proposición 13 . 1. Si a, b ∈ FIN entonces a b ∈ FIN. 2. Si n, m ∈  son tales que a  n y b  m, entonces a b  m n . Prueba: TAREA. Proposición 14 . 1. El conjunto de todos los subconjuntos de un conjunto finito es finito. 2. Si n ∈  es tal que a  n, entonces ℘a  2 n . Prueba: Es inmediata de la proposición anterior y del teorema de Cantor: ℘a 

a

2. †

Proposición 15 . La imagen de un conjunto finito, a través de una función, es finita. Prueba: Sean f ∈ FNC y a ∈ FIN. P.D. f a ∈ FIN. Puesto que: f a 

fx / x ∈ a





fx

/ x∈a

resulta que f a es la unión finita de conjuntos finitos y por tanto finito.

†

Otra demostración podría ser por inducción sobre la cardinalidad del dominio: Si f ∈ FUN, entonces ∀n ∈  DOMf  n  IMGf ∈ FIN

Rafael Rojas Barbachano.

5