View source for Simple theorems in the algebra of sets

The '''simple theorems in the algebra of sets''' are some of the elementary properties of the [[algebraic structure|algebra]] of [[Union (set theory)|union]] ([[infix operator]]: ∪), [[intersection (set theory)|intersection]] (infix operator: ∩), and [[set complement]] ([[postfix (linguistics)|postfix]] ') of sets.

These properties assume the existence of at least two sets: a given [[universal set]], denoted '''U''', and the [[empty set]], denoted {}. The algebra of sets describes the properties of all possible [[subset]]s of  '''U''', called the [[power set]] of '''U''' and denoted  ''P''('''U'''). ''P''('''U''') is assumed [[closure (mathematics)|closed]] under union, intersection, and set complement. The algebra of sets is an [[interpretation (logic)|interpretation]] or [[model theory|model]] of [[Boolean algebra (structure)|Boolean algebra]], with union, intersection, set complement, '''U''', and {} interpreting Boolean [[logical disjunction|sum]], [[logical conjunction|product]], [[logical negation|complement]], 1, and 0, respectively.

The properties below are stated without [[Mathematical proof|proof]], but can be derived from a small number of properties taken as [[axiom]]s. A "*" follows the algebra of sets interpretation of [[Edward V. Huntington|Huntington's]] (1904) classic postulate set for [[Boolean algebra]]. These properties can be visualized with [[Venn diagram]]s. They also follow from the fact that ''P''('''U''') is a [[Boolean lattice]]. The properties followed by "L" interpret the [[lattice (order)|lattice]] axioms.

Elementary [[discrete mathematics]] courses sometimes leave students with the impression that the subject matter of [[set theory]] is no more than these properties. For more about elementary set theory, see [[Set (mathematics)|set]], [[set theory]], [[algebra of sets]], and [[naive set theory]]. For an introduction to set theory at a higher level, see also [[axiomatic set theory]], [[cardinal number]], [[ordinal number]], [[Cantor–Bernstein–Schroeder theorem]], [[Cantor's diagonal argument]], [[Cantor's first uncountability proof]], [[Cantor's theorem]], [[well-ordering theorem]], [[axiom of choice]], and [[Zorn's lemma]].

The properties below include a defined binary operation, [[relative complement]], denoted by the infix operator "\". The "relative complement of ''A'' in ''B''," denoted ''B''&nbsp;\''A'', is defined as (''A''&nbsp;∪''{{prime|B}}''){{prime}} and as ''{{prime|A}}''&nbsp;∩''B''.


'''PROPOSITION 1'''. For any '''U''' and any subset ''A'' of '''U''':
*{}{{prime}} = '''U''';
*''{{prime|'U'}}'' = {};
*''A''&nbsp;\ {}&nbsp;= ''A'';
*{}&nbsp;\ ''A''&nbsp;= {};
*''A''&nbsp;∩ {}&nbsp;= {};
*''A''&nbsp;∪ {}&nbsp;= ''A''; *
*''A''&nbsp;∩ '''U'''&nbsp;= ''A''; *
*''A''&nbsp;∪ '''U'''&nbsp;= '''U''';
*''{{prime|A}}'' ∪ ''A'' = '''U'''; *
*''{{prime|A}}'' ∩ ''A'' = {}; * 
*''A''&nbsp;\ ''A''&nbsp;= {};
*'''U'''&nbsp;\ ''A''&nbsp;= ''{{prime|A}}'';
*''A''&nbsp;\ '''U'''&nbsp;= {};
*''{{prime|A}}''{{prime}}&nbsp;= ''A'';
*''A''&nbsp;∩ ''A''&nbsp;= ''A'';
*''A''&nbsp;∪ ''A''&nbsp;= ''A''.


'''PROPOSITION 2'''. For any sets ''A'', ''B'', and ''C'':
:*''A''&nbsp;∩ ''B''&nbsp;= ''B''&nbsp;∩ ''A''; * L
:*''A''&nbsp;∪ ''B''&nbsp;= ''B''&nbsp;∪ ''A''; * L
:*''A'' ∪ (''A'' ∩ ''B'') = ''A''; L
:*''A'' ∩ (''A'' ∪ ''B'') = ''A''; L
:*(''A'' ∪ ''B'') \ ''A'' = ''B'' \ ''A'';
:*''A''&nbsp;∩ ''B''&nbsp;= {} [[if and only if]] ''B''&nbsp;\ ''A''&nbsp;= ''B'';
:*(''{{prime|A}}'' ∪ ''B''){{prime}} ∪ (''{{prime|A}}'' ∪ ''{{prime|B}}''){{prime}} = ''A'';
:*(''A''&nbsp;∩&nbsp;''B'')&nbsp;∩ ''C''&nbsp;= ''A''&nbsp;∩ (''B''&nbsp;∩&nbsp;''C''); L
:*(''A''&nbsp;∪&nbsp;''B'')&nbsp;∪ ''C''&nbsp;= ''A''&nbsp;∪ (''B''&nbsp;∪&nbsp;''C''); L
:*''C''&nbsp;\ (''A''&nbsp;∩&nbsp;''B'')&nbsp;= (''C''&nbsp;\&nbsp;''A'')&nbsp;∪ (''C''&nbsp;\&nbsp;''B'');
:*''C''&nbsp;\ (''A''&nbsp;∪&nbsp;''B'')&nbsp;= (''C''&nbsp;\&nbsp;''A'')&nbsp;∩ (''C''&nbsp;\&nbsp;''B'');
:*''C''&nbsp;\ (''B''&nbsp;\&nbsp;''A'') = (''C''&nbsp;\&nbsp;''B'')&nbsp;∪(''C''&nbsp;∩&nbsp;''A'');
:*(''B''&nbsp;\&nbsp;''A'')&nbsp;∩ ''C''&nbsp;= (''B''&nbsp;∩&nbsp;''C'')&nbsp;\ ''A''&nbsp;= ''B''&nbsp;∩ (''C''&nbsp;\&nbsp;''A'');
:*(''B''&nbsp;\&nbsp;''A'')&nbsp;∪ ''C''&nbsp;= (''B''&nbsp;∪&nbsp;''C'')&nbsp;\ (''A''&nbsp;\&nbsp;''C'').
The [[distributive law]]s:
:*&nbsp;''A''&nbsp;∩ (''B''&nbsp;∪ ''C'')&nbsp;= (''A''&nbsp;∩ ''B'')&nbsp;∪ (''A''&nbsp;∩ ''C''); *
:*&nbsp;''A''&nbsp;∪ (''B''&nbsp;∩ ''C'')&nbsp;= (''A''&nbsp;∪ ''B'')&nbsp;∩ (''A''&nbsp;∪ ''C''). *


'''PROPOSITION 3'''. Some properties of ⊆:
:*''A''&nbsp;⊆ ''B'' [[if and only if]] ''A''&nbsp;∩ ''B''&nbsp;= ''A'';
:*''A''&nbsp;⊆ ''B'' if and only if ''A''&nbsp;∪ ''B''&nbsp;= ''B'';
:*''A''&nbsp;⊆ ''B'' if and only if ''{{prime|B}}''&nbsp;⊆ ''{{prime|A}}'';
:*''A''&nbsp;⊆ ''B'' if and only if ''A''&nbsp;\ ''B''&nbsp;= {};
:*''A''&nbsp;∩ ''B''&nbsp;⊆ ''A''&nbsp;⊆ ''A&nbsp;''∪ ''B''.

==See also==

* {{annotated link|List of set identities and relations}}

==References==
* [[Edward Huntington]] (1904) "Sets of independent postulates for the algebra of logic," ''Transactions of the American Mathematical Society'' 5: 288-309.
* Whitesitt, J. E. (1961) ''Boolean Algebra and Its Applications''. Addison-Wesley. Dover reprint, 1999.

{{DEFAULTSORT:Simple Theorems In The Algebra Of Sets}}
[[Category:Operations on sets| ]]