The Algebra of Sets
Number Types
Number Types
Natural Numbers
Natural numbers are the numbers used for counting. They include all whole numbers starting from 0 and extending to infinity.
Examples:
3, 10, 289, 1098.
Integers
Integers include all natural numbers along with negative numbers. They consist of all whole numbers, ranging from negative infinity to positive infinity.
Examples:
-1, 34, -235, 0, 195.
Rational numbers
Rational and Irrational Numbers
- Rational numbers are numbers that can be expressed in the form p/q, where p and q are integers, and q ≠ 0.
- Some numbers occur naturally in mathematics but cannot be expressed as rational numbers; these are called irrational numbers (also known as surds).
Examples of Irrational Numbers:
- √2 (a non-repeating, non-terminating decimal)
- π (the ratio of a circle’s circumference to its diameter)
- Euler’s number (e), an important mathematical constant used in exponential growth and logarithms.
Real Numbers
Real numbers are numbers that can have a fractional part. They include both rational numbers and irrational numbers.
Additionally, real numbers encompass integers (and, by extension, natural numbers) because integers can be expressed in decimal form, such as 2.0, 3.0, -5.0, and so on.
Examples of real numbers include:
-3.127, 34.987, 0.001, -108.7, 3.0.
Complex numbers
Complex numbers are used in advanced mathematics and consist of a real part and an imaginary part.
The imaginary part involves a special number, i, which is defined as the square root of -1. Since no real number can produce -1 when squared, this is why we refer to it as an imaginary number.
A typical complex number may be written as 3 + 2i.
The set of complex numbers also includes real numbers, which occur when the coefficient of i is 0.
Worked example
Consider the following numbers: -4.82 33 -262 45.987 0.3
Which of these numbers are:
a) Real numbers b) Integers c) Natural numbers
Solution
a) All of them are real numbers.
b) 33 and -262 are integers (as well as being real numbers)
c) 33 is a natural number (as well as being an integer and a real number).
Working with Complex Numbers
Addition
To add complex numbers, we simply add the real parts and the imaginary parts separately.
For example:
(3 + 2i) + (4 – i) = (3 + 4) + (2i – i) = 7 + i.
Multiplication
To multiply complex numbers, we use the distributive property (binomial multiplication).
For example:
(3 + 2i)(4 – 2i)
= 3(4) + 3(-2i) + 2i(4) + 2i(-2i)
= 12 – 6i + 8i – 4i²
Now, since i² = -1, we substitute -1 for i²:
= 12 – 6i + 8i + 4
= (12 + 4) + (-6i + 8i)
= 16 + 2i.
Application in Computing
In most programming languages, we need to declare the type of a variable before using it. This is because different types of numbers are stored differently in memory. For instance, storing a real number requires significantly more memory than storing an integer. The available variable types in Java are shown on the next slide.
Number Sets
It is common to represent different sets of numbers using the following symbols:
- {N} for the set of natural numbers
- {Z} for the set of integers
- {Q} for the set of rational numbers
- {R} for the set of real numbers
- {C} for the set of complex numbers
We see that: N ⊂ Z ⊂ Q ⊂ R ⊂ C
Discrete vs. Continuous Values
Imagine turning on a tap just enough for it to drip. You can count the individual drops of water. Now, if you open the tap further, the water flows in a continuous stream, making it impossible to count individual drops.
Discrete values are like water droplets—they come in separate units that can be counted. Natural numbers and integers are discrete since you can count how many integers exist between 1 and 10.
Continuous values are like a flowing stream of water—there are no distinct, countable units. Real numbers are continuous, meaning it is impossible to count how many values exist between 2.1 and 2.2, as there are infinitely many.
Countable and Uncountable Sets
Consider the set of positive integers from 5 to 10. This set contains exactly six numbers, which we can count one by one.
Now, what if there were no upper limit? We could still count the numbers sequentially—5, 6, 7, and so on—but we would never finish because the set is infinite. A set like this is called countably infinite since we can list its elements in order, even if the process never ends.
Now, consider the set of real numbers between 5 and 10. How would we count them? If we start at 5.0 and move to 5.1, what about 5.01, 5.001, or the infinitely many numbers between them? No matter how small a step we take, there will always be another number in between.
Mathematically, it has been proven that between any two real numbers, there is always another real number. This means the set of real numbers, ℝ, is uncountable and infinite, whereas the set of natural numbers ℕ and the set of integers ℤ are countable and infinite.
This distinction shows that there are actually two types of infinity: countable infinity and uncountable infinity!
Operation
In mathematics, an operation is a calculation that transforms one or more input values (called operands) into a result.
The four basic arithmetic operations are:
- Addition (+)
- Subtraction (–)
- Multiplication (× or * )
- Division (÷ or / )
Commutative Operations
An operation is commutative if changing the order of the operands does not affect the result.
In arithmetic, the following operations are commutative:
- Addition: x+y=y+xx + y = y + x
- Example: 2+3=3+2=52 + 3 = 3 + 2 = 5
- Multiplication: x×y=y×xx \times y = y \times x
- Example: 2×3=3×2=62 \times 3 = 3 \times 2 = 6
Non-Commutative Operations
Some arithmetic operations are not commutative, meaning that changing the order of the operands affects the result.
- Subtraction: x − y ≠ y − x
- Example: 10 − 3 = 7, but 3−10= -7
- Division: x ÷ y ≠ y ÷ x
- Example: 10 ÷ 5 = 2 but 5 ÷ 10 = 0.5
Associative Operations
An operation is associative if changing the grouping of the operands does not affect the result.
In arithmetic, the following operations are associative:
- Addition: x + (y + z) = (x + y) + z
- Example: 2 + (3+4) = (2+3) + 4 = 92 + (3 + 4) = (2 + 3) + 4 = 9
- Multiplication: x X (y X z) = (x X y) X z
- Example: 2 × (3 × 4) = (2 × 3) × 4 = 24
Non-Associative Operations
Some arithmetic operations are not associative, meaning that changing the grouping of the operands affects the result.
- Subtraction: x − (y−z) ≠ (x−y) − z
- Example: 12−(6−2)=812 – (6 – 2) = 8, but (12−6)−2=4, 12 – (6 – 2) ≠ (12 – 6) – 2
- Division: x÷(y ÷ z ) ≠ (x ÷ y)÷z
- Example: 12÷(6÷2)=4, but (12 ÷ 6) ÷ 2 = 1, 12 ÷ (6 ÷ 2) ≠ (12 ÷ 6) ÷ 2
Commutative and Non-Commutative Operations in Set Theory
In set theory, some operations are commutative, meaning the order of the sets does not affect the result:
- Union: A ∪ B = B ∪ A
- Intersection: A ∩ B = B ∩ A
However, some operations are not commutative, meaning that changing the order of the sets affects the result:
- Difference: A ∖ B ≠ B ∖ A
- Cartesian Product: A × B ≠ B × A
Associative and Non-Associative Operations in Set Theory
Some set operations are associative, meaning the way elements are grouped does not affect the result:
- Union: (A ∪ B) ∪ C = A ∪ (B ∪ C)
- Intersection: (A ∩ B) ∩ C = A ∩ (B ∩ C)
However, set difference is not associative, meaning the grouping of elements affects the result:
- Difference: (A ∖ B) ∖ C ≠ A ∖ (B ∖ C)
Is the Cartesian Product Associative?
Strictly speaking, the Cartesian product is not associative. This means that: (A × B) × C ≠ A × (B × C)
To illustrate, let’s consider the following sets:
- A={a, m, n}
- B={b, x, y}B = \{b, x, y\}
- C={c, d, e, f, g}C = \{c, d, e, f, g\}
The left-hand side would give us ordered pairs of pairs, such as: {((a, b),c),((a, b),d),((a, b),e),… }
The right-hand side would give us pairs where the second element is itself a pair, such as: {(a,(b, c)),(a,(b, d)),(a,(b, e)),… }
These two results are clearly different.
However, in practice, we often treat the Cartesian product of three sets as forming ordered triples. In this case, both sides would give the same result, such as: {(a, b, c), (a, b, d), (a, b , e),…..}
Thus, while the Cartesian product is not strictly associative, it is commonly assumed to be associative when dealing with ordered triples.
Groups
A group is a set combined with an operation. For example, the set of integers with the operation of addition forms a group.
However, for a set and an operation to constitute a group, they must satisfy the following criteria:
- Identity: The group must contain an identity element, which, when combined with any element of the group, leaves that element unchanged.
- Inverses: Every element in the group must have an inverse, meaning that for every element aa, there exists an element bb such that aa combined with bb results in the identity element.
- Associativity: The operation must be associative, meaning that the grouping of operations does not affect the result.
- Closure: The group must be closed under the operation, meaning that performing the operation on any two elements of the group will always result in an element that is also in the group.
Next, we will explore each of these criteria in detail.
Identity Element in a Group
When the operation is applied to any element and the identity, the element remains unchanged.
For example, consider the set of integers with the operation of addition. The identity element in this case is 0:
- 5 + 0 = 5 5 + 0 = 5, 0 + 5 = 5 0 + 5 = 5
- 7 + 0 = 7 7 + 0 = 7, 0 + 7 = 7 0 + 7 = 7
- −5 + 0 = −5 -5 + 0 = -5, −5 + 0 = −5 -5 + 0 = -5
And so on.
Key Points about the Identity Element:
- The identity element must be an element of the set.
- There is only one identity element for each group.
- The symbol commonly used for the identity element is e.
Formal Definition:
For a set G under the operation *:
there exists an identity element e in G, such that a * e = a and e * a = a, for all elements a in G.
This means that the operation with the identity element leaves every other element unchanged.
A group must contain inverses
For every element of the group, there exists another element in the group such that when the operation is applied to both, the result is the identity element e.
For example, in the set of integers with the operation of addition, the inverse of 5 is −5 because 5+(−5)=0, which is the identity element. Similarly, the inverse of −5 is 5.
Key Points:
- If aa is the inverse of bb, then bb is also the inverse of aa.
- Inverses are unique. For example, there is no other number x, apart from −5, such that 5 + x = 0.
Notation:
- The inverse of an element a is written as a^{-1}, and in this case, a^{-1} = b.
Formal Definition:
For every element a ∈ G, there exists an element b ∈ G such that: a ∗ b = e and b * a = e
This means that when the operation is applied to aa and bb, it results in the identity element e.
A group must be associative
- we already know the meaning of this.
For example
For the set of integers, addition is an associative operation.
A group must be associative
Formally:
For all a, b, and c in G, a * (b * c) = (a * b) * c
A group must be closed under the operation
- if there are two elements in the group, a and b, and * represents the operation,
then it must be the case that a * b is also in the group. - we say that the group is closed under the operation.
For example
With integers and addition, then the group is closed because whatever the value of
and a and b, a + b is always an integer.
Formally:
For all a, b in G, a * b is in G
We see that the group integers with addition is formally a group because it has all of
the required properties.
Notation and terminology
You will often see a group written like this: (G, *)
where G represents the set, and * the operation.
For example:
The set of integers with addition: (ℤ, +)
The set {1} with multiplication: ({1}, x)
Note
- Sometimes you will see the symbol used instead of *.
- If a group is also commutative, it is referred to as an abelian group.
- A group that has associativity and closure only is called a semigroup.
- A semigroup that has an identity element is called a monoid.
Worked examples
- Is the set {-1, 1} under multiplication a group?
Solution
Is there an identity element?
The identity element is 1 because 1 x 1 = 1 and -1 x 1 = -1.
Are there inverses?
1 x 1 = 1 and -1 x -1 = 1, so there is an inverse for each element.
Is the operation associative?
We already know that multiplication is associative with any integers.
Is there closure?
It is closed because the results of all of the following are in the group:
1 x 1 -1 x -1 1 x -1 -1 x 1
Therefore the set {-1, 1} under multiplication is a group.
- Is the set {-1, 0, 1} under addition a group?
Solution
Is there an identity element?
The identity element is 0.
Are there inverses?
-1 + 1 = 0, 1 + -1 = 0 and 0 + 0 = 0, so there is an inverse for each element.
Is the operation associative?
We already know that addition is associative with any integers.
Is there closure?
It is not closed because the result of adding -1 to itself is not in the group, neither
is the result of adding 1 to itself.
Therefore the set {-1, 0, 1} under addition is not a group.
- Is the set of integers under multiplication a group?
Solution
Is there an identity element?
The identity element is 1.
Are there inverses?
If you take an integer such as 7, there is no integer that will result in 1 if multiplied by 7.
This applies to all integers except 1.
So it does not satisfy the inverse property
The set of integers under multiplication is therefore not a group.
- Is the set of rational numbers excluding zero under multiplication a group?
Solution
Is there an identity element?
The identity element is 1.
Are there inverses?
We can find an inverse for every element.
For example: The inverse of 5
7 is 7
5 because 5
7 × 7
5 = 1.
The same applies to every rational number (excluding zero)
Is the operation associative?
We already know that multiplication is associative with all numbers.
Is there closure?
It is closed because the result of any possible multiplication always results in
another rational number:
𝑎/𝑏 × 𝑐/𝑑 = 𝑎𝑐/𝑏𝑑
Therefore the set of rational numbers excluding zero under multiplication is a group.
But notice that if we include zero, it is not a group because there is no inverse for zero.
***THE END***