Simple theorems in the algebra of sets: Difference between revisions

Content deleted Content added

Inline

Revision as of 07:59, 16 March 2011

The simple theorems in the algebra of sets are some of the elementary properties of the algebra of union (infix ∪), intersection (infix ∩), and set complement (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 subsets of U, called the power set of U and denoted P(U). P(U) is assumed closed under union, intersection, and set complement.

The algebra of sets is a model of Boolean algebra, with union, intersection, set complement, U, and {} interpreting Boolean sum, Boolean product, complementation, Boolean 1, and Boolean 0, respectively. The properties below are stated without proof, but can be derived from a small number of properties taken as axioms. A "*" follows the algebra of sets interpretation of Huntington's (1904) classic postulate set for Boolean algebra. These properties can be visualized with Venn diagrams. They also follow from the fact that P(U) is a Boolean lattice. The properties followed by "L" interpret the 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, 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 infix "\". The "relative complement of A in B," denoted B \A, is defined as (A ∪B′)′ and as A′ ∩B.

PROPOSITION 1. For any U and any subset A of U:

3

PROPOSITION 2. For any sets A, B, and C:

A ∩ B = B ∩ A; * L
A ∪ B = B ∪ A; * L
A ∪ (A ∩ B) = A; L
A ∩ (A ∪ B) = A; L
(A ∪ B) \ A = B \ A;
A ∩ B = {} if and only if B \ A = B;
(A′ ∪ B)′ ∪ (A′ ∪ B′)′ = A;
(A ∩ B) ∩ C = A ∩ (B ∩ C); L
(A ∪ B) ∪ C = A ∪ (B ∪ C); L
C \ (A ∩ B) = (C \ A) ∪ (C \ B);
C \ (A ∪ B) = (C \ A) ∩ (C \ B);
C \ (B \ A) = (C \ B) ∪(C ∩ A);
(B \ A) ∩ C = (B ∩ C) \ A = B ∩ (C \ A);
(B \ A) ∪ C = (B ∪ C) \ (A \ C).

The distributive laws:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); *
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). *

PROPOSITION 3. Some properties of ⊆:

A ⊆ B if and only if A ∩ B = A;
A ⊆ B if and only if A ∪ B = B;
A ⊆ B if and only if A′ ∪ B;
A ⊆ B if and only if B′ ⊆ A′;
A ⊆ B if and only if A \ B = {};
A ∩ B ⊆ A ⊆ A ∪ 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.

@@ Line 1: / Line 1: @@
-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]] &cup;), [[intersection (set theory)|intersection]] ([[infix]] &cap;), and [[complementation (mathematics)|complementation]] ([[postfix]] ') 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]] &cup;), [[intersection (set theory)|intersection]] ([[infix]] &cap;), and [[set complement]] ([[postfix]] ') of sets.
-This algebra, called [[Boolean algebra (structure)|Boolean algebra,]] describes the properties of all possible [[subset]]s of a [[universal set]], denoted '''U'''. These properties assume the existence of at least two sets: '''U''', and the [[empty set]], denoted {}. '''U''' is assumed [[closure|closed]] under union, intersection, and complementation.
+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|closed]] under union, intersection, and set complement.
+The algebra of sets is a model of [[Boolean algebra (structure)|Boolean algebra,]] with union, intersection, set complement, '''U''', and {} interpreting [[Boolean sum]], [[Boolean product]], [[complementation]], Boolean 1, and Boolean 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. The properties marked with a "*" make up an 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 the [[power set]] of any '''U''', denoted ''P''('''U'''), is a [[Boolean lattice]]. The properties followed by "L" are interpretations of the axioms for a [[lattice (order)|lattice]].
+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]].