Foundations of Mathematics Overview
Foundations of Mathematics Overview
MATHEMATICS
Abdulqader Othman
Department of Mathematics
Koya University
2022
Contents ii
List of Tables xi
Dedication xv
Preface xvi
1 Mathematical Logic 1
1.1 Introduction 1
1.2 Definition 2
1.3 The Initial Statement 2
1.4 The Axiom 2
1.5 Sets 2
1.5.1 Express of Sets 2
1.5.2 Membership to Sets 3
1.5.3 Empty Set 3
1.5.4 Subset 4
1.5.5 Proper Subset 4
1.5.6 Universal Set 4
1.6 Types of Set Numbers 4
1.7 Sets in the Form of Intervals 5
1.8 Equality 6
1.8.1 Properties of Equality 6
1.8.2 Equality of Sets 6
1.9 Sentences 7
1.9.1 Statements 7
iii
1.9.2 Variables 8
1.9.3 Parameters 8
1.9.4 Open Sentences 9
1.9.5 Solution Sets 9
1.10 Exercises 9
1.11 Negation and Compound Statements 11
1.11.1 Negation 11
1.11.2 Axiom of Negation 11
1.11.3 Truth Table 11
1.11.4 Compound Statements 12
1.12 Exercises 17
1.13 The Compound Statements with More Than One
Connective 18
1.14 Exercises 19
1.15 Logical Equivalence 20
1.15.1 Tautology 21
1.15.2 Contradiction 22
1.16 Exercises 24
1.17 Logical Implication 25
1.18 Exercises 26
1.19 Algebra of Statements 26
1.20 Exercises 28
1.21 Quantifiers 29
1.21.1 Existential Quantifier 29
1.21.2 Universal Quantifier 29
1.21.3 Negation of Quantifiers 30
1.21.4 Hilbert Operator on an Open Sentence 31
1.22 Exercises 32
1.23 Logical Reasoning 33
1.24 Exercises 34
1.25 Mathematical Proof 34
1.25.1 Proof of Sentences of Type (P → Q) 35
1.25.2 Proof of Sentences of Type (P ↔ Q) 36
1.25.3 Proof of Sentences of Type (∀x, P (x)) 36
1.25.4 Proof of Sentences of Type (∃x, P (x)) 37
1.25.5 Proof of Sentences of Type (P ∨ R → Q) 37
iv
2 Algebra of Sets 41
2.1 Introduction 41
2.2 Union and Intersection of Sets 42
2.2.1 Union of Sets 42
2.2.2 Intersection of Sets 44
2.3 Exercises 47
2.4 Complement of a Set 47
2.5 Symmetric Difference 50
2.6 Exercises 51
2.7 Family of Sets 53
2.7.1 Power Sets 53
2.7.2 Index Family of Sets 56
2.7.3 Generalized Union and Intersection 56
2.8 Exercises 58
3 Relations 61
3.1 Introduction 61
3.2 Ordered Pairs 62
3.2.1 Cartesian Product 63
3.2.2 Co-ordinate Diagram 65
3.2.3 Generalization of Cartesian Product 65
3.3 Exercises 67
3.4 Binary Relation 68
3.5 Expression of the Relation 68
3.6 Basic Concepts of Relations 71
3.6.1 Identity Relation 71
3.6.2 Inverse Relation 71
3.6.3 Domain and Range of a Relation 72
3.6.4 Restriction of a Relation 73
3.6.5 Composition of Relations 74
3.7 Exercises 76
3.8 Types of Relations 77
3.8.1 Reflexive Relation 78
v
4 Mapping 111
4.1 Introduction 111
4.2 Mapping 112
4.3 The Basic Definitions 112
4.4 Graph of the Mapping 115
4.5 Surjective Mapping 116
4.6 Injective Mapping 117
4.7 Bijective Mapping 117
4.8 Equality of Mapping 118
4.9 Types of Mappings 119
4.9.1 Identity Mapping 119
4.9.2 Constant Mapping 119
4.9.3 Inclusion Mapping 120
4.9.4 Characteristic Mapping 120
4.9.5 Restriction of Mapping 120
4.9.6 Extension of Mapping 121
4.9.7 Numerical Mapping 121
vi
Bibliography 353
Index 387
List of Tables
1.1 Introduction
athematics consists of three main branches; arithmetic and
M probability, algebra and what are related them, and geometry
in all its branches. Logic is the only way to connect these branches
directly or indirectly. All mathematicians agree that the mathematics
generally is a connected and consistent unit, based on sets in its the
mathematical structures or mathematical systems, basically formed on
sets and the associated concepts.
The traditional mathematics focus on acquiring mathematical
skills rather than mathematical concepts, while the modern
mathematics balance between the acquiring mathematical skills and
the mathematical concepts.
Since mathematics interference all the fields in the real life,
because all modern sciences are structured based on the sets and the
relationships on them, hence, the progress of the mathematics is closely
related to the progress of the society and its intellectual and material
prosperity.
2 Foundations of Mathematics
1.2 Definition
We can define the concept of definition based on some researchers in
literature (Eves and Newsom, 1958; Stoll, 1979; Ian, 1995; Kamke, 1950)
as follows.
1.5 Sets
Definition 1.4 The set A is any collection of definite, distinguishable
objects of our intuition or of our intellect to be conceived as a whole.
The objects are called elements or members (Stoll, 1979).
.
(ii) Tabulation method. In this method the elements of the set can
be written between braces and named. For example, (1). A =
{1, p, y, x, 0, −5}. (2). the set of the integer numbers of 5, 6, 7 can
be written as {5, 6, 7}.
(iii) Rule method. This method can assigned a property owned by all
the elements in the set, and not owned by others. P (x) can be
used as a sentence in the variable x. For example (x ≤ 5, x is an
odd integer), can be expressed as: {x|P (x)} = {5, 3, 1}. Or, can
be defined as: {x|1 ≤ x ≤ 5}. It means, (the set of all odd integers
such that, 1 ≤ x ≤ 5). As well as the set of all integers that their
square are greater than 3 can written as, {x|x2 > 3, x ∈ Z}.
Example 1.1 (i) The set of natural numbers less than zero= φ.
(ii) {x|x2 = 13 ∧ x ∈ Z+ } = φ.
4 Foundations of Mathematics
(iii) {x|x 6= x ∧ x ∈ C} = φ.
1.5.4 Subset
Definition 1.6 Let A, B 6= φ, A ⊆ B ⇔ a ∈ A ⇒ a ∈ B(Stoll, 1979).
And said A is subset of B, or B contain of A.
(iii) Half open interval from the left = {x|a < x ≤ b} = (a, b].
Example (−2, 5].
(iv) Half open interval from the right= {x|a ≤ x < b} = [a, b).
Example [−2, 5).
6 Foundations of Mathematics
1.8 Equality
Definition 1.9 If both a, b are symbols to the same thing (object) then
the statement a = b means the same thing (Carolyn, 1981).
Note: If a is the symbol to an object, and b is the symbol to another
different object then said a is not equal to b, and expressed by a 6= b.
(ii) 17 = 7 + 3 + 7.
22
(iii) π 6= 7
.
(i) a = a.
(ii) If a = b then b = a.
1.9 Sentences
Depending on some reliable sources in literature (Eves and Newsom,
1958; Stoll, 1979; Stoll, 1960; Patrick, 1999; Wilder et al., 2012; Zulauf,
1969b; Zulauf, 1969a), we can define a sentence as follows;
1.9.1 Statements
Definition 1.12 A statement is an informative sentence, and could
be true or false. It does not be true and false at the same time(Eves
and Newsom, 1958; Stoll, 1979; Stoll, 1960; Patrick, 1999; Wilder et al.,
2012; Zulauf, 1969b; Zulauf, 1969a).
Note: The statements can be denoted by symbols like; p, q, r, ....
(1) Truth or false of the statement called the value of the statement.
(2) Paired with the true statement the symbol T, while paired with
the false statement the symbol F.
(iii) Where are you going? This is the interrogative sentence not
statement.
1.9.2 Variables
Depending on the researchers in the literature (Eves and Newsom,
1958; Stoll, 1979; Stoll, 1960; Patrick, 1999; Wilder et al., 2012; Zulauf,
1969b), the variable can defined as follows;
1.9.3 Parameters
Thomas et al. (2010) defined the parameter as follows;
(i) The alternative selection for the variable must be in the universal
set in which P (x) has been defined on it.
(ii) TP ⊆ U, ∀ TP .
1.10 Exercises
Solve the following questions:
Q1: Identify which of the following sentences is statement, and
mention the reason.
(i) x < 2.
10 Foundations of Mathematics
(ii) x + y = y + x.
(vi) If x, y ∈ R then x + y = y + x.
(v) x2 + 1 = 0 and U = R.
Q4: Find the value of the truth from what comes where x ∈ R and
f is a real valued function.
(i) ∀x, x2 = 0.
(iii) If x = 0 ∨ x = 1 then x2 = x.
(iv) ∀a ∈ N, a2 = a.
(v) ∃a ∈ N, a2 = a.
(vii) ∃b ∈ Q, b < 2.
Mathematical Logic 11
1.11.1 Negation
Definition 1.17 Let P be a statement, the statement not P is a
negation of it and denoted by ∼ P (Cauman, 1998).
Example: P : Mathematics is a Language of Science. The ∼ P :
Mathematics is not a Language of Science.
The first column in the table is the truth value of P while the second
column is the truth value of ∼ P .
(ii) P : a ∈ A then ∼ P : a 6= A.
Note: ∼∼ P = P .
12 Foundations of Mathematics
Note: p ∧ q = q ∧ p.
Mathematical Logic 13
√
(c) The statement 5 > 20 ∨ x2 = |x| is a true statement ∀x ∈
R.
(d) The statement π > 0 ∨ 3 + 4 = 7 is a true statement.
Note: p ∨ q = q ∨ p.
14 Foundations of Mathematics
(a) p → q.
(b) If p then q.
(c) p lead to q. Or, p requires q.
(d) q if p (p only if q).
(e) p is sufficient condition to q.
(f) q is necessary condition to p.
(g) q is concluding from p.
(viii) p ↔ q it means p → q ∧ q → p.
1.12 Exercises
Answer the following questions:
Q1: Find a truth value of;
1
(i) e ∈ Q ∧ lim = 1.
x→∞ n
√
(ii) 9 6= 4 ∧ x2 = |x| , ∀x ∈ R.
(iii) π ∈ Q ∨ R.
(iii) ∼ (4 ≤ x).
(iv) ∼ (y 3 ≥ 2 + x).
√
(v) ∼ ( x2 = |x|).
Q4: Write the following sentences in the form of (if p then q) and show
the hypothesis and conclusion.
18 Foundations of Mathematics
1.14 Exercises
Solve the following questions:
Q1: Write the truth table for the following statements;
(i) ∼ p ∨ q.
(ii) p →∼ q.
(iii) (p ∧ q) → (p ∨ q).
(i) p ≡ p.
Mathematical Logic 21
(ii) (p ↔ q) ≡ (p → q) ∧ (q → p).
(iii) p ∨ p ≡ p and p ∧ p ≡ p.
1.15.1 Tautology
Definition 1.23 If a compound statement is true regardless of the
truth value of its components, it is called the tautology (Elliott, 2009;
Stoll, 1979).
Tautology held the following two laws;
(i) Law of the excluded middle.
(1) p ∨ ∼ p, as illustrated in Table 1.13.
(2) Let P, Q be statements, then P ≡ Q if and only if P ↔ Q is
tautology.
(ii) Law of syllogism.
Let P, Q, R be statements. The statement ((P → Q) ∧ (Q →
R)) → (P → R) is tautology and it called law of syllogism. As
described in Table 1.14.
0
Note that the eighth column contains of T s only.
22 Foundations of Mathematics
1.15.2 Contradiction
Definition 1.24 If a compound statement is false, regardless of the
truth value of its components, it is called the contradiction(Elliott,
2009; Stoll, 1979).
(i) P ∧ I ≡ P .
(ii) P ∧ 0 ≡ 0.
(iii) P ∨ I ≡ I.
(iv) P ∨ 0 ≡ P .
Let us clarify the first and third case by truth table, and leave the
second and fourth case as exercise to the reader, as shown in Tables
(1.17, 1.18).
1.16 Exercises
Solve the following questions:
Q1: Which of the following statements is tautology?
(i) (P ∧ (P → Q)) → Q.
(ii) ∼ (P ∧ Q) ↔ (∼ P ∨ ∼ Q).
(iii) (P → Q) ↔ (P ∧ ∼ Q).
(iv) (P → Q) → (Q → P ).
(i) p ∨ p ≡ p.
(ii) p ∧ p ≡ p.
(iii) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r).
(iv) p ∧ q ≡ q ∧ p.
(v) ∼ (∼ p) ≡ p.
(vi) ∼ (p ∨ q) ≡∼ p∧ ∼ q.
(ix) (p →∼ q) ≡ q →∼ p.
Proof
1.18 Exercises
Solve the following questions:
(i) Show by an example that P ⇒ Q does not mean Q ⇒ P .
(a) P ∨ P ≡ P .
(b) P ∧ P ≡ P .
(a) (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R).
Mathematical Logic 27
(b) (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R).
(a) P ∨ Q ≡ Q ∨ P .
(b) P ∧ Q ≡ Q ∧ P .
(a) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).
(b) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R).
(a) P ∨ 0 ≡ P .
(b) P ∧ I ≡ P .
(c) P ∨ I ≡ P .
(d) P ∧ 0 ≡ 0.
(a) P ∨ ∼ P ≡ I.
(b) P ∧ ∼ P ≡ 0.
(c) ∼ (∼ P ) ≡ P .
(d) ∼ I ≡ 0, ∼ 0 ≡ I.
(a) ∼ (P ∧ Q) ≡∼ P ∨ ∼ Q.
(b) ∼ (P ∨ Q) ≡∼ P ∧ ∼ Q.
Now, we will prove the distributive law, and leave others as an exercise
to the reader, as described in Table 1.19. Thus, P ∧(Q∨R) ≡ (P ∧Q)∨
(P ∧ R). By using these laws, we can often dispense of truth tables.
1.20 Exercises
Solve the following questions:
Q1: Prove that
(i) ∼ (p → q) ≡ p ∧ ∼ q.
(ii) ∼ (p → q) ≡ p →∼ q.
Q2: Simplify the statements
(i) ∼ (∼ p ↔ q).
(ii) ∼ (∼ p → q).
(iii) ∼ (∼ p →∼ q).
(iv) (p ∨ q) ∨ (∼ p ∧ q).
(v) (p ∨ q) ∧ ∼ p
Q3: Show that
Mathematical Logic 29
(i) p → (q ∧ r) ≡ (p → q) ∧ (p → r).
1.21 Quantifiers
The statements and their concepts expressed in wholly or partially.
This section deals with existential quantifier and total quantifier.
(ii) The statement ∃x ∈ A, P (x) is true if and only if its truth set is
not empty. Or TP 6= φ.
(i) ∀x ∈ A, ∃y ∈ A, x + y = 0 is true.
(ii) ∃y ∈ A, ∀x ∈ A, x + y = 0 is false.
Solution ∼ (∃x ∈ R, ∀y ∈ R, x + y = y)
≡ ∀x ∈ R, ∼ (∀y ∈ R, x + y = y)
≡ ∀x ∈ R, ∃y ∈ R, ∼ (x + y = y)
≡ ∀x ∈ R, ∃y ∈ R, x + y 6= y
1.22 Exercises
Solve the following questions:
(i) Express the following statements by using logical symbols
(iii) Is the following statement true?: ∀x∃y, p(x, y) → x∃y∀x, p(x, y).
1.24 Exercises
Solve the following questions:
Q1: Find the set of premises, such that the argument will be valid,
and each premises is necessary to the conclusion: S1 : The clever
student his average is excellent. S2 : Who he average is excellent will
be a master candidate. S3 : Ali is excellence. S :.... .
Q2: Are the following arguments valid?
(i) p → q, ∼ p `∼ q.
(ii) p ↔ q, q ` p.
(ii) Contrapositive.
It is possible to prove that P → Q by its contrapositive, whereas
∼ Q →∼ P , because P → Q ≡∼ Q →∼ P .
(i) P ↔ Q ≡ (P → Q) ∧ (Q → P ).
First, we prove that P → Q, and then we have to prove Q → P .
(ii) Contrapositive (∼ Q →∼ P ).
Solution
(i) a = 0 → ab = 0. Suppose that, a = 0 then ab = 0.b = 0.
(ii) b = 0 → ab = 0. Suppose that, b = 0 then ab = a.0 = 0.
(ii) ∼ (P → Q) ≡∼ (∼ P ∨ Q) ≡ P ∧ ∼ Q.
(iii) From the equivalence (i) and (ii), we suppose that P is true and
∼ Q is true. Then we will try to get contradiction, and then
prove that the ∼ (P → Q) is false. Or, (P → Q) is true.
Solution
1.26 Exercises
Solve the following questions:
Q1: Prove that all sentence of the kind of ∀x, P (x) → ∃x, P (x) is
true.
Mathematical Logic 39
Q2: Show why the statement ∀x, P (x) → ∃x, P (x) is true, when
∀x, P (x) is false.
Q3: Prove that the statement of the kind of ∃y∀x, P (x, y) →
∀x∃y, P (x, y) is true.
Q4: Give a direct proof using the rule of conditional proof of the
following questions;
Q14: Prove that the truth of [∀x, (x) ∨ ∀x, Q(x)] → [∀x, P (x) ∨
Q(x)].
Q15: Prove that if x rational number, and y is irrational number,
then x + y is irrational number.
Q16: Prove that if f (x) = f (x + α), ∀α > 0, then f must be
constant mapping. √
Q17: Prove that √3 is irrational
√ number.
Q18: Prove that x < x + 2, ∀x > 0.
Q19: Prove that ∀x > 0, x + x1 ≥ 2,.
2
Algebra of Sets
2.1 Introduction
hen we deal with the system of numbers, we will use regular
W calculations, like additions and multiplications. But, when
dealing with sets, the similar operations like union (∪) and intersection
(∩) can be used.
Using these operations on sets generates the concept of the algebra
of sets. The algebra of sets is similar of normal algebra. But broader
and more complex in terms of operations, because the operations on
sets give the student the following skills; applications and extensions
of the algebra operations on non-numbers. And Helping the student
discover the relationships between algebra and the other branches of
mathematics.
There are some applications of algebra of sets in the real life fields
which far away from mathematics in the first glance. For example,
the applications in insurance companies that are specialized in a set of
people of a certain ages, or, used by sociologists who care about a set
of human characteristics, qualities, and properties.
The algebra of sets is a type of Boolean algebra. Symbols like,
∨, ∧, ∼ which are operations on statements are just algebra of logic in
the first chapter.
42 Foundations of Mathematics
Proof
(i) To prove A ⊆ A ∪ B, suppose that
x∈A
Now, x ∈ A → x ∈ A ∨ x ∈ B
→x∈A∪B
Thus, A ⊆ A ∪ B.
And similarly, B ⊆ A ∪ B.
(ii) Let A ⊆ B, and x ∈ A ∪ B
Now, x ∈ A ∪ B → x ∈ A ∨ x ∈ B
x∈B∨x∈B
→x∈B
Thus, A ∪ B ⊆ B
SinceB ⊆ A ∪ B
Thus, A ∪ B = B.
Algebra of Sets 43
Similarly,
Suppose thatA ∪ B = B
From (i), A ⊆ A ∪ B.
Thus, A ⊆ B.
Proof
(ii) A ∪ B = B ∪ A ⇔ (A ∪ B) ⊆ (B ∪ A) ∧ (B ∪ A) ⊆ (A ∪ B).
Letx ∈ A ∪ B,
Now, x ∈ A ∪ B → x ∈ A ∨ x ∈ B
→x∈B∨x∈A
→x∈B∪A
Thus, A ∪ B ⊆ B ∪ A...(1).
Similarly,
Lety ∈ B ∪ A,
Now, y ∈ B ∪ A → y ∈ B ∨ y ∈ B
→y ∈A∨y ∈B
→y ∈A∪B
Thus, B ∪ A ⊆ A ∪ B...(2).
Thus, from (1)&(2), A ∪ B = B ∪ A.
(iii) Based on (i) & (ii), we can easily prove this part of the theorem.
(i) A ∪ φ = A.
Proof
(i) Since φ ⊆ A, ∀A. Thus from Theorem 2.1, we get A ∪ φ = A.
(ii) Since, A ⊆ U, ∀A. Thus from Theorem 2.1, we get A ∪ U = U .
Proof
(i) To prove A ∩ B ⊆ A,
Let x ∈ A ∩ B.
Now , x ∈ A ∩ B → x ∈ A ∧ x ∈ B,
→ x ∈ A,
which means A ∩ B ⊆ A.
Algebra of Sets 45
Similarly, A ∩ B ⊆ B.
(ii) Suppose that A ⊆ B, and x ∈ A.
Now, x ∈ A,
→ x ∈ B,
→ x ∈ A∧ ∈ B
So, x ∈ A → x ∈ A ∧ x ∈ B,
→ x ∈ A ∩ B.
Thus, A ⊆ A ∩ B.
SinceA ∩ B ⊆ A, hence, A ∩ B = A....(1).
Conversely, let A ∩ B = A. Since, A ∩ B ⊆ B, thus A ⊆ B. ...(2).
From (1)& (2), A ⊆ B ↔ A ∩ B = A.
Proof
(i) It is left as an exercise for the reader (Similar to Theorem 2.2 (i)).
(ii) It is left as an exercise for the reader (Similar to Theorem 2.2
(ii)).
(iii) Let x ∈ A ∩ (B ∩ C).
Now, x ∈ A ∩ (B ∩ C) → x ∈ A ∧ x ∈ (B ∩ C)
→ x ∈ A ∧ (x ∈ B ∧ x ∈ C)
→ (x ∈ A ∧ x ∈ B) ∧ x ∈ C)
→ x ∈ (A ∩ B) ∧ x ∈ C)
→ x ∈ (A ∩ B) ∩ C
Thus, A ∩ (B ∩ C) ⊆ (A ∩ B) ∩ C....(1)
Similaly, y ∈ (A ∩ B) ∩ C,
We prove thaty ∈ (A ∩ B) ∩ C → y ∈ A ∩ (B ∩ C)
Thus, (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C)....(2)
From(1)&(2), we get, A ∩ (B ∩ C) = (A ∩ B) ∩ C.
46 Foundations of Mathematics
Proof
(i) Since φ ⊆ A, ∀A, and based on Theorem 2.4, we conclude that
A ∩ φ = φ.
(ii) Since A ⊆ U, ∀A, and based on Theorem (2.4), we conclude that
A ∩ U = A.
The following theorem illustrates the relation between intersection and
union.
Proof
(i) Suppose that x ∈ A ∩ (B ∪ C).
Now, x ∈ A ∩ (B ∪ C) → x ∈ A ∧ x ∈ (B ∪ C)
→ x ∈ A ∧ (x ∈ B ∨ x ∈ C)
→ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)
→ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C)
→ x ∈ (A ∩ B) ∪ (A ∩ C)
Thus, A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∪ C)...(1)
Similarly, suppose that y ∈ (A ∩ B) ∪ (A ∩ C)
Now, y ∈ (A ∩ B) ∪ (A ∩ C) → y ∈ (A ∩ B) ∨ y ∈ (A ∩ C)
→ (y ∈ A ∧ y ∈ B) ∨ (y ∈ A ∧ y ∈ C)
→ y ∈ A ∧ (y ∈ B ∨ y ∈ C)
→ y ∈ A ∧ y ∈ (B ∪ C)
→ y ∈ A ∩ (B ∪ C)
Thus, (A ∩ B) ∪ (A ∪ C) ⊆ A ∩ (B ∪ C)...(2)
From(1)&(2), we concluting thatA ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Algebra of Sets 47
(ii) Proof of this branch has been left as an exercise to the reader.
2.3 Exercises
Solve the following questions:
Q1: If A ∪ B = A, ∀A, prove that B = φ.
Q2: Describe the following set;
{x ∈ R|x2 > 2} ∩ {x ∈ R| |x − 2| < |x + 3|}.
Q3: Let A, B be nonempty sets, prove that φ ⊆ (A ∩ B) ⊆ (A ∪ B).
Q4: Let A, B, C be nonempty sets, prove that
(A ∩ B) ∪ C = A ∩ (B ∪ C) ↔ C ⊆ A.
Q5: Let A, B be nonempty sets, prove that
(1). A ∪ (A ∩ B) = A. (2). A ∩ (A ∪ B) = A.
Q6: Let A, B, C be nonempty sets, prove that
A ∩ C = φ ⇒ A ∩ (B ∪ C) = A ∩ B.
Q7: Let A, B be sets, prove that
A ∪ B = φ ⇒ A = φ ∧ B = φ.
Q8: Let A, B, C be sets, when will be it A ∪ C = B ∪ C?
Q9: If n(A) represents the number of A’s elements, prove that
n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
Q10: If C ⊆ A, C ⊆ B, prove that C ⊆ A ∩ B.
Q11: Let A0 , B 0 be any two arbitrary sets. If A ⊆ A0 , B ⊆ B 0 then
A ∩ B ⊆ A0 ∩ B 0 .
Definition 2.5 Let A, B be sets, the set that its elements belong to
A, and not belong to B is called the difference of two sets A, B. And
denoted by A − B. In the other statement, A − B = A ∩ B c . Or,
A − B = {x|x ∈ A ∧ x ∈/ B}(Givant and Halmos, 2008; Dwinger, 1971;
Drake, 1980; Mustafa et al., 1980; Wilder et al., 2012).
Note: If A = U , then: A − B = B c .
Thus, A − B ⊆ B c − Ac ...(1).
Similarly, we can prove that B c − Ac ⊆ A − B...(2).
From(1)&(2), we get, A − B = B c − Ac .
(i) U c = φ.
(ii) φc = U .
Algebra of Sets 49
(iii) A ∩ Ac = φ.
(iv) A ∪ Ac = U .
Proof
(i) According to the definition U c = {x|x ∈ U ∧ x ∈
/ U }. And this is
contradiction, because there is any element like x belongs to U ,
and in the same time does not exists in U . Thus, U c = φ.
(ii) This part is left as an exercise for the reader.
(iii) According to the definition A∩Ac = {x|x ∈ A ∧ x ∈ / A}. And this
is contradiction, because is not exists any element like x belongs
to A, and in the same time does not exists in A. Thus, A∩Ac = φ.
(iv) This part is left as an exercise for the reader.
Proof
(i) Let x ∈ (A ∪ B)c .
Now, x ∈ (A ∪ B)c → x ∈ / (A ∪ B)
→x∈ / A∧x∈ /B
→ x ∈ Ac ∧ x ∈ B c
→ x ∈ (Ac ∩ B c )
Thus, (A ∪ B)c ⊆ (Ac ∩ B c )...(1).
Conversely, y ∈ Ac ∩ B c .
Now, y ∈ Ac ∩ B c → y ∈ Ac ∧ y ∈ B c
→y∈ / A∧y ∈ /B
→y∈ / A ∪ B → y ∈ (A ∪ B)c .
Thus, Ac ∩ B c ⊂ (A ∪ B)c ...(2).
From(1)&(2), we get that(A ∪ B)c = Ac ∩ B c .
(ii) This part is left, as an exercise for the reader.
50 Foundations of Mathematics
Example 2.7 Let A = {1, 5, 9, 11, 13}. B = {2, 5, 11, 18, 19}. Then
A 4 B = {1, 9, 13, 2, 18, 19}.
The following theorem describes the properties of the symmetric
difference.
(i) A 4 φ = A.
(ii) A 4 B = φ ↔ A = B.
Proof
(i) A ∪ (A ∩ B) = A.
(ii) A ∩ (A ∪ B) = A.
(iii) A ∩ (Ac ∪ B) = A ∩ B.
(iv) A ∪ (A ∪ B c )c = A ∪ B.
Proof
(iii) A ∩ (Ac ∪ B) = (A ∩ Ac ) ∪ (A ∩ B) = φ ∪ (A ∩ B) = A ∩ B.
2.6 Exercises
Solve the following questions:
Q1: Let P, Q be sets, prove the following:
(i) P ⊆ Q ↔ P ∩ Qc = φ.
(ii) P ⊆ Q ↔ P c ∪ Q = U .
(iii) P ⊆ Q ↔ (P ∩ Qc ) ⊂ P c .
(iv) P ⊆ Q ↔ (P ∩ Qc ) ⊂ Q.
(i) A 4 φ = A.
(ii) A 4 B = B 4 A.
(iii) A 4 (B 4 C) = (A 4 B) 4 C.
52 Foundations of Mathematics
(iv) A 4 (B 4 C) = (A ∩ B) 4 (A ∩ C).
(v) A 4 A = φ.
(vi) A 4 C = B 4 C → A = B.
(i) A ∩ (B − C) = (A ∩ B) − C.
(ii) (A ∪ B) − C = (A − C) ∪ (B − C).
(iii) A − (B ∪ C) = (A − B) ∩ (A − C).
(iv) A − (B ∩ C) = (A − B) ∪ (A − C).
(vi) (A ∪ C) 4 (B ∪ C) = (A 4 B) − C.
(ii) Let A = {a, b, c}. The subsets of A are making the family of
sets as follows: {φ, {a} , {b} , {c} , {a, b} , {a, c} , {b, c} , A}. Each
element is subset of A.
(a) ak+1 ∈
/ W , in this case W ⊆ B.
(b) ak+1 ∈ W , or W = D ∪ {ak+1 }, where D ⊆ B. i.e. W ⊆
A → W ⊆ B ∨ W = D ∪ {ak+1 } , D ⊆ B.
∴ n(P (A)) = 2k + 2k = 2.2k = 2k+1 . Thus, P (k + 1) is true.
∴ P (m) is true ∀m ∈ N.
Proof
Now, X ∈ P (A) → X ⊆ A
→X⊆B
→ X ∈ P (B)
Or, X ∈ P (A) → X ∈ P (B)
∴ P (A) ⊆ P (B)
Conversully, suppose that P (A) ⊆ P (B), we have to prove A ⊆ B
Suppose that a ∈ A
∴ {a} ∈ A
Based on the difinition of the power set {a} ∈ A
→ {a} ∈ B
∴ {a} ⊆ B. Or, a ∈ B
Thus, we conclude that a ∈ A → a ∈ B
→ A ⊆ B.
(ii) Let i ∈ N and let Ai = (i, ∞). Then {Ai }i∈I is an infinite index
set, and the indexed set N is infinite set.
Note that ... ⊂ An ⊂ An−1 ⊂ ... ⊂ A3 ⊂ A2 ⊂ A1 ⊂ A0 , where
A0 = (0, ∞), A1 = (1, ∞), A2 = (2, ∞), ....
Proof
S
(i) Suppose that Ai ⊆ B ∀i ∈ I, and x ∈ Ai .
i∈I
∴ j ∈ I 3 x ∈ Aj
since Aj ⊆ B,
∴x∈B
Or, Ai ⊆ B ∀i ∈ I.
(ii) It is left as an exercise for the reader.
Ai )c = Aci .
T S
(ii) (
i∈I i∈I
Proof
Ai )c .
S
(i) Suppose that x ∈ (
i∈I
c
S S
Now x ∈ ( Ai ) → x ∈
/ Ai
i∈I i∈I
→x∈ / Ai , ∀i ∈ I
→ x ∈ Aci ,T∀i ∈ I
→ x ∈ Aci
i∈I
∴ ( Ai )c ⊆ Aci ...(1)
S T
i∈I i∈I
Aci
T
Conversaly, suppose that y ∈
i∈I
∴ y ∈ Aci
Since y ∈ Aci → yS∈ / Ai , ∀i ∈ I
→y∈ / Ai
i∈I
→ y ∈ ( Ai )c
S
Si∈I
∴ Aci ⊆ ( Ai )c ...(2).
T
i∈I i∈I
From (1)&(2)( Ai )c = Aci .
S T
i∈I i∈I
58 Foundations of Mathematics
Proof
S T S
(i) Suppose that x ∈ ( Ai ) ( Bj ).
i∈I j∈J
S T S
Now x ∈ ( Ai ) ( Bj )(∃h ∈ I 3 x ∈ Ah ) ∧ (∃k ∈ J 3 x ∈ Bk )
i∈I j∈J T
→ ∃(h, k) ∈ I × SJ 3 x T ∈ Ah Bk
→x∈ (Ai Bj )
S T S (i,j)∈I×JS T
∴ ( Ai ) ( Bj ) ⊆ (Ai Bj )...(1).
i∈I j∈J (i,j)∈I×J
S T
Conversely, suppose that y ∈ (Ai Bj )
(i,j)∈I×J
T
∴ ∃(s, t) ∈ I × J 3 y ∈ As Bt
∴ (∃s ∈ I ∧ t ∈ J) 3 (y ∈ As ∧ y ∈ Bt )
Or (∃s ∈ I 3 y ∈ S As ) ∧ (∃t S∈ J 3 y ∈ Bt )
∴ y ∈ Ai ∧ y ∈ Bj
i∈I S j∈J
T
→y∈ (Ai Bj )
S T (i,j)∈I×JS T S
∴ (Ai Bj ) ⊆ ( Ai ) ( Bj )...(2).
(i,j)∈I×J
S T Si∈I j∈J
S T
From (1)&(2) ( Ai ) ( Bj ) = (Ai Bj ).
i∈I j∈J (i,j)∈I×J
2.8 Exercises
Solve the following questions:
Q1: Let {Ai }i∈I , {Bj }j∈J be two index family of sets. Prove
Algebra of Sets 59
S S S T
(i) ( Ai ) − ( Bj ) = ( (Ai − Bj )).
i∈I j∈J i∈I j∈J
T T T S
(ii) ( Ai ) − ( Bj ) = ( (Ai − Bj )).
i∈I j∈J i∈I j∈J
(i) A ∪ B.
(ii) (A ∪ B)0 .
(iii) A0 .
(iv) B 0 .
60 Foundations of Mathematics
(v) A0 ∩ B 0 .
(vi) A ∩ B.
(vii) (A ∩ B)0 .
(viii) A0 ∪ B 0 .
3.1 Introduction
ocial relation, in social science, is any social interaction between
S two or more individuals. International relation is studying
interconnections of politics, economics and law on a global level.
Public relation is managing the spread of information to the public.
Interpersonal relationship is association or acquaintance between two
or more people. . . etc.
In mathematics, there are many kinds of relations like, binary
relation, or dyadic relation or two place relation. Heterogeneous
relation is relations between distinct sets, relations with a finite number
of places. And relation algebra is an algebraic structure inspired by
algebraic logic.
Mathematical science deals with a special kinds of sets called
relations. Let the set A consists of two things x, y. In many cases
or situations it is necessary to deal with these two things. For example,
Before dealing with the definition of relation and what related it,
we have to know what is ordered pairs and Cartesian product? The
next section provides logically convincing answers.
Now, a ∈ A → ∀b ∈ B 3 (a, b) ∈ A × B
→ (a, b) ∈ B × A
∴ (a, b) ∈ B × A → a ∈ A ∧ b ∈ B
∵a∈A→a∈B
∴A⊆B
Through the same method, we can prove that B ⊆ A
∴ A = B...(2).
From, (1)&(2), A × B = B × A ↔ A = B.
Proof
T
(i) Let, (x, y) ∈ A × (B C)
T T
Now, (x, y) ∈ A × (B C) → x ∈ A ∧ y ∈ (B C)
→ x ∈ A ∧ (y ∈ B ∧ y ∈ C)
→ (x ∈ A ∧ y ∈ B) ∧ (x ∈ A ∧ y ∈ C)
→ (x, y) ∈ (A × B) ∧T (x, y) ∈ (A × C)
→ (x, y) ∈ (A × B) (A × C)...(1). T
Conversely, suppose that (a, b) ∈T(A × B) (A × C)
Now, (a, b) ∈ (A × B) (A × C)
→ (a, b) ∈ (A × B) ∧ (a, b) ∈ (A × C)
→ (a ∈ A ∧ b ∈ B) ∧ (a ∈ A ∧ b ∈ C)
→ a ∈ A ∧ (b ∈ B ∧ T b ∈ C)
→ a ∈ A ∧ (b ∈ B T C)
→T(a, b) ∈ A × (B C)T
∴ (A × B) (A × T C) ⊆ A × (B C)...(2).
T
From (1)&(2)A × (B C) = (A × B) (A × C).
T
(iii) Suppose that (x, y) ∈ (A × B) (C × D).
T
Now, (x, y) ∈ (A × B) (C × D)
→ (x, y) ∈ (A × B) ∧ (x, y) ∈ (C × D)
→ (x ∈ A ∧ y ∈ B) ∧ (x ∈ C ∧ y ∈ D)
→ (x ∈ A ∧ x T ∈ C) ∧ (y ∈ B T ∧ y ∈ D)
→ x ∈ (A C)T∧ y ∈ (B T D)
→T(x, y) ∈ (A C)T× (B D)T
→ (A × B) (C × D) ⊆ (A C) ×T(B D)...(1). T
Conversely, suppose that (a,
T b) ∈ (A TC) × (B D)
∈ (A C) × (B
Now, (a, b) T T D)
→ a ∈ (A C) ∧ b ∈ (B D)
→ (a ∈ A ∧ a ∈ C) ∧ (b ∈ B ∧ b ∈ D)
→ (a ∈ A ∧ b ∈ B) ∧ (a ∈ C ∧ b ∈ D)
→ (a, b) ∈ (A × B) ∧ (a,Tb) ∈ (C × D)
T → (a, b)T∈ (A × B) (C T × D)
→ (A C) ×T(B D) ⊆T(A × B) (C ×TD)...(2)
From, (1)&(2)(A C) × (B D) = (A × B) (C × D).
y ..............
.......
....
...
...
...
...
...
...
...
...
d ... ....................................................................................................
... ...
... ....
... ... ...
... ... ...
... ... ...
... ... ...
... ...
...
.
...
... A×B ...
B ...
...
...
.
...
...
...
... ... ...
... ... ...
... ...................................................................................................
.
c ...
...
...
...
...
..
.............................................................................................................................................................................................................................
...
..
...
a A b x
y ...............
.......
..
...
...
...
d 2 .....
....................................................................................................
...
...
..
...
.... ... ...
... ... ...
... ... ...
... ... ...
Dd 1 ... ... ......................................................................................................
...
...
...
...
.
.
.
.
...
...
... ... ... .
.
. ...
... . ...
...
...
... R ...
.
...
.
.
.
.
. ...
... .
... ... .
....................................
. .
Bc 2 ... ...
...
...
...
.
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
.
.
.
.
.
.
.
.
...
... ... ....
... ... ...
... ... ..
... .....................................................................................................
c 1 ....
...
..
...
...
..
...........................................................................................................................................................................................................................
a .... a
...
..
1 2 b 1 b x 2
A C
Qn
Example 3.3 Let us consider Ai = R; 1 ≤ i ≤ n, then: i=1 Ai =
n
{(a1 , a2 , ..., an )|ai ∈ R, 1 ≤ i ≤ n} = R .
3.3 Exercises
Solve the following questions:
Q1: If (a − b, 2a − 7b) = (a + b, 3a + 5b) then find a value of a, b.
Q2: If (u, v, w) = (x, y, z) then prove that u = x, v = y, w = z.
Q3: IfSA = {1, 3, 5, 7} , B = {−2,
S −9, 6} , C = {x, S y, z}, find
S each
of: (1) (A B) × C. (2) (A × C) (B × C). (3) (A B) × (B C).
Q4: Let A, B, C, D be sets. Prove the following statements:
T T T
(i) (A × A) (B × C) = (A B) × (A C).
S
(ii) (A × B) − (C × C) = [(A − C) × B] [A × (B − C)].
S
(iii) (A × A) − (B × C) = [(A − B) × A] [A × (A − C)].
(iv) A × (B − D) = (A × B) − (A × D).
T T
(v) (A × B) (C × D) = (A × D) (C × B).
S
SQ8: Give an
S example for A, B, C to show that A (B × C) 6=
(A B) × (A C).
Q9: If A × A = B × B then A = B.
Q10: If A × Y = A × Z, A 6= φ then B = C.
Q11: Let A, C 6= φ and A ⊆ B ∧ C ⊆ D ↔ A × C ⊆ B × D.
Q12: Consider a nonempty sets A, B, C, D. Prove that A × B =
C × D ↔ A = C ∧ B = D.
(i) Write its elements (ordered pairs, ordered triple, ..., n−tuple)
between braces. This method called tabulation method (See
1.5.1(ii)).
(ii) Rule method or, writing the relation by its own property.
As R = {(x, y)|x ∈ A ∧ y ∈ B, P (x, y)}, where P (x, y) is the
characteristic of R (See 1.5.1(iii)).
Note: If (x, y) ∈ R, then we will express in this membership by xRy,
and read x is related with y via the relation R. And if (x, y) ∈
/ R, it
can be written x 6R y, and read x does not related with y.
Note: The study for this book will focus on the binary relation.
Example 3.5 Let A the set of all straight lines in the plane, then
70 Foundations of Mathematics
(i) Union
S of the relations
R Q = {(x, y) ∈ A × B|(x, y) ∈ R ∨ (x, y) ∈ Q} is a relation
from A to B.
(ii) Intersection
T of the relations
R Q = {(x, y) ∈ A × B|(x, y) ∈ R ∧ (x, y) ∈ Q} is a relation
from A to B.
(ii) If A = Z.
The IA = {(x, y) ∈ Z × Z|x = y}
= {..., (−2, −2), (−1, −1), (0, 0), (1, 1), (2, 2), ...}.
(iii) If A = N.
The IA = {(x, y) ∈ N × N|x = y} = {(0, 0), (1, 1), (2, 2), ...}.
Example 3.10 (i) Let A = {7, 11, 13} , B = {0, 2, 4}, and let R =
{(7, 0), (7, 0), (13, 2)} be a relation from A to B. Then, dom R =
{7, 13}, ran R = {0, 2}.
Relations 73
Proof
(iv) If R ⊆ S then
(a) T ◦ R ⊆ T ◦ S.
(b) R ◦ T ⊆ S ◦ T : The composition of the relations keeps the
containment of relations.
T = φ ↔ (T ◦ R−1 )
T T
(v) (S ◦ R) S = φ.
Proof
3.7 Exercises
Answer the following questions:
Q1: Given X = {a, b, c, d} , Y = {1, 2, 0}. Write down all possible
relations from
(i) X to Y .
(ii) Y to X.
(i) (S T )−1 = S −1 T −1 .
T T
(ii) (S T )−1 = S −1 T −1 .
S S
Relations 77
(i) G ⊆ H ∧ J ⊆ K → G ◦ J ⊆ H ◦ K.
(ii) G ⊆ H ↔ G−1 ⊆ H −1 .
(ii) Let A = N
(iii) Let X be any arbitrary set, and P (X) be a power set of X, then
and Newsom, 1958; Quine, 1969; Mustafa et al., 1980; Hafstrom, 2013;
Nešetřil, 1972).
Example 3.15 (i) Consider A = N, and R is a relation on A
in which R = {(x, y)|x + y = 5, x, y ∈ A}. R is a symmetric
relation on A because x + y = 5 ⇒ y + x = 5. Or, R =
{(0, 5), (5, 0), (1, 4), (4, 1), (2, 3), (3, 2)}.
(ii) Consider A = N, and R is a relation on A in which R =
{(x, y)|x is a divisor of y}. R is not symmetric as 3R9 does not
imply 9R3 for 3 divides 9, but 9 does not divide 3.
Note: From the first part of the Example 3.15, R−1 =
{(5, 0), (0, 5), (4, 1), (1, 4), (3, 2), (2, 3)} = R. Thus R is symmetric if and
only if it equals to its inverse as empathized in the following theorem.
Theorem 3.9 Let R be a relation on A, R is symmetric relation on A
if and only if R = R−1 .
T
Proof Suppose T that (x, y) ∈ ν σ.
Now (x, y) ∈ ν σ → (x, y) ∈ ν ∧ (x, y) ∈ σ,
∵ each of ν, σ are a symmetric, T
∈ ν ∧ (y, x) ∈ σ → (y, x) ∈ ν σ.
∴ (y, x) T
Thus, ν σ is a symmetric relation.
3.9 Exercises
Answer the following questions:
Q1: Let η be a relation on A, then, prove that
(ii) R2 ⊆ R2 ◦ R1 .
Q7: Consider ϕ S is a reflexive relation on A, and χ be any relation
on A. Prove that ϕ χ is a reflexive.
Q8: Consider ϕ, χ be relations on the set A. Show that the following
statements are false;
S
(i) If ϕ, χ are anti-symmetric relations, then ϕ χ is anti-symmetric
too.
S
(ii) If ϕ, χ are transitive relations, then ϕ χ is transitive too.
(a) ∀A ∈ P (X), A = A.
Or, ∀A ∈ P (X), (A, A) ∈ ψ. Thus, ψ is a reflexive relation.
(b) ∀A, B ∈ P (X), A = B → B = A.
Or, ∀A, B ∈ P (X), (A, B) ∈ ψ → (B, A) ∈ ψ. Thus, ψ is a
symmetric relation.
(c) ∀A, B, C ∈ P (X), A = B ∧ B = C → A = C.
Or, ∀A, B, C ∈ P (X), (A, B) ∈ ψ ∧ (B, C) ∈ ψ → (A, C) ∈
ψ. Thus, ψ is a transitive relation. Based on the definition,
ψ is the equivalence relation.
Proof
(ii) If ((a, b), (c, d)) ∈ A, and if ((a, b), (c, d)) ∈ Υ → a + b = c + d →
c + d = a + b. Thus, (c, d), (a, b) ∈ Υ, and so on, Υ is symmetric
relation.
(iii) If (a, b), (c, d), (e, f ) ∈ A, ((a, b), (c, d)) ∈ Υ ∧ ((c, d), (e, f )) ∈ Υ,
then a + b = c + d ∧ c + d = e + f → a + b = e + f .
Thus, ((a, b), (e, f )) ∈ Υ, and so on Υ is transitive relation. From
(i), (ii), and (iii), we conclude that Υ is the equivalence relation
on A.
T
Theorem 3.11 If R1 , R2 are equivalence relations on A, then R1 R2
is an equivalence relation on A.
86 Foundations of Mathematics
Proof
(i) a ∈ [a].
Proof
T
Thus, x ∈ [a] [b] → x ∈ [a] ∧ x ∈ [b].
→ (x, a) ∈ R ∧ (x, b) ∈ R.
→ (x, b) ∈ R ∧ (x, a) ∈ R.
Since R is symmetric, hence (b, x) ∈ R ∧ (x, a) ∈ R.
Since R is transitive, so that (b, x) ∈ R ∧ (x, a) ∈ R → (b, a) ∈ R.
Since R is symmetric, that why (a, b) ∈ R.
From (iii), (a, b) ∈ R → [a] = [b].
3.10.4 Partition
Definition 3.20 Let {Ai }i∈I family of sets of the nonempty set A.
The {Ai }i∈I it said to be partition for A, if:
T
(i) ∀i, j ∈ I, Ai Aj = φ ∨ Ai = Aj .
S
(ii) A = Ai (Halmos, 2017b; Lucas, 1990; Brualdi, 1992).
i∈I
S
To prove, Aa ⊆ A, we note that Aa ⊆ A, ∀a ∈ A.
a∈A S
From the Theorem 2.15 Aa ⊆ A ...(2).
S a∈A
From (1)& (2), A = Aa .
a∈A
Thus, from (i)& (ii) we conclude that, {Aa }a∈A is a partition of A.
Thus, R is transitive.
From, (i)& (ii)& (iii), R is equivalence relation.
Now, we are going to prove each subset Ai within the partition {Ai }i∈I
is an equivalence class with respect to the relation R.
∵ Ai 6= φ, ∀i ∈ I,
∴ Ai is contains at least one element like x, and Ax will be equivalence
class with respect to the relation R.
Let us, claim that Ai = Ax . To prove the claim,
Suppose that y ∈ Ax .
From the definition of the equivalence class, we have (y, x) ∈ R.
∵ x ∈ Ai ,
∴ from the definition of R, also, y ∈ Ai .
Or, y ∈ Ax → y ∈ Ai .
∴ z ∈ Ai ∧ x ∈ Ai → (z, x) ∈ R.
By the same way, suppose that z ∈ Ai .
That why, z ∈ Ai ∧ x ∈ Ai → (z, x) ∈ R.
And from the definition of the equivalence class, we conclude that,
z ∈ Ax .
∴ z ∈ Ai → z ∈ Ax .
Or, Ai ⊆ Ax .
Thus, Ai = Ax .
Example 3.24 Let A = {1, 3, 5, 7, 9} , X = {1, 3} , Y = {5, 7} , Z =
{9}. According to the definition, there exists, equivalence
classes,
S the partition; {X, Y, Z}, in respect to the relation:
IA {(1, 3), (3, 1), (5, 7), (7, 5)}.
We can easily prove that:
(i) The set X, Y, Z is a partition to A.
(ii) The relation R is equivalence on A. And the equivalence classes
are; [1] = [3], [5] = [7], [9]. Note that; X = [1] = [3], Y = [5], [7],
Z = [9].
Example 3.25 Let, A = Z, X = Ze ), Y = Zo ). The set
X, Y is the partition of A. Now, if we consider the relation R =
{(x, y) ∈ A × A|x − y even number}. R is the equivalence relation on
A, and the equivalence classes are: [0], [1], where X = [0], Y = [1].
92 Foundations of Mathematics
3.11 Exercises
Answer the following questions:
Q1:
T Let Γ is the set of all equivalence relations on the set A. Prove
that Γ is equivalence relation.
Q2: Consider γ1 is the equivalence relation on the set X, and γ2
is the equivalence relation on the set Y . The defined relation χ on the
set X × Y as follows:
(x1 , y1 )χ(x2 , y2 ) ↔ (x1 , y1 ) ∈ γ1 ∧ (x2 , y2 ) ∈ γ2 . Prove that χ is the
equivalence relation on X × Y .
Q3: Let each of H, G is an equivalence relation on A. Prove that
G ◦ H is an equivalence relation on A if and only if G ◦ H = H ◦ G. S
Q4: Let each of H, G is an equivalence relation on A. when G H
will be an equivalence relation on A?
Q5: Let {Ai }i∈I is a partition of the set A, {Bj }j∈J is a partition of
the set B. Prove that {Ai × Bj }(i,j)∈I×J is a partition of the set A × B.
Here we are going to learn some types of order: partial order, strict
order, partially ordered sets, totally ordered sets, and well ordered sets.
∃x ∈ A 3 (a, x) ∈ R ∧ (x, b) ∈ R
∃y ∈ A 3 (b, y) ∈ R ∧ (y, c) ∈ R
(x, b) ∈ R ∧ (b, y) ∈ R → (a, y) ∈ R ◦ R
(a, y) ∈ R(a, y) ∈ R ∧ (y, c) ∈ R → (a, c) ∈ R ◦ R
→ (a, c) ∈ R
∴ (a, b) ∈ R ∧ (b, c) ∈ R → (a, c) ∈ R
∴ R is a transitive relation
From (1), (2)&(3), R is transitive.
The conversely direction of the proof has been left to the reader, as an exercise.
b ...
.
.....
....
......
b
.......... ........
.... ....
.. ....
... ..
... ...
.... ...
.. ...
... ...
... ...
.... ...
.. ...
... ...
... ...
.... ...
.. ...
... ...
... ...
.... ...
.. ...
... ...
... ...
.... ...
.. ...
... ...
a ..
..
.
.
...
...
a b
.. . a ........................................................................................................................................................
12 ....
.......
........
....
....
..
... .
... .....
... ...............
... ......
... ..
.....
. 12
... .....
.....
... .....
.. .....
.....
5 .....
.........
.
.
..................
.
.
......
....
..... .
.....
.....
5
... ..
.
...
.. .....
.. .....
..... ................................................
3 ....
.
.........
. 1 3
....
...
..
... 1 3 5 12
...............................................................................................................................................................................................................................................
1 .
20................... 20 ..............
.. ........
... .
... ...
... ...
..... ...
15
.. ...
... ...
...
...
...
...
• ...
...... 6
.
.... ... ............
.. ... ..
... ... ..
... ... ...
... ... ...
..... ... ...
.. ... ..
... ... ..
... ...
... ...
...
....
. ...
... ...
... ... ....
...
15 ...
...
... ..
.......
• ................................................................................ ..
2 6 2
d
....
.......
..........
...
....
..
...
...
...
...
...
...
a ...
...
.....
.............
........
.
.
..
..
. . . e
............ ................
..
........
..... ..
..
..... . .....
..... .
..
.....
. .....
.
..... ...... .....
.....
..... ..
..
....... .....
.....
..... ..
..
..... .....
.....
..... ..
..
..... .....
.....
..... ..
..
..... .....
.....
..... ..
..
..... .....
.....
..... ..
..
..... .....
..... ..
..
..... .....
..... ....
. .....
.....
b
..... .........
..........
.
..
. .....
.....
.....
.. .....
........ .....
.....
....... .....
... .....
.....
... .....
... .....
.....
... .....
... .....
... .....
.....
... .....
... .....
.....
... .....
... .....
.....
... .....
...
...
..
.... f
...
...
...
...
...
...
....
..
...
...
..
Figure 3.7: (A × B, R1 × R2 )
(i) Least element is a minimal element, but the vice versa is not true.
(ii) Each finite partial ordered set has at least maximal element and
minimal element.
x is un upper bound to B.
x is a lower bound to B.
Example 3.45 Let R = {(x, y) ∈ R × R|x ≤ y}, and let B = [−1, 5].
Then, supB = 5, inf B = −1.
Notes: Let (A, ≤) be a partial ordered set, and B ⊆ A then:
(ii) b will be upper bound for the set B in (A, ≤) if and only if b is
lower bound for the set B in (A, ≥).
Definition 3.35 Let (A, R) be a partial ordered set. The set (A, R)
called complete, if and only if each B ⊆ A bounded above. Or, supB
is existed. This, equivalency mean, each B ⊆ A is bounded below.
(Abramsky et al., 1992; Burris and Sankappanavar, 2006; Markowsky,
1976)
Example 3.48 (1) The binary (Z, ≤) is a totally ordered set, because
it satisfies; (i) (Z, ≤) is partially ordered set, and (ii) each binary
elements in it is comparable.
(2) Consider the sets, A = {a|a ∈ N ∧ 1 ≤ a ≤ 9}, B = {2, 4, 8},
R = {(x, y) ∈ A × A|x divisable by y}.
It should be noted that not each binary elements in A are
comparable, while each binary elements are comparable in B.
Thus, the set (A, R) is not totally ordered set, while the set
(B, R/B) is totally ordered set.
Note: All subset of a totally ordered set is a totally ordered set.
Theorem 3.23 Consider the well ordered set A, then for all a ∈ A
except the greatest element immediate successor.
108 Foundations of Mathematics
3.13 Exercises
Solve the following questions:
Q1: Write all possible partial ordered relations on the set A =
{0, 1, 2}, and show that the totally ordered relations.
Q2: Show that if φ can be partially ordered relation?
Q3: Consider δ is a subset of of partial ordered relations on A.
Prove that ∩δ is a partial ordered relation.
Q4: If S is a partial ordered relation on the set X, and A ⊆ X.
Prove that S ∩ (A × A) is a partial ordered relation. And, prove that if
S is totally ordered relation then S ∩ (A × A) is totally ordered relation
on A.
Q5: Let S be a partial ordered relation on X. Prove that S − IX
is a strict order relation.
Q6: Let S be strict order relation on X. Prove that S ∪IX is partial
order relation.
Q7: Give an example on a set X and on a set δ of partial order
relations on X to show that ∪δ is not partial order relation on X.
Q8: Draw Hasse Diagram for the ordered sets (X, S), X =
{a, b, c, d, e}, S = {(a, d), (a, c), (a, b), (a, e), (b, e), (c, e), (d, e)} ∪ IX
110 Foundations of Mathematics
4.1 Introduction
mapping (function) is a relation that uniquely associates
A members of one set with members of another set. A function
from is an object such that every is uniquely associated with an object.
More formally, it is therefore a many-to-one (or sometimes one-to-one)
relation.
Mapping is one of the important basic mathematical concepts. It
enters almost any mathematical discussion, and in all areas of the real
life.
Consider the sets A, B. The mapping from A to B is a rule of
correspondence, such that for all x ∈ A corresponds a unique element
y ∈ B, and denoted by: x → y, where y is called image of x.
The concepts mapping and function are synonyms, the function
from A to B it means mapping from A to B. In other words, mapping
from A on a subset C in B. The set A is called domain of the mapping,
while the se B is called codomain, and C is a range of the mapping.
Mapping ought to be distinguished between f, f (x), the f is the
function from A to B, while f (x) is the element y ∈ B corresponds to
the element x ∈ A. The express y = f (x) is read y is a function of x.
The graph of a function is a mapping from A to B, the graph of
112 Foundations of Mathematics
4.2 Mapping
Definition 4.1 Let each of A, B be a set. The mapping from A to B
is an ordered triple (f, A, B) where f is a subset of A × B provides:
(1) ∀x ∈ A, ∃y ∈ B | (x, y) ∈ f . (2) If (x, y1 ) ∈ f, (x, y2 ) ∈ f → y1 = y2
(Halmos, 2017b; Saunders and Birkhoff, 1967).
In the definition, the second condition is a functional relation. The
expression of the function in the form of f : A → B instead of (f, A, B)
is more convenient. Furthermore, the conditions in the definition can
be combined in a unique condition as; ∀x ∈ A∃! y ∈ B 3 (x, y) ∈ f . x
is called independent variable, and y is called dependent variable.
Example
4.4 Let A =[−1, 2), B = [2,4], and let
1 − 2x; x ∈ A
f = (x, f (x))|f (x) = .
x; x ∈ B
(4, 4)
} ....
............
........
..
......
.
.. ....
. .....
(−1,..3) y ................
.... .....
.....
..
......
.
...
.... .....
... .....
... ... .....
...
... .....
...
... ... ..
......
... .. .....
...
... .... .....
.....
... ..
... . .....
.....
.....
........
(2, 2)
... .....
... ....
... ...
...
... ...
... ...
... ...
... ...
...
... ...
...
... ...
... ..
............................................................................................................................................................................................................................................................................................................
... ...
O ...
...
...
...
...
x
... ...
... .
... .............
... .....
...
...
..
} (2, −1) ...
....
...
...
...
...
...
...
...
...
...
...
...
...
...
....
.
A
....................................
.......... ......
........ .....
....... ...
........... ...
..
...... ...
...
....... ...
.....
. ...
..... ..
.... ...
.... ..
.
... ...
... ... ...............
.......................
... ... .........
.......
.....
... .. ....... ....
.. ...........
.... x ..
.. ........
...
...
...
....
...
• ......
......
...... ... ..
..
.. .......
.. ......
...
...
...
B
...... .
... ......
... ...... .
.. ..
... ...... ....... .... ...
... ......
.. . . . . . ... .... ..
... .
...... ...... .. .
..... .......... .. ..
.
......
........
.... ....
........ ..............
.. ...
...................................... .. ...
............... ..
..
f .... ......
...... ....
.. ...... . ...
..
....
.........
............ y ..
...
...
... • ...
.
.....
.
.....
.
... .....
... .....
... ......
..... ............
...... ..
........ ........
......................................
Definition 4.5 Consider the function (f, A, B). The set of all elements
which are images of all elements of A is called range of mapping, and
denoted by ran f . Or, ran f = {y ∈ B|∃x ∈ A 3 y = f (x)} (Childs,
2009; Dummit and Foote, 2004a; Rudin, 1991).
Note: Consider the mapping (f, A, B), then: (1). dom f = A. (2).
ran f ⊆ B.
n √ o
Example 4.6 (1) Let A = B = R, f = (x, y) ∈ A × B|y = x2 .
√
The
relation f : A → B is mapping, because y = x2 = |x| =
x; ∀x ≥ 0
−x; ∀x ≤ 0
Mapping 115
A
...........................
............. .......
........
....... .....
...... ....
..
....
. ..
. ...... •b...
.......
. . .......
...
...
...
...
.
.......
...
c ...
......
. .
...
...
...
.
.... • .....
.....
..
......
. ..
......
.. ..
...
.... .....
.
. .
. ......
.. ...
.
..... ...... .
...
. .....
..... ... .
....... .
... ..... . ... ..................................
... ..... .. ........... .................. ......
...
..... .. ..... .....
..... ... ........................ ...
.... a .....
..... . ...
. ....... .. .. .
........... ...
...
....
...
...
• ......
......
......
........ .. ....
..... ... .....
.
....... ....
. . •z ... ...
... B
...... . . . ...
... ...... .
...... .............. .
... ......
....... .... ........ ..
... .......
... .. . . . ... .... . ..........
. . .
.. ...
.
... ...... ...... .....
.....
......
........
...........
.. ..
........ ...............
. . ... •y ...
...
...................................... .... ...
... ............ ..
...
f ....
..
......
......
...... . ...
. ..
.. .................... ...
.... ...
...
... •x ...
.
....
.
.......
... .....
... .....
... ......
..... ............
...... .
........ ........
......................................
Example 4.7 (1) Let (f, R, R) be a function such that: f (x) = −x2 .
The graph of the function will be G = {(x, y) ∈ R × R|y = −x2 } =
{(0, 0), (1, −1), (−1, −1), (2, −4), (−2, −4), ...}.
(2) Let A = {0, 2, 4, 6, 8} , B = {1, 3, 5, 10, 11, 15, 17, 21, 23, 25, 29}.
Let (f, A, B) be a mapping where f (x) = 3x + 5. The
116 Foundations of Mathematics
is a constant mapping.
120 Foundations of Mathematics
4.9.9 Sequence
Definition 4.18 Let A ba any arbitrary set. The mapping f : N → A
is called sequences in A, and denoted by {fn }. Or, f1 , f2 , f3 , ..., fn ; n ∈
N, where fn = f (n); n ∈ N(Ramsey, 1926; Gaughan, 2009b; Wilder
et al., 2012).
Note: If A = R then, the sequence is called sequence of real numbers.
And if A = C, then the sequence is called sequence of complex numbers.
n o
n −n
Example 4.23 Each of {(−1) } , 3(2n ) is sequence of real numbers.
122 Foundations of Mathematics
4.9.10 Permutation
Definition 4.19 Let φ 6= A. The bijection function f : A → A is
called permutation (McCoy, 1968).
4.9.14 Projections
Definition 4.23 Let each of A1 , A2 be a set. The mapping Pi : A1 ×
A2 → Ai ; i = 1, 2 denoted by Pi (a1 , a2 ) = ai ; i = 1, 2. It is called
the projection of the A1 × A2 on Ai ; i = 1, 2 (Halmos, 2017b; Mustafa
et al., 1980).
Note:
4.10 Exercises
Solve the following questions:
Q1: Let f :√[1, ∞) → R be a mapping defined as:
(1) f (x) = 4x − 1. Find range of the mapping.
(2) f (x) = (4x − 1)( 31 ).
Find domain, codomain, and range of the domain.
Q2: Draw the graph of the following relationships:
(1) f = {(x, y) ∈ R × R|3x − y = 4}.
2
(2) g = {(x,
y) ∈ R × R|y = x − 4}.
2x; x ∈ (−2, 4)
(3) h = (x, y) ∈ R × R|y = 3x+1 .
2
; x ∈ (−4, −2)
Q3: Discuss the following statements:
(1) The value of the sphere is a function for its radius.
(2) Radius of the sphere is a function of its value.
(3) The value of the gas is a function of the pressure.
Q4: If f (n) represents the prime numbers which is less than or
equal the positive integer number n. Find f (5), f (79).
Q5: Let f : A → B be an injective function, and let C ⊆ A. Prove
that f /C : C → B is an injective function.
126 Foundations of Mathematics
B C
A
. x1 . y1 . z1
f g
.x2 .y2 .z2
Figure 4.4: g ◦ f
∵ f −1 is a functional relation,
∴ (x1 , y) ∈ f ∧ (x2 , y) ∈ f → x1 = x2 .
∴ f : A → B is bijective function ...(1).
Now, we have to prove that f : A → B is surjective function.
Let y ∈ B, ∵ f −1 : B → A is a mapping,
∴ ∃x ∈ A 3 (y, x) ∈ f −1 .
Or, ∃x ∈ A 3 (x, y) ∈ f → ∃x ∈ A 3 y = f (x) ...(2).
Thus, from (1)& (2), f : A → B is bijective.
Conversely, suppose that f : A → B is bijective.
We have to prove the mapping f : A → B is invertible.
Or, it ought to be proved that f −1 : B → A is a mapping.
Suppose that y ∈ B. As, f : A → B is surjective,
∴ ∃x ∈ A 3 f (x) = y → ∃x ∈ A 3 (x, y) ∈ f .
But (x, y) ∈ f → (y, x) ∈ f −1 .
Thus, ∃x ∈ A 3 (y, x) ∈ f −1 .
Or, domf −1 = B ...(3).
In order to prove f −1 : B → A is a functional relation, suppose that
(y, x1 ) ∈ f −1 ∧ (y, x2 ) ∈ f −1 .
∴ (x1 , y) ∈ f ∧ (x2 , y) ∈ f .
Or, f (x1 ) = y ∧ f (x2 ) = y → f (x1 ) = f (x2 ).
As f : A → B is injective, ∴ x1 = x2 .
Or, (y, x1 ) ∈ f −1 ∧ (y, x2 ) ∈ f −1 → x1 = x2 .
∴ f −1 is functional relation ...(4).
From (3)& (4) f −1 : B → A is a mapping.
(ii) f ◦ f −1 = IB .
4.12 Exercises
Solve the following questions:
Q1: Let each of f : X → Y, g : Y → X be a mapping, and let
g ◦ f = IX . Prove that f : X → Y is an injection mapping, then
g : Y → X will be surjective.
Q2: Let each of f : X → Y, g : Y → X be a mapping, and let
g ◦ f = IX , f ◦ g = IY . Prove that each of (1) f, g is a bijective. (2)
g = f −1 .
Q3: Let f : A → B be a mapping, and let C ⊆ A. Prove that
f /C = f ◦ EC , where EC : C → A is the inclusion mapping.
Mapping 133
4.14 exercises
Solve the following questions:
138 Foundations of Mathematics
A
.............................
............
........ ......
.....
.......
...... ....
................
. .
•b......
........
.
...
...
...
.
. ..
.
....
..
.... c ......
..
. ......
...
...
.........
• .....
... .....
.
. ..
......
........
. ..
.
.
..
. ....... ........ .. .
. ... .....
..... ........... .
... ..... ..
... ..... ......... .........................................
...
..... .. ........................... ......
..... ... .
...... ............. .....
.... ..... .
... a d• ...........
........... ..........
.
..
.
. ..........
. .. ..........
.
...
...
...
... • ......
......
......
........... ..... .... ........
................ .. ....
..................
•z .... ...
... B
... ...... .... ................. ...
... ...... . .
... ..... ........ .................. ..
........ . .. ........... .
... ... .
...... .... .......
. .
. . . . .. .
. ..
... ......
...... ........... ....
. ............ .................
. ...
...
.....
...... .........
.
.. ..
........ ...............
.
. . •y .
... .. . . .
•w
..
.......
..
.
.
.........
................................... ...
......... ...
... ........... ..
f ..
.... ......
...... ..
.
...
.....
......... ...
............. ...
...
... •x ...
..
.
.....
....
... ....
.....
... ......
... ......
.....
...... ....
.........
........ .... .
......................................
A
................................
........... ......
........ .....
.......
•b
...... ....
..... . ...
........ ......
........
...
.
..... .. ...
.
....
.
.....
c . ......
.. . ......
...
...
......
• ......
. .......
.........
........ ..
.
..
.... .....
..... ... ...... .. ..
... ...... .. ......... .
... .....
..... ...... .................................
... ..... ... ........... ................... ......
... .....
..... ... ......... .....
.... . ...... ................ ...
... a d• .....
.....
..
.....
..... .
.
.. .........
. .......... ...
...
....
...
• ......
......
......
.....
.....
..
..... ... ......
. .
..... .. .....
.
...
.
..
. •z ... ...
... B
... ...... .....
.. ...
............... ...
...... ..... . .
... ...... ..... ......... ..... .......... . .
..
... ...... ...
. ... .. ... ... .. .
.. . ..
... ...... ......... ...
. .......... ..
....
.....
.......
.. .
.
..........
... ..
.
....
.... ......... ... .......
.
......
. .
.
. •y ... .
..
.
.
............... ......................... ...... ..... ...
...... .. ...... .... ...
... .................... ..
f .... ...... .....
............ ......
.. ............. ...
.... ................. ...
...
... •x ...
..
.
.....
.....
... ....
... .....
... ......
..... ......
...... ...
...
........
........ ..
......................................
4.15.3 Isomorphism
Definition 4.30 If each of A, B are partial ordered sets. The mapping
f : A → B is an isomorphism if and only if (1) f : A → B is bijective
function. (2) x ≤ y → f (x) ≤ f (y), ∀x, y ∈ A(Awodey, 2010; Vinberg,
2003).
Theorem 4.19 Let W be a set of all partial ordered sets, and let R be
a relation defined on W as R : A → B, ∀A, B ⊆ W . If A ∼= B, then R
is an equivalence relation.
144 Foundations of Mathematics
Theorem 4.25 If each of A, B be well ordered sets, then one and only
one of the following statements is true.
(i) A is isomorphic with B.
4.16 exercises
Answer the following questions:
Q1: Let A be a well ordered set. Prove that any subset of A will
be isomorphic with A, or with a initial segment with A.
Q2: Let A, B be well ordered sets. Prove that there is at most one
isomorphism, f : A → B.
Q3: Let A, B be well ordered sets. Prove that if A is isomorphic
with B and B is isomorphic with a subset of A there is at most one
isomorphism, then A is isomorphic with B.
Q4: Let A be well ordered set. Prove that IA is a unique
isomorphism from A to A.
Q5: Let A, B be well ordered sets. If each of f : A → B, g : B → A
isomorphic, then g = f −1 .
Q6: Let A, B be well ordered sets. Consider that A does not
contains on a greatest, and assume that all elements in B (except of
least element) have an immediate predecessor. And, prove that B is
isomorphic with an initial segment of A.
Q7: Consider a bijective function f : A → B. If the set A is
partially ordered set or totally ordered set or well ordered set, then it is
possible to define on B, a partially ordered relation or totally ordered
relation or well ordered relation via f to make f isomorphism.
Mapping 149
(ii) Let A be a set, its elements are nonempty sets and separated.
There exists a set C contains one element of A ∈ A, ∀A. Or,
{∃!c|c} = C ⊆ A ∈ A, ∀A.
(a) Each set of the finite family subsets in any element of the
family belongs to the family of sets.
(b) If all finite subsets of X belongs to the family of sets, then
X itself belongs to the family of sets.
Mapping 151
4.18 Exercises
Solve the following questions:
Q1: Consider a set A, and a mapping f : A → A. The mapping
f : A → A is surjective if and only if there exists a mapping g : B → A,
such that f ◦ g = IB .
Q2: Consider a sets A, B, and a mapping f : A → B. There exists
a set C ⊆ A, g ⊂ f , such that g : C → B is injective function, and
ranf = rang.
Q3: Prove that the following hypothesis is equivalent to the axiom
of choice. If E be a set, and assume that G ⊆ E × E and A =
domG, B = ranG, then there exists a mapping f : A → B, such that
f ⊆ G.
Q4: Let R : A → B be a relation such that domR = A. There
exists a subset R∗ ⊂ R such that R∗ : A → B be a mapping.
Q5: Consider a sets A, B, C. Let f : B → C, g : A → C be
mappings. Assume that ranf ⊆ g. Prove that there exists a mapping
g ◦ h = f where h : B → A.
152 Foundations of Mathematics
Q6: Consider this quote from Bertrand Russell (18 May 1872 - 2
February 1970) “The Axiom of Choice is necessary to select a set from
an infinite number of pairs of socks, but not an infinite number of pairs
of shoes.” Do you think that explanation makes sense for the quote?
The observation here is that one can define a function to select from
an infinite number of pairs of shoes, for example by choosing the left
shoe from each pair. Without the axiom of choice, one cannot assert
that such a function exists for pairs of socks, because left and right
socks are (presumably) indistinguishable.
5
Potency of Sets
5.1 Introduction
onsider a finite sets A, B. Now, let us ask the following question,
C Are the contents of the sets of the same number have same
elements? We can answer this question by one of the following methods;
(i) We begin to account elements for each set separately. But we can
not generalize this method in the case of infinite sets because it
is impractical.
cardinal numbers. In the case of dealing with the finite sets, the concept
of the ordinal number matches with the concept of the cardinal number.
(v) There exists a unique natural number (N), where this set is infinte
and denoted for its cardinal numbers by the symbol No .
5.4 Exercises
Answer the following questions:
Q1: Prove that:
(i) #(A) = α.
(ii) #(B) = β.
(iii) A ∩ B = φ. (Deiser, 2010; Enderton, 1977).
Theorem 5.5 Let {Aα }α∈I be a family of sets, there exists a family of
sets {A∗α }α∈I such that:
(i) A∗α ∼ Aα , ∀α ∈ I.
(ii) α 6= β → A∗α A∗β = φ.
T
(ii) x = No .
(iii) x = C.
(i) The associated property for the addition α +(β +γ) = (α +β)+γ.
(i) No No = No .
(ii) No C = C.
(iii) C C = C.
Proof (i) No No = # {N × N}
We can express of elements of N × N as follows;
(0, 0) (0, 1) (0, 2) (0, 3) ...
(1, 0) (1, 1) (1, 2) (1, 3) ...
(2, 0) (2, 1) (2, 2) (2, 3) ...
(3, 0) (3, 1) (3, 2) (3, 3) ...
. . . .
. . . .
. . . .
Then arranged in an infinite sequence:
{(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), ...}.
∴ #(N × N) = No ⇒ No No = No .
(ii) No C = # {N × [0, 1)}.
Now, let us define a mapping f : N × [0, 1) → [0, ∞), such that
f ((x, y)) = x + y.
It is clear that f : N × [0, 1) → [0, ∞) is a surjective , and injective
mapping.
∴ f : N × [0, 1) → [0, ∞) is bijective.
∵ #([0, ∞)) = C,
∴ No C = C.
(iii) C C = # {(x, y)|x, y ∈ [0, 1)}.
We will express of x, y as an infinite decimal fraction (this expression
is unique).
∴ (x, y) = (0.x1 x2 x3 ..., 0.y1 y2 y3 ...).
Note that z = 0.x1 y1 x2 y2 ... is an infinite decimal fraction.
∴ z is represents a certain number on [ 0, 1). Thus, we have defined
injective function f : [0, 1) × [0, 1) → [0, 1).
Also, we can define an injective function g : [0, 1) → [0, 1) × [0, 1).
Now, according to Schroeder-Bernstein theorem (Bernstein, 1905),
it will be [0, 1) × [0, 1) ∼ [0, 1).
∴ C C = C.
Potency of Sets 165
Corollary If the set B has the power of continuum, then the set B×B
has a power of continuum too.
Figure 5.2: x = α
S S
∴ Aα ∼ Lα Then α Aα ∼ B ⊆ α Lα
166 Foundations of Mathematics
S
But, S α Lα = R × R
∴ #( α LSα ) = C C = C.
Thus, #( S α Aα ) = #B ≤ C ...(1)
But, Aα ⊆ α A Sα
∴ #(Aα ) ≤ #(S α Aα )
Thus, C ≤ #( α Aα ) ...(2)
From (1)& (2) S and by utilizing Schroeder-Bernstein theorem, we
conclude that #( α Aα ) = C.
Q that Aγ = A∀γ ∈ B
We can assume
∴ αβ = #( Aγ |γ ∈ B)
∴ αβ = # AB .
Or, ∴ αβ = # {f |f : B → A}, such that f : B → A is a mapping,
and #(A) = α, #(B) = β.
Note: The above operation is well defined.
(i) αβ αγ = αβ+γ .
(iii) αγ β γ = (αβ)γ .
Potency of Sets 167
(ii) The Cantor theorem (Cantor, 1883b) states that 2α > α for all
cardinal number α.
5.6 Exercises
Answer the following questions:
Q1: Prove that No + α = α, for all the cardinal number α.
Q2: Consider a cardinal numbers α, β, such that α ≤ β. For any
cardinal number γ prove that;
Potency of Sets 169
(i) αγ ≤ β γ .
(ii) γ α ≤ γ β .
(iii) α + γ ≤ β + γ.
(iv) αγ ≤ βγ.
Q3: Prove that #(T ) = C, where T is the set of transcendental
real numbers.
Q4: Let each of α, β, γ be a cardinal number. Prove that
(i) αβ = 0 ↔ α = 0 ∨ β = 0.
(ii) αβ = 1 ↔ α = 1 ∧ β = 1.
Q5: For each of a cardinal number α, β, prove that α ≤ β ↔ ∃γ 3
β = α + γ.
Q6: Consider the cardinal numbers α, β, γ, δ, such that α ≤ γ, β ≤
δ. Prove that
(i) α + β ≤ γ + δ.
(ii) αβ ≤ γδ.
(iii) αβ ≤ γ δ .
Q7: If α be an infinite cardinal number, then αα = α.
Q8: Consider a cardinal numbers α, β, γ, prove that
(i) αβ < αγ → β < γ.
(ii) α + β ≤ α + γ → β < γ.
(iii) α + α = α + β → α ≥ β.
(iv) α ≤ β → αβ = 2β .
Q9: Evaluate No ! = 1.2.3....No .
Q10: Prove the Konig’s theorem (Rubin P and Rubin,
Q 1985; Holz
et al., 2010; König, 1905) If αλ < αλ , ∀λ, then λ αλ < λ βλ .
Q11: Find C No .
Q12: Let each of α, β be an infinite cardinal number, prove that
α + β = αβ max {α, β}.
170 Foundations of Mathematics
(i) The expression A 6' B means that the set A is not similarity to
the set B.
(i) The similarity sets are potency sets. The order type sets are the
cardinal numbers, but vice versa is not true.
(ii) It is clear from the above definition that the order type set is
totally ordered set, which is just an abstract
Q concept. We denote
to the type order set A by the symbol (A).
(i) The order type of N associated with its usual ordering denoted
by the symbol W which is the order type for N. The Q with its
usual order denoted by η. The R with its usual order denoted by
λ.
(ii) With respect to the finite sets, the concepts of the potency and
the similarity have the same meaning. Thus, ordering of a set
consists of n elements, denoted by the symbol n.
Q Q
Note: If (A) = α, (B) = β, A ∩ B = φ. Thus, based on theorem of
the standard substitution theorem, we Q
can substitute each of A, B by
A , B respectively, such that α + β = {A? , B ? }.
? ?
(ii) The association property for the addition operation is hold. Or,
α + (β + γ) = (α + β) + γ), where α, β, γ are ordinal patterns.
(iv) The ordinal pattern of the open interval (a, b) is equal to the
ordinal pattern of R(or equal to λ).
(v) W 2 = W.W
= W +1W3 +5W +1...2 where W 2 is the ordinal pattern
for K = 1, 2, 3, ...; 2 , 2 , 2 , ...; 3 , 3 , 34 , ...; ...; ... . It should be noted
that K = Q+ .
(i) Let each of A, B be well ordered sets, The sets {A, B}, B × A
are well ordered sets too. Thus, the addition and multiplication
of the ordered sets are well ordered sets.
Theorem 5.14 Every ordinal number α is the ordinal pattern for the
set Wα .
Now, it should be noted that the well ordered sets are comparable.
Or, anyone of them is similar for a subset of others. But the similar
sets are the potency sets.
Therefore, A is equipotent set with a subset of B, or B is equipotent
set with a subset of A.
Thus, either a ≤ b, or b ≤ a.
5.8 Exercises
Answer the following questions:
Q1: Consider the ordinal patterns α, β, γ, then;
(i) (α + β)? = β ? + α? .
(i) n? = n, λ? = λ.
(ii) n + n = n.
(iii) λ + λ 6= λ.
(iv) n + 1 + n = n.
(v) λ + 1 + λ = λ.
(i) W + m 6= W + n.
(ii) m + W ? 6= n + W ? .
5.9 Paradoxes
There are negatives and disadvantages in the intuitive set theory in
which in which they lead to contradictions. It is crucial to note that,
we assumed that any collection of things may be called a set. For
example, we expect there is a so-called set of all cardinal numbers or
the ordinal numbers, but this leads to the following contradictions.
6.1 Introduction
umber is a fundamental concept in mathematics and it is
N an effective tool in scientific and practical studies. There is
a difference between the numerical sense and the number itself.
The numerical sense is a common property among organisms while
operations on numbers involve complex mental processes. Thus,
operations on numbers are related to humans exclusively.
Comparison of sets is the primitive and optimal method to
determine the elements of sets in which someone takes and specifies
a typical set to compares it to other sets to determine their elements.
The matter becomes easier if we add the ordinal property of sets, where
we arrange sets ordinally and sequentially where the first set does not
contain any element, the second contains just one element, the third
contains two elements and so on. In other words, every set is a subset
of the next set that has one extra element.
It should be given names and symbols to such sets and typical sets,
for example, zero, one, two, three, ... and so on, in which denoted by
symbols 0, 1, 2, 3, ...
It should be noted the natural numbers (N) consists of the ideas
cardinal number and ordinal number. For example the set consists of 5
180 Foundations of Mathematics
numbers, its cardinal numbers is 5, while its ordinal numbers are first,
second, third, fourth, and fifth. Or, the number that is determined
relative to others in the series of the natural numbers.
The mathematical accuracy drives us to insert axiom of infinity
which states of a successor set. Or the set contains on X∪{X} whenever
contains of X. The intersection of all the successor sets is the set of
the natural numbers (N). In what follows we are going to the state
of Peano’s axioms and proof of them. In addition to the addition and
multiplication operations on N, and defining on the ordinal relation on
it.
.
.
Thus, 0 = φ, 1 = {φ}, 2 = {φ, {φ}}, 3 = {φ, {φ} , {φ, {φ}}}... etc.
Definition 6.3 The intesection of all successor sets is called the set of
natural numbers denoted by N, and any element belongs to it, called a
number of N (Carothers, 2000; Bancerek, 1990; Grassmann, 1861).
182 Foundations of Mathematics
Note:
(1) The statement P4 called the mathematical induction (Bather,
1994).
(2) By assuming the infinity axiom, Peano’s axioms converted to
theorems, and could be proved (Kapur et al., 1986), as in the following
section.
(i) 0 ∈ X,
(i) 0 ∈ X because if 0 ∈
/ X that means ∃y ∈ 0 3 y * 0. But this is
contradiction because 0 = φ.
(ii) n ∈ X → n+ ∈ X.
Because if m ∈ n+ where n+ = n ∪ {n}. ∴ (m = n) ∨ (m ∈ n).
If m ∈ n then m ⊆ n, because n ∈ X as assumed before.
On the other hand, we have n ⊆ n+ and it implies m ⊆ n+ .
If m = n → m ∈ n+ because n ∈ n= .
Thus, from (i) & (ii), we obtain m ∈ n → n+ .
∴ n+ ∈ X.
Now, by utilizing P4 we get X = N. Or, for all n ∈ X , then
x ∈ n → x ⊆ n (Peano, 1967) .
184 Foundations of Mathematics
6.3 Exercises
Answer the following questions:
Q1: Assume that each of A and B are sets. Prove that if A = B →
A# = B # .
Q2: For all n ∈ N, prove that n ∈
/ n.
Q3: Use the mathematical induction to prove;
(1) (A ∈ n) ∧ (n ∈ N) → A ∈ N. (2) n ∈ N → (n = 0) ∨ (n =
+
m ), m ∈ N.
Q4: Prove that if A+ ∈ N → A ∈ N
6.4 Arithmetic of N
Before defining addition and multiplying of N. We need to state and
proof Recursion theorem (Kjos-Hanssen et al., 2011; Rogers, 1987;
Kirby and Paris, 1982) as follows:
(a) 0 ∈ S, because if 0 ∈
/ S → (0, b) ∈ α 3 b 6= a.
Let β = α − {(0, b)}. It is noted that β ∈ F and this is
contradiction because α is a smallest set in F .
∴ 0 ∈ S.
(b) Assume that n ∈ S
∴ ∃! x ∈ X 3 (n, x) ∈ α.
∴ (n+ , f (x)) ∈ α.
If n+ ∈/ S then (n+ , y) ∈ α 3 y 6= f (x).
Assume that γ = α − {(n+ , y)}.
It is noted that, (0, a) ∈ γ, because n+ 6= 0.
Also, (m, t) ∈ γ → (m+ , f (t)) ∈ γ
∴ γ ∈ F , and this is contradiction because α is the smallest
set in F .
∴ n+ ∈ S.
Thus, N = S.
6.4.1 Addition of N
Definition 6.4 For all m ∈ N, and based on Recursion Theorem
(Theorem 6.2), there existed a unique mapping as follows:
βm : N → N, such that
(1) βm (0) = m. (2). βm (n+ ) = (βm (n))+ .
The addition of N can be defined as follows;
m + n = βm (n), ∀m, n ∈ N.
Or, (1) m + 0 = m. (2) m + n+ = (m + n)+ .
We list some addition properties of N in the next sections.
Theorem 6.4 n = 0 + n, ∀n ∈ N.
6.4.2 Multiplication of N
Definition 6.5 If m ∈ N, according of the Recursion Theorem
(Theorem 6.2), there is a unique mapping as follows;
γm : N → N, such that:
188 Foundations of Mathematics
Theorem 6.6 0n = 0, ∀n ∈ N.
Theorem 6.7 1n = n, ∀n ∈ N.
6.5 Exercises
Solve the following Questions:
Q1: Consider a set A, let C ∈ A, and let f : A → A be an
injective mapping such that C ∈ / ranf . Prove that, there exists a
unique injective function γ : N → A such that
(a) γ(0) = C. (b) γ(n+ ) = f (γ(n)), ∀n ∈ N.
Q2: Consider a set A, and let f : A → B be an injective mapping
such that B ⊂ A. Prove that A contained of a subset D, such that
there is a corresponding between D and N.
190 Foundations of Mathematics
Q3: Let A be a set that does not contains of big elements. Prove
that there exists a strictly increasing sequences of A. Or, there exists
a mapping γ : N → A, in which γ(0) < γ(1) < γ(2) < ....
Q4: For all m, n, k ∈ N. Prove that
(a). If m = n → m + k = n + k. (b). If m = n → mk = nk.
Q5: Give an induction definition for mn similarity to the definition
of addition and multiplication of natural numbers satisfying the
Recursion theorem. Then, prove that
(a) mn+k = mn mk . (2) (mn)k = mk nk . (3) (mn )k = mnk .
6.6 Order on N
In review of the Ns, researchers noted that the most important property,
which is the order of it (Shilnikov, 1967; Schmidt, 1993; Davey and
Priestley, 2002). It is noted that the natural number n is just a
prenumbers of it in which n = {0, 1, ..., n − 1}. Based on this we can
say n is precedes m if n is an element of the set m. Thereby we set the
following definition.
Proof (1) ∀m ∈ N, m = m.
∴ m ≤ m.
Thereby ≤ is the reflex relation on N.
(2) Assume that m ≤ n ∧ n ≤ m.
∴ m = n ∨ ((m ∈ n) ∧ (n ∈ m)).
Or, (m ⊆ n) ∧ (n ⊆ m).
Or, n = m.
Thus, m = n.
Thereby ≤ is the symmetric relation on N.
(3) Assume that m ≤ n ∧ n ≤ p.
There are four cases;
(i) m ∈ n ∧ n ∈ p.
The Natural Numbers 191
That means m ∈ n ∧ mn ⊆ p.
∴ m ∈ p.
Or, m ≤ p.
(ii) m ∈ n ∧ m = p.
m ∈ p.
Or, m ≤ p.
(iii) m = n wedgen ∈ p.
∴ m ∈ p.
Or, m ≤ p.
(iv) m = n ∧ n = p. ∴ m = p.
Or, m ≤ p.
∴ frome (i), (ii), (iii) & (iv) we conclude that ≤ is the transitive
relation on N.
From (1), (2) & (3) ≤ is the partial ordered relation on N.
If n ∈ m → n ≤ m.
now, based on the induction axiom we have n+ ≤ m, but m < m+ .
∴ n+ ≤ m+ .
∴ n < m+ → n+ ≤ m+ .
Or, n+ ∈ Ln .
Thus, by P4 , n < m → n+ ≤ m, ∀n, m ∈ N.
Or, Ln = N.
Now, we are ready to begin proving the theorem of the well ordered
set.
Let φ 6= A ⊆ N, and assume that the set A does not consists of a
least element.
Let T = {n ∈ N|n ≤ m, ∀m ∈ A}.
Based on (1) we conclude that 0 ∈ T .
Now, assume that n ∈ T .
∴ n ≤ m, ∀m ∈ A, because if n = a 3 a ∈ A → a ≤ m, ∀m ∈ A.
Or, a is the least element in A, and we get contradiction.
∴ n < m, ∀m ∈ A.
According of (2), we have n+ ≤ m, ∀n ∈ A.
Or, n+ ∈ T .
Thereby, n ∈ T → n+ T .
Thus, based on P4 we conclude that T = N.
∴ T ∩ A = N ∩ A = A.
But, T ∩ A = φ, because A does not consistent of a least element.
∴ A = φ and this is contradiction since A 6= φ.
∴ A has a least element.
Or, N is well ordered set.
Corollary
Proof
(i) If m, n ∈ N → (n ≤ m) ∨ (m ≤ n).
Or, ∀m, n ∈ N → (m = n) ∨ (m < n) ∨ (n < m).
It is clear that just one of these relationships could be satisfied,
and this is called Trichotomy Law.
6.6.1 System of N
Definition 6.7 The set N with the two operations addition and
multiplication and the relation ≤ is called the algebraic system of
the natural numbers, and denoted by (N, +, ., ≤) (Eves and Newsom,
1958; Eves, 1992; Ian and David, 2015; Wilder et al., 2012; Jech, 1977;
Mustafa et al., 1980).
6.6.2 Weaknesses of N
The system (N, +, ., ≤) has weaknesses, for example, the following
system;
194 Foundations of Mathematics
m+x=n
∀m, n ∈ N has no solution in the N in general. That
mx = n
why we are forced to extension the system (N, +, ., ≤) to (Z, +, ., ≤) to
find solutions of the kind of m + x = n in the next chapter.
6.7 Exercises
Solve the following questions:
Q1: Prove that m < 1 → m = 0, ∀m ∈ N.
Q2: Prove that there is not a natural number k such that satisfies
m < k < m+ , m ∈ N.
Q3: prove that n < k → m + n < m + k, m, n, k ∈ N.
Q4: Prove that m + n = m + k → n = k, m, n, k ∈ N.
Q5: Consider m, n, k ∈ N, show that (i) ((m < n) ∧ (k 6= 0)) →
mk < nk. (ii) ((mk = nk) ∧ (k 6= 0)) → m = n.
Q6: Consider m, n, k ∈ N, show that m + k < n + k → m < n.
Q7: Prove that ((p = mn) ∧ m 6= 1) → p > n, ∀p, m, n ∈ N.
Example 6.3 The following are countable sets; (1) No . (2) Q. (1) Let
the mapping g : N → No , defined as: g(n) = 2n + 1.
Its easy to prove that g is bijective. thereby, from the definition of
the countable set, we can confirm that the set No is countable. Similarly,
we can prove that the set Ne is countable too.
(2) We prove this problem in the chapter of the rational numbers.
Proof ∵ A is countable, ∴ ∃f : N → A.
Assume that f (n) = x; n ∈ N.
the mapping g : N → A as follows:
Now, define
f (m); m < n
g(m) =
f (m + 1); m ≥ n
It is clear that g : N → A − {x} is a bijective mapping.
Thereby, A − {x} is a countable set.
Corollary
Let B ⊆ A.
Now, there are two cases:
(i) If B 6= φ then B is a finite set. (ii) If B 6= φ then assume that
an1 is the first element of the sequence a0 , a1 , ... 3 an1 ∈ B.
Again, assume that an2 is the first element after an1 of the sequence
a0 , a1 , ... 3 an2 ∈ B.
Now, let us consider B = {an1 , an2 , ...}.
If the set B ∗ = {n1 , n2 , ...} is bounded then the set B will be finite.
And, if B ∗ is unbounded then B will be a countable.
Theorem 6.19 N × N ∼ N.
Proof A ⊆ A ∪ B ⊆ A ∞
S
i=1 Bi where B = Bi , i = 1, 2, ...
So, No ≤ #(A ∪ B) ≤ No .
∴ #(A ∪ B) = No .
Thus, A ∪ B is a countable.
6.9 Exercises
Solve the following questions:
Q1: If A be infinite set, and B 6= φ then each of A × B, B × A is
infinite.
Q2: Let A be a finite set, and B ⊂ A, where B infinite. Prove that
A − B is infinite.
Q3: Prove that A is an infinite set if and only if ∀n ∈ N, ∃B ⊂ A
such that B ∼ n.
The Natural Numbers 201
1
(viii) The set S = n
, ∀n ∈ N .
7.1 Introduction
e will dive into this chapter to the binary operations on sets in
W details. The binary operation on the set A is a mapping from
A × A to A. Or its domain is A × A, and its codomain is A. Thereby,
the binary operation is an algebraic operation to connect two elements
of the set to get the third element in the same set. Also, there are mono
and triple operations and... etc.
Then, we define the mathematical system, which is a set A with
one or more than an operation on A. The most important system with
the mono operation is a group in which the group is the fundamental
subject of abstract algebra. The next sections deals with rings, vector
spaces, and fields.
Although various types of groups were dealt with during the 18th
and 19th centuries, however the concept of the abstract group did not
appear until the end of the 19th century.
Group theory is the most important algebraic theory and has wide
contributions and applications in mathematics, physics, chemistry,
electrical engineering, computers,...and so on.
Many scientists and researchers contributed to the development of
the group theory (Taton, 1972; Wussing, 2007; Hunter et al., 1977;
204 Foundations of Mathematics
Thus, f ∗ g 6= g ∗ f .
Example 7.7 (1) Each of the following mathematical systems are the
associative mathematical systems:
210 Foundations of Mathematics
(N, +), (Z, +), (Q, +), (R, +), (N, .), (Z, .), (Q, .), (R, .).
(2) Each of the following mathematical systems are not associative
mathematical systems:
(N, −), (Z, −), (Q, −), (R, −), (N − {0} , ÷), (Z − {0} , ÷), (Q −
{0} , ÷), (R − {0} , ÷).
(3) If X 6= φ then each of (P (X), ∪), (P (X), ∩), (P (X), ∆) are
associative mathematical systems.
(4) If X 6= φ, and S : X → X be a set of all mappings, then (S, ◦)
is associative mathematical system.
a ∗ (b ∗ c) = (a ∗ b) ∗ c, ∀a, b, c ∈ A.
(i) If a = x, b = x, c = x then
a ∗ (b ∗ c) = x ∗ (x ∗ x) = x ∗ x = x
(a ∗ b) ∗ c = (x ∗ x) ∗ x = x ∗ x = x.
(ii) If a = x, b = x, c = y then
a ∗ (b ∗ c) = x ∗ (x ∗ y) = x ∗ y = y
(a ∗ b) ∗ c = (x ∗ x) ∗ y = x ∗ y = y.
(iii) If a = x, b = y, c = x then
a ∗ (b ∗ c) = x ∗ (y ∗ x) = x ∗ y = y
(a ∗ b) ∗ c = (x ∗ y) ∗ x = y ∗ x = y.
(iv) If a = x, b = y, c = y then
a ∗ (b ∗ c) = x ∗ (y ∗ y) = x ∗ x = x
(a ∗ b) ∗ c = (x ∗ y) ∗ y = y ∗ y = x.
(v) If a = y, b = x, c = x then
a ∗ (b ∗ c) = y ∗ (x ∗ x) = y ∗ x = y
(a ∗ b) ∗ c = (y ∗ x) ∗ x = y ∗ x = y.
(vi) If a = y, b = x, c = y then
a ∗ (b ∗ c) = y ∗ (x ∗ y) = y ∗ y = x
(a ∗ b) ∗ c = (y ∗ x) ∗ y = y ∗ y = y.
(vii) If a = y, b = y, c = x then
a ∗ (b ∗ c) = y ∗ (y ∗ x) = y ∗ y = x
(a ∗ b) ∗ c = (y ∗ y) ∗ x = x ∗ x = x.
(viii) If a = y, b = y, c = y then
a ∗ (b ∗ c) = y ∗ (y ∗ y) = y ∗ x = y
(a ∗ b) ∗ c = (y ∗ y) ∗ y = x ∗ y = y.
Thus, we conclude that (A, ∗) is semigroup.
(4) The mathematical system (Z, −) is not a semigroup, because −
is not associative binary operation.
214 Foundations of Mathematics
7.5 Exercises
Solve the following questions:
√
Q1: Let S = a + b 3|a, b ∈ Z , and ∗ be The multiplication
operation on S.
(1) Prove that S closed on ∗.
(2) Prove that (S, ∗) ia a commutative semigroup with an identity
element.
Q2: Let R∗ = R − {0} , T = {(a, b) ∈ R × R∗ }. Define ∗ on T as
follows;
(a, b) ∗ (c, d) = (ac, bd). Prove that the system (T, ∗) is the
commutative semigroup has the identity element.
Q3: Give an example of noncommutative but associative
mathematical system.
Hint: Let X 6= φ, S = {f |f : X → X}, then (S, ◦) is a noncommutative
but associative mathematical system .
Q4: Give an example of a commutative but not associative a
mathematical system.
Hint: Let A 6= φ, a ∗ b = a + b − ab, ∀a, b ∈ A, then (A, ∗) is a a
commutative but not associative mathematical system because ∗ is a
commutative but not associative binary operation.
Q5: Distinguish the commutative binary operation from the
associative binary operation on Q of the following binary operations;
(1) a ∗ b = b. (2) a ∗ b = a + b − 2.
Binary Operations and Groups 215
Q6: Let (S, ∗) be a mathematical system that has its own identity
element, and let (a ∗ b) ∗ (c ∗ d) = (a ∗ c) ∗ (b ∗ d), ∀a, b, c, d ∈ S. Prove
that ∗ is a commutative and associative.
Q7: Consider S = {1, ..., 6}. Define ∗ on S as follows;
a ∗ b = gcd {a, b}. Prove that (S, ∗) is semigroup.
Q8: Let the binary operation ∗ defined on Q as follows;
a ∗ b = a + b − ab.
(1) Find the identity element. (2) Is each element of Q has inverse?
Q9: Define ∗ on N as a ∗ b = a + b2 , ∀a, b ∈ N. Does the identity
element exist?
Q10: Consider the binary operation ∗ on Q, and defined as;
a ∗ b = a+b
2
, ∀a, b ∈ Q. Dose ∗ a commutative on Q?
Q11: Prove that the system (Q, +, .) is a number system.
Q12: Consider the set pf all mappings S : R → R. Is (S, +, .) a
numerical system?
7.6 Groups
Definition 7.15 The mathematical system (G, ∗) is called a group if
and only if the following three conditions are met;
(1) The binary operation ∗ is associative on G. Or, a ∗ b ∗ c =
a ∗ (b ∗ c) = b ∗ (a ∗ c) = c ∗ (a ∗ b), ∀a, b, c ∈ G.
(2) There is an identity element. Or, ∃e ∈ G 3 a ∗ e = e ∗ a =
a, ∀a ∈ G.
(3) Every element is invertible. Or, ∀a ∈ G, ∃a−1 ∈ G 3 a ∗ a−1 =
a−1 ∗ a = e (Hall, 2018; Hall, 1962; Ledermann, 1973; Robinson, 2012;
Hall, 1967).
Example 7.15 (1) Consider G = {−1, 1}, then (G, ∗) is a finite group,
and O(G) = 2.
218 Foundations of Mathematics
(i) a ∗ x = b.
(ii) y* a= b.
Proof (i) ∵ a ∈ G,
∴ a−1 ∈ G.
∴ a−1 ∗ b ∈ G.
∴ a−1 ∗ b is a solution for the equation a ∗ x = b, and it satisfies as
followings;
a ∗ x = a ∗ (a−1 ∗ b) = (a ∗ a−1 ) ∗ b = e ∗ b = b.
∴ there exists at least one solution satisfies the equation.
Now, to prove a solution is a unique.
Suppose that x0 is another solution for a ∗ x = b.
∴ a ∗ x0 = b.
∵ a ∗ (a−1 ∗ b) = b.
∴ a ∗ x0 = a ∗ (a−1 ∗ b).
Thus, and based on the cancellation law, we get that x0 = a−1 ∗ b.
Or, the solution is a unique.
(ii) It is left as an exercise.
(i) an ∗ am = an+m = am ∗ an .
Proof The proof has been left as an exercise for the reader.
∵ x2 6= x3 ,
∴ α ◦ β 6= β ◦ α.
Proof Let a ∈ Z.
Now, based on division algorithm, we have a = qn + r 3 q, r ∈
Z, 0 ≤ r < n.
Binary Operations and Groups 225
∴ a − r = qn.
∴ [a] = [r].
∵ r = 0, 1, ..., n − 1,
∴ [a] = [0] ∨ [1] ∨ ... ∨ [n − 1].
Thus there are n of equivalence classes.
Note: If n ∈ Z+ then Zn = {[0], [1], ..., [n − 1]}.
Theorem 7.13 If [a0 ] = [a] ∧ [b0 ] = [b] then [a0 ] +n [b0 ] = [a] +n [b].
7.7 Exercises
Solve the following questions:
Q1: Consider G = {a0 , a1 , ..., a6 }, and let ∗ defined as a binary
operation
on G as follows;
ai ∗ aj = ai+j ; if i + j < 7
ai ∗ aj = ai+j−7 ; if i + j ≥ 7
Is G, ∗ a group? Give logical reasons.
Q2: Let (G, ∗) be a commutative group. Prove that
(a ∗ b)n = an ∗ bn , ∀a, b ∈ G, n ∈ Z.
Q3: If (G, ∗) is a group, such that (a∗b)2 = a2 ∗b2 , ∀a, b ∈ G. Prove
that (G, ∗) is a commutative group.
Q4: Give an example in the group S3 with two elements x, y such
that
(x ◦ y)2 6= x2 ◦ y 2 .
Q5: Consider (G, ∗) such that O(G) = 3. Prove that (G, ∗) is a
commutative group.
Q6: Let (G, ∗) be a group such that O(G) = 2k, k ∈ Z+ . Prove
that ∃a 6= e 3 a2 = e, where e is the identity element.
Q7: Prove that a mathematical system (G, ∗) is a group if
(i) ∗ is associative. (ii) Cancellation law is verified in G.
Q8: Let n > 2 and be an integer number. Create a noncommutative
group such that its order is equal to Zn .
Q9: Let n ∈ Z∗ . Define the operation δn on Z∗ as follows: [a]δn [b] =
[ab]. Prove that:
(i) δn is a binary operation on Zn . (ii) Is the mathematical system
(Zn , δn ) is a group? Explain your answer logically.
Q10: Prove that any noncommutative group has at least six
elements.
Q11: Let a ≡ b(mod n). Prove that ca ≡ cb(mod cn).
Q12: If x ∈ [0, 15) then solve the equation 3x ≡ 6(mod 15).
Q13: Prove that 6n ≡ 6(mod 10), ∀n ∈ Z+ .
Q14: Prove that the ordered pair ({0, 4, 8, 12} , +16) is a group.
Q15: Prove that the integer number n is divisible on q if and only
if its summation of numbers is divisible on q.
228 Foundations of Mathematics
7.8 Subgroups
Definition 7.26 Let φ 6= H ⊆ G, and (G, ∗) be a group. The binary
(H, ∗/H) is a subgoup of (G, ∗) if and only if (H, ∗/H) is a group,
and ∗/H is a restriction binary operation on H × H(Hungerford, 1974;
Dummit and Foote, 2004a).
Note: For convenience, we use (H, ∗) instead of (H, ∗/H).
Example 7.25 Consider the group (Z, ∗). and let H be a set of all
multiples of the number 3 then (H, ∗) is a nontrivial subgroup of (Z, ∗).
(i) a, b ∈ H → a ∗ b ∈ H.
(ii) a ∈ H → a−1 ∈ H.
Binary Operations and Groups 229
Proof Suppose that (H, ∗) is a subgroup of the group (G, ∗), and let
a, b ∈ H.
∵ b ∈ H → ∃b−1 ∈ H.
∵ ∗ is a binary operation,
∴ a, b−1 ∈ H → a ∗ b−1 ∈ H.
Conversely, suppose that H ⊆ G, in which, a, b ∈ H → a ∗ b−1 ∈ H
...(1).
Now, we have to prove (H, ∗) is a subgroup of (G, ∗).
∵ H 6= φ,
∴ there is at least one element like a ∈ H.
From (1), we get that a ∗ a−1 = e ∈ H.
Or, H contains of the identity element.
Again, from (1), e ∗ a−1 = a−1 ∈ H.
Or, ∀a ∈ H → ∃a−1 ∈ H.
∴ (H, ∗) is a group.
230 Foundations of Mathematics
Proof Let a ∈ H.
∵ H is closed on ∗,
∴ a2 = a ∗ a ∈ H, a3 = a2 ∗ a ∈ H, .... and so on.
In general, am ∈ H, m ∈ Z+ .
Let, S = {a, a2 , ...}.
Note that each element in S is an element in H.
Thereby, the set is nonempty infinite, S is a subset of the finite set,
and this is contradiction.
So, there is a repetition of elements of S. Or there are integer
numbers like r, s, r > s > 0 ∧ ar = as .
Binary Operations and Groups 231
But, as ∗ ar−s = as .
∵ ar = ar ∗ e = as ∗ e,
∴ as ∗ ar−s = as ∗ e,
Thereby, according on cancellation law in G, we get ar−s = e.
∵ r − s > 0,
∴ ar−s ∈ H.
∴ e ∈ H.
∵ r − s > 0 → r − s − 1 ≥ 0,
∴ ar−s−1 ∈ H.
It should be noted that, a ∗ ar−s−1 = ar−s = e.
Or, a ∗ ar−s−1 = e.
∴ a−1 = ar−s−1 is the inverse for a.
Thereby, we have proved that a ∈ H → a−1 ∈ H.
Thus, (H, ∗) is a subgroup of the group (G, ∗).
Note: The opposite of the theorem is incorrect. Or, consider a
group (G, ∗), and infinite φ 6= H ⊂ G. If H is closed set on ∗, it is
not necessary (H, ∗) be a subgroup of the group (G, ∗), as shown in the
following example.
Example 7.27 Consider the group (G, ∗), and the set of N.
Although N is closed on the ordinary addition, but (N, +) is not
subgroup of (N, +).
Proof ∵ e ∈ H1 ∧ e ∈ H2 ,
∴ H1 ∩ H2 6= φ.
Suppose that a, b ∈ H1 ∩ H2 .
∴ a, b ∈ H∧ a, b ∈ H2 .
∴ a ∗ b−1 ∈ H1 (According on Theorem 7.16).
In the same way ∴ a ∗ b−1 ∈ H2 (According on Theorem 7.16).
∴ a ∗ b−1 ∈ H∩ H2 .
Thereby, a, b ∈ H1 ∩ H2 → a ∗ b−1 ∈ H1 ∩ H2 .
Thus, (H1 ∩ H2 , ∗) is a subgroup of (G, ∗).
Note: The opposite of the theorem is incorrect. Or, if each of
(H1 , ∗), (H2 , ∗) are subgroups on the group (G, ∗) then in general
232 Foundations of Mathematics
Example 7.28 Consider the group (Z, +), and the sets
H1 = {..., −4, −2, 0, 2, 4, ...} , H2 = {..., −6, −3, 0, 3, 6, ...}.
Each of (H1 , +), (H2 , +) are subgroups of the group (Z, +), while
(H1 ∪ H2 , +) is not a subgroup of (Z, +). For example, 2, 3 ∈ H1 ∪ H2
but 2 + 3 = 5 ∈/ H1 ∪ H2 .
Theorem 7.19 Let each of (H1 , ∗), (H2 , ∗) be a subgroup of (G, ∗).
The (H1 ∪ H2 , ∗) is a subgroup of (G, ∗) if and only if H1 ⊆ H2 ∨ H2 ⊆
H1 .
Proof Let h1 , h2 ∈ H.
∴ h1 = ar , h2 = as , r, s ∈ Z.
∵ h1 ∗ h−1 r
2 = a ∗ (a )
s −1
= ar ∗ a−s = ar−s ∈ H.
∴ (H, ∗) is a subgroup of (G, ∗) (Theorem 7.16).
Note: To convenience, we denote {an |n ∈ Z} by (a).
Theorem 7.21 If ((a), ∗) is a finite cyclic group with the rank n then
(a) = {e, a, a2 , ..., an−1 }.
Proof Since the set (a) is a finite, thereby the powers of it can not
be differentiated.
∴ ∃i, j ∈ Z 3 ai = aj , 0 < i < j.
∴ ai ∗ a−i = aj ∗ a−j
∴ a0 = aj−i → e = aj−i .
Let us suppose that W = k ∈ Z+ |ak = e
∵ aj−i 3 j − i > 0 → W 6= φ.
∴ W is well ordered set, implies W has a minimal element.
Suppose that m is a minimal element for W .
Or, am = e.
Since ak 6= e, 0 < k < m.
Let S = {e, a, a2 , ..., am−1 },
Thereby, the elements of S are differentiated, and ∴ S ⊆ (a) ...(1).
Because if ar = as 3 0 ≤ r < s ≤ m − 1 → as−r = e.
But, s − r < m, and this is contradiction, thus S is differentiated.
Now, we have to prove, (a) ⊆ S.
Suppose that b ∈ (a).
∴ b = a1 3 1 ∈ Z.
Now, based on division algorithm, we have 1 = qm + r 3 q, r ∈
Z, 0 ≤ r < m.
Thereby, a1 = amq+r = amq ∗ ar = (am )q ∗ ar = eq ∗ ar = e ∗ ar = ar
∴ a1 = ar .
∵ ar ∈ S,
∴ b ∈ S.
∴ (a) ⊆ S ...(2).
Thus, from (1)&(2), (a) = S.
Or, (a) = {e, a, a2 , ..., am−1 } → m = n.
Binary Operations and Groups 235
Example
√ 7.31 Let (G, ∗) be a group, in which G = {1, −1, i, −1} , i =
−1, and ∗ is the ordinary multiplication operation.
It should be noted that 1 is the identity element, and 11 =
1, (−1)2 = 1, (i)4 = 1, (−i)4 = 1.
∴ O(1) = 1, O(−1) = 2, O(i) = 4, O(−i) = 4.
(2) Consider the cyclic group (G, ∗) with order of r, generated by
a ∈ G. Or, G = {e, a, a2 , ..., a5 }.
It should be noted that a6 = e, (a2 )3 = a6 = e, (a3 )2 = a6 =
e, (a4 )3 = a12 = e, (a5 )6 = a30 = e.
∴ O(6) = 6, O(a2 ) = 3, O(a3 ) = 2, O(a4 ) = 3, O(a5 ) = 6.
Proof Let x ∈ HH → x = h1 ∗ h2 , h1 , h2 ∈ H.
∵ h1 , h2 ∈ H → h∗ h2 ∈ H.
∴ x ∈ H.
∴ HH ⊆ H...(1).
Conversely, let y ∈ H → y ∗ e ∈ HH.
∵e∈H
∵ y ∗ e = y,
∴ y ∈ HH...(2).
From (1)&(2), HH = H.
Example 7.34 (1) Let (H, ∗) be a subgroup of the group (G, ∗). H
will be a right coset and left coset for itself because
H ∗ e = {h ∗ e|h ∈ H} = {h|h ∈ H} = H.
∴ H ∗ e = H.
Also, e ∗ H = {e ∗ h|h ∈ H} = {h|h ∈ H} = H.
∴ e ∗ H = H.
(2) Let H = {..., −6, −3, 0, 3, 6, ...}. The following sets are right
cosets of H in G:
H + 0 = {h + 0|h ∈ H} = H.
H + 1 = {h + 1|h ∈ H} = {..., −5, −2, 1, 4, 7, ...}.
H + 2 = {h + 2|h ∈ H} = {..., −4, −1, 2, 5, 8, ...}.
.
.
.
Binary Operations and Groups 237
Also,
0 + H = {0 + h|h ∈ H} = H.
1 + H = {1 + h|h ∈ H} = {..., −5, −2, 1, 4, 7, ...}.
2 + H = {2 + h|h ∈ H} = {..., −4, −1, 2, 5, 8, ...}.
.
.
.
(i) a ∗ H = H ↔ a ∈ H.
(ii) H ∗ a = H ↔ a ∈ H.
∴ a ∈ a ∗ H.
Thus, a ∈ H.
(ii) It can be proved in the same way.
(i) H ∗ a = H ∗ b ↔ a ∗ b−1 ∈ H.
(ii) a ∗ H = b ∗ H ↔ b−1 ∗ a ∈ H.
Corollary
(a) H ∗ a ∩ H ∗ b = φ ∨ H ∗ a = H ∗ b.
(b) a ∗ H ∩ b ∗ H = φ ∨ a ∗ H = b ∗ H.
(ii) If (H, ∗) is a subgroup of the group (G, ∗) then the set of all
right(left) cosets of H in G will be a partition of G.
Binary Operations and Groups 239
Proof (i) (a) Suppose that c is a common element between the right
coset H ∗ a and the left coset H ∗ b.
∵ c ∈ H ∗ a,
∴ ∃h1 ∈ H 3 c = h1 ∗ a.
∵ c ∈ H ∗ b,
∴ ∃h2 ∈ H 3 c = h2 ∗ b.
Thereby, h1 ∗ a = h2 ∗ b.
∴ h−1 −1
2 ∗ (h1 ∗ a) = h2 ∗ (h2 ∗ b)
(h−1 −1
2 ∗ h1 ) ∗ a = (h2 ∗ h2 ) ∗ b = e ∗ b = b.
∴ (h−12 ∗ h1 ) ∗ a = b.
Also, [(h−12 ∗ h1 ) ∗ a] ∗ a
−1
= b ∗ a−1 ,
∴ (h−1 −1
2 ∗ h1 ) ∗ (a ∗ a ) = b ∗ a ,
−1
−1
∴ (h2 ∗ h1 ) ∗ e = b ∗ a−1 .
∴ h−12 ∗ h1 = b ∗ a .
−1
∵ h−12 , h1 ∈ H,
∴ h−12 ∗ h1 ∈ H.
∴ b ∗ a−1 ∈ H.
∴ H ∗ b = H ∗ a.
Thus, we conclude that if there is a common element between the
right coset H ∗ a and the right coset H ∗ b then the cosets will be equal.
In addition, if there is no common element between them, then they
are separate.
(b) In the same way, we can proof it.
(ii) The proof is left as an exercise to the reader. ,
Theorem 7.26 If (H, ∗) be a subgroup of the finite group (G, ∗), then
O(H) divides O(G) i. e. O(H)
O(G)
.
∴ O(H ∗ ai ) = n, ∀i = 1, 2, ..., k − 1.
∴ O(G) = |m + m{z+ ...m}.
k−times
∴ n = km, k ∈ Z+ .
∴ O(H) divides O(G).
Thus, O(H)
O(G)
.
Definition 7.33 Let (H, ∗) be a subgroup of the group (G, ∗). The
index of (H, ∗) in (G, ∗) is a numbers of the different right cosets of
H in G, and denoted by iG (H) (Fraleigh, 2003; Joshi, 1989; Rotman,
2013; Miller, 2012; Scott, 2012; Scott, 1987).
O(G)
Note: If (G, ∗) is the finite group, then iG (H) = O(H)
.
Example 7.35 Consider the (Z, +), and H = (3). The (H, +) is
subset of the group (Z, +). The different right cosets of H in G are
H + 0 = H, H + 1, H + 2.
Thus, iG (H) = 3.
Corollary
Example 7.36 (1) Consider the group (R, +), then (Z, +) will be a
normal subgroup of (R, +) because
(a) (Z, +) is subgroup of (R, +).
(b) ∀a ∈ R, h ∈ Z|a + h − a = h ∈ Z.
In general, every subgroup of a commutative group is a normal
subgroup.
x 1 x2 x3
(2) Consider S3 , H = {e, ψ}, where ψ = It should be
x2 x1 x3
noted that H is a nonnormal subgroup.
x 1 x 2 x 3
While Γ = {e, λ, λ2 }, where λ = is a normal
x2 x3 x1
subgroup.
Proof Suppose that (H, ∗) is a normal subgroup of the group (G, ∗).
So, based on the Theorem 7. 27, a ∗ H ∗ a−1 = H, ∀a ∈ G.
∴ (a ∗ H ∗ a−1 ) ∗ a = H ∗ a,
∴ a ∗ H = H ∗ a.
Thus, every right coset, it is also a left coset.
Conversely, suppose that every right coset, it is also a left coset, and
let a ∈ G.
So, H ∗ a = {h ∗ a|h ∈ H} is a right coset.
∵ e ∈ H,
∴ e ∗ a ∈ H ∗ a.
∵ e ∗ a = a,
∴ a ∈ H ∗ a.
Now, it should be noted that if left coset equal to the right coset
(H ∗ a) has to contain of a. Suppose that L is represents to left coset,
and contains of a.
∵ a ∗ H is also contains of a.
∴ a ∈ L ∧ a ∈ a ∗ H.
∴ according to the Corollary of Theorem 7.24, L = a ∗ H.
∴ a ∗ H is a unique left coset equal to H ∗ a.
244 Foundations of Mathematics
Now, we have H ∗ a = a ∗ H.
∴ H ∗ a ∗ a−1 = a ∗ H ∗ a−1 ,
∴ H = a ∗ H ∗ a−1 , ∀a ∈ G.
Thus, (H, ∗) is a normal subgroup of the (G, ∗).
∵ h−1
1 ∈ H,
∴ h−1
1 H = H.
∵ h−1 −1 −1
1 ∗ [(h1 ∗ a) ∗ (h ∗ a )] = a ∗ h ∗ a ,
−1
∴ a ∗ h ∗ a ∈ H.
Thus, (H, ∗) is a normal subgroup of the group (G, ∗).
7.10 exercises
Solve the following questions:
Q1: Let G be a group, and W ⊆ G. Consider (W ) the set of all
elements of G in which represented as a multiply finite sets of W to the
power integer number. Prove that (W ) is a subgroup of G [Hint: (W )
is a subset of G generated by W ].
Q2: If G is a group, and O(G) = P , and P is a prime number.
Prove that G is a cyclic group.
Q3: If each of H, K are subgroups of the group G. Prove that HK
is a subgroup of G if and only if HK = KH.
Q4: If each of H, K are subgroups of the commutative group G.
Prove that HK is a subgroup of G.
Q5: Consider a finite group G in which O(G) = P q, P, q are prime
numbers and P > q. Prove that G has at most a unique subgroup in
order P .
Q6: If each of H, K are subgroups of the commutative group G,
in which O(H) = n, O(K) = m. Prove that G has a subgroup L
where O(L) = [n, m] [Hint: [n, m] is the simple common multiple of
the numbers [n, m].
Q7: Let a ∈ G, and define N (a) = {x ∈ G|Xa = aX}. Prove that
N (a) is a subgroup of G [Hint: N (a) is called a normalizer of a in G ].
Q8: Let G be a group, and define ZG = {z ∈ G|zx = xz, ∀x ∈ G}.
Prove that ZG is a subgroup of G [Hint: ZG is called a center of G ].
Q9 Prove that any subgroup of a cyclic group is a cyclic group.
Q10: Let G be a cyclic group in order n. How many generators
have G? Prove your answer.
248 Foundations of Mathematics
Example 7.38 Consider the groups (G, ∗), (G0 , ◦), and the mapping
f : G → G0 , defined as f (a) = ē, ∀a ∈ G where ē is the identity element
in G0 .
The mapping f : G → G0 is a homomorphism from (G, ∗) to (G0 , ◦),
because ∀a, b ∈ G
f (a ∗ b) = ē, f (a) = ē, f (b) = ē.
On the other hand, f (a) ◦ f (b) = ē ◦ ē = ē.
∴ f (a ∗ b) = f (a) ◦ f (b) = ē.
Binary Operations and Groups 249
Example 7.39 Consider the groups (R, +), R − {0}, and the mapping
f : (R → R − {0} defined as f (a) = 2a , ∀a ∈ R.
The mapping f is homomorphism, because ∀a, b ∈ R, we have
f (a + b) = aa+b , f (a) = 2a , f (b) = 2b .
But, f (a + b) = 2a+b = 2a .2b = f (a).f (b).
Or, f (a + b) = 2a+b = f (a).f (b).
∴ f : (R → R − {0} is a Homomorphism.
∴ iN (a ∗ b) = N ∗ (a ∗ b).
∵ (N, ∗) / (G, ∗),
∴ according Theorem 7.29, N ∗ (a ∗ b) = (N ∗ a)(N ∗ b).
∴ iN (a ∗ b) = (N ∗ a)(N ∗ b) = iN (a)iN (b).
Thus, the mapping is homomorphism.
To prove that the mapping is surjective, let Y ∈ G/N.
∵ Y ∈ G/N,
∴ Y = N ∗ a, ∀a ∈ G.
Let iN (a) = N ∗ a.
∴ ∀N ∗ a ∈ G/N∃a ∈ G|iN (a) = N ∗ a.
∴ iN : G → G/N.
Now, we have to prove that ker(iN ) = N.
It should be noted that ker(iN ) ={a ∈ G|iN (a) = N} ={a ∈ G|N ∗ a = N} =
{a ∈ G|a ∈ N} = N.
∴ keriN = N.
7.11.2 Isomorphism
Definition 7.38 If (G, ∗), (G0 , ◦) are groups, and f : G → G0 be a
mapping then f is an isomorphism if and only if it is a homomorphism
and injective mapping (Dummit and Foote, 2004a; Lang, 2002b).
Example 7.41 (1) Let G = (R, +), G0 = (R−{0} , .), and the mapping
f : G → G0 , in which f (a) = 2a .
(a) f is a homomorphism. (b) f is an injective function because
f (a) = f (b) ↔ 2a = 2b ,
2a = 2b ↔ a = b, ∀a, b ∈ G.
∴ f : G → G0 is an isomorphic mapping.
It should be noted that f is not surjective function. Thereby f is
called isomorphic embedding.
(2) Let G = (Z, +), G0n = (Zn , +n ), and f : G → G0n be a mapping
in which f (x) = [x], ∀x ∈ G.
For illustrating, let n = 6, we find that
f (20) = [20] = [2], and note that f (26) = [26] = [2].
∴ f is not injective.
Thus, f is not isomorphic mapping from G to G0n .
254 Foundations of Mathematics
Definition 7.39 It is said that the two groups (G, ∗), (G0 , ◦) are
isomorphic if and only if there is a complete isomorphic between them,
and denoted by (G, ∗) ≈ (G0 , ◦) (Dummit and Foote, 2004a; Lang,
2002b; Herstein, 1975; Herstein, 1996; Herstein, 2006).
Note:
(i) (a) G ≈ G.
(b) G ≈ G0 → G0 ≈ G.
(c) (G ≈ G0 ) ∧ (G0 ≈ G00 ) → (G ≈ G00 ).
(a) f is a surjective.
(b) ker(f ) = (0).
Proof Consider the Figure 7.1, where ρ(g) = wg, and ρ : G → G/W
is the canonical mapping.
The aim is to complete the figure into Figure 7.2, where ψ : G/W →
G0 is a mapping and defined as follows
X ∈ G/W in which X = W G, ∀g ∈ G.
Now, we define ψ(wg) = ϕ(g). The defined function is
Binary Operations and Groups 255
ϕ
G ..........................................................................................................................................................
... G0
.....
...
...
...
...
...
...
...
...
ρ ...
...
...
...
...
...
...
...
..
.........
........
...
G/W
ϕ
G ................................................................................................................................................................
... .............
.......
G0
..... .....
... ......
... ...
......
.... ......
.....
... ......
......
...
... ..
......
.
.
... ......
.....
ρ ...
...
.....
......
.....
ψ
... ...
..
... ......
.....
... .....
... ......
... .
..
......
..
... ......
.....
........ ..........
........ .......
.........
.
G/W
∵ ψ(W g) = ψ(g),
∴ ψ(g) = ē.
Thereby, g ∈ kerϕ = W → W g = W .
∴ W g ∈ kerϕ → W g = W .
∴ kerϕ = W .
Thereby, ψ is surjective homomorphism and injective from G/W to
G0 .
Thus, G
W
≈ G0 .
7.12 Exercises
Solve the following questions:
Q1: Verify a homomorphism of the following mapping if they are
isomorphic mapping then find kernel of them.
(a) φ : (R − {0} , .) → G0 , where φ(x) = x2 , ∀x ∈ G.
(b) φ : (R, +) → G0 , where φ(x) = x + 1, ∀x ∈ G.
(c) Let G be a commutative group, and φ : G → G0 , where φ(x) =
x5 , ∀x ∈ G.
Binary Operations and Groups 257
(i) Log : R+ → R.
(ii) Exp : R → R+ .
Q9: Consider the group (Z6 , +), the integers from 0 to 5 with
addition modulo 6. Also consider the group (Z2 × Z3 , +), the ordered
pairs where the x− coordinates can be 0 or 1, and the y− coordinates
can be 0, 1, or 2, where addition in the x−coordinate is modulo 2 and
addition in the y−coordinate is modulo 3.
Are these structures isomorphic under addition, under the following
scheme?
(0, 0) → 0
(1, 1) → 1
(0, 1) → 2
(1, 0) → 3
(0, 1) → 4
(1, 2) → 5
In general (a, b) → (3a + 4b) mod 6
258 Foundations of Mathematics
8.1 Introduction
et each of n, m ∈ N, and let us try to solve the equation m + x =
L n, ∀x ∈ N. We will see that, we often fail to solve this equation,
because we do not find an additive inverse for every element in N. This
imposes us to recourse another system than N to recover this drawback.
Of course, a new system should contains N in order not to lose the
advantages of this system in dealing with other situations, and we call
the new system the integer numbers Z.
There are two methods to creating N:
8.2 Construction of Z
Definition 8.1 If (m, n), (p, q) ∈ N × N then (m, n)R(p, q) if and only
if m+q = p+n, and it is called relation (R) on the set N×N (Mendelson,
1973; Frobisher, 1999; Campbell, 1970).
Example 8.3 (1) If a = (2, 3), b = (4, 5), then a + b = [2, 3] + [4, 5] =
[2 + 4, 3 + 5] = [6, 8], and a · b = [2, 3] · [4, 5] = [2 · 4 + 3 · 5, 2 · 5 + 3 · 4] =
[23, 22].
(2) If a = (−3, 0)], b = (7, −4), then a + b = [4, −4], a · b = [−21, 12].
(i) −(−a) = a.
(ii) a + (−b) = a − b.
(iv) (a − b) + (b − c) = a − c.
(v) −(a − b) = b − a.
= [m, n] · [p + r, q + t]
= [m · (p + r) + n · (q + t), m · (q + t) + n · (p + r)]
= [(m · p + m · r) + (n · q + n · t), (m · q + m · t) + (n · p + n · t)]
= (m · p + n · q) + (m · r + n · t), (m · q + n · p) + (n · t + n · r)
= [(m · p + n · q, m · q + n · p)] + [m · r + n · t, m · t + n · r]
= [m, n] · [p, q] + [m, n] · [r, t]
=a·b+a·c
similarly, (b + c) · a = b · a + c · a.
8.4 Rings
Definition 8.5 If A 6= φ, and ∗, # are binary operations on A then
the ordered triple (A, ∗, #) is a ring if
Definition 8.6 The ring (A, ∗, #) called the commutative ring if the
operation ∗ is commutative, and it is called the ring with an identity
if there exists an identity element with to # (Atiyah and Macdonald,
1969; Balcerzyk and Józefiak, 1989; Poonen, 2019).
Notation: (1) We will call the binary operations ∗, # addition
and multiplication respectively, and denote them by +, ·, respectively.
This does not mean that the operations are a usual addition and
multiplication.
(2) For convenient, we write (A, +, ·) instead of (A, ∗, #), and denote
to the identity element in the (A, ∗) by 0A .
(i) a · 0A = 0A · 0 = 0A .
268 Foundations of Mathematics
(iv) a · (b − c) = a · b − a · c.
(v) (a − b) · c = a · c − b · c.
∴ a = 0A .
This is contradiction, thereby 0A 6= 1A .
a b
Example 8.5 Let M = be the set of all matrices where
c d 2×2
a, b, c, d ∈ Z.
The
binary operation
defined on Mas follows;
a b e f ae + bg af + bh
= .
c d g h ce + dg cf + dh
The
binary ⊕ defined on
operation M as follows;
a b e f a+e b+f
⊕ = .
c d g h c+g d+h
The mathematical
system (M, ⊕, ) is noncommutative ring with
1 0
identity element .
0 1
Example
8.6 To illustrate,
noncommutative
ring,if
3 4 0 2 36 10
x= ,y = , then xy = , while
5 −1
−9 9 9 1
10 −2
yx = .
32 35
Example
8.7 It should be noted that A 6= 0, B 6= 0, but AB =
0 0
= 0, as shown below;
0 0
0 5 6 7 0 0
A= ,B = , while BA = .
0 13 0 0 0 0
8.5 Homomorphism
Definition 8.9 The mapping ψ : A → A0 from a ring A to a ring A0 is
called a homomorphism if ∀a, b ∈ A, then (1) ψ(a + b) = ψ(a) + ψ(b).
(2) ψ(a·b) = ψ(a)·ψ(b) (Artin, 1991; Hazewinkel et al., 2004; Bourbaki,
1989b).
Note: (i) The binary operations +, · on the left of (1), (2) are
defined on the ring A. (ii) The binary operations +, · on the right of
(1), (2) are defined on the ring A0 .
√ √ √
(1) If x, y ∈ Z 5, then x = a1 + b1 √ 5 ∧ y = a2 + b2 5. √
∵ ψ(x√ + y) = ψ(a1√ + a2 ) + (b1 + b2 ) 5 = a1 + a2 + (b1 − b2 ) 5 =
(a1 − b1 5) + (a2 − b2 5) = ψ(a) + ψ(b).
In the same way, we can get ψ(xy) = ψ(a)ψ(b).
∴ ψ is a homomorphism.
(2) We have to prove that ψ√is injective homomorphism.
√
If ψ(x) = ψ(y), then a1 + b1 5 = a2 + b2 5.
∴ a1 = a2 , b1 = b2 ,
∴ x = y.
(3) ψ is a surjective homomorphism.
Thus, from (1), (2), and (3), ψ is Automorphism.
Example 8.12 The ring (Z, +, ·) 6≈ (Zn , +n , ·n ), because does not one
to one correspondence between Z and Zn . For convenient, there is
Z 6≈ Zn .
Example 8.13 Consider the ring (A, ⊕, ) with the identity element
1. Define the operations ⊕, on A as follows;
x ⊕ y = x + y + 1, x y = xy + x + y, ∀x, y ∈ A.
The ring (A, +, ·) ≈ (A, ⊕, ), because if we have a mapping ψ :
A → A, such that ψ(x) = x − 1, we have;
(1) The mapping is isomorphic
ψ(x + y) = x + y − 1 = x − 1 + y − 1 + 1 = ψ(x) + ψ(y) + 1 =
ψ(x) ⊕ psi(y).
In the same way ψ(xy) = ψ(x) ψ(y).
(2) The mapping is surjective
y ∈ A → y = x + 1 ∈ A.
The Integer Numbers 273
∴ ψ(y) = y − 1 = x + 1 − 1 = x.
(3) The mapping is injective
ψ(x) = ψ(y) → x − 1 = y − 1 → x = y.
From (1), (2) & (3), we get ψ : A → A is isomorphic.
Thus, (A, +, ·) ≈ (A, ⊕, ).
It should be noted that
(1) −1 is the identity element with respect to ⊕ such that
x ⊕ (−1) = a + (−1) + 1 = a.
(2) 0 is the identity element with respect to such that
a 0 = a · 0 + a + 0 = a.
Definition 8.15 Let U be an ideal in the ring (A, +, ·), and let the
set UA = {a + U |a ∈ A}. Define the binary operations ⊕, on UA as
follows;
(a + U ) ⊕ (b + U ) = (a + b) + U ,
(a + U ) (b + U ) = ab + U , (Mustafa et al., 1980; Jacobson, 2012;
Hungerford, 1974; Artin, 1991; Dummit and Foote, 2004a).
Example 8.15 Consider the ring (Z, +, ·), and let U = (7), then z
U
=
{a + U |a ∈ Z}.
Assume that a = 7b + r, b ∈ Z, 0 ≤ r < 7.
∴ a + U = (7b + r) + U = r + U .
Now, let us define that
Z
(7)
= {0 + U = U, 1 + U, 2 + U, ..., 6 + U },
Z
τ : (7) → Z7 3 τ (a + (7)) = a.
276 Foundations of Mathematics
Z
So that τ : (7) → Z7 will be isomorphism.
Z
Thereby, (7) ≈ Z7 .
Note: Generally, Z
(n)
≈ Zn .
8.7 Exercises
Answer the following questions:
Q1: Let I1 = [2, 5], I2 = [4, 7]. Prove that I1 = I2 .
Q2: Evaluate each of
(i) ([3, 1] + [5, 8]) + [8, 3]. (ii) [4, 3] · ([1, 2] + [4, 2]). (iii) ([7, 4] · [5, 3]) ·
[2, 2]. (iv) [9, 3] − [10, 19].
Q3: (i) Is ([5, 3] ÷ [0, 5]) ∈ Z? (ii) Evaluate [3, 15] ÷ [8, 4].
Q4: Let (A, +, ·) be a ring, such that x2 = x, ∀x ∈ A. Prove that
(A, +, ·) is the Boolean ring (commutative ring).
Q5: Let (A, +, ·) be a commutative ring with the identity element.
Prove that (A, +, ·) is an integral domain if and only if (ab = ac) ∧ (a 6=
0) → b = c.
Q6: Let A be a set of all real continuous functions defined on [a, b].
Define the addition and multiplication on A so that it becomes a ring.
Define τ A → R such that τ (f (x)) = f (1/2). Prove that
(i) τ is homomorphism. (ii) find ker τ .
Q7: Consider U an ideal in A such that 1 ∈ U . Prove that U = A.
Q8: If each of U, V an ideal in A, such that U + V =
{u + v|u ∈ U, v ∈ V }. Prove that U + V is the ideal in A.
Q9: Let (A, +, ·), U = (17). Prove that if there is an ideal V in Z
such that U ⊂ V ⊂ Z, then V = Z ∨ V = U .
Q10: Consider the ring (A, +, ·) with the identity element 1, and
the ring (A0 , +0 , ·0 ). If τ A → A0 is a surjective homomorphism, then
τ (1) is the identity element for the ring (A0 , +0 , ·0 ).
Q11: Consider the ring (A, +, ·) with the identity element 1, and
let τ : A → D be a homomorphism, such that (D, ⊕, ) is the integral
domain and ker τ 6= A. Prove that τ (1) is the identity element in D.
The Integer Numbers 277
Proof (1) ∵ a ≤ a, ∀a ∈ Z,
∴≤ is a reflexive relation.
(2) Suppose that (a ≤ b) ∧ (b ≤ a).
The expression a ≤ b → b − a ∈ Z+ ∨ a = b.
Also, b ≤ a → a − b ∈ Z+ ∨ b = a.
∴ b − a ∈ Z+ ∧ a − b ∈ Z+ .
But, a − b = −(b − a) → b − a, −(b − a) ∈ Z+ , and this is a
contradiction.
∴ a − b = b − a = 0 → a = b.
∴≤ is an anti-symmetric relation.
(3) The ≤ is a transitive relation.
Thereby, from (1), (2)& (3), the ≤ is a partially ordered relation.
Now, we have to prove that any two elements a, b ∈ Z are
comparable.
∵ b − a ∈ Z,
∴ b − a ∈ Z+ ∨ −(b − a) ∈ Z+ ∨ a = b.
∴ b > a ∨ a > b ∨ a = b → a ≥ b ∨ b ≥ a.
Thus, (Z, ≤) is a totally ordered set.
Proof ∵ a, b ∈ Z+ ,
∴ a = [n + 1, 0], b = [m + 1, 0], ∀n, m ∈ N.
a · b = [n + 1, 0] · [m + 1, 0] = [nm + n + m + 1, 0] = [r + 1, 0], r =
nm + n + m ∈ N.
∴ a · b ∈ Z+ .
Corollary If 0 6= a, b ∈ Z then ab 6= 0.
The Integer Numbers 281
Proof From Theorem 8.16, 8.17, 8.21, we get the Definition 8.23 and
its three conditions.
Thereby, Z+ will be the set of positive elements in Z.
Theorem 8.26 Consider the integral domain (A, +, ·), and let A+ be
the set of positive elements in A, then
(1) The subset T in A×A defined as (a, b) ∈ T ↔ a = b∨b−a ∈ A+
will be a total ordered relation on A.
(2) If the relation ≤ on A defined as a ≤ b ↔ (a, b) ∈ T , then
(A, +, ·, ≤) will be integral domain.
(3) A+ = {a|a > 0A )}.
Proof ∵ a 6= 0,
∴ a ∈ A+ ∨ −a ∈ A+ .
If a ∈ A+ → a · a = a2 ∈ A+ .
If −a ∈ A+ → (−a) · (−a) = a2 ∈ A+ .
∴ a2 ∈ A + .
∵ IA 6= 0 → IA · IA will be a positive.
∵ IA · IA = IA → IA > 0.
Note: If a, b ∈ Z, then ab = 1 ↔ a = b = ∓1.
8.9 Embedding
Definition 8.24 Let ENZ : N → Z be a mapping, such that
The Integer Numbers 285
Proof Let m, n ∈ N.
(1) Preserving on addition.
∵ m, n ∈ N,
∴ E(m + n) = [m + n, 0] = [m, 0] + [n + 0] = E(m) + E(n).
∴ E preserves on addition.
(2) Preserving on multiplication.
∵ m, n ∈ N,
∴ E(mn) = [mn, 0] = [m, 0] · [n, 0] = E(m) · E(n).
∴ E preserves on multiplication.
(2) Preserving on ordinal.
∵ m, n ∈ N, and let E(m) ≤ E(n) ↔ [m, 0] ≤ [n, 0], ∀m, n.
∵ [m, 0] ≤ [n, 0] ↔ [n, 0] − [m, 0] ∈ Z+ ∨ m = n.
↔ [n, 0] + [0, m] ∈ Z+ ∨ m = n,
↔ [n, m] ∈ Z+ ∨ m = n,
↔ m < n ∨ m = n,
↔ m ≤ n.
∴ E preserves on ordinal.
∴ from (1), (2)& (3), we get that E : N → Z is isomorphism from
N to Z+ ∪ {0} with respect to addition, multiplication, and ordinal
operation.
Note: ENZ (1) = [1, 0] = IZ .
Notation: We use (1) n instead of [n, 0]. (2) 1 instead of IZ .
8.10 Exercises
Answer the following questions:
Q1: Let (A, +, ·) be a commutative ring with an identity element
1 6= 0 defined on the totally ordered relation ≤, where
(1) a < b → a+c < b+c, ∀a, b, c ∈ A. (2) a < b → ac < bc, ∀a, b, c ∈
A ∧ c > 0.
Prove that (A, +, ·) is an ordered integral domain.
Q2: Consider the ordered integral domain (A, +, ·, ≤). Prove that
A is an infinite set.
Q3: Let Zn ba the set of the integer numbers module n. The system
(Zn , +n , ·n ) is integral domain if and only if n is a prime. Prove that if
n is a prime then the system (Zn , +n , ·n ) can not be an ordered integral
domain.
Q4: If a ∈ Z, then @b ∈ Z 3 a < b < a + 1.
Q5: Any nonempty subset of Z+ has a least element.
Q6: Any nonempty subset of Z− 3 −a ∈ Z+ has a greatest element.
Q7: Let φ 6= A ⊆ Z, where A has a least element. Prove if φ 6=
B ⊆ A, then B has also a least element.
9
The Rational Numbers
9.1 Introduction
n this chapter, we extend the field of integers to another, more
I general, and comprehensive field within it to meet mathematical
necessaries and practical reality. We call the new field the field of
rational numbers, and denote it by Q.
Let us consider the problem ax = b, ∀1 6= a, b ∈ Z. Whenb we are
looking for the value of s in this problem, we find that x = a |a, b ∈ Z .
The value of variable does not belongs to Z. Thereby, it is inevitable
for us to create a field of Q to overcome this defect and drawback in
the field of Z.
We are going to define the addition, multiplication, and partial order
relation on Q denoted them Q+ , Q· , Q≤ respectively. To organizing the
mathematical system (Q, Q+ , Q· , Q≤ ) to be extension of the system
(Z, Z+ , Z· , Z≤ ) with respect to addition, multiplication, and partial
ordered relation.
9.2 Construction of Q
Let us define the equivalence relation on the ordered pairs of integer
numbers in which we call to each equivalence class by rational numbers.
288 Foundations of Mathematics
From now on, we express the order pairs (a, b) in the form of fractions
denoted by ab , b 6= 0. Mathematically, A = {(a, b)|a, b ∈ Z, b 6= 0}
(Rosen and Krithivasan, 2012; Lass, 2009; Robinson, 1996; Weisstein,
2002c).
Example 9.1 Let (2, 3), (10, 15), (1, 3), (7, 8) ∈ A.
(2, 3)R(10, 15) because 2 · 15 = 3 · 10.
∴ [(2, 3)] = [(10, 15)].
While (1, 3) 6R (7, 8) because 1 · 8 6= 3 · 7.
∴ [(1, 3)] 6= [(7, 8)].
Notation: Then the expression (a, b) ∼ (c, d) to indicate that
(a, b), (c, d) ∈ R. It reads (a, b) ≡ (c, d).
= [acbdf + aebd, b2 df ]
= [ac, bd] + [ae, bf ]
= [a, b] · [c, d] + [a, b] · [e, f ]
= x · y + x · z ...(i).
In the same way, (y + z) · z = y · x + z · x ...(ii).
From (i)& (ii) multiplication in distribution over addition.
Thus, from (1), (2)& (3), the system (Q, +, ·) is a commutative ring
with unit element.
Note: The mathematical system (Q, +, ·) is a numerical system,
and called system of the rational numbers.
Notation:
(1) 0Q vee0 is denoted to [0, 1].
(2) −x is denoted to the inverse of x.
(3) IQ ∨ 1Q is denoted to [1, 1].
9.2.2 Fields
Definition 9.4 Let φ 6= A, and ∗, # be binary operations on A. The
mathematical system (A, ∗, #) is called a field if and only if
(1) (A, ∗) is a commutative group.
(2) (A0 , #0 ) is a commutative group where A0 = A\ {0}, 0 is a unit
element with respect to ∗, and #0 is a restriction operation on A0 .
(3) Distribution laws are fulfilled. Or, if ∀x, y, z ∈ A, then:
(a) x · (y + z) = x · y + x · z.
(b) (y + z) · x = (y · x) + (z · x) (Beachy and Blair, 2006; Fraleigh,
2003; McCoy, 1968; Sharpe, 1987).
9.2.3 Subfields
Definition 9.6 Consider the field (A, ∗, #), and φ 6= B ⊆ A. The
mathematical system (B, ∗0 , #0 ) is a field such that ∗0 , #0 are restriction
of ∗, # respectively on B. The system (B, ∗0 , #0 ) is subfield of (A, ∗, #)
(Fraleigh, 2003; Herstein, 1964; Lang, 2004; McCoy, 1968).
294 Foundations of Mathematics
9.3 Exercises
Solve the following problems:
Q1: Prove that every finite integral domain is a field.
Q2: Give an example of a field consists of five elements.
Q3: Give an example of an integral domain that does not form a
field.
Q4: Is there a field with ten elements?
Q5: Consider an integral domain D, and a, b ∈ D. Suppose that
an = bn , am = bm where (m, n) = 1 (m, n are relatively prime). Prove
that a = b.
Q6: Let F be a field, and F [x] = { n0 ai |n ∈ N, ai ∈ F }. Define
P
the operations of addition and multiplication on F [x] in order it be a
ring of polynomials.
Q7: Consider the field (Z15 , +15 , ·15 ). Let S = {[0], [5], [10]} ⊂
Z15 , and T = {[0], [3], [6], [9], [12]} ⊂ Z15 . Prove that each of
(S15 , +15 , ·15 ), (T15 , +15 , ·15 ) is a field.
9.4 Order on Q
In this section we are going to present and deal with a set of element
of Q.
296 Foundations of Mathematics
Theorem 9.8 Let x ∈ Q, (a, b), (c, d) ∈ x. If ab > 0, then cd > 0, and
vise versa.
Proof Let x, y ∈ Q+ .
(1) ∴ x = [a, b], y = [c, d] where (ab > 0) ∧ (cd > 0), a, b, c, d ∈ Z.
∵ x + y = [a, b] + [c, d] = [ad + cb, bd] where (ad + cb) · bd =
a · b · d · d + c · d · b · d.
∴ x + y ∈ Q+ .
(2) x · y = [a, b] · [c, d] = [ac, bd], where (ac)(bd) = (ab)(cd) > 0.
∴ x, y ∈ Q+ .
(3) By using the Trichotomy Property (Marsden et al., 1993; Bear,
1997; Patrick, 1960; Takeuti and Zaring, 2013; Suppes, 1960; Suppes,
1972) in Z, only one of the following relationships can be satisfied;
(a) ab > 0. (b) ab = 0. (c) −(ab) > 0.
Now, if
(a) ab > 0 ↔ x ∈ Q+ .
(b) ab > 0 ↔ a = 0 ∧ b 6= 0, Z is the integral domain.
Or, ab = 0 ↔ x = [0, b] = 0.
(c) −(ab) > 0 = −(a) · b = −ab > 0 ↔ [−a, b] = −x ∈ Q+ .
The Rational Numbers 297
∴ x ∈ Q+ ∨ x = 0 ∨ −x ∈ Q+ .
∴ Q+ is a positive elements of Q.
Now, lut us utilize Q+ to define a partial ordered relation on Q.
Proof (1) ∵ x ≤ x, ∀x ∈ Q,
∴≤ is a reflexive relation.
(2) Suppose that x ≤ y, y ≤ x.
∵ x ≤ y → (x = y) ∨ (y − x ∈ Q+ ).
∵ y ≤ x → (y = x) ∨ (x − y ∈ Q+ ).
∵ y − x ∈ Q+ → −(y − x) ∈ Q+ .
This is a contradiction because Q+ consists of the positive elements
only.
∴ x = y.
In the same way, we can prove the other hypothesis (Have is to the
reader).
∴≤ is anti symmetric relation.
(3) Suppose that x ≤ y, y ≤ z, ∀x, y, z ∈ Q+ .
x ≤ y → (x = y) ∨ (x < y).
y ≤ z → (y = z) ∨ (y < z).
∵ (x < y) ∧ (y < z),
∴ (y − x) ∈ Q+ ∧ (z − y) ∈ Q+ .
∴ (y − x) + (z − y) ∈ Q+ → (z − x) ∈ Q+ .
∴ x < z.
298 Foundations of Mathematics
In the same way, we can prove the other hypothesis (Have is to the
reader).
∴ x ≤ z.
∴≤ is a transitive relation.
∴≤ is an ordered relation on Q.
(4) If x, y ∈ Q, then
((y − x) ∈ Q+ ∨ (y − x = 0) ∨ (−(y − x) ∈ Q+ ).
∴ (x < y) ∨ (y = x) ∨ (y < x).
∴ (x ≤ y) ∨ (y ≤ x).
Thereby, every two elements in Q are comparable.
Thus, ≤ is a totally ordered relation on Q.
Note: The relation ≤ is not perfect ordered relation on the set Q,
because the set S = {x ∈ Q|x ≤ 1} does not have first element.
Proof The proof can be obtained directly from the definition, and
previous theorems.
9.4.2 Embedding
Definition 9.11 The mapping from the set Z to the set Q denoted by
EZQ defined as EZQ = [n, 1] is called embedding (Spivak, 1975; Sharpe,
1987; Gunderson, 2019; Smith, 2015; Junghenn, 2018).
9.5 Exercises
Solve the following problems:
Q1: Consider the injective mapping F : A → B from the field
A into the field B such that F preserves addition and transports the
positive elements. Prove that F preserves order.
Q2: If x, y ∈ Q then x = nh , y = nk where n ∈ Z+ , h, k ∈ Z.
Q3: Prove that the ordered field of Q can isomorphically embedded
in any other ordered field. Or, the field of Q is a smallest order field.
Q4: Let x, y ∈ Q where the mathematical system (A, +, ·, ≤) is an
ordered field. Prove that
(a) |xy| = |x| · |y|.
(b) |x| · |y| ≤ ||x| − |y|| ≤ |x − y|.
Q5: Let x, y ∈ Q if x < y, then x1 > y1 .
Q6: Prove that every rational number can be expressed as a
terminating or repeating decimal, and vice versa.
Q7: Let z < 0. Prove that xz < yz ↔ x > y, ∀x, y ∈ Q.
9.6 Properties of Q
This section addresses the properties of the set Q where some of these
properties are general properties of any ordered field and others are the
specific properties of the set Q.
1 2 3 4
1 1 1 1
...
1 3 5 7
2 2 2 2
...
1 2 4 5
3 3 3 3
...
1 3 5 7
4 4 4 4
...
. . . . ...
. . . . ...
. . . . ...
When listing all the positive rational numbers as follows; We start
from the first number, which is 11 , and go down to the number 12 , and
go up at the angle of 45◦ to the number 12 . Then, we go back to the
third row and start at the number 13 , and go up at an angle of 45◦ until
we reach the number 31 , and so on...
Thus, we can list Q+ as follows;
1, 12 , 2, 31 , 32 , 3, 14 , 23 , 55 , 4, 51 , ...
0↔0
1↔1
−1↔2
1
↔3
2
1
− ↔4
2
...
Thus, the set of Q is a countable.
∴ m + p + 1 < m,
∴ p + 1 < 0, and this is contradiction.
∴ there is not an integer between n, n + 1.
As a result of this introductory theorem, we realize that the order
on Z is not dense as we introduce in the following definition.
Proof ∵ a < b,
∴ 2a = a + a < a + b < b + b = 2b.
∵ 2 = IA + IA > 0A → 21 > 0.
∴ a < a+b
2
< b.
Now, put c = a+b
2
→ a < c < b, c ∈ A.
∴ ≤ is a dense.
The ordered pair (X, Y ) is a cut. It is not a gap in Q since the lower
class X contains the maximum element 2.
9.7 Exercises
Solve the following problems:
Q1: If 0 6= x, y ∈ Q then prove that ∃n ∈ N − {0}, such that
nx > y.
Q2: Prove that @x ∈ Q 3 x2 = 6.
Q3: Prove that @x ∈ Q 3 x3 = 4.
Q4: Let (A, +, ·, ≤) be an ordered field. What is a necessary and
sufficient condition in order to (A, +, ·, ≤) be Archimedean field?
Q5: Let (A, +, ·, ≤) be a field, and ≤ be a partial ordered relation
on A, and let it be a dense relation. Is it necessary (A, +, ·, ≤) to be
ordered field?
Q6: Consider the subset D ⊆ Q in which D bounded above. Is
there least upper bound for the D?
Q7: Let Q[x] be a set of all polynomials ni=0 ai xi where n ∈ N, ai ∈
P
Q, and x is a variable.
(a) Define addition and multiplication operation on Q[x] in which
Q[x] be an integral domain.
(b)Let f (x) ∈ Q[x], 0 6= g(x) ∈ Q[x]. Prove that there are
polynomials t(x), r(x) ∈ Q[x] in which f (x) = t(x)g(x) + r(x) where
r(x) = 0. Or, degree of r(x) is less than degree of g(x).
10
The Real Numbers
10.1 Introduction
his chapter deals with structuring the real numbers (R) in the
T same methodology in which we have structured the Q, in which
ere we defined the Q as equivalence classes to the ordered pairs of the
Z. The chapter begins with defining the equivalence relations on the
set of all basic sequences. So the R is the equivalence class of a basic
rational sequence.
We will define the following operations; addition, multiplication,
and ordering on the set of R so that the set becomes an ordered field
and is an expansion to the ordered field of the Q. Thereby, the ordering
of the elements on the set R is free of gaps, and this means that each
sequence of real numbers has a limit in R.
This chapter attempts to prove the gaps in Q are quite narrow
and can be approximated by Q sequences. More precisely, the process
of expanding from the Q into the Q came to fill each gap of Q with
equivalence classes of sequences that almost fill the gaps, so that we
can find the solution to the equation x2 − 2 = 0 in the set R.
308 Foundations of Mathematics
10.2 Construction of R
Definition 10.1 The mapping F : N → A is called a sequence in A.
If F (n) = an , ∀n ∈ N, then we will expressed it by (an ) to denote the
mapping of F (Gaughan, 2009a; Saff and Snider, 1993).
Theorem 10.1 If the ordered pair (X, Y ) is a gap in the set Q then
there is a sequences (xn ), (yn ) in Q where for all n ∈ N, xn ∈ X, yn ∈ Y
such that yn − xn = n1 .
Moreover, in Q, the following inequalities are satisfied;
|xm − xn | < n1 , |ym − yn | < n1 , ∀n ∈ N − {0}.
Theorem 10.4 The sequence (an ) in the ordered field A has at most
one limit in A.
∴ |a| ≤ b.
Theorem 10.9 For all fundamental sequence (an ) in the ordered field
A, one of the following statements is true
The Real Numbers 315
(1) L(an ) = 0.
(2) (an ) is positive.
(3) −(an ) is positive.
bn + bn 2
an+1 = an + 10 n , ∀n ∈ N, bn ∈ Z ∪ {0}, where (an + 10n
) <2<
bn+1 2
(an 10n ) .
√
∴ [(an )] = [( 2)].
Proof ∵ L(xn ) 6= 0,
∴ ∃0 < ¯ ∈ Q 3 ∀n ∈ N, ∃k ≥ n 3 |xk | ≥ ¯.
∵ (xn ) is a fundamental sequence,
∴ ∃n̄ ∈ N 3 |xm − xn | ≤ 2¯ , ∀m, n ≥ n̄.
Currently, ∀n̄ ∈ N, ∃k̄ > n̄ 3 |xk̄ | ≥ ¯.
The Real Numbers 319
∴ |xn | = |xk̄ − (xk̄ − xn )| > |xk̄ | − |xk̄ − xn | > ¯ − 2¯ = 2¯ , ∀n ≥ n̄.
∴ xn 6= 0, ∀n ≥ n̄.
1; ∀n < n̄
Now, let us suppose that yn = 1
xn
; ∀n ≥ n̄
Thereby, yn is a fractional sequence.
−2
Let 0 < ∈ Q, ∃n ∈ N 3 |xm − xn | < 4 , ∀m, n ≥ n .
∴ |ym − yn | = | x1m − x1n | = | xxnm−x
xn
m
| = |x m −xn |
|xm ||xn |
−2
< 4 · 2¯ · 2¯ = , ∀m, n ≥ max {n̄, n}.
∴ yn is a fundamental sequence in Q.
Also, and since xn yn = 1, ∀n ≥ n̄, hence L(xn yn ) = 1.
∴ (xn yn ) ∼ (1).
∴ [(xn )][(yn )] = [(xn yn )] = [(1)].
10.3 Exercises
Solve the following questions:
Q1: Give an example of a bounded but not fundamental sequence.
Q2: Give an example of A that has no singularity limit.
Q3: If A be Archimedean field then L( n1 ) = 0, and L( p1n ) =
0, ∀0, p 6= 1 ∈ N.
Q4: Give an example of a fundamental but Divergent sequence.
Q5: If an is a fundamental sequence in the field A such that L(an ) =
0, then (|an |) is a positive fundamental sequence.
Q6: If (an ), (bn ) are positive fundamental sequences in the ordered
field A, then (an + bn ), (an bn ) are positive sequences in A.
Q7: Let A, B be ordered fields, and F : A → B be a bijective
mapping such that preserves on addition, multiplication, and ordering.
Prove that
(1) (an ) is a fundamental sequence in A if and only if (F (an )) is a
fundamental sequence in B.
(2) L(an ) = a if and only if L(F (an )) = F (a).
(3) (an ) is a positive sequence in A if and only if (F (an )) is a positive
sequence in B.
Q8: Let (xn ) be a convergent sequence in the ordered field A. Prove
that (xn ) is a positive sequence in A if and only if L(xn ) > 0 in A.
The Real Numbers 321
10.4 Order on R
Definition 10.7 The set of all equivalence classes belonging to the
positive sequences in FQ is called positive real numbers, and denoted
R. Mathematically, R+ = {r|(xn ) is a positive, (xn ) ∈ r}(Temirovna,
2021; Dijksterhuis, 1961; Kist and Leestma, 1970).
∴ xn + yn ≥ 1 + 2 = , ∀n ≥ n .
∴ (xn + yn ) is a positive sequence in Q.
In the same way, we can prove that xn yn is a positive sequence in
Q.
∴ (r1 + r2 = [(xn + yn )] ∈ R) ∧ (r1 r2 = [(xn yn )] ∈ R).
Now, to prove the third property, let r = [(xn )].
∴ (xn ) is a positive sequence in Q ↔ r ∈ R+ .
Thereby 0 = r ∈ R ↔ L(xn ) = 0 ∈ Q.
∴ −r = [(−xn )] ∈ R+ ↔ (−xn ) ∈ Q is a positive sequence.
But, according on Theorem 10.15 one of the following statements is
true
((−xn ) is a positive) ∨ ((xn ) is a positive) ∨ (L(xn ) = 0.
Thereby, one of the following statements is true
(−r ∈ R6+ ) ∨ (r ∈ R) ∨ (r = 0).
Thereby, the third property is satisfied.
Thus, R+ is a set of positive elements of R.
∴ r2 − r1 = 0.
∴ r1 = r2 .
Thereby, ≤ is anti-symmetric.
(3) Transitive.
Suppose that r1 ≤ r2 , r2 leqr3 .
∴ (r2 − r1 ∈ R+ ) ∨ (r1 = r2 ), (r3 − r2 ∈ R+ ) ∨ (r3 = r2 ).
If, (r2 − r1 ∈ R+ ) ∧ (r3 − r2 ∈ R+ ),
then (r3 − r2 ) + (r2 − r1 ) ∈ R+ .
∴ r3 − r1 ∈ R+ .
∴ r1 < r3 → r1 ≤ r3 .
In the same way, we can prove the other cases.
∴≤ is transitive.
Thereby, ≤ is a partial ordered relation.
(4) Ordering.
Let r1 , r2 ∈ R.
∴ r1 − r2 ∈ R.
Now, according on triple property, we have
(r1 − r2 ∈ R+ ) ∨ (r1 = r2 ) ∨ (−(r1 − r2 ) ∈ R+ ).
∴ (r1 < r2 ) ∨ (r2 < r1 ) ∨ (r1 = r2 ) → (r1 ≤ r2 ) ∨ (r2 ≤ r1 ).
Thereby, every pair element in R is comparable.
Thus, ≤ is a totally ordered relation.
∴ bc − ac ∈ R+ .
∴ ac < bc, ∀a, b ∈ R, ∀c ∈ R+ .
Thus, the mathematical system (R, +, ·, ≤) is the ordered domain.
10.4.1 Embedding
In this section, we will explain that it is possible to embed the ordered
field (Q, +, ·, ≤) into the ordered field (R, +, ·, ≤), which is ordered field
(R, +, ·, ≤) is the expansion to the ordered field (Q, +, ·, ≤).
Notation: We denote to the mapping EQR : Q → R in which EQR =
[(x)] by E.
x < y ↔ (y − x) > 0,
↔ (y − x) is a positive sequence in FQ
↔ [(y)] − [(x)] > 0.
↔ [(x)] < [(y)].
↔ E(x) < E(y).
From (1), (2)& (3) E is preserves on ordering.
Note:
(1) We are going to write x instead of [(x)]. Or, we don’t
differentiate between Q and is isomorphic image in R.
(2) The mathematical system (Q, +, ·) is a subfield of (R, +, ·).
10.4.2 Completeness on R
We have demonstrated in Theorem 10.5 that in any ordered field A,
every convergent sequence is a fundamental sequence, whereas the
opposite is not true according in Theorem 10.8. Or every convergent
sequence is a fundamental sequence, but the opposite is not true.
10.4.3 Density of Q in R
Definition 10.10 If B is a subset of the ordered set A, then B is a
dense in A if and only if ∀a, b ∈ A, (a < b) ∈ A, ∃c ∈ B 3 a < c < b
(Bourbaki, 2013; Steen et al., 1978; Kleiber and Pervin, 1969).
3→4:
Let φ 6= B ⊆ A, where B is bounded below.
X = {x : x ≤ b, ∀b ∈ B}
Let
Y =A−X
∴ (X, Y ) is a cut in A, because
(1) X = φ is the set of all bounded below to B, and B is bounded
below.
(2) Y 6= φ because b + 1 ∈ Y, ∀b ∈ B 6= φ.
(3) (X ∪ Y = A) ∧ (X ∩ Y = φ).
(4) If x ∈ X, y ∈ Y , then x < y.
If x ≥ y, then y ≤ x ≤ b, ∀b ∈ B.
∴ y ∈ X, and this is contradiction.
∴ (X, Y ) is a cut to A.
If b ∈ X, ∀b ∈ B, then b = maxX = inf B.
If (b ∈ Y, ∀b ∈ B) ∧ (yo ) minimum in Y , then yo is a bounded below
to B.
∴ yo ∈ X.
This is impossible since X ∩ Y = φ.
∴ Y has no minimum.
∵ (X, Y ) is not a gap,
∴ X has a maximum, say xo .
Thereby, xo = inf B.
4 → 1 : It is left for the reader.
10.5 Exercises
Answer the following questions:
Q1: If (xn ) ∈ FQ , then |[(xn )]| = [(|xn |)].
Q2: Prove that the (xn ) ∈ Q is fundamental in Q if and only if it
is fundamental in R.
Q3: Let (xn ) be a quotient sequence, and x ∈ Q. Prove that
(L(xn ) = x) ∈ Q ↔ (L(xn ) = x) ∈ R.
Q4: Prove that the ordered field A is Archimedean if and only if
the subset QA of all quotient elements of A is dense in A.
Q5: Consider the ordered fields A, B, where B is a dense in A. If
(xn ) be a sequence in B, then prove that
The Real Numbers 333
Q13: If (xm ) ∼
= (ym ). Prove that;
(i) If one of them is Cauchy or convergent, then so is the other.
(ii) (n).
11.1 Introduction
ttempts that were efforts to solve the equation in the kind of
A x2 + 1 = 0 of the real numbers led to the system of new
kinds of numbers, called the system of complex numbers. A complex
number is a number that can be expressed in the form a + bi where
a and b are real numbers, and i is a symbol called the imaginary
unit and satisfying the equation i2 = −1. Because no real number
satisfies this equation, i was called an imaginary number by René
Descartes. The set of complex numbers is denoted by C. Despite the
historical nomenclature “imaginary”, complex numbers are regarded
in the mathematical sciences just as “real” as real numbers and are
fundamental in many aspects of the scientific description of the natural
world (Bourbaki, 1994; Andreescu et al., 2006).
Proof ∵ ∀(u, v) ∈ C × C,
∴ F (u, v) will be a unique image because every two ordered pairs of
the R are equal if and only if the first element of the first ordered pair
is equal to the first element of the second ordered pair and, the second
element of the first ordered pair is equal to the second element of the
second ordered pair.
∴ F : C × C → C is a mapping.
∴ F is a binary operation on C.
In the same way G is a binary operation on C.
∴ u · v = (1, 0) = 1C .
Thereby, ∀ 0 6= c ∈ C has a multiplicative inverse.
Thus, the mathematical system (C, +C , ·C ) is a ring.
Thus, u1 < u2 .
Fourth case;
((x1 = x2 ) ∧ (y1 < y2 )) ∧ ((x2 = x3 ) ∧ (y2 < y3 )).
(x1 = x3 ) ∧ (y1 < y2 ) ∧ (y2 < y3 ).
(x1 = x3 ) ∧ (y1 < y3 ).
∴ u1 < u2 .
Thus, ≤ is a transitive relation.
(4) Comparison.
Let u1 = (x1 , y1 ), u2 = (x2 , y2 ).
First case:
x1 6= x2 .
∵ (y1 ≤ y2 ) ∨ (y2 ≤ y1 ),
∴ (u1 ≤ u2 ) ∨ (u2 ≤ u1 ).
Second case;
x1 6= x2 .
∴ (x1 < x2 ) ∨ (x2 ≤ x1 ).
∴ (u1 < u2 ) ∨ (u2 < u1 ).
∴ (u1 ≤ u2 ) ∨ (u2 ≤ u1 ).
Thereby, every two elements are comparable.
Thus, ≤ is totally ordered relation on C.
11.3 Embedding
The symbol E is used to denote the mapping RRC : R → C, where RRC =
(r, 0), r ∈ R (Spivak, 1975; Sharpe, 1987; Gunderson, 2019; Smith, 2015;
340 Foundations of Mathematics
Proof ∵ z ∈ C,
∴ z = (x, y), ∀x, y ∈ R.
∴ z = (x, y) = (x, 0) + (0, y) = (x, 0) + (y, 0)(0, 1) = x + iy.
Now, suppose that z = x0 + y 0 i 3 x0 , y 0 ∈ R.
∵ x0 + y 0 i = (x0 , 0) + (y 0 , 0)(0, 1) = (x0 , 0) + (0, y 0 ) = (x0 + y 0 ) = z =
(x, y),
∴ x = x0 , y = y 0 .
Thus, z can only be expressed in a unique way.
11.5 Exercises
Solve the following questions:
Q1: Consider a field K, n ∈ Z+ , and Kn is a set of n− tuples. The
operations +, ◦ are defined as follows respectively;
(ai ) + (bi ) = (a1 + b1 , ..., an + bn ), λ ◦ (ai ) = (λa1 , ..., λan ).
Prove that Kn is is a two dimensional vector space on K.
Q2: Prove that each field is a one dimensional vector space on itself.
Q3: Prove that C is a smallest field contains of R in which every
equation in the second degree has a solution.
The Complex Numbers 343
Definition 11.10 Euler’s formula states that for any real number θ,
there are
(1) eiθ = cosθ + isinθ.
(2) e−iθ = cosθ − isinθ.
where e is the base of the natural logarithm, i is the imaginary unit,
cos, sin are the trigonometric functions cosine and sine respectively
(Moskowitz, 2002).
Corollary
√ √ If w = C − {0}, where w = r(cosθ + isinθ), then
w = r(cos( n + 2πk
θ
n
) + isin( nθ + 2πk
n
)); k = 0, 1, 2, ..., n − 1.
∵ z w̄ = z̄w,
∴ |z + w|2 = |z|2 + |w|2 + 2R(z w̄) ≤ |z|2 + |w|2 + 2z w̄ = |z|2 + |w|2 +
2 |z| |w| = (|z| + |w|)2 .
∴ |z + w| ≤ |z| + |w|.
(5) By utilizing (4), we have
|z| = |w + (z − w)| ≤ |w| + |z − w|.
∴ |z − w| ≥ |z| − |w|.
Also, |w| = |z + (w − z)| ≤ |z| + |w − z|...(i).
∴ |w − z| ≥ |w| − |z| = −(|z| − |w|)...(ii).
From (i)& (ii), we get
|z − w| ≥ ||z| − |w||.
az+b
Example 11.6 If |z| = 1, prove that | b̄z+ā
, ∀a, b ∈ C.
Solution.
∵ |z| = 1,
∴ z = (z̄)−1 .
∴ az+b
b̄z+ā
= az+b · 1.
b̄+āz̄ z
The Complex Numbers 351
11.8 Exercise
Answer the following questions:
Q1: Prove that:
(1) 1i = −i.
1
(2) i+1 = i−1
2
.
1
(3) z1 z2 = z1 · z12 .
1
√
Q10: If
Pi=n−1 i w = n
1, w 6= 1 (w is a nth root of unity), then prove that
1 + i=1 w = 0.
Q11: Let z =√ x + iy, w = a + ib. Prove that
(1)|x| + |y| ≤ 2 |z|.
(2) Arg(z̄) = −Arg(z).
(3) Arg( wz ) = Arg(z) − Arg(w)mod(2π).
Q12: Find the greatest value of |z n + a| such that |z| ≤ 1.
Q13: Prove that |a − b|2 + |a + b|2 = 2(|a|2 + |b|2 ).
Bibliography
Anton, H. A., De Sesa, B., Black, C., Gregas, M., Grobe, C. A. and
Grobe, E. M. (2005). Elementary linear algebra: student solutions
manual. Wiley.
Anton, H., Bivens, I., Davis, S. and t. Polaski (2010). Calculus: early
transcendentals. Wiley Hoboken, NJ.
Christoph, B., Armin, F., Malte, G., Helmut, H., Ivana, K., Manfred,
P., Jörg, S., Dimitra, T., Bao Quoc, V. and Magdalena, W.
(2003). Tutorial dialogs on mathematical proofs. In Proceedings of
IJCAI-03 Workshop on Knowledge Representation and Automated
Reasoning for E-Learning Systems. 12–22.
Crow, J. F. (1993). Felix bernstein and the first human marker locus.
Genetics. 133(1): 4.
©
and funda mental concepts of mathematics. new york: Rinehart
& company. Inc , i960. 523.
BIBLIOGRAPHY 363
Quine, W. v. (1969). Set theory and its logic. Vol. 9. Harvard University
Press.
Rucker, R. (2013). Infinity and the mind: The science and philosophy
of the infinite. Vol. 26. Princeton University Press.
Strang, G. (2006). Linear algebra and its applications. 4th. Brooks Cole.
.
A Axiom
Absolute of choice, 149-152
value, 300, 309, 344, 351 of extension, 182
value function, 121 of infinity, 180-181
Addition module k, 295 of negation, 11
Additive identity, 293, 319, 336
Algebra B
of sets, 41 Basis, 342
Antecedent, 14 Biconditional statement, 15
Anti- Bijective mapping, 117, 128-129, 141,
lexicographic ordering, 99, 110, 153, 158-159, 195, 199-200,
172 220, 302, 320
lexicographic relation, 100 Binary
symmetric relation, 81, 83, 94- operation, 203-210, 212-216, 225,
95, 110, 279, 297, 338 227-230, 245, 262-263, 266,
Arbitrary, 36-37, 47, 78, 83, 121-123, 269-270, 274, 285, 290, 292,
166, 341 317-318, 336, 341
Archimedean order, 305, 330 relation, 61, 68-69, 258, 285
Argument, 33-35, 344 Boolean
Associative algebra, 41
law, 43, 45, 189 ring, 276
Automorphism, 257, 271-272 Bounded, 103, 105, 151, 199, 306,
309-310, 312, 317, 320, 328-
388 Index
226, 229, 233, 258, 272, 277, 148, 151, 170-177, 191-192,
283, 286, 296, 311, 314-316, 196, 234, 276, 279, 297, 322,
322, 333, 336, 342 327, 329
-one correspondence, 117 subset, 106, 151
Open theorem, 175
interval, 5, 172 triple, 68-69, 112, 266
sentence, 9, 29, 30-31, 68, 108 Ordering
Operator, 31-32, 225 on the cardinal numbers, 156
Order n, 247 sets, 153
Order theorem, 109, 151
of a, 235 Ordinal
of the group, 217 number, 153-154, 170, 173-177,
on N, 190 179-180
on Q, 297 pattern, 171-177
on R, 321
on Z, 277, 303 P
P , 247 Paradoxes, 177
preserving mappings, 139 Parameter, 8
q, 257 Partially ordered set, 94, 98-99, 105-
type, 170-171 106, 144, 148, 151, 170
Ordered Partition, 83, 89-91, 93, 238, 240
domain, 323-324 Permutation, 122, 235
field, 229-301, 303-307, 309-314, Positive, 3, 39, 125, 224, 257, 265,
320, 324-325, 327-328, 330, 277-280, 282-284, 296-297,
332-333, 338-339 301-302, 305, 314-315, 320-
integral domain, 282, 284, 286, 323, 325-326, 331, 333, 345
298 divisor, 39
numbers, 141 element, 282-284, 296-297, 301,
pairs, 62-63, 69, 71-72, 112, 115, 305, 321-322, 331
163, 257, 287, 307, 336, 340 fundamental sequence, 320, 326
pattern, 172 integer, 5, 39, 125, 224, 227, 278-
relation, 93-95, 98-99, 101-103, 280
107, 109-110, 148, 157, 160, of the statement, 26
171, 191, 279, 282-284, 286- Q, 5, 3296-297, 301-302,
287, 297-298, 303, 306, 323, R, 5, 257, 321
337, 339 sequence, 314, 320-322, 325, 331,
ring, 282 333
set, 94, 96-99, 141-110, 139-146, x− axis, 344
Potency of sets, 153, 170
394 Index
U Z
Unbounded, 199, 309 Zero, 3, 179, 269-271, 281, 294, 316,
sequence, 309 341
Union, 41-42, 46, 50, 56, 70, 75, 205, divisor, 269-270, 281, 294
208 element, 270, 341
of sets, 42, 56 homomorphism, 271
of relations, 75 real number, 316
operation, 208 Zorn’s lemma, 151
Universal
quantifier, 29-30
set, 4, 8-9, 36-37, 43
Upper
bound, 103-105, 306, 328-329
class, 304