Sets

A set is mathematical method of listing elements. For example:

X  = {1, 2, 4, 7}

means X represents a set of numbers which are 1, 2, 4 and 7, or we can have another saying that 1, 2, 4 and 7 are the elements of set X. How should we write this statement in mathematical form? We can write 7 ∈ X, symbolizes 7 is an element of X. We can see in the set, there are only 1, 2, 4 and 7. There is no other numbers, like 10, 3, 5 and so on. Take number 10, for example, we can say that 10 is not an element of X, or in mathematical statement 10 ∉ X.

Example 1:

Set S contains all the alphabets of the English word “MATHEMATICS”.

Rewrite set S in mathematical form, we should get:

S  = { M, A, T, H, E, I, C, S }

Alphabet A is one of the alphabets contained in the word “MATHEMATICS”. We can say that alphabet A is an element of set S, or in the mathematical form: A ∈ S

A set can also contain elements which have no relation to each other. For example:

S  = { 1, Pang, 435.88, Cloud }

Instead of listing every element in a huge set, we use the symbol “…”.

Example 2:

Numbers in set S are not less than 50 and more than 100

S  = { 50, 51, 52, …, 100 }

Example 3:

Set S contains numbers within 1 to 1000 that is divisible by 8. We can write the set notation like this:

S  = { 8, 16, 24, …, 1000 }

However, there is another way to express this set by suing set builder notation. A set builder notation add a more detailed specification on what are the elements that a set has. It is suitable in expressing a set which has a great number of elements in it.

S  = { 1 < x <= 1000 | x is divisible by 8 }

The part which is bold is the condition for a number to become the element of the set. We should look in another example applying set builder notation.

Example 4:

Set A contains elements consists of whole numbers. Instead of writing it in the form S  = { 0, 1, 2, … }, we can write it in a specific way, which is:

A  = { x ∈ R | x is a whole number }

The above statement implies every real number can be an element of set S with condition that it must be a whole number too.

Empty Set

There exists sets which have no elements in them. We call a single set which has no elements in it as an empty set or some people prefer the term null set which sounds more technical.

Example 4:

Set N is a null set.

To show that set N is a null set, which is also an empty set. We write the set in mathematical form like below:

N = {}

or

N = ∅

Set of Numbers

Mathematics is useful in our daily life. Since younger age, we had the opportunity on learning numbers. However, numbers can be classified into different sets for different types. Here are some of them.

Natural numbers is the term we used to refer positive integers.

N  = { 1, 2, 3, 4, 5, …. }

There is no universal definition on natural numbers. Some books and resources define natural numbers as set of positive integers, in which the integer 0 is not included because it is neither positive nor negative. But in the Longman Pearson Discrete Mathematics reference book that we’re now using throughout this course mentioned that natural numbers are a set of non-negative integers, in which the neutral integer 0 is counted as one of the natural numbers because it is not negative. In this case, we’ll assume that natural numbers are positive integers, in which 0 is excluded.

Whole numbers is similar to natural numbers, but the neutral integer 0 is included.

W  = { 0, 1, 2, 3, 4, 5, …. }

There is no definition of whole number in the reference book that we’re using. Natural numbers are assumed to have a set of non-negative integers and they possess the characteristics of whole number.

Integers are a set of numbers with positive and negative numbers included. 

Z = { …, -2, -1, 0, 1, 2, … }

Positive integers are a set of integers carrying positive values.

Z⁺ = { 1, 2, 3, 4, … }

Negative integers are a set of integers carrying negative values.

Z^- = { … , -4, -3, -2, -1 }

Rational numbers are numbers with a fixed pattern of decimals. For example:  , transforms into decimal numbers 0.33333…… The decimal number has a fixed pattern of recursive 3’s as decimal. Therefore, it is a rational number. Unlike irrational numbers which have no fixed pattern of decimal. For example: 1.414213562373095…..

Q = { p / q | p ∈ Z , q ∈ Z , q ≠ 0 }

All the sets of numbers above are classified as real numbers. Real numbers are numbers that do exist in our real life.

R = { N, W, Z, Q }

Set Equality

When we have 2 sets which contain the exactly the same elements with each other, we can say that these 2 sets are equal to each other. Let us express this theory in more technical and mathematical terms.

Example 5:

There are 2 sets names P and Q respectively. P = { 3, 7, 1, 9 } and Q = { 3, 7, 1, 9 }. Since they both have the same value of elements. We can make a conclusion that:

Two sets are considered to be equal if ∀ x ( x ∈ P ↔ x ∈ Q )  is true.

Venn Diagram

A venn diagram is a graphical way of expressing sets. It is often represented by a rectangle followed with circles inside it. The rectangle represents universal set, which includes all elements involved. Universal set often denoted by capital letter U.

Example 6:

Let’s take the set from Example 1 as an example, the Venn diagram for the set representing all the alphabets in the word “MATHEMATICS” are shown below. 

 

From the graphic, we can see that there is a universal set, U and set S is a subset of U. There are points in the circle, indicating all the elements of set S.

Subset

We say that set A is a subset of set B, if every element of set A is also available in set B.

We use the symbol ⊆ to represents “is a subset of”.

Therefore, we can say that A ⊆ B.

Example 7:

Let’s take the set S in Example 1.

S  = { M, A, T, H, E, I, C, S }

There is another set called set T which has all the alphabets in the word “TITAS”.

Therefore, set T should looks like this:

T  = { T, I, A, S }

If you observe these 2 sets carefully, you’ll notice that all the elements in set T are available in set S. Therefore, we can make a conclusion that: S ⊆ T, or in other word, S is a subset of T.

The Venn diagram for the two sets should looks like this: 

 

Power Sets

Sometimes we may need to figure out what are the possible combinations of elements that may occur in a set. In this case, we use a power set on this. A power set of set X is denoted by P(S).

Example 8:

List out the power set of set G which consists of elements a, b, c.

G = { a, b, c }

Therefore, P(G) = { {}, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c} }

Set Operations

Sets are like numbers or English sentences. They can be combined together to form a new set. They are combined using some sort of set operations.

Union

Union of set A and set B, or A ∪ B is a set which contains all the elements from A or B. In mathematical definition, A ∪ B = { x | x ∈ A ∨ x ∈ B }

 

 

 

Example 9:

If set P = { 70, 45, 30, 56 } and set Q = { 44, 69, 70, 56 }, find out P ∪ Q.

Wrong : P ∪ Q = { 70, 45, 30, 56, 44, 69, 70, 56 }

Correct : P ∪ Q = { 70, 45, 30, 56, 44, 69 }

Intersection

Intersection of set A and set B, or A ∩ B is a set which contains elements that both of the sets A and B have. We can define intersection mathematically that A ∩ B = { x | x ∈ A ∧ x ∈ B }

 

Example 10:

If set P = { 70, 45, 30, 56 } and set Q = { 44, 69, 70, 56 }, find out P ∩ Q.

Since both sets P and Q contains the elements 70 and 56, then P ∩ Q = { 70, 56 }

Disjoint

When there is no intersection between 2 sets, we say the pair of sets are disjoint. The mathematical statement P ∩ Q = {} is used to describe this concept. 

 

 

Example 11:

P = { 70, 45, 30, 56 }

Q = { 44, 69, 60, 104 }

Sets P and Q do not have common elements, or in other words there is no element which they both have. Each set has its own and unique elements. Therefore, sets P and Q are disjoint.

Set Difference

The difference between set A and set B yields a set which has only elements in set A but has no elements in set B or both sets A and B. We can write the difference between set A and set B as A – B, since – sign indicates the difference operator.

A – B = { x | x ∈ A ∧ x ∉ B }

 

 

Example 12:

Find P – Q if P = { D, O, R, A, E, M, N } and Q = { N, O, B, I, T, A }

P – Q means difference between P and Q. Every element of Q is omitted. The elements left are D, O R, A, E, M, N. But this is not the final answer. Not only elements of set Q we have to omit but also elements of set P ∩ Q. O, A and N in set P have to be omitted too. The rest of the elements remained are D, R, E, M. Therefore, the difference between sets P and Q, or P – Q is { D, R, E, M }

Complement

We say a set is a complement of set A, or ¬A when the set involves all the regions of the universal set S, except for the region of set A. The symbol “¬” represents “not”.

 

 

Example 13:

Consider the universal set, S has the elements that represents the colour of a rainbow. 

 

 

S = { Red, Orange, Yellow, Green, Blue, Indigo, Purple }

Another set, L represents the light colour in a rainbow.

L = { Red, Orange, Yellow, Green }

The rest of the colours are dark colours.

Perhaps, we can create a set for the dark colours. Since all the colours other than light colours are dark colours, we’ll just using ¬L as the name of the set. Therefore, set ¬L should looks like this:

¬L = { Blue, Indigo, Purple }

Characteristics of Sets

We’ve learned the operation of sets. Now we’ll be looking on the characteristics of sets.

We learn different characteristics of sets so as to solve problems regarding to sets easier.

There are several laws regarding sets that we can make use of in applications of sets.

Laws	Definition
Identity Law	A ∩ U = A A ∪ ∅ = A
Domination Law	A ∪ U = U A ∩ ∅ = ∅
Idempotent Law	A ∪ A = A A ∩ A = A
Complementation Law	¬ (¬A) = A
Commutative Law	A ∩ B = B ∩ A A ∪ B = B ∪ A
Associative Law	(A ∩ B) ∩ C = A ∩ (B ∩ C) (A ∪ B) ∪ C = A ∪ (B ∪ C)
Distributive Law	A ∩ (B ∪ C) = (A ∩ B)(A ∩ C) A(B ∩ C) = (A ∪ B) ∩ (A ∪ C)
De Morgan’s Law	¬ (A ∩ B) = ¬ A ∪¬ B ¬ (A ∪ B) = ¬ A ∩ ¬ B
Absorption Law	A ∪ (A ∩ B) = A B ∪ (A ∩ B) = B
Complement Law	A ∪¬ A = U A ∩ ¬ A = ∅

Generalized Unions and Intersections

From associative law, we know that (A ∩ B) ∩ C = A ∩ (B ∩ C). Therefore we can conclude that A ∩ B ∩ C.

Same as A ∪ B ∪ C, where (A ∪ B) ∪ C = A ∪ (B ∪ C).

 

 

                                    A ∩ B ∩ C

 

                                 A ∪ B ∪ C

Example 14:

A = { 1, 5, 7, 9 }

B = { 2, 3, 5, 8 }

C = { 3, 4, 5, 9 }

Find A ∩ B ∩ C and A ∪ B ∪ C.  

The concept of union and intersection of sets is just the same. Therefore, I think I need not to explain further on this.

A ∩ B ∩ C = { 5 }

The element 5 exists in every set. Notice that 9 is not an element of A ∩ B ∩ C because there is no 9 in set B, same goes to number 3. Elements of A ∩ B ∩ C must exists in sets A, B, and C.

A ∪ B ∪ C = { 1, 2, 3, 4, 5, 7, 8, 9}

The methods used to denote unity and intersection of 3 sets are  A ∩ B ∩ C and A ∪ B ∪ C respectively. You will find this irritating when you comes to unity or intersection of more than 3 sets or even more than that. For example, you are asked to find unity of 100 sets. From what we have learnt, we would write lie this:

A₁ ∪ A₂ ∪A₃ ∪ …… ∪A₁₀₀

It’s reasonable but yet not really a practical way of showing sets. The more practical way we show this is

 

Substitute n with 100, we would get 

 

Same as A₁ ∩ A₂ ∩ A₃ ∩ ……∩ A₁₀₀. We use:

  

Substitute n with 100, we would get

 

 

Example 15:

Refer to Example 14, Let A = A₁, B = A₂, C = A₃,

Therefore we can write:

 

  

Before we proceed to Cartesian Product, there are a few things you have to take note.

Pair

A set having two elements is called a pair.

Example 16:

{1,2}, {2,1}

Both sets are equal despite of its location of the elements as long as both of them have 1 and 2 as their elements.

Ordered Pair

Ordered  pairs are a set having two elements, where the numbers are written in a particular order. The ordered pair with the first element x and second element y is written  as (x, y).

{x, y} and {y, x} represent different ordered pairs unless x = y.

Example 17:

Refer back to Example 16, both pairs are equal but they are not an ordered pair. An ordered pair of sets must have the same elements at the same positions. Meaning that both of them must be {1, 2} or {2, 1}.

Cartesian Product

The Cartesian product, or in other term, cartesian join of two sets is the set of all possible ordered pairs whose first element is from the first set and the second element is from the second set. In simple language, the Cartesian product is the direct product of the elements of two sets. If A and B are two non empty sets, then the Cartesian product is defined as follows:

A x B = {{ a , b } | a ∈ A and b ∈ B}

If the first and second elements are taken from a set of real numbers, then it is known as the Cartesian product of  Real numbers.

Example 18:

Let A = {1,2,3} and B={a, b, c}
Then A x B={{1,a}, {1,b}, {1,c}, {2,a}, {2,b}, {2,c}, {3,a}, {3,b}, {3,c}}

Example 19:

Let A = {Book, Pen, Pencil} and B={1,2}
Then A x B ={{Book, 1}, {Book, 2}, {Pen, 1}, {Pen, 2}, {Pencil, 1}, {Pencil, 2}}

 

Properties of Cartesian Products

1.     Cartesian product is not Commutative (except for empty Sets)
A x B ≠ B x A

2.     A x B = B x A if A = B (A and B are equal Sets)

3.     Cartesian Product of Empty Set

The Cartesian product of any set A with the empty set ∅ or { } is an empty set, since we cannot form any ordered pairs.
A x ∅ = ∅ x A = ∅

4.     Cartesian product is not Associative
(A x B) x C ≠ A x (B x C)

5.     (A ∩ B) x (C ∩ D) = (A x C) ∩ (B x D)

6.     (A ∪ B) x (C ∪ D) = (A x C) ∪ (B x D)

7.     A x (B ∩ C) = (A x B) ∩ (A x C)

8.     A x (B ∪ C) = (A x B) ∪ (A x C)

Powerpoint slides for this chapter

Please click here