Conjuntos finitos – Inducción Matemática

Posted on by Antonio E.P. Heredia

El principio de inducción matemática se puede aplicar para demostrar proposiciones sobre conjuntos finitos. Para estas sentencias es recomendable considerar el caso base como el conjunto de tamaño cero, es decir, el conjunto vacío.

En seguida se muestra una proposición de ésta naturaleza que se puede probar como fue sugerido:

Proposición
Si el conjunto \displaystyle A es finito, entonces \displaystyle |\mathscr{P}( A) |=2^{|A|}

Dem.

Sea \displaystyle S( n) :Si \displaystyle A es un conjunto con \displaystyle n elementos, entonces \displaystyle |\mathscr{P}( A) |=2^{n}.

Considerando \displaystyle n=0, es decir, el conjunto vacío \displaystyle \emptyset; se tiene \displaystyle |\mathscr{P}( \emptyset ) |=2^{0} =1, dado que su único subconjunto es sí mismo, \displaystyle S( 0) =1 se cumple. Asumiendo que \displaystyle S( k) se cumple para algún \displaystyle k\geqslant 0, es decir, para cualquier conjunto \displaystyle A con \displaystyle k elementos, se tiene que \displaystyle |\mathscr{P}( A) |=2^{k}.

Sea \displaystyle B un conjunto con \displaystyle k+1 elementos y \displaystyle b uno de sus elementos \displaystyle ( b\in B), su conjunto potencia \displaystyle \mathscr{P}( B) se puede dividir en dos conjuntos: \displaystyle Q={\{X\in \mathscr{P}( B) \ |\ b\in X\}} y \displaystyle R={\{X\in \mathscr{P}( B) \ |\ b\notin X\}}.

El conjunto \displaystyle R es realmente el conjunto potencia de \displaystyle B-\{{b}\} (que incluye el conjunto \displaystyle \emptyset). Dado que \displaystyle B-\{{b}\} consiste de \displaystyle k elementos, entonces \displaystyle |R|=2^{k}. Además, el conjunto \displaystyle Q contiene a todos los subconjuntos de \displaystyle B que contienen al elemento \displaystyle b (no incluye al conjunto \displaystyle \emptyset). Se puede notar que cada elemento de \displaystyle Q es realmente la unión única de un elemento de \displaystyle R con el conjunto \displaystyle\{{b}\}, por lo que \displaystyle |Q|=|R|=2^{k}.

Siendo \displaystyle Q\cap R=\emptyset, es decir, \displaystyle Q y \displaystyle R no tienen elementos en común, se tiene que \displaystyle |\mathscr{P}( B) |=|Q\cup R|=|Q|+|R|=2^{k} +2^{k} =2\cdotp 2^{k} =2^{k+1} y \displaystyle S( k+1) es verdadera. Por lo tanto, por inducción podemos ver que \displaystyle S( n) se cumple para cada \displaystyle n\geqslant 0.

\blacksquare

Contenido elaborado por Antonio Enrique Pérez Heredia. CEFYM © 2024Licencia de Creative Commons
Este obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional
+1
0
+1
0
+1
0
+1
0
+1
0

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *