Teoría de grafos y relaciones
Sean A y B dos conjuntos. Una relación binaria de A en B es un subconjunto del producto cartesiano A por B. Las relaciones de un conjunto en sí mismo tienen un interés especial. Una relación en un conjunto a es un subconjunto de A por A.
¿Cuántas relaciones hay en un conjunto de n elementos?
2 respuestas
Magdalena González!
Primero veamos cuantos elementos tiene el conjunto producto cartesiano
Si |A| = n entonces |AxA| = n·n = n^2
Y una relación es un subconjunto de AxA. El número de relaciones será el cardinal de las partes de AxA que denotateremos así
|P(AxA)|
Este cardinal depende del cardinal de AxA y es conocido y fácilmente demostrable por inducción que
|P(C)| = 2^(|C|)
luego
|P(AxA)| = 2^(|AxA|) = 2^(n^2)
Hay |P(AxA)|=2^(n^2), donde x es el produto cartesianio, P es el conjunto potencia, y |X| es el cardinal de X.