Conjunto potencia


Conjunto potencia

En matemáticas, dado un conjunto S, se llama conjunto potencia o conjunto de partes de S (se denota por P(S) o 2S) al conjunto formado por todos los subconjuntos posibles de S.

En la teoría de conjuntos basada en los Axiomas de Zermelo-Fraenkel, la existencia del conjunto potencia se establece por el axioma del conjunto potencia.

Por ejemplo, si S= {a, b, c} entonces el conjunto potencia de S es P(S) = {{ }, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

El conjunto potencia de un conjunto S, junto con las operaciones de la unión, de la intersección y del complemento forman el ejemplo prototípico de álgebra de Boole. De hecho, uno puede demostrar que cualquier álgebra de Boole finita es isomorfa al álgebra booleana del conjunto potencia de un conjunto finito. Para las álgebras booleanas infinitas esto no es verdad, pero cada álgebra booleana infinita es subálgebra de una álgebra booleana de partes.[cita requerida]

Contenido

Cardinalidad del conjunto potencia

Cuando S es finito, si n = |S| es el número de elementos de S entonces su conjunto potencia contiene |P(S)| = 2n elementos. En este caso también se puede establecer una biyección entre los elementos del conjunto potencia con números de n-bits: el n-ésimo bit se refiere a la presencia o ausencia del n-ésimo elemento de S. Hay 2n tales números. Este argumento prueba la identidad de coeficientes binomiales:

{n \choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose n} = 2^n

La cardinalidad de un conjunto potencia siempre es mayor que la cardinalidad del conjunto base, el argumento diagonal de Cantor demuestra la afirmación para conjuntos infinitos, mientras que el hecho de que n < 2n la prueba para conjuntos finitos. El conjunto potencia de los números naturales, por ejemplo, se puede poner en correspondencia uno a uno con el conjunto de números reales. Usualmente se establece primero una biyección entre los números reales y el intervalo cerrado [0,1], para luego, usando la expansión diádica de los números reales, identificar cada elemento de [0,1] con la sucesión infinita de ceros y unos dada por los coeficientes.

La notación 2S

En teoría de conjuntos, XY es el conjunto de todas las funciones de Y a X. Como 2 puede ser definido como {0, 1} (véase número natural), 2S es el conjunto de todas las funciones de S a {0, 1}. Cada función en 2S está en correspondencia biyectiva con un subconjunto de S (la antiimagen de 1) por lo que se establece una equivalencia de conjuntos entre 2S y P(S)

Implementación en Haskell

Esta implementación recibe una Lista de elementos y devuelve una lista con todas las listas que representan los subconjuntos posibles

parts [] = [[]]
parts (x:xs) = agregar x (parts xs) ++ (parts xs)
 
agregar x [] = []
agregar x (y:ys) = (x:y) : agregar x ys
 
-- notar que tanto el nombre parts como agregar son triviales

Para su ejecución se le pasa una lista de elementos a la función parts Por ejemplo:

parts [10,20,30]

y obtenemos

[[10,20,30],[10,20],[10,30],[10],[20,30],[20],[30],[]]


Implementación en Python

Esta implementación del algoritmo para obtener un conjunto potencia de una colección dada:

def addTo(e, t):       
        for s in t:
                s += [e]
        return t
 
def powerSet(a_set):
        if not a_set: return [[]]
        e = a_set[0]
        t = a_set[1:]
        return powerSet(t) + addTo(e, powerSet(t))

La cual puede ser probada ejecutando luego:

a = [1,2,3]
 
print powerSet(a)

Y la respuesta será:

[[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]

Referencia

Bibliografía

  • Ferreirós, Jose, 2007 (1999). Labyrinth of Thought: A history of set theory and its role in modern mathematics. Basel, Birkhäuser. ISBN 978-3-7643-8349-7
  • Johnson, Philip, 1972. A History of Set Theory. Prindle, Weber & Schmidt ISBN 0-87150-154-6
  • Kunen, Kenneth, Set Theory: An Introduction to Independence Proofs. North-Holland, 1980. ISBN 0-444-85401-0.
  • Tiles, Mary, 2004 (1989). The Philosophy of Set Theory: An Historical Introduction to Cantor's Paradise. Dover Publications.
  • Puntambekar, A.A. (2007). Theory Of Automata And Formal Languages. Technical Publications. ISBN 9788184311938. 

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Conjunto potencia — En matemáticas, dado un conjunto S, el conjunto potencia o conjunto de partes de S, escrito P(S) o 2S, es el conjunto de todos los subconjuntos de S. En la teorá de conjuntos basada en los axiomas de Zermelo Fraenkel, la existencia del conjunto… …   Enciclopedia Universal

  • Construcción de conjunto potencia — En la teoría de la computación, la construcción de conjunto potencia es un método estándar para convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. En la teoría es… …   Wikipedia Español

  • Potencia de un conjunto — Saltar a navegación, búsqueda La potencia de un conjunto es un conjunto definido a partir de las propiedades del producto cartesiano. No debe confundirse este concepto con el de conjunto potencia que se obtiene sin recurrir a las propiedades del… …   Wikipedia Español

  • Conjunto finito — En matemática, un conjunto finito es un conjunto que tiene un número finito de elementos. Por ejemplo {2, 4, 6, 8, 10} es un conjunto finito con cinco elementos. La cardinalidad o número de elementos de un conjunto finito es igual a un número… …   Wikipedia Español

  • Conjunto vacío — El conjunto vacío es aquél que no tiene elementos. En matemáticas, específicamente en teoría de conjuntos, el conjunto vacío es el conjunto que no contiene ningún elemento. Puesto que lo único que define a un conjunto son sus elementos, el… …   Wikipedia Español

  • Conjunto infinito — En teoría de conjuntos, un conjunto infinito es un conjunto que no es finito. Algunos ejemplos son: Los números enteros Z = {..., 3, 2, 1, 0, 1, 2, 3, ...} forman un conjunto infinito y numerable. Los puntos en una recta, representados por un… …   Wikipedia Español

  • Conjunto no numerable — Un conjunto no numerable es un conjunto que no puede ser enumerado, es decir, un conjunto tal que no existe una función sobreyectiva del conjunto de los número naturales a dicho conjunto. Es decir, un conjunto A es no numerable si no existe… …   Wikipedia Español

  • Potencia de un punto — Saltar a navegación, búsqueda …   Wikipedia Español

  • Potencia (desambiguación) — Saltar a navegación, búsqueda Potencia puede referirse a: En física: Potencia en Física: cantidad de trabajo realizado por unidad de tiempo. Potencia en Geometría: la potencia de un punto respecto de una circunferencia Potencia óptica: inverso de …   Wikipedia Español

  • potência — s. f. 1. Poder, força. 2. Vigor, robustez. 3. Autoridade, mando. 4. Personagem de grande importância e influência. 5. Estado, nação. 6. Conjunto de aptidões ou elementos próprios para produzir um ser ou um ato. 7.  [Mecânica] Força com que se… …   Dicionário da Língua Portuguesa