Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint
Share this Page URL
Help

Chapter 3. Set Theory > Properties of Set Operations

3.7. Properties of Set Operations

Set operations have properties like those of the arithmetic operations. Addition and union of sets are both operations of putting things together, and they turn out to have similar properties. It is not obvious why multiplication and intersection of sets should be alike, but it turns out that they also have similar properties. These properties are very useful to simplify expressions and computations.

Examples of properties in arithmetic are commutativity and distributivity. Addition and multiplication are commutative because a + b = b + a and a × b = b × a for all numbers. Multiplication is distributive over addition because a × (b + c) = a × b + a × c for all numbers.

The numbers 0 and 1 are important in arithmetic because they are identity elements—they don't change numbers that they operate on. In addition, we have 0 + a = a and in multiplication, 1 × a = a. The null set ∅ plays a role like 0 since A ∪ ∅ = A, and the universal set U or the sample space S plays a role like 1 since AU = A.

Parentheses are used to clarify an expression involving set operations in the same way that they are used to clarify arithmetic or algebraic expressions. The expression 2 + 4 × 5 is ambiguous because you don't know whether to perform the addition first or the multiplication first. By putting in parentheses, you can distinguish between (2 + 4) × 5 = 30 and 2 + (4 × 5) = 22. In set theory, ABC can be different, depending on whether union or intersection is done first, so parentheses are necessary.

By convention, complementation is done before the other operations. It is not necessary to use parentheses in an expression like ABC to mean the intersection of the set A with the complement of the set B. However, it is necessary to use parentheses in the expression (AB)C to mean that the union must be performed before the complementation.

The most important properties of set operations are given below. The events A, B, and C are all taken from the same universe U.

  • Commutativity. This law says that the order of the operation doesn't matter.

    • Commutativity of Union: AB = BA

    • Commutativity of Intersection: AB = BA

  • Associativity. This law says that in a sequence of two or more instances of the same operation, it doesn't matter which one is done first. In arithmetic, addition and multiplication are associative since (a + b) + c is the same as a + (b + c) and (a × b) × c is the same as a × (b × c).

    • Associativity of Union: (A ∪ B) ∪ C = A ∪ (B ∪ C)

    • Associativity of Intersection: (A ∩ B) ∩ C = A ∩ (B ∩ C)

  • Distributivity. In arithmetic, multiplication is distributive over addition, a × (b + c) = a × b + a × c for all numbers, but addition is not distributive over multiplication since, for example, 3 + (2 × 5) is not the same as (3 + 2) × (3 + 5). Set theory is different, and we have two distributivity laws: intersection is distributive over union, and union is distributive over intersection.

    • A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

    • A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

  • Identity. In addition, 0 acts as an identity since 0 + a = a and in multiplication, 1 acts as identity since 1 × a = a. In set theory, the empty set acts as identity for union, and the sample set S or universal set U acts as identity for intersection.

    • ∅ ∪ A = A

    • UA = A

  • Idempotence. A number is an idempotent if the number operated on itself gives the number back again. In addition, 0 is idempotent since 0 + 0 = 0 and in multiplication 1 is idempotent since 1 × 1 = 1. In set theory, every set is idempotent with respect to both union and intersection.

    • A ∪ A = A

    • A ∩ A = A

  • Involution. The operation of complementation in set theory behaves somewhat like finding the additive or multiplicative inverse of a number—the inverse of the inverse of a number is the number itself. For addition, – (– a) = a, and for division, 1 / (1 / a) = a.

    • (AC)C = A

  • Complements. These laws show how sets and their complements behave with respect to each other.

    • A ∪ AC = U

    • A ∩ AC = ∅

    • UC = ∅

    • C = U

  • DeMorgan's Laws. These laws show how complementation interacts with the operations of union and intersection.

    • (AB)C = AC ∩ BC

    • (A ∩ B)C = AC ∪ BC

  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint