Maths for computing topics, Sets and group: part 1

Topic

Sets and Groups: Part 1

Sets and Groups: Part 2

Matrices

Relations and Functions

Equations and Graphs/Spreadsheets

Mathematical Logic: Part 1

Mathematical Logic: Part 2

Permutations and Combinations

Probability

Introduction to Statistics

Further Spreadsheet Work

Set and Groups: Part 1

What is a set?

A set is a collection of distinct objects in no particular order. These objects, known as elements or members of the set, can be anything, including people, words, numbers, animals, or even other sets.

Examples of sets include:

• Songs stored on my phone
• Students at UEL
• Positive integers less than ten
• Countries in the European Union
• Words in the English language

Notation

In set theory, we typically use uppercase letters to represent sets. When listing the elements of a set, we enclose them in curly brackets {} and separate each element with a comma.

Examples:

• If A represents the set of all countries in the UK, we write:
  A = {Wales, Scotland, England, Northern Ireland}
• If B is the set of positive even numbers greater than zero and less than ten:
  B = {2, 4, 6, 8}
• When working with sets in mathematics, we often use lowercase letters to denote elements of a set. For example:
  C = {a, d, f, e, x, g}

Membership of a Set

To indicate whether an object belongs to a set, we use the following notation:

• x ∈ A → means x is an element of set A.
• x ∉ A → means x is not an element of set A.

Two sets are considered equal if and only if they contain exactly the same elements—no more and no fewer.

Ordering in a Set

A set is an unordered collection of elements, meaning the order in which elements are listed does not matter. There is no concept of a “first” or “second” element.

Example:

{a, b, c, d, e} = {e, d, b, c, a}

These two sets are identical because they contain the same elements, regardless of order.

Repetition in a Set

Each element in a set appears only once. Duplicates are not considered.

For example, if A = {1, 2, 3}, adding another 3 does not change the set—it remains {1, 2, 3}.

---

Set Theory: Key Concepts and Operations

Membership of a Set

• x ∈ A → x is an element of set A.
• x ∉ A → x is not an element of set A.
• Two sets are equal if they contain exactly the same elements.

Ordering in a Set

• A set is unordered, meaning the order of elements does not matter.
• Example:
  {a, b, c, d, e} = {e, d, b, c, a}

Repetition in a Set

• Each element appears only once in a set, regardless of how many times it is added.
• Example:
  A = {1, 2, 3} remains unchanged even if 3 is added again.

---

Worked Example on Set Relations

Given sets:
A = {1, 4, 6, 7, 9, 10}
B = {6, 7, 9, 10}
C = {3, 7, 9, 10}
D = {10, 7, 6, 9}

Evaluate the truth value of each expression:
a) B ⊆ A → True
b) A ⊆ B → False
c) B = D → True (same elements)
d) C ⊈ A → True (3 is not in A)
e) D ⊆ B → False
f) B ⊆ A → True

---

Set Operations

Basic Operations in Mathematics

• Addition
• Subtraction
• Multiplication
• Division

Basic Operations on Sets

• Union (∪)
• Intersection (∩)
• Difference ()
• Complement (A’ or Ac)
• Cartesian Product (×)

---

Union (∪)

The union of two sets A and B contains all elements from both sets, without duplicates.

Notation:
A ∪ B = A union B

Example:
If A = {John, Delroy, Adewale, Mohammed}
and B = {John, Sheila, Delroy, Zelda},
then:
A ∪ B = {John, Sheila, Adewale, Mohammed, Delroy, Zelda}

---

Intersection (∩)

The intersection of two sets A and B contains only the elements that both sets have in common.

Notation:
A ∩ B = A intersection B

Example:
If A = {John, Delroy, Adewale, Mohammed}
and B = {John, Sheila, Delroy, Zelda},
then:
A ∩ B = {John, Delroy}

• If two sets have no common elements, their intersection is the empty set (∅).
  • Example:
    If X = {a, b, d, e, g}
    and Y = {m, n},
    then: X ∩ Y = ∅

---

The Exclusion Principle

When finding the union of two sets, we avoid counting duplicates.

Formula:
n(A ∪ B) = n(A) + n(B) – n(A ∩ B)

Example:
Given A = {a, b, d, e, g} → n(A) = 5
and B = {a, b, c, f} → n(B) = 4
with A ∩ B = {a, b} → n(A ∩ B) = 2,

then: n(A ∪ B) = 5 + 4 – 2 = 7
(Verified: A ∪ B = {a, b, d, e, g, c, f} → n(A ∪ B) = 7)

---

Difference ()

The difference of two sets A and B contains elements in A that are not in B.

Notation:
A \ B = A difference B

Example:
If A = {John, Delroy, Adewale, Mohammed}
and B = {John, Sheila, Delroy, Zelda},
then:
A \ B = {Adewale, Mohammed}

---

Complement (A’)

The complement of a set A consists of all elements in the universal set (U) that are not in A.

Notation:
A’ = U \ A

Example:
If U = all UEL students
and A = UEL students studying computing,
then A’ = UEL students NOT studying computing.

Properties:

• A ∪ A’ = U
• A ∩ A’ = ∅
• U’ = ∅

---

Cartesian Product (×)

The Cartesian product of two sets A and B results in a set of ordered pairs, where each element in A is paired with each element in B.

Notation:
A × B

Example:
If A = {a, b, c}
and B = {d, e},
then:
A × B = {(a,d), (a,e), (b,d), (b,e), (c,d), (c,e)}

---

Worked Example on Set Operations

Given sets:
A = {b, d, f, g, h, x, y}
B = {f, g}
C = {g, x, z}
D = {z}

Evaluate the following:

1. A ∩ C = {g, x}
2. B ∪ C = {f, g, x, z}
3. B \ C = {f}
4. B ∩ D = ∅
5. B × C = {(f, g), (f, x), (f, z), (g, g), (g, x), (g, z)}

If the universal set is U = {b, d, f, g, h, x, y, z, w}, then:
C’ = {b, d, f, h, y, w}

Venn Diagrams

Venn Diagrams

A Venn diagram is a visual representation of sets, showing relationships between them.

• The universal set (U) is depicted as a rectangle, containing all possible elements.
• Each set is represented as a circle within the rectangle.
• Overlapping regions indicate common elements between sets, while non-overlapping areas show distinct elements.

Symmetric difference

The symmetric difference, denoted by the symbol ∆ (or sometimes ⊕), is defined as:

A ∆ B = (A \ B) ∪ (B \ A)

In other words, the symmetric difference of sets A and B consists of the elements that are in either A or B, but not in both.

The shaded area in the Venn diagram below represents the symmetric difference:

Worked examples

1. A = { a, b, c, d, e, f } B= { x, b, c, d, y, w, z }
   The universal set U= {a, b, c, d, e, f, x, y, w, z, p, q, r }
   Represent this information on a Venn diagram.

De Morgan’s Laws

De Morgan’s Laws describe the relationship between union and intersection in set theory and logic. They state that:

1. The complement of a union is the intersection of the complements: A∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B} This means that everything not in (A ∪ B) is the same as everything not in A and not in B.
2. The complement of an intersection is the union of the complements: A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B} This means that everything not in (A ∩ B) is the same as everything not in A or not in B.

Example:

Let U be the universal set, and let:

• A = {1, 2, 3, 4}
• B = {3, 4, 5, 6}
• U = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Verifying the First Law:

A∪B={1,2,3,4,5,6}A \cup B = \{1, 2, 3, 4, 5, 6\} A∪B‾={7,8,9}\overline{A \cup B} = \{7, 8, 9\} A‾={5,6,7,8,9},B‾={1,2,7,8,9}\overline{A} = \{5, 6, 7, 8, 9\}, \quad \overline{B} = \{1, 2, 7, 8, 9\} A‾∩B‾={7,8,9}\overline{A} \cap \overline{B} = \{7, 8, 9\}

So, A∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B}, confirming De Morgan’s first law.

Verifying the Second Law:

A∩B={3,4}A \cap B = \{3, 4\} A∩B‾={1,2,5,6,7,8,9}\overline{A \cap B} = \{1, 2, 5, 6, 7, 8, 9\} A‾={5,6,7,8,9},B‾={1,2,7,8,9}\overline{A} = \{5, 6, 7, 8, 9\}, \quad \overline{B} = \{1, 2, 7, 8, 9\} A‾∪B‾={1,2,5,6,7,8,9}\overline{A} \cup \overline{B} = \{1, 2, 5, 6, 7, 8, 9\}

So, A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B}, confirming De Morgan’s second law.

Classes of Sets and Power Sets

In set theory, the term class is often used to describe a collection of sets (also known as a set of sets).

For example, a class C may be defined as: C={{1,2,3},{4,5},{1,4,6}}C = \{ \{1, 2, 3\}, \{4, 5\}, \{1, 4, 6\} \}

Power Set

The power set of a set A is the collection of all possible subsets of A, including both the empty set and A itself. It is denoted as P(A).

Example

If A = {CAT, DOG, PARROT}, then the power set of A is: P(A)={∅,{CAT},{DOG},{PARROT},{CAT,DOG},{CAT,PARROT},{DOG,PARROT},{CAT,DOG,PARROT}}P(A) = \{ \emptyset, \{CAT\}, \{DOG\}, \{PARROT\}, \{CAT, DOG\}, \{CAT, PARROT\}, \{DOG, PARROT\}, \{CAT, DOG, PARROT\} \}

Key Property of Power Sets

If a set has a cardinality of nn (i.e., it contains n elements), then the total number of subsets in its power set is given by: ∣P(A)∣=2n|P(A)| = 2^n

where |P(A)| represents the number of elements in the power set.

Worked Examples

Example 1

If A is the set {x, y}, what is the power set, P(A)?

Solution:
The power set of A includes all possible subsets of A, including the empty set and A itself: P(A)={∅,{x},{y},{x,y}}P(A) = \{ \emptyset, \{x\}, \{y\}, \{x, y\} \}

---

Example 2

(a) If a set has a cardinality of 5 (i.e., it contains 5 elements), how many elements will be in its power set?

Solution:
The total number of subsets in a power set is given by: ∣P(A)∣=2n|P(A)| = 2^n

where n is the number of elements in the original set.

For n = 5: ∣P(A)∣=25=32|P(A)| = 2^5 = 32

So, the power set contains 32 subsets.

---

(b) How many proper subsets does the above set have?

Solution:
A proper subset is any subset except the set itself. Since the power set includes all subsets, the number of proper subsets is: 2n−1=25−1=32−1=312^n – 1 = 2^5 – 1 = 32 – 1 = 31

So, the set has 31 proper subsets.

Application to Computing

• The concept of collections is fundamental in computer science, especially in programming.
• Various types of collections, such as sequences and sets, frequently appear in real-world scenarios that need to be modeled in programs.
• While set theory may not always have direct applications in programming, its importance lies in its influence on other mathematical concepts that are crucial to computer science.
• In future discussions, we will explore how set theory plays a key role in understanding functions, logic, and probability—all of which are essential in computing.

Russell’s Paradox

The British philosopher Bertrand Russell identified a fundamental problem with the concept of a “set of all sets.” This paradox is explained as follows:

• Suppose T is the set of all sets that do not contain themselves as elements.
• Now, we ask: Is T an element of itself?

Two Contradictory Cases:

1. If T is an element of T, then by definition, T must be a set that does not contain itself. This contradicts the assumption that T is in T.
2. If T is not an element of T, then according to its definition, T should belong to itself, which again creates a contradiction.

Thus, we reach a logical paradox, known as Russell’s Paradox.

Avoiding the Paradox:

To resolve this issue, mathematicians distinguish between sets and classes (a broader concept). By using the term class instead of set in such cases, we avoid the paradox.

***THE END***