Introduction

A Set is a mechanism for describing a collection of elements. These collections can be of any discrete terms. Some examples of sets are as follows:

• Rainbow = {Red, Orange, Yellow, Green, Blue, Indigo, Violet}
• Cities = {All cities in France}
• SomeNumbers = {6, 1, 99, 10243, 8}

Set notation

1. Defining a Set

The elements of the set are coma-separated and enclosed within curly braces {}. Often, a Set is labelled by a symbol or an identifier. For example:

A = {1, 2, 3, 4}

Here, set A contains 4 elements (1 to 4).

2. Membership

If we wish to show that an element is a member of a set, we denote this as follows:

element ∈ Set

For example:

blue ∈ Colours
5 ∈ {1, 2, 3, 4, 5, 6}

If we wish to show that an element is NOT a member of a set, we use the following notation:

element ∉ Set

For example:

tree ∉ Colours
5 ∉ {9, 10, 11, 12}

3. Special Sets

• ∅: Empty Set.
• ℙ: All prime numbers.
• ℕ: All Natural numbers.
• ℤ: All Integers.
• ℚ: Fractions.
• ℝ: All Real numbers.
• ℂ: Counting Numbers.
• S: Universal Set.

4. Sub Sets

If set A is a subset of set B, we denote this as:

A ⊂ B

5. Power Set

The Power Set of A is the set of all subsets of A. It is denoted as:

P(A)

To demonstrate the idea of a power set, lets consider the following example:

A = { a, b, c}
P(A)= {a, b, c}
{a, b}
{a, c}
{b, c}
{a}
{b}
{c}

6. Cardinality

The Cardinality of a set is the number of elements a set contains. For example, the cardinality of set A is denoted as follows:

||A||

A= { Apple, Banana, Carrot}
Therefore, ||A|| = 3

Properties of a Set

1. Order of elements within a set

The order of elements in a set is not important. Therefore:

{8, 10, 1, 2} = {1, 2, 8, 10} = {10, 2, 8, 1}

2. Subsets

Definition: If the set B contains all the elements in the set A together with some other, then we say that A is a subset of B.

If we consider Sets as subsets of a Universe, we can visualize the Set A within the universal set S as follows:

Here, the outer square is labelled S, denoting the universal Set. The inner grey circle is shown to be Set A. We note there is a white area surrounding Set A within S. This space represents all elements not contained within set A. This is denoted as follows:

¯A (not A)

Thus we have the following mathematical relationship:

S - A = ¯A

Inferences

1. For A ⊂ B, if a ∈ A, then a ∈ B. Therefore a ∈ A ==> a ∈ B
2. If B is a subset but might possibly be the same as A then we use A ⊆ B.
3. If A ⊆ B, and B ⊆ A, then A = B.

Set Manipulations

Intersection

When we want a set of elements which are common to two (or more) sets, we refer to this as an intersection. In other words, the elements in common at an intersection of two (or more) sets.

The intersection of two sets, A and B, is denoted as

A ∩ B

Formally, we define the intersection of two sets as follows:

(x ∈ A) ∧ (x ∈ B) ==> (x ∈ A ∩ B)

Examples:

A = {1, 22, 53, 9}
B = {9, 10, 11}
C = A ∩ B = {9}

A = {Apples, Bananas, Carrots}
B = {Pineapples, Apples, Bananas, Eggplant}
C = A ∩ B = {Apples, Bananas}

Union

When we want a set of elements which are included in two (or more) sets, we refer to this as a union. In other words, all the elements from the two (or more) sets.

The union of two sets, A and B, is denoted as

A U B

Formally, we define the union of two sets as follows:

(x ∈ A) ∨ (x ∈ B) ==> (x ∈ A U B)

Examples:

A = {1, 22, 53, 9}
B = {9, 10, 11}
C = A U B = {1, 9, 10, 11, 22, 53}

A = {Apples, Bananas, Carrots}
B = {Pineapples, Apples, Bananas, Eggplant}
C = A U B = {Apples, Bananas, Carrots, Pineapples, Eggplant}

Rules for Set Operations

Using what we know so far regarding unions and intersections, we can derive the following list of rules for set operations.

Cartesian Product

The Cartesian Product of two sets, A and B, is defined as follows:

P = A x B = {(a,b)} where a ∈ A, and b ∈ B.

or more formally,

P = {(a, b) : (a ∈ A) ∧ (b ∈ B)}

The result is an ordered pair (a, b).

A example of where the Cartesian Product is used is with Euclidean Geometry. Here, we normally denote a point on the Cartesian Plain with (x,y), which is an ordered pair.

Here are some examples of the operation:

A = {a, b}
B = {1, 2}
P = A x B = {(a, 1), (a,2), (b,1), (b,2)}

A = {apples, bananas}
B = {green, red}
C = {small, large}
P = A x B x C = {(apples, green, small), (apples, green, large), (apples, red, small), (apples, red, large), (bananas, green, small), (bananas, green, large), (bananas, red, small), (bananas, red, large)}

As we can see by the second example above, we can calculate the Cartesian Product of any number of sets.

Relations

We use R to denote the relationship between two sets, A and B. Here a ∈ A and b ∈ B are related if (a,b) ∈ R. This is usually presented as aRb, which is a subset of the Cartesian Product of A and B.

Example 1

A relation R where the two elements are equal.

A = {1, 2, 3}
B = {1, 2, 3}
P = A x B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

R = {(i, j) : i = j} = [(1,1), (2,2), (3,3)}

Example 2

A relation R where the first element is larger than the second.

A = {1, 2, 3}
B = {1, 2, 3}
P = A x B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

R = {(i, j) : i > j} = [(2,1), (3,1), (3,2)}

Special Relations

Reflexive: ∀ x ∈ X, xRx.

Symmetric: ∀ (x, y) ∈ X, xRy ==> yRx.

Antisymmetric: ∀ (x, y) ∈ X, xRy ∧ yRx ==> x = y.

Video Overview

Exercises

A. Prove that for sets A, B and C

1. If A ⊆ B and B ⊆ C, then A ⊆ C
2. If A ⊆ B and B ⊂ C, then A ⊂ C
3. If A ⊂ B and B ⊆ C, then A ⊂ C

B. Having the following sets defined

A = {x ∈ ℤ: for some integer y > 0, x = 2y}
B = {x ∈ ℤ: for some integer y > 0, x = 2y - 1}
C = {x ∈ ℤ: for some integer x < 10}

Describe ¬A, ¬(A U B), ¬C, A - ¬C, and C - (A U B)

C. Show that for all sets A, B and C

(A ∩ B) U C = A ∩ (B U C)
    iff C ⊆ A

D. What is the cardinality of {{1,2},{3},1}?

E. Define the relation δ between the ordered pairs {(x,y) and (u, v) where x,y,u,v ∈ ℤ}, where (x,y) δ (u,v) means xv = yu, and show that δ is an equivalence relation.

Continue to next section.