Álgebra de conjuntos

En matemáticas, el álgebra de conjuntos, que no debe confundirse con la estructura matemática de un álgebra de conjuntos, define las propiedades y leyes de los conjuntos, las operaciones teóricas de conjuntos de unión, intersección, y complementación y las relaciones de igualdad de conjuntos e inclusión de conjuntos. También proporciona procedimientos sistemáticos para evaluar expresiones y realizar cálculos que involucran estas operaciones y relaciones.

Cualquier conjunto de conjuntos cerrados bajo las operaciones set-teoretic forma un álgebra boo con el operador de la unión siendo sindicato, el operador de la reunión intersección, el operador de complementos complemento, el fondo de ser ${\displaystyle \varnothing }$ y la parte superior es el universo que se está considerando.

Fundamentos

El álgebra de conjuntos es el análogo teórico de conjuntos del álgebra de números. Así como la suma y la multiplicación aritméticas son asociativas y conmutativas, también lo son la unión y la intersección de conjuntos; así como la relación aritmética "menor o igual" es reflexiva, antisimétrica y transitiva, al igual que la relación de conjunto de "subconjunto".

Es el álgebra de las operaciones teóricas de unión, intersección y complementación, y las relaciones de igualdad e inclusión. Para una introducción básica a conjuntos ver el artículo sobre conjuntos, para una cuenta más completa ver la teoría de conjunto ingenua, y para un tratamiento axiomático riguroso ver la teoría de conjunto axiomático.

Propiedades fundamentales del álgebra de conjuntos

Las operaciones binarias del sindicato establecido (${\displaystyle \cup }$) e intersección (${\displaystyle \cap }$) satisfacer muchas identidades. Varias de estas identidades o "leyes" tienen nombres bien establecidos.

Propiedad mercantil:

• ${\displaystyle A\cup B=B\cup A}$
• ${\displaystyle A\cap B=B\cap A}$

Propiedad asociativa:

• ${\displaystyle (A\cup B)\cup C=A\cup (B\cup C)}$
• ${\displaystyle (A\cap B)\cap C=A\cap C$

Propiedad distributiva:

• ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$
• ${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$

La unión e intersección de conjuntos puede considerarse análoga a la suma y multiplicación de números. Al igual que la suma y la multiplicación, las operaciones de unión e intersección son conmutativas y asociativas, y la intersección distribuye sobre la unión. Sin embargo, a diferencia de la suma y la multiplicación, la unión también se distribuye en la intersección.

Dos pares adicionales de propiedades implican los conjuntos especiales llamados el conjunto vacío ${\displaystyle \varnothing }$ y el conjunto del universo ${\displaystyle {\boldsymbol}}$; junto con el operador de complementos (${\displaystyle A^{\complemento }$ denota el complemento de ${\displaystyle A}$. Esto también puede ser escrito como ${\displaystyle A'$, leer como "A prime"). El conjunto vacío no tiene miembros, y el conjunto del universo tiene todos los miembros posibles (en un contexto particular).

Identidad:

• ${\displaystyle A\cup \varnothing =A}$
• ${\displaystyle A\cap {\boldsymbol {U}=A}$

Complemento:

• ${\displaystyle A\cup A^{\complemento }={\boldsymbol {U}}$
• ${\displaystyle A\cap A^{\complemento }= \varnothing }$

Las expresiones de identidad (junto con las expresiones comunicativas) dicen que, al igual que 0 y 1 para la adición y multiplicación, ${\displaystyle \varnothing }$ y ${\displaystyle {\boldsymbol}}$ son los elementos de identidad para unión e intersección, respectivamente.

A diferencia de la suma y la multiplicación, la unión y la intersección no tienen elementos inversos. Sin embargo, las leyes del complemento dan las propiedades fundamentales de la operación unaria algo inversa de complementación de conjuntos.

Los cinco pares de fórmulas anteriores (las fórmulas conmutativa, asociativa, distributiva, de identidad y de complemento) abarcan todo el álgebra de conjuntos, en el sentido de que toda proposición válida en el álgebra de conjuntos puede derivarse de ellas.

Tenga en cuenta que si las fórmulas de complemento se debilitan a la regla ${\displaystyle (A^{\complement })^{\complement }=A}$, entonces este es exactamente el álgebra de la lógica lineal proposición.

Principio de dualidad

Cada una de las identidades indicadas arriba es una de las identidades tales que cada una puede ser transformada en la otra por intercambio ${\displaystyle \cup }$ y ${\displaystyle \cap }$, mientras que también intercambió ${\displaystyle \varnothing }$ y ${\displaystyle {\boldsymbol}}$.

Estos son ejemplos de una propiedad extremadamente importante y poderosa del álgebra de conjunto, es decir, el principio de la dualidad para conjuntos, que afirma que para cualquier declaración verdadera sobre conjuntos, dual declaración obtenida por uniones intercambiantes e intersecciones, intercambiando ${\displaystyle {\boldsymbol}}$ y ${\displaystyle \varnothing }$ y la inversión de inclusiones es también cierto. Se dice que una declaración es auto-dual si es igual a su propio dual.

Algunas leyes adicionales para uniones e intersecciones

La siguiente proposición establece seis leyes más importantes del álgebra de conjuntos, que involucran uniones e intersecciones.

PROPOSICIÓN 3: Para cualquier subconjunto ${\displaystyle A}$ y ${\displaystyle B}$ de un universo ${\displaystyle {\boldsymbol}}$, las siguientes identidades sostienen:

Idempotent laws:

• ${\displaystyle A\cup A=A}$
• ${\displaystyle A\cap A=A}$

leyes de dominación:

• ${\displaystyle A\cup {\boldsymbol {U}={\boldsymbol {U}}$
• ${\displaystyle A\cap \varnothing =\varnothing }$

leyes de absorción:

• ${\displaystyle A\cup (A\cap B)=A}$
• ${\displaystyle A\cap (A\cup B)=A}$

Como se ha señalado anteriormente, cada una de las leyes enunciadas en la propuesta 3 puede derivarse de los cinco pares fundamentales de leyes mencionados anteriormente. Como ilustración, a continuación se da una prueba para la ley idempotente de unión.

Prueba:

${\displaystyle A\cup A}$	${\displaystyle =(A\cup A)\cap {\boldsymbol}}$	por la ley de identidad de la intersección
	${\displaystyle =(A\cup A)\cap (A\cup A^{\complement }$	por la ley complementaria para la unión
	${\displaystyle =A\cup (A\cap A^{\complement )}$	por la ley distributiva de unión sobre intersección
	${\displaystyle =A\cup \varnothing }$	por la ley complementaria de intersección
	${\displaystyle =A}$	por la ley de identidad sindical

La siguiente prueba ilustra que la prueba dual de la prueba anterior es la prueba del dual de la ley idempotente para la unión, es decir, la ley idempotente para la intersección.

Prueba:

${\displaystyle A\cap A}$	${\displaystyle =(A\cap A)\cup \varnothing }$	por la ley de identidad sindical
	${\displaystyle =(A\cap A)\cup (A\cap A^{\complement }$	por la ley complementaria de intersección
	${\displaystyle =A\cap (A\cup A^{\complement )}$	por la ley distributiva de intersección sobre unión
	${\displaystyle =A\cap {\boldsymbol {U}}$	por la ley complementaria para la unión
	${\displaystyle =A}$	por la ley de identidad para la intersección

La intersección se puede expresar en términos de diferencia de conjuntos:

${\displaystyle A\cap B=A\setminus (A\setminus B)}$

Algunas leyes adicionales para complementos

La siguiente proposición establece cinco leyes más importantes del álgebra de conjuntos, que involucran complementos.

PROPOSICIÓN 4# ${\displaystyle A}$ y ${\displaystyle B}$ ser subconjuntos de un universo ${\displaystyle {\boldsymbol}}$Entonces:

Las leyes de De Morgan:

• ${\displaystyle (A\cup B)^{\complemento }=A^{\complement }\cap B^{\complement }$
• ${\displaystyle (A\cap B)^{\complement }=A^{\complemento }\cup B^{\complemento }$

doble complemento o ley de involución:

• ${\displaystyle (A^{\complement })^{\complement }=A}$

complementa leyes para el conjunto del universo y el conjunto vacío:

• ${\displaystyle \varnothing ^{\complement }={\boldsymbol {U}}$
• ${\displaystyle {\boldsymbol} {\complemento} }= \varnothing }$

Observe que la ley de doble complemento es auto-dual.

La proposición siguiente, que también es auto-dual, dice que el complemento de un conjunto es el único conjunto que satisface las leyes de complemento. En otras palabras, la complementación se caracteriza por las leyes complementarias.

PROPOSICIÓN 5# ${\displaystyle A}$ y ${\displaystyle B}$ ser subconjuntos de un universo ${\displaystyle {\boldsymbol}}$Entonces:

singularidad de complementos:

• Si ${\displaystyle A\cup B={\boldsymbol {U}}$, y ${\displaystyle A\cap B=\varnothing }$Entonces ${\displaystyle B=A^{\complemento }$

Álgebra de inclusión

La siguiente proposición dice que la inclusión, es decir la relación binaria de un conjunto siendo subconjunto de otro, es un orden parcial.

PROPOSICIÓN 6Si ${\displaystyle A}$, ${\displaystyle B}$ y ${\displaystyle C}$ are sets then the following hold:

reflexividad:

• ${\displaystyle A\subseteq A}$

antisimetría:

• ${\displaystyle A\subseteq B}$ y ${\displaystyle B\subseteq A}$ si ${\displaystyle A=B.$

transitividad:

• Si ${\displaystyle A\subseteq B}$ y ${\displaystyle B\subseteq C}$Entonces ${\displaystyle A\subseteq C}$

La siguiente proposición dice que para cualquier conjunto S, el conjunto potencia de S, ordenado por inclusión, es una red acotada y, por lo tanto, junto con el distributivo y el complemento Las leyes anteriores muestran que es un álgebra booleana.

PROPOSICIÓN 7Si ${\displaystyle A}$, ${\displaystyle B}$ y ${\displaystyle C}$ son subconjuntos de un conjunto ${\displaystyle S.$ entonces la siguiente sujeción:

existencia de un elemento mínimo y un elemento más grande:

• ${\displaystyle \varnothing \subseteq A\subseteq S}$

existencia de uniones:

• ${\displaystyle A\subseteq A\cup B}$
• Si ${\displaystyle A\subseteq C}$ y ${\displaystyle B\subseteq C}$Entonces ${\displaystyle A\cup B\subseteq C}$

existencia de encuentros:

• ${\displaystyle A\cap B\subseteq A}$
• Si ${\displaystyle C\subseteq A}$ y ${\displaystyle C\subseteq B}$Entonces ${\displaystyle C\subseteq A\cap B}$

La siguiente propuesta dice que la declaración ${\displaystyle A\subseteq B}$ equivale a otras declaraciones que involucran sindicatos, intersecciones y complementos.

PROPOSICIÓN 8: Para cualquier dos sets ${\displaystyle A}$ y ${\displaystyle B}$, los siguientes son equivalentes:

• ${\displaystyle A\subseteq B}$
• ${\displaystyle A\cap B=A}$
• ${\displaystyle A\cup B=B$
• ${\displaystyle A\setminus B=\varnothing }$
• ${\displaystyle B^{\complemento Subseteq A^{\complement }$

La propuesta anterior muestra que la relación de inclusión de conjunto puede caracterizarse por cualquiera de las operaciones de unión de conjunto o intersección de conjunto, lo que significa que la noción de inclusión de conjunto es axiomáticamente superflua.

Álgebra de complementos relativos

La siguiente proposición enumera varias identidades relativas a complementos relativos y diferencias en la teoría de conjuntos.

PROPOSICIÓN 9: Para cualquier universo ${\displaystyle {\boldsymbol}}$ y subconjuntos ${\displaystyle A}$, ${\displaystyle B}$ y ${\displaystyle C}$ de ${\displaystyle {\boldsymbol}}$, las siguientes identidades sostienen:

• ${\displaystyle C\setminus (A\cap B)=(C\setminus A)\cup (C\setminus B)}$
• ${\displaystyle C\setminus (A\cup B)=(C\setminus A)\cap (C\setminus B)}$
• ${\displaystyle C\setminus (B\setminus A)=(A\cap C)\cup (C\setminus B)}$
• ${\displaystyle (B\setminus A)\cap C=(B\cap C)\setminus (A\cap C)=(B\cap C)\setminus A=B\cap (C\setminus A)}$
• ${\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus (A\setminus C)}$
• ${\displaystyle (B\setminus A)\setminus C=B\setminus (A\cup C)}$
• ${\displaystyle A\setminus A=\varnothing }$
• ${\displaystyle \varnothing \setminus A=\varnothing }$
• ${\displaystyle A\setminus \varnothing =A}$
• ${\displaystyle B\setminus A=A^{\complement }\cap B}$
• ${\displaystyle (B\setminus A)^{\complement }=A\cup B^{\complement }$
• ${\displaystyle {\boldsymbol {U}\setminus A=A^{\complemento }$
• ${\displaystyle A\setminus {\boldsymbol Nada.$