### Set Theory

It is natural for us to classify items into groups, or sets, and consider how those sets overlap with each other. We can use these sets understand relationships between groups, and to analyze survey data.

### Basics

An art collector might own a collection of paintings, while a music lover might keep a collection of CDs. Any collection of items can form a **set**.

### SET

A **set** is a collection of distinct objects, called **elements** of the set

A set can be defined by describing the contents, or by listing the elements of the set, enclosed in curly brackets.

### EXAMPLE 1

Some examples of sets defined by describing the contents:

- The set of all even numbers
- The set of all books written about travel to Chile

#### Answers

Some examples of sets defined by listing the elements of the set:

- {1, 3, 9, 12}
- {red, orange, yellow, green, blue, indigo, purple}

A set simply specifies the contents; order is not important. The set represented by {1, 2, 3} is equivalent to the set {3, 1, 2}.

### NOTATION

Commonly, we will use a variable to represent a set, to make it easier to refer to that set later.

The symbol ∈ means “is an element of”.

A set that contains no elements, { }, is called the **empty set** and is notated ∅

### EXAMPLE 2

Let *A *= {1, 2, 3, 4}

To notate that 2 is element of the set, we’d write 2 ∈ *A*

Sometimes a collection might not contain all the elements of a set. For example, Chris owns three Madonna albums. While Chris’s collection is a set, we can also say it is a **subset** of the larger set of all Madonna albums.

### SUBSET

A **subset** of a set *A* is another set that contains only elements from the set *A*, but may not contain all the elements of *A*.

If *B* is a subset of *A*, we write *B* ⊆ *A*

A **proper subset** is a subset that is not identical to the original set—it contains fewer elements.

If *B* is a proper subset of *A*, we write *B* ⊂ *A*

### EXAMPLE 3

Consider these three sets:

*A* = the set of all even numbers*B* = {2, 4, 6}*C* = {2, 3, 4, 6}

Here *B* ⊂ *A* since every element of *B* is also an even number, so is an element of *A*.

More formally, we could say *B* ⊂ *A* since if *x *∈ *B*, then *x *∈ *A*.

It is also true that *B* ⊂ *C*.

*C* is not a subset of *A*, since C contains an element, 3, that is not contained in *A*

### EXAMPLE 4

Suppose a set contains the plays “Much Ado About Nothing,” “MacBeth,” and “A Midsummer’s Night Dream.” What is a larger set this might be a subset of?

There are many possible answers here. One would be the set of plays by Shakespeare. This is also a subset of the set of all plays ever written. It is also a subset of all British literature.

### Union, Intersection, and Complement

Commonly sets interact. For example, you and a new roommate decide to have a house party, and you both invite your circle of friends. At this party, two sets are being combined, though it might turn out that there are some friends that were in both sets.

#### UNION, INTERSECTION, AND COMPLEMENT

The **union** of two sets contains all the elements contained in either set (or both sets). The union is notated *A *⋃* B. *More formally, *x *∊ *A *⋃ *B* if *x *∈ *A* or *x *∈ *B* (or both)

The **intersection **of two sets contains only the elements that are in both sets. The intersection is notated *A *⋂* B. *More formally, *x *∈ *A *⋂ *B* if *x *∈ *A* and *x *∈ *B.*

The **complement** of a set *A* contains everything that is *not* in the set *A*. The complement is notated *A’*, or *A ^{c}, or sometimes ~A.*

### EXAMPLE 5

Consider the sets:

*A* = {red, green, blue}*B* = {red, yellow, orange}*C* = {red, orange, yellow, green, blue, purple}

Find the following:

- Find
*A*⋃*B* - Find
*A*⋂*B* - Find
*A*⋂^{c}*C*

#### Answers

- The union contains all the elements in either set:
*A*⋃*B*= {red, green, blue, yellow, orange} Notice we only list red once. - The intersection contains all the elements in both sets:
*A*⋂*B*= {red} - Here we’re looking for all the elements that are
*not*in set*A*and are also in*C*.*A*⋂^{c}*C*= {orange, yellow, purple}

### UNIVERSAL SET

A **universal set** is a set that contains all the elements we are interested in. This would have to be defined by the context.

A complement is relative to the universal set, so *A ^{c}*contains all the elements in the universal set that are not in

*A*.

### EXAMPLE 6

- If we were discussing searching for books, the universal set might be all the books in the library.
- If we were grouping your Facebook friends, the universal set would be all your Facebook friends.
- If you were working with sets of numbers, the universal set might be all whole numbers, all integers, or all real numbers

#### EXAMPLE 7

Suppose the universal set is *U* = all whole numbers from 1 to 9. If *A* = {1, 2, 4}, then *A ^{c} *= {3, 5, 6, 7, 8, 9}.

### Cardinality

Often times we are interested in the number of items in a set or subset. This is called the cardinality of the set.

### CARDINALITY

The number of elements in a set is the cardinality of that set.

The cardinality of the set *A* is often notated as |*A*| or n(*A*)

### CARDINALITY PROPERTIES

n(*A* ⋃ *B*) = n(*A*) + n(*B*) – n(*A* ⋂ *B*)

n(*Ac*) = n(*U*) – n(*A*)

### EXAMPLE 12

Let *A* = {1, 2, 3, 4, 5, 6} and *B* = {2, 4, 6, 8}.

What is the cardinality of *B*? *A* ⋃* B*, *A *⋂* B*?

#### Answers

The cardinality of *B* is 4, since there are 4 elements in the set.

The cardinality of *A* ⋃* B* is 7, since *A* ⋃* B* = {1, 2, 3, 4, 5, 6, 8}, which contains 7 elements.

The cardinality of *A *⋂* B* is 3, since *A *⋂* B* = {2, 4, 6}, which contains 3 elements.

### EXAMPLE 13

What is the cardinality of *P* = the set of English names for the months of the year?

#### Answers

The cardinality of this set is 12, since there are 12 months in the year.

### Cartesian product definition

For two sets *A* and *B*, the Cartesian product of *A* and *B* is denoted by *A*×*B* and defined as:

A×B = { (a,b) | aϵA and bϵB }

Cartesian Product is the multiplication of two sets to form the set of all ordered pairs. The first element of the ordered pair belong to first set and second pair belong the second set. For an example,

Suppose, A = {dog, cat}

B = {meat, milk} then,

A×B = {(dog,meat), (cat,milk), (dog,milk), (cat,meat)}

### Cartesian Product Examples

#### Example #1: Practical Example on Cartesian Product

**If X be the set of points on x-plane and Y be the set of points on y-plane then, X×Y represents the on XY plane.**

#### Example #2

**Suppose two sets A = {a, b} and B = {1, 2, 3}. Find A×B and B×A.**

Here,

A = {a, b}

B = {1, 2, 3}

Now,

A×B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

B×A = {(1,a), (1,b), (2,a),(2,b), (3,a), (3,b)}

### Example #3

**If A×B = { (x,1), (x,2), (x,3),(y,1), (y,2), (y,3)}. Find A and B.**

Since, set A contains first element of each ordered pair only,

A = {x, y}

Since, set B contain second element of ordered pair only,

B = {1, 2, 3}

We exclude duplicate elements in both sets (because, set can only contain unique element).

**Cartesian Product of 3 Sets**

For three sets A, B and C, the Cartesian product of A, B and C is denoted by A×B×C and defined as:

A×B×C = { (p, q, r) | pϵA and qϵB and rϵC }

## Key Points on Cartesian Product

### Cartesian Product of Empty Set

**If either of two set is empty, the Cartesian product of those two set is also an empty.**

If *A = {1, 2}* and *B = ϕ*. Then, *A×B = ϕ* and *B×A = ϕ*.

### Non-commutativity Property

**For two unique and non-empty sets A and B, A×B is not equal to B×A.**

If *A = {a, b}* and *B = {1, 2, 3}* then,

A×B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

B×A = {(1,a), (1,b), (2,a),(2,b), (3,a), (3,b)}

Here, A×B ≠ B×A

### Condition for Commutative Property

**For two sets A and B, the Cartesian product of two sets A×B and B×A are equal if either of the following condition is satisfied:**

- either of two set is empty
- both sets are equal

If *A = {1, 2}* and *B = ϕ*. Then,

A×B = ϕB×A = ϕHence,A×B = B×A

If *A = B = {1, 2}* then,

A×B = {(1,2), (2,2), (2,1), (2,2)}

B×A = {(1,2), (2,2), (2,1), (2,2)}

A×A = A^{2}= {(1,2), (2,2), (2,1), (2,2)}

B×B = B^{2}={(1,2), (2,2), (2,1), (2,2)}

Hence,A×B = B×A = A^{2}= B^{2}