### Unit 5: Set Theory

Computer scientists often find themselves working with sets of homogeneous or heterogeneous values. Scientists have devised set theory in order to respond to these situations. In this unit, we will learn the basics of set theory, taking a look at definitions and notations and using the proof methods and counterexample means we introduced earlier to establish set properties.a

Set theory is a fundamental tool of mathematics and often used as the starting point for its study and to define basic concepts, such as functions, numbers, and limits.

**Completing this unit should take you approximately 15 hours.**

Upon successful completion of this unit, you will be able to:

- define sets, operations on sets, and prove important valid set properties, called set identities; and
- apply the definitions and identities to prove set theoretic statements.

### 5.1: Definition of Set Theory

### 5.1.1: Set Notation

Study the notation used for sets in Section 1 on pages SF-1 to SF-2.

A set is a collection of elements, called members of the set. Sets are denoted using capital letters; elements are denoted using small letters. We write a ∈ A for a an element of A; and a A, for a not an element of A. Examples of sets can be found everywhere. All the units in this course comprise a set. The collection of people related to you comprise a set. Sets can be described using English descriptions, predicates in logic, or mathematical functions, in particular Boolean functions. A set can also be defined by listing the members of the set. A set can be finite, having a finite number of members; a set can be infinite. The number of elements of a set is one obvious property of a set.

The members, or elements, of a set can be anything, even sets themselves. For example, {a, b, {a, b}} is a set of 3 members, and one of the members is a set.

### 5.1.2: Set Equality

Study Definition 1 on page SF-1. Typically, when an object is defined in mathematics, we next define when two of those objects are equal. Then we define operations on those objects. Now, for the objects are sets. When are two sets equal?

If A and B are sets, and if a ∈ A, implies a ∈ B, then we say A is a subset of B, denoted A B. The number of subsets of a set A, is denoted 2A (the reason for this notation will become clear when you study functions.)

A = B, if and only if, A B and B A. A and B are assumed to be subsets of a universal set E. Ø is the empty set or the set that has no members.

Note that the order of the elements in a set does not change the set. Work sufficient examples to ensure that you completely understand the concept of set equality.

### 5.2: Set Operations

Recall that in logic, operations for building compound statements were defined. We do the same for sets, i.e. define operations for building new sets from old sets.

### 5.2.1: The Union Operator

Study set operations and the property of set operations Section 1 on pages SF-2 - SF-3. Set Union is defined on page SF-2.

Set Union is defined on page SF-2. Note that A B = {x : x ∈ A or x ∈ B}. You will read and reread this section several times, each time focusing on a basic set operation. These basic operations are so fundamental and ubiquitous (i.e. occur so frequently in mathematics, computer science, and their applications) that they deserve more than a quick reading. Work a lot of examples.

### 5.2.3: The Intersection Operator

Study the reading on set intersection, defined on page SF-2. Note: A ∩ B = {x : x ∈ A and x ∈ B}.

### 5.2.4: The Complement of a Set

This time, focus on complement of a set. Complement is set difference with respect to the largest set, called the universal set, namely, E - A is the complement of A. E is the universal set, the set of all elements; when sets are defined, the type of the elements is specified. For example, in a set of all red cars, the type of the members in this example, is car. We also say that the domain of the elements is the (universal) set of all cars.

### 5.2.5: Cartesian Products

One last time, look over the above reading. Now study the product of sets defined on page SF-2, just before the section titled "Set Properties and Proofs." The Cartesian Product, A x B = {(a, b) : a ∈ A and b ∈ B}, is referred to as the set of ordered pairs of A and B. Clearly, it is analogous to multiplication of numbers.

### 5.2.6: Binary Relation

Given a set A, a binary relation, R on A, is a subset of A x A. Note that a binary relation is a set of order pairs (x, y) where x and y are in A. The next subunits define properties of a binary relation, reflexive and symmetric. A third property is transitivity.

Relations are another critically important concept in set theory, functions, science, and every other subject. Work a lot of examples.

A binary relation on A is reflexive, if (a, a) ∈ R.

A binary relation is symmetric if (a, b) ∈ R, then (b, a) ∈ R.

A binary relation is transitive if (a, b) ∈ R, (b, c) ∈ R, then (a, c ) ∈ R. There is an important consequence of a binary relation being reflexive, symmetric, and transitive. A binary relation that has all 3 properties is called an equivalence relation. If a binary relation on A is an equivalence relation, it determines a partition of A. A partition of A is a set of subsets of A, which are mutually disjoint, and whose union is A.

### 5.3: Set Identities and Proof of Set Identities

Read "Set Properties and Proofs" on pages SF-2 - SF-6.

### 5.3.2: Associative Laws

Study Theorem 1 on pages SF-2 and SF-3 on the associative laws: (A B) C = A (B C) = A B C. Note that we can write the rightmost expression, which has no parenthesis, because is associative. Replacing by the intersection operations, gives the associative law for intersection. Prove the associative laws.

### 5.3.5: Complement Laws

Study the identities involving complement on pages SF-3 and SF-4. For universal set E, E' = Ø= A ∩ A'; A - A = Ø. Study example 1 on SF-4; VENN diagrams are a visual representation of sets, which are useful for depicting set membership of complements as well as other sets resulting from set operations. Use a VENN diagram to prove one of the identities involving complement.

### 5.3.6: Double Complement Laws

Study Theorem 1 on pages SF-2 and SF-3. Double complement is also referred to as double negative: (A') ' = A. Take the identities in the theorem involving set difference or complement. Insert a second difference or complement operator, thus creating some new set equations, and check whether the new set equations are still identities. Prove or disprove several of the equations you created by adding a second difference or complement operation.

### 5.3.8: Universal Laws

Study the identities involving the universal set in Theorem 1 and in examples 1 and 2 on pages SF-2 to SF-4. Prove some of the identities involving the universal set.

### 5.3.9: DeMorgan's Laws

Study Theorem 1 on pages SF-2 and SF-3 on DeMorgan's laws: (A B) ' = A' B'; (A B)' = A' B'. In English, the complement of A union B is the intersection of A complement and B complement; and the complement of A intersect B is the complement of A union the complement of B. DeMorgan's laws are famous and appear in many places in mathematics, engineering, and computer science. Prove DeMorgan's Laws.

### 5.3.10: Absorption Laws

Study Theorem 1 on pages SF-2 and SF-3 on absorption laws. These are called absorption identities because one of the sets is absorbed by the other(s). Prove the absorption laws.

### 5.3.11: Set Difference Laws

Study pages SF-1 and SF-2, and Theorem 1 on pages SF-2 and SF-3. The set difference laws: A - (B U C) = (A - B) ∩ (A - C); A - (B ∩ C) = (A - B) U (A - C) follow from the definition of set difference and De Morgan's Laws (use the fact the A - B = A ∩ B').

### Unit 5 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment