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 ∪), [[Intersection (set theory)|intersection]] (infix ∩), and set complement (postfix ') of sets.
These properties assume the existence of at least two sets: a given [[Universal set|universal set]], denoted '''U''', and the [[Empty set|empty set]], denoted {}. The algebra of sets describes the properties of all possible [[Subset|subset]]s of  '''U''', called the [[Power set|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 [[Philosophy: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]], 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|axiom]]s. A "*" follows the algebra of sets interpretation of 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|discrete mathematics]] courses sometimes leave students with the impression that the subject matter of [[Set theory|set theory]] is no more than these properties. For more about elementary set theory, see [[Set (mathematics)|set]], [[Set theory|set theory]], [[Algebra of sets|algebra of sets]], and [[Naive set theory|naive set theory]]. For an introduction to set theory at a higher level, see also axiomatic set theory, [[Cardinal number|cardinal number]], [[Ordinal number|ordinal number]], Cantor–Bernstein–Schroeder theorem, [[Cantor's diagonal argument]], Cantor's first uncountability proof, [[Cantor's theorem]], [[Well-ordering theorem|well-ordering theorem]], [[Axiom of choice|axiom of choice]], and [[Zorn's lemma]].

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


'''PROPOSITION 1'''. For any '''U''' and any subset ''A'' of '''U''':
*{}&prime; = '''U''';
*'''U'''&prime; = {};
*''A''&nbsp;\ {}&nbsp;= ''A'';
*{}&nbsp;\ ''A''&nbsp;= {};
*''A''&nbsp;∩ {}&nbsp;= {};
*''A''&nbsp;∪ {}&nbsp;= ''A''; *
*''A''&nbsp;∩ '''U'''&nbsp;= ''A''; *
*''A''&nbsp;∪ '''U'''&nbsp;= '''U''';
*''A''&prime; ∪ ''A'' = '''U'''; *
*''A''&prime; ∩ ''A'' = {}; * 
*''A''&nbsp;\ ''A''&nbsp;= {};
*'''U'''&nbsp;\ ''A''&nbsp;= ''A''&prime;;
*''A''&nbsp;\ '''U'''&nbsp;= {};
*''A''&prime;&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|if and only if]] ''B''&nbsp;\ ''A''&nbsp;= ''B'';
:*(''A''&prime; ∪ ''B'')&prime; ∪ (''A''&prime; ∪ ''B''&prime;)&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'')&nbsp; = (''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 laws:
:*&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|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 ''B''&prime;&nbsp;⊆ ''A''&prime;;
:*''A''&nbsp;⊆ ''B'' if and only if ''A''&nbsp;\ ''B''&nbsp;= {};
:*''A''&nbsp;∩ ''B''&nbsp;⊆ ''A''&nbsp;⊆ ''A&nbsp;''∪ ''B''.

==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:Basic concepts in set theory]]

{{Sourceattribution|Simple theorems in the algebra of sets|1}}