User:Paul August/Subpage 3
New article: The algebra of sets
The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It also provides systematic procedures for evaluating expressions, and performing calculations, involving these operations and relations.
Introduction
The algebra of sets is the development of the fundamental properties of set operations and set relations. These properties provide insight into the fundamental nature of sets. They also have practical considerations.
Just like expressions and calculations in ordinary arithematic, expressions and calculations involving sets can be quite complex. It is helpful to have systematic procedures available for manipulating and evaluating such expressions and performing such computations.
In the case of arithmetic, it is elementary algebra that develops the fundamental properties of arithmetic operations and relations.
For example, the operations of addition and multiplication obey familiar laws such as associativity, commutivity and distributivity, while, the relation "less than or equal" satisfies such laws as reflexivity, antisymmetry and transitivity. These laws, provide tools which facilitate computation, as well as describe the fundamental nature of numbers, their operations and relations.
The algebra of sets is the set-theoretic analogue of the algebra of numbers. It is the algebra of the set-theoretic operations of union, intersection and complementation, and the relations of equality and inclusion. These are the topics covered in this article. For a basic introduction to sets see, Set, for a fuller account see Naive set theory. Axiomatic set theory describes a rigourous axiomatic approach to set theory.
The fundamental laws of unions and intersections
The set operations of union and intersection satisfy many identities. Several of these identities or "laws" have well established names. Three pairs of laws, are stated, without proof, in the following proposition.
PROPOSITION 1: For any sets A, B, and C, the following identities hold:
- commutative laws:
- A ∪ B = B ∪ A
- A ∩ B = B ∩ A
- associative laws:
- (A ∪ B ) ∪ C = A ∪ (B ∪ C )
- (A ∩ B ) ∩ C = A ∩ (B ∩ C )
- distributive laws:
- A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
- A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
Notice that the analogy between unions and intersections of sets, and addition and multiplication of numbers, is quite striking. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over unions. However, unlike addition and multiplication, union also distributes over intersection.
The next proposition, states two additional pairs of laws involving three specials sets: the empty set, the universal set and the complement of a set.
PROPOSITION 2: For any universal set U and subset A of U, the following identities hold:
- identity laws:
- A ∪ ∅ = A
- A ∩ U = A
- complement laws:
- A ∪ A′ = U
- A ∩ A′ = ∅
The identity laws says that in the same way that 0 is an identity element for addition, and 1 is an identity element for multiplication, ∅ is an identity element for union and U is an identity element for intersection.
The complement laws gives the fundamental properties of unary operation of set complementation.
The preeceding five pairs of laws can be said to be fundamental, because, it turns out, every valid proposition in the algebra of sets can be derived from them.
The principle of duality
The above propositions display the following interesting pattern. Each of the identities stated above is one of a pair of identities, such that, each can be transformed into ithe other by interchanging ∪ and ∩, and also ∅ and U.
These are examples of an extremely important and powerful property of set algebra, namely, the principal of duality for sets, which asserts that for any true statement about sets, the dual statement obtained by interchanging unions and intersections, interchanging U and ∅ and reversing inclusions is also true. A statement is said to be self-dual if it is equal to its own dual.
∅, U and A′ are unique
As was noted above, ∅ and U are, respectively, identity elements for the operations of union and intersection. The next proposition says that, like 0 and 1, they are the only such identity elements.
PROPOSITION 3: Let A and B be subsets of a universe U, then:
- If for every set A, A ∪ B = A, then B = ∅.
- If for every set A, A ∩ B = A, then B = U.
- If A ∪ B = U, and 'A ∩ B = ∅ then B = A′.
Other laws
PROPOSITION 4: For any universe U and subsets A, B, and C of U, the following identities hold:
- idempotent laws:
- A ∪ A = A
- A ∩ A = A
- domination laws:
- A ∪ U = U
- A ∩ ∅ = ∅
- De Morgan's laws:
- (A ∪ B )′ = A′ ∩ B′
- (A ∩ B )′ = A′ ∪ B′
- absorption laws:
- A ∪ (A ∩ B ) = A
- A ∩ (A ∪ B ) = A
- complement laws:
- ∅′ = U
- U′ = ∅
- double complement law:
- A′′ = A
The algebra of relative complements
The following proposition, lists several identities concerning relative complements or set-theoretic difference.
PROPOSITION 5: For any universe U and subsets A, B, and C of U, the following identities hold:
- C − (A ∩ B ) = (C − A ) ∪ (C − B )
- C − (A ∪ B ) = (C − A ) ∩ (C − B )
- C − (B − A ) = (A ∩ C ) ∪ (C − B )
- (B − A ) ∩ C = (B ∩ C ) − A = B ∩ (C − A )
- (B − A ) ∪ C = (B ∪ C ) − (A − C )
- A − A = ∅
- ∅ − A = ∅
- A − ∅ = A
- B − A = A' ∩ B
- (B − A )' = A ∪ B′
- U − A = A′
- A − U = ∅
The following proposition says that, the statement "A ⊆ B ", is equivalent to various other statements involving unions, intersections and complements.
PROPOSITION 6: For any two sets A and B, the following are equivalent:
- A ⊆ B
- A ∩ B = A
- A ∪ B = B
- B − A = ∅
- B′ ⊆ A′