Foundations of Mathematics

MATH 220
Lecture Notes

F. Baudier (Texas A&M University)

December 8, 2018
2
Contents

1 Introduction to Mathematical Logic 5

1.1 Statements and predicates . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Logical connectives . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Negation, disjunction, conjunction . . . . . . . . . . . . . 6
1.2.2 Implication, contrapositive, converse, biconditional . . . . 8
1.3 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Statements with mixed quantifiers . . . . . . . . . . . . . . . . . 14

2 Classical Proof Techniques 15

2.1 Modus Ponens and Modus Tollens . . . . . . . . . . . . . . . . . 15
2.2 Proofs of existential statements . . . . . . . . . . . . . . . . . . . 16
2.2.1 Existential statements of the form (∃x ∈ U)P (x) . . . . . 16
2.2.2 Uniqueness in proofs of existential statements . . . . . . . 16
2.3 Proofs of universal statements . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Universal statements of the form (∀x ∈ U)P (x) . . . . . . 17
2.3.2 Statements of the form (∀x ∈ U)[P (x) =⇒ Q(x)] . . . . 17
2.3.3 Disproving universal statements: counterexamples . . . . 18
2.4 Proofs by contrapositive . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Proof by contradiction . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Other useful proof techniques . . . . . . . . . . . . . . . . . . . . 21
2.6.1 Proving biconditional statements . . . . . . . . . . . . . . 21
2.6.2 Proving disjunction statements . . . . . . . . . . . . . . . 21
2.6.3 Proof by cases . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.4 Working backwards . . . . . . . . . . . . . . . . . . . . . 22

3 Induction 23
3.1 Principle of Mathematical Induction . . . . . . . . . . . . . . . . 23
3.2 Principle of Strong Mathematical Induction . . . . . . . . . . . . 25

4 Introduction to Elementary Set Theory 29

4.1 Sets and subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Operation on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.1 Union and intersection of two sets . . . . . . . . . . . . . 32
4.2.2 Complement . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.3 Arbitrary unions and intersections . . . . . . . . . . . . . 37
4.2.4 Power set . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.5 Cartesian products . . . . . . . . . . . . . . . . . . . . . . 41

3
4 CONTENTS

5 Functions 43
5.1 Definition and Basic Properties . . . . . . . . . . . . . . . . . . . 43
5.2 Composition of Functions . . . . . . . . . . . . . . . . . . . . . . 45
5.3 Surjective and Injective Functions . . . . . . . . . . . . . . . . . 46
5.3.1 Definitions and examples . . . . . . . . . . . . . . . . . . 46
5.3.2 Injectivity, surjectivity and composition . . . . . . . . . . 48
5.4 Invertible Functions . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.5 Functions and Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6 Relations 57
6.1 Definitions and basic properties . . . . . . . . . . . . . . . . . . . 57
6.2 Equivalence relations and partitions . . . . . . . . . . . . . . . . 58

7 Introduction to Abstract Algebra 61

7.1 Binary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 61

8 Order Relations 65
8.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

9 From the Natural Numbers to the Real Numbers 67

9.1 The Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 67
9.1.1 Peano’s Axioms . . . . . . . . . . . . . . . . . . . . . . . . 67
9.1.2 Binary operations and order relations on N . . . . . . . . 69
9.1.3 Basic properties of N . . . . . . . . . . . . . . . . . . . . . 71
9.1.4 Principle of Mathematical induction revisited . . . . . . . 71
9.1.5 The Well-Ordering Principle . . . . . . . . . . . . . . . . 72
9.2 The Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.2.1 Construction of Z . . . . . . . . . . . . . . . . . . . . . . 73
9.2.2 Basic properties of Z . . . . . . . . . . . . . . . . . . . . . 74
9.2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.2.3.1 The Division Algorithm and Greatest Common
Divisors . . . . . . . . . . . . . . . . . . . . . . . 74
9.2.3.2 Primes and Unique Factorization . . . . . . . . . 74
9.2.3.3 Congruences . . . . . . . . . . . . . . . . . . . . 74
9.3 The Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . 74
9.3.1 Construction of Q . . . . . . . . . . . . . . . . . . . . . . 74
9.3.2 Basic properties of Q . . . . . . . . . . . . . . . . . . . . . 74
9.4 The Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.4.1 Construction of R . . . . . . . . . . . . . . . . . . . . . . 74
9.4.2 Basic properties of R . . . . . . . . . . . . . . . . . . . . . 74
9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

10 Cardinality of Sets 75
10.1 Finite and Infinite sets . . . . . . . . . . . . . . . . . . . . . . . . 75
10.1.1 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . 76
10.2 Countable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.3 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.4 Collections of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Chapter 1

Introduction to
Mathematical Logic

1.1 Statements and predicates

A mathematical proof should not be subject to personal interpretation and to
avoid ambiguity we need to restrict our attention to certain types of declarative
sentences.
Definition 1: Statement

A statement is any declarative sentence that has a truth value (either

true or false).

Characteristics of statements:
• a statement has a truth value;
• a statement is either true or false;
• a statement cannot be neither true nor false;
• a statement cannot be true and false.
We will often represent statements with capital letters, such as P , Q, ...
Mathematical statements are commonly written with symbols for convenience
but should be thought of as full-fledged sentences.
Example 1. P : 3 + 5 = 8, is a statement.
Example 2. P : 3 + 5 = 9, is a statement.

Definition 2: Predicate
A predicate is any declarative sentence containing one or more variables
that is not a statement but becomes a statement when the variables are
assigned values.

A predicate is usually written P (n), Q(x, y), and variants thereof, depending
on the number of variables and the letters used for the variables.

5
6 CHAPTER 1. INTRODUCTION TO MATHEMATICAL LOGIC

Example 3. P (x) : x + 1 = 2, is a predicate with one variable.

Example 4. P (m, n) : n + m is odd, is a predicate with two variables.
Exercise 1. Are the following sentences statements, predicates or none of these?

1. Michael Phelps won 23 gold medals.

2. 3+5=8

3. 3+5=9

4. Today is cold.

5. x+5=8

6. table+5=8

7. This sentence is false.

1.2 Logical connectives

We have introduced two types of expressions that we will use in our mathe-
matical proofs: statements and predicates. We can build more complicated
expressions using the basic logical connectives: ¬ (negation), ∧ (conjunction),
∨ (disjunction).
Terminology. Expressions of the form P ∧ Q, P ∨ Q, ¬P , (¬P ) ∧ (Q ∨ ¬R),
and so on, where P and Q are considered as variables representing statements
are called statement forms. They are not actually statements themselves but
become statements when the variables P and Q are replaced by statements.

1.2.1 Negation, disjunction, conjunction

Definition 3: Negation

If P is a statement, the negation of P is the statement “not P ”. We use

the notation ¬P , which reads “not P ” for the negation of P .

If P is a statement only the following two cases can occur: either (P is true
and ¬P is false) or (P is false and ¬P is true).
Truth tables for statement forms are tables that give the truth value of
the statement form in terms of the truth values of the variables and are used
to rigorously define the action of a logical connective on the statement(s) it
operates.

P ¬P
T F
F T

Table 1.1: Negation truth table

1.2. LOGICAL CONNECTIVES 7

Definition 4: Conjunction

Let P and Q be statements. The conjunction of P and Q is the statement

“P and Q”. The notation for the conjunction of P and Q is P ∧ Q and
reads “P and Q”.

P Q P ∧Q
T T T
T F F
F T F
F F F

Table 1.2: Conjunction truth table

Definition 5: Disjunction

Let P and Q be statements. The disjunction of P and Q is the statement

“P or Q”. The notation for the disjunction of P and Q is P ∨ Q and
reads “P or Q”.

P Q P ∨Q
T T T
T F T
F T T
F F F

Table 1.3: Disjunction truth table

Using logical connectives one can create new statements out of given state-
ments. One can naturally extend the definitions above to create new predicates
out of given predicates.
Example 5. The predicate R(x) : |x| > 3 is the disjunction of the predicates
P (x) : x > 3 and Q(x) : x < −3, i.e., R(x) = P (x) ∨ Q(x).
Example 6. The system of linear equations

2x + 1 = 0
3y − 2 = 0
is a predicate with two variables R(x, y) which is the conjunction of the predi-
cates P (x) : 2x + 1 = 0 and Q(y) : 3y − 2 = 0, i.e., R(x, y) = P (x) ∧ Q(y).
The disjunction is commutative, since it is plain that P ∨ Q and Q ∨ P
have the same truth tables. The same remark holds for the conjunction. We
can make this observation precise by defining the notion of logical equivalence
between statement forms.
Definition 6: Logically equivalent statement forms

We say that two statement forms are logically equivalent if they have the
same truth tables.
8 CHAPTER 1. INTRODUCTION TO MATHEMATICAL LOGIC

We sometimes use the notation ≡ for logical equivalence.

Example 7. As we just observed P ∨ Q ≡ Q ∨ P and P ∧ Q ≡ Q ∧ P .
Example 8. By looking at their truth tables it is easy to see that the statement
forms P and ¬¬P are logically equivalent.

Theorem 1: DeMorgan’s Laws

1. ¬(P ∧ Q) is logically equivalent to (¬P ) ∨ (¬Q).

2. ¬(P ∨ Q) is logically equivalent to (¬P ) ∧ (¬Q).

Proof. We just need to build the truth tables of all the statement forms involved.

P Q P ∨Q P ∧Q ¬[P ∨ Q] ¬[P ∧ Q] ¬P ¬Q ¬P ∨ ¬Q ¬P ∧ ¬Q
T T T T F F F F F F
F T T F F T T F T F
T F T F F T F T T F
F F F F T T T T T T

Exercise 2. What is the negation of the predicate 0 < x < 1. Find a useful
denial of the predicate 0 < x < 1?

Definition 7: Tautology

A statement form that is always true no matter what are the truth values
of the variables is called a tautology.

Example 9. P ∨ (¬P ) is a tautology.

Definition 8: Contradiction
A statement form that is always false no matter what are the truth values
of the variables is called a contradiction.

Example 10. P ∧ (¬P ) is a contradiction.

Note that if S is a tautology then ¬S is a contradiction and vice-versa.

1.2.2 Implication, contrapositive, converse, biconditional

Roughly speaking an implication is a statement with an “if-then” structure.
The “if” part of the statement gives the premise or assumption that is made,
and P is called the hypothesis or antecedent. The “then” part is the conclusion
that is asserted from the premise and Q is called the conclusion or consequent.
1.2. LOGICAL CONNECTIVES 9

Definition 9: Implication

Let P and Q be statements. The implication “P =⇒ Q” (read “P

implies Q”) is the statement “If P , then Q.”

There is no sense of causality in the statement “P =⇒ Q” and P might

be (apparently) entirely unrelated to Q. The only case when an implication is
false is when P is true and Q is false. In particular a false proposition implies
anything!

P Q P =⇒ Q
T T T
F T T
T F F
F F T

Table 1.4: Implication truth table

Theorem 2

1. P =⇒ Q is logically equivalent to (¬P ) ∨ Q.

2. ¬(P =⇒ Q) is logically equivalent to P ∧ ¬Q.

Proof. We compare the truth tables.

P Q P =⇒ Q ¬[P =⇒ Q] ¬P ¬P ∨ Q ¬Q P ∧ ¬Q
T T T F F T F F
F T T F T T F F
T F F T F F T T
F F T F T T T F

For 2. we could also give a proof using DeMorgan’s law and (1), since
¬[(¬P ) ∨ Q] ≡ (¬¬P ) ∧ ¬Q ≡ P ∧ ¬Q.

Exercise 3. Let

P : The square function is differentiable at 0.

Q : The square function is continuous at 0.

Are the implications P =⇒ Q, Q =⇒ P true?

Definition 10: Contrapositive

Let P and Q be statements. The statement (¬Q) =⇒ ¬P is called the

contrapositive of the statement P =⇒ Q.
10 CHAPTER 1. INTRODUCTION TO MATHEMATICAL LOGIC

Theorem 3: Logical equivalence between an implication and its

contrapositive

P =⇒ Q is logically equivalent to (¬Q) =⇒ (¬P ).

Proof. First observe that (P =⇒ Q) ≡ (¬P ) ∨ Q. On the other hand,

[(¬Q) =⇒ (¬P )] ≡ [(¬¬Q) ∨ ¬P ] ≡ [Q ∨ ¬P ] ≡ [(¬P ) ∨ Q],

and the conclusion follows.

We could also have compared the truth tables.

P Q P =⇒ Q ¬P ¬Q ¬Q =⇒ ¬P
T T T F F T
F T T T F T
T F F F T F
F F T T T T

Definition 11
Let P , Q be statements. The statement Q =⇒ P is called the converse
of the statement P =⇒ Q.

Proposition 1

P =⇒ Q is NOT logically equivalent to Q =⇒ P .

Proof. We compare the truth tables.

P Q Q =⇒ P P =⇒ Q
T T T T
F T F T
T F T F
F F T T

Definition 12: Biconditional or equivalence

Let P and Q be statements. The statement P ⇐⇒ Q (or P iff Q, read

P if and only if Q) is the statement (P =⇒ Q) ∧ (Q =⇒ P )

The statement (P =⇒ Q) ∧ (Q =⇒ P ) is true when P and Q are

simultaneously true or simultaneously false, and false otherwise. The symbol
⇐⇒ is called the biconditional.
1.2. LOGICAL CONNECTIVES 11

P Q Q =⇒ P P =⇒ Q (P =⇒ Q) ∧ (Q =⇒ P )
T T T T T
F T F T F
T F T F F
F F T T T

P Q P ⇐⇒ Q
T T T
F T F
T F F
F F T

Table 1.5: Biconditional truth table

Consider the implication “P =⇒ Q”. We say that P is a sufficient condition

for Q, because in order for Q to be true it is sufficient that P be true. Also, we
say that Q is a necessary condition for P meaning that Q must be true in order
for P to be true, or in other words if Q is false then P is false.
Theorem 4

1. P ⇐⇒ Q is logically equivalent to ((¬P ) ∨ Q) ∧ ((¬Q) ∨ P ).

2. P ⇐⇒ Q is logically equivalent to Q ⇐⇒ P .

Proof. For 1. one has

(P ⇐⇒ Q) ≡ (P =⇒ Q) ∧ (Q =⇒ P ) ≡ ((¬P ) ∨ Q) ∧ ((¬Q) ∨ P )

For 2.

(P ⇐⇒ Q) ≡ (P =⇒ Q)∧(Q =⇒ P ) ≡ (Q =⇒ P )∧(P =⇒ Q) ≡ (Q ⇐⇒ P )

Remark 1
The placement of the parentheses in statement forms matters. As it can
be easily seen by examining their truth tables (¬P ∨ Q) ∧ (¬Q ∨ P ) and
¬P ∨(Q∧¬Q)∨P are not logically equivalent (actually ¬P ∨(Q∧¬Q)∨P
is a tautology).

Exercise 4. Are the statement forms P ∨ Q, ¬P =⇒ Q, and ¬Q =⇒ P

logically equivalent?

Solution. Yes.
12 CHAPTER 1. INTRODUCTION TO MATHEMATICAL LOGIC

P Q P ∨Q ¬P =⇒ Q ¬Q =⇒ P
T T T T T
T F T T T
F T T T T
F F F F F

1.3 Quantifiers
Another way a predicate can be made into a statement is by modifying it with
quantifiers that acts on the free variables which live in a certain ambient (and
often implicit) universe.
If P (x) is a predicate, then the mathematical expression “(∃x)P (x)” (read
“there exists x such that P (x)”) is also a declarative sentence with a truth value.
The symbol ∃ is called the existential quantifier.
Definition 13: Turning a predicate into a statement with an ex-
istential quantifier

Let P (x) be a predicate. The declarative sentence (∃x)P (x) is a state-

ment that is true exactly when at least one individual element a in the
ambient universe has the property that P (a) is true.

If P (x) is a predicate, then the mathematical expression “(∀x)P (x)” (read

“for all x, P (x)”) is a declarative sentence with a truth value. The symbol ∀ is
called the universal quantifier.
Definition 14: Turning a predicate into a statement with a uni-
versal quantifier

Let P (x) be a predicate. The declarative sentence (∀x)P (x) is a state-

ment that is true exactly when every element a in the ambient universe
has the property that P (a) is true.

Remark 2
In practice it is usually simpler and more convenient to use the same
letter for the variable and its assigned value. We will do it from now on.

Terminology. A variable x is called a bound variable once a quantifier is applied

to x. Otherwise we say that x is a free variable.
Example 11. Discuss the truth values of the following statements.

1. (∀x) x + 5 = 8.

2. (∃x) x + 5 = 8.

3. (∃x) x2 + 1 = 0.

4. (∃n) n + 5 = π.
1.3. QUANTIFIERS 13

Remark 3
As it can be seen in the examples above, the truth values of statements
that come from binding with a quantifier the free variable of a predicate
depend on the intended universe in which the variable belong. To avoid
ambiguity, we will usually make the intended universe explicit unless it
is completely clear from the context.

Definition 15: Rules of negation for quantifiers

The two basic rules to negate statements with quantifiers are:

Rule 1 the negation of the statement “(∃x)P (x)” is the statement

“(∀x)¬P (x)”,

Rule 2 the negation of the statement “(∀x)P (x)” is the statement

“(∃x)¬P (x)”.

An important notion in mathematical logic is the notion of “membership”.

To say that a free variable belongs to a specific universe U, we write x ∈ U.
If we want to say “there exists x in the universe U such that P (x)” we should
formally write

(1.1) (∃x)[x ∈ U ∧ P (x)].

However, we will use the convenient abbreviation (∃x ∈ U)P (x) to refer to
(1.1).
Similarly, If we want to say “for all x in the universe U, P (x)” we should
formally write

(1.2) (∀x)[x ∈ U =⇒ P (x)].

In this case, we will use the convenient abbreviation (∀x ∈ U)P (x) to refer
to (1.2).
From Rule 1 and Rule 2, we can derive the rules of negation for the abbre-
viations just discussed above.
Theorem 5: Negation of statements with quantifiers and mem-
bership

1. ¬[(∃x ∈ U)P (x)] is logically equivalent to (∀x ∈ U)¬P (x).

2. ¬[(∀x ∈ U)P (x)] is logically equivalent to (∃x ∈ U)¬P (x).

Proof. 1.

¬[(∃x ∈ U)P (x)] ≡ ¬[(∃x)(x ∈ U) ∧ P (x)]

≡ (∀x)(¬(x ∈ U)) ∨ ¬P (x)
≡ (∀x)[x ∈ U =⇒ ¬P (x)]
≡ (∀x ∈ U)¬P (x)
14 CHAPTER 1. INTRODUCTION TO MATHEMATICAL LOGIC

2.
¬[(∀x ∈ U)P (x)] ≡ ¬[(∀x)[x ∈ U =⇒ P (x)]]
≡ (∃x)¬[x ∈ U =⇒ P (x)]
≡ (∃x)(x ∈ U) ∧ ¬P (x)
≡ (∃x ∈ U)¬P (x)

Example 12. The negation of “(∀x)(∃y)P (x, y)” is “(∃x)¬[(∃y)P (x, y)]” which
is “(∃x)(∀y)¬P (x, y)”.
Example 13. Define formally, i.e., using quantifiers, what it means to be an odd
number.
Example 14. Define formally, i.e., using quantifiers, what it means to be an
rational number and what it means to be a irrational number.
Example 15. Write formally the statement of the Fundamental Theorem of
Arithmetic.
Example 16. Define formally what it means that ` is a limit of a sequence
(xn )∞ ∞
n=1 . What does it mean that ` is not the limit of the sequence (xn )n=1 ?

1.4 Statements with mixed quantifiers

When a statement involves several quantifiers the order usually matters and
one cannot swap quantifiers without care! Let P (x, y) be a predicate with two
variables. The statement
(∀x)(∃y)P (x, y)
is in general not logically equivalent to the statement
(∃y)(∀x)P (x, y).
For instance, “For all odd number n there exists a number k ∈ {0, 1, 2, . . . , }
such that n = 2k + 1” is a true statement, while “there exists a number k ∈
{0, 1, 2, . . . , } such that for all odd number n, n = 2k + 1” is clearly a false
statement.
Example 17. The definition of the limit of a sequence involves three quantifiers.
Let ` be a fixed real number and (xn )∞ n=1 be a sequence of real numbers. We say
that ` is the limit of (xn )∞
n=1 , and we write limn→∞ xn = `, if for all ε > 0 there
exists a natural number N such that if n ≥ N then |xn − `| < ε. Symbolically,
limx→x0 f (x) = ` if
(∀ε > 0)(∃N ∈ N)(∀n ≥ N )(|xn − `| < ε).
Example 18. The definition of the limit of a function at a point involves three
quantifiers. Let x0 ∈ (a, b), ` ∈ R and f : (a, x0 ) ∪ (x0 , b) → R. We say that ` is
the limit of f at x0 , and we write limx→x0 f (x) = `, if for all ε > 0 there exists
δ > 0 such that if x satisfies 0 < |x − x0 | < δ then |f (x) − `| < ε. Symbolically,
limx→x0 f (x) = ` if
(∀ε > 0)(∃δ > 0)(∀x)[0 < |x − x0 | < δ =⇒ |f (x) − `| < ε].
Chapter 2

Classical Proof Techniques

2.1 Modus Ponens and Modus Tollens

From the implication truth table we can deduce two elementary rules of infer-
ence. Recall that the truth table of the implication is:

P Q P =⇒ Q
T T T
F T T
T F F
F F T

Modus Ponens is a logical argument that exploits the first row in the impli-
cation truth table and says that “Q is true” is a valid conclusion based on the
hypotheses that “P is true” and “P =⇒ Q is true”.
Example 19. You know from your Calculus course that P (f ) =⇒ Q(f ) is true
where,
P (f ) :The function f is differentiable at 0,
Q(f ) :The function f is continuous at 0.

Therefore you can conclude that a function f is continuous at 0 if you know

that f is differentiable at 0.
Modus Tollens is a logical argument that exploits the last row in the impli-
cation truth table and says that “P is not true” is a valid conclusion based on
the hypotheses that “Q is not true” and “P =⇒ Q is true”.
Example 20. You know from your Calculus course that P (f ) =⇒ Q(f ) is true
where,
P (f ) :The function f is differentiable at 0,
Q(f ) :The function f is continuous at 0.

Therefore you can conclude that a function f is not differentiable at 0 if you

know that f is not continuous at 0.

15
16 CHAPTER 2. CLASSICAL PROOF TECHNIQUES

2.2 Proofs of existential statements

Recall that in practice it is usually simpler and more convenient to use the same
letter for the variable and its assigned value and we will adopt this convention.

2.2.1 Existential statements of the form (∃x ∈ U)P (x)

For existential statements we proceed as follows.
Proof Technique 1: Existential statements (∃x ∈ U)P (x)

To prove directly that a statement of the form (∃x ∈ U)P (x) is true we
proceed as follows:

• We must find, or simply exhibit, an element x ∈ U and demonstrate

that P (x) is true.

Example 21. Show that there exists x ∈ R such that 2x + 1 = 0.

Example 22. Show that there exists x ∈ R such that x2 + x − 1 = 0.

2.2.2 Uniqueness in proofs of existential statements

Let P (x) be a predicate. There are two equivalent ways to express the statement
“there exists a unique x such that P (x)”:

(2.1) (∃x)[P (x) ∧ ((∀y)[P (y) =⇒ (x = y)])]

or
(2.2) [(∃x)P (x)] ∧ [(∀y)(∀z)[(P (y) ∧ P (z)) =⇒ (y = z)]].
Both logical formulas (2.1) and (2.2) are abbreviated as (∃!x)P (x). There-
fore, to prove that there exists a unique x ∈ U such that P (x) is true we can
proceed in two different ways.
Proof Technique 2: Uniqueness, first approach

• We first find, or simply exibit, an element a ∈ U and demonstrate

that P (a) is true.
• Then, we demonstrate that if x is such that P (x) is true then
necessarily x = a.

Proof Technique 3: Uniqueness, second approach

• We first find, or simply exibit, an element a ∈ U and demonstrate

that P (a) is true.
• Then, we prove that if x, y are such that if P (x) and P (y) are true
then x = y,

Example 23. Prove that the equation 2x + 1 = 0 has a unique solution.

Example 24. Prove that the equation x2 + 2x + 1 = 0 has a unique solution.
2.3. PROOFS OF UNIVERSAL STATEMENTS 17

2.3 Proofs of universal statements

A universal statement is a statement of the form (∀x)P (x) where P (x) is some
given predicate. We discuss two very common occurrences of universal state-
ments.

2.3.1 Universal statements of the form (∀x ∈ U)P (x)

We first describe how to prove statements with universal quantifiers.
Proof Technique 4: Direct proof of (∀x ∈ U)P (x)

To prove directly that a statement of the form (∀x ∈ U)P (x) is true we
proceed as follows:
• We begin with “Let x be a fixed element of U.”
• Then, we must demonstrate that P (x) is true.

• Finally, we must check that no restriction other than being in U

has been imposed on x and thus our proof is valid for an arbitrary
choice of x ∈ U. If this is the case, we could conclude by saying
that x was fixed but arbitrary.

For the following example we need to define the notion of odd number.
Definition 16: Odd numbers
Let n be an integer. We say that n is odd if there exists an integer k
such that n = 2k + 1. Formally,

n is odd ⇐⇒ (∃k ∈ Z)(n = 2k + 1)

Example 25. Prove that for all n ∈ N, 6n + 5 is odd.

2.3.2 Statements of the form (∀x ∈ U)[P (x) =⇒ Q(x)]

Many of the statements we will have to prove are of the form (∀x ∈ U)[P (x) =⇒
Q(x)].
Proof Technique 5: Direct proof of (∀x ∈ U)[P (x) =⇒ Q(x)]

According to the implication truth table, to prove directly that a state-

ment of the form (∀x ∈ U)[P (x) =⇒ Q(x)] is true we proceed as
follows:
• We begin with “Let x ∈ U, such that P (x) is true, be fixed”.
• Then, we must demonstrate that Q(x) is true.
• Finally, we must check that no restriction other than being in U
and satisfying P has been imposed on x and thus our proof is valid.

For the following example we need to define the notion of even number.
18 CHAPTER 2. CLASSICAL PROOF TECHNIQUES

Definition 17: Even numbers

Let n be an integer. We say that n is even if there exists an integer k
such that n = 2k. Formally,

n is even ⇐⇒ (∃k ∈ Z)(n = 2k)

Example 26. Prove that for all integer n if n is even, then n2 + 5n + 2 is even.
The mechanism of the proof technique above can be adjusted to handle
statements involving several universal quantifiers and implications where the
assumption in the implication does not necessarily involve the variables. For
the following example we need to define the notion of divisibility.
Definition 18: Divisibility

Let n be an integer. We say that n is divisible by the integer k (or that

k divides n), and we write k | n, if there exists an integer r such that
n = rk. Formally,

k | n ⇐⇒ (∃r ∈ Z)(n = rk)

Example 27. Let a and b be integers. Prove that for all integers m and n, if
7 | a and 7 | b, then 7 | (am + bn).

2.3.3 Disproving universal statements: counterexamples

The negation of the statement (∀x)P (x) is the statement (∃x)¬P (x). Therefore
to show that a statement of the form (∀x)P (x) is false we need to find an
assignment of x (still denoted by x) such that P (x) is false.
Terminology. An assignment of the variable x such that ¬P (x) is true, is called
a counterexample for the statement (∀x)P (x).
We now discuss how to disprove some of the most common universal state-
ments.
Proof Technique 6: Disproving (∀x ∈ U)P (x)

To prove that a statement of the form (∀x ∈ U)P (x) is false we proceed
as follows:
• We find an assignment of the variable x ∈ U (still denoted by x)
such that P (x) is false.

For the following example we need to define the notion of prime number.
Definition 19: Prime numbers
Let p be a natural number. We say that p is a prime number if it is only
divisible by 1 and p itself. Formally,

p is a prime number ⇐⇒
[(p > 1) ∧ [(∀m ∈ N)(∀n ∈ N)[p = mn =⇒ ((m = 1) ∨ (n = 1))]].
2.4. PROOFS BY CONTRAPOSITIVE 19

Example 28. Is the following statement true or false?

For all positive integers n, n2 + n + 41 is prime.
The negation of the statement (∀x ∈ U)[P (x) =⇒ Q(x)] is the statement
(∃x ∈ U)¬[P (x) =⇒ Q(x)], and thus the negation of (∀x ∈ U)[P (x) =⇒ Q(x)]
is logically equivalent to (∃x ∈ U)P (x) ∧ ¬Q(x). Note that the negation of an
implication is not an implication!
Proof Technique 7: Disproving (∀x ∈ U)[P (x) =⇒ Q(x)]

To prove that a statement of the form (∀x ∈ U)[P (x) =⇒ Q(x)] is false
we proceed as follows:
• We find an assignment of the variable x ∈ U (still denoted by x)
such that P (x) is true and Q(x) is false.

Example 29. Prove or disprove that for all integer n, if n is even then n2 + 1 is
even.

2.4 Proofs by contrapositive

The statement forms P =⇒ Q and ¬Q =⇒ ¬P are logically equivalent.
Proof Technique 8: Proving the contrapositive

To prove P =⇒ Q one may choose instead to prove ¬Q =⇒ ¬P .

Example 30. Let n be an integer. If n3 is odd, then n is odd.

Example 31. For this example you can use the following fact that will be proven
later: 5 does not divides n if and only if there exists an integer k and an integer
i ∈ {1, 2, 3, 4} such that n = 5k + i.
Prove that for every integer n, if 5 divides n2 then 5 divides n.

2.5 Proof by contradiction

A proof by contradiction is based on the observation that the statement form
(¬P ) =⇒ [Q ∧ ¬Q] is logically equivalent to P .

P Q Q ∧ ¬Q ¬P (¬P ) =⇒ [Q ∧ ¬Q]
T T F F T
T F F F T
F T F T F
F F F T F

Therefore, in order to prove a statement P , for example, we could assume

that P is false and deduce a statement that we know is false (like 0 = 1 or 21 is
an integer...).
20 CHAPTER 2. CLASSICAL PROOF TECHNIQUES

Proof Technique 9: Proof by contradiction

To prove a statement P is true by contradiction we proceed as follows:

• We begin first with “Assume ¬P is true for the sake of contradic-

tion.”
• Then, we deduce a contradiction.
• Finally, we conclude that P must be true.

Example 32. Prove that there does not exist integers m and n such that 15m +
5n = 81.
Example 33. Let x ∈ R. If for all ε > 0, |x| < ε, then x = 0.
A classical use of a proof by contradiction allows us to show that some real
numbers are irrational.
√
Theorem 6: Irrationality of 2
√
The real number 2 is irrational.

Recall that a number x is irrational if it is not rational, i.e.,

 
p
¬ (∃p ∈ N)(∃q ∈ Z+ ) = x

q

Another celebrated proof by contradiction is a proof of Euclid’s Theorem.

Euclid’s Theorem says that there are infinitely many prime numbers. We recall
the formal definition of a prime number.

Definition 20: Prime numbers

A natural number p is prime if

p > 1 and (∀m, n ∈ N)[p = mn =⇒ (m = 1 ∨ n = 1)].

We will assume the Fundamental Theorem of Arithmetic.

Theorem 7: Fundamental Theorem of Arithmetic
Every positive integer greater than 1 can be written as a product of
primes. Furthermore, this product of primes is unique, except for the
order in which the factors appear.

Theorem 8: Euclid’s Theorem

There are infinitely many prime numbers.
2.6. OTHER USEFUL PROOF TECHNIQUES 21

2.6 Other useful proof techniques

2.6.1 Proving biconditional statements
Since P ⇐⇒ Q is logically equivalent to (P =⇒ Q) ∧ (Q =⇒ P ), in order
to prove that a statement of the form P ⇐⇒ Q is true, we need to prove that
P =⇒ Q AND that Q =⇒ P .
Proof Technique 10: Biconditional statements P ⇐⇒ Q

1. Prove P =⇒ Q

and
2. prove Q =⇒ P .

Example 34. Prove that for all integer n,

n is even ⇐⇒ n + 2 is even.

Example 35. Prove that for all numbers x, y ∈ R with y ≥ 0, |x| ≤ y if and only
if −y ≤ x ≤ y.

2.6.2 Proving disjunction statements

Let P and Q be statements. To prove disjunction statements we can use the
observation that P ∨ Q, ¬P =⇒ Q, and ¬Q =⇒ P are logically equivalent.

P Q P ∨Q ¬P =⇒ Q ¬Q =⇒ P
T T T T T
T F T T T
F T T T T
F F F F F

Proof Technique 11: Proving disjunction statements

To prove that a statement of the form P ∨ Q is true, we may choose

either one of the following to options:

1. Assume ¬P and prove Q,

or
2. assume ¬Q and prove P .

Example 36. Prove that for all real numbers x and y with y ≥ 0, if x2 ≥ y, then
√ √
x ≥ y or x ≤ − y

2.6.3 Proof by cases

Example 37. Prove that for all integer k, k(k + 1) is even.
22 CHAPTER 2. CLASSICAL PROOF TECHNIQUES

Example 38. Prove that for all real numbers x and y, |x + y| ≤ |x| + |y|.
Hint.

2.6.4 Working backwards

x x+1
Example 39. Prove that for every positive real number x, one has x+1 < x+2 .
Chapter 3

Induction

3.1 Principle of Mathematical Induction

The principle of mathematical induction is a very powerful tool to deal with
infinite objects and to prove rigorously infinitely many (in the sense that they
can be enumerated) statements.
Theorem 9: Principle of Mathematical Induction

Let P (n) be a predicate where the variable takes integer values. Suppose
that there exists k0 ∈ Z such that
P (k0 ) is true (the base case)
and

for all k ≥ k0 , P (k + 1) is true under the assumption that P (k) is true

(the induction step),
then for all k ≥ k0 P (k) is true (the conclusion).

Proof. Follows from the Induction Axiom applied to the set Y := {n ∈ N|P (k0 +
n) is true}.

The principle of mathematical induction is most commonly used with k0 = 0

or k0 = 1.
Pn
Example 40. Show that for all integers n ≥ 1, i=1 i = n(n+1)
2 .

Pn n(n+1)
Solution: For all integers n ≥ 1, let P (n) : i=1 i= 2 .
P1 1(1+1) P1 1(1+1)
Base case: Since i=1 i = 1 and 2 = 1, one has that i=1 i = 2
and P (1) is true.

Induction step: Let k ≥ 1 and assume that P (k) is true, i.e. we assume that

23
24 CHAPTER 3. INDUCTION

Pk k(k+1)
i=1 i= 2 . Then,

k+1
X k
X
i= i + (k + 1)
i=1 i=1
k(k + 1)
= + (k + 1) (by the induction hypothesis)
2
(k + 1)(k + 2)
= ,
2

and hence P (k + 1) is true.

Conclusion: By the Principle of Mathematical Induction, one can conclude

Pn
that ∀n ≥ 1, P (n) is true, which means that for all n ≥ 1, i=1 i = n(n+1)
2 .

Example 41. Show that the following equalities hold.

Pn n(n+1)(2n+1)
1. for all n ≥ 1, i=1 i2 = 6 .

Pn n2 (n+1)2
2. for all n ≥ 1, i=1 i3 = 4 .

Pn 2 2n(2n+1)(2n+2)
3. for all n ≥ 1, i=1 (2i) = 6 .
Pn
Solutions. 1. Let P (n) be the statement “ i=1 (2i − 1) = n2 ”.

Base case Since 1 = 12 , P (1) is true.

Pn
Induction Step Assume that P (n) is true, i.e. we assume that i=1 (2i−
1) = n2 . Then,

n+1
X n
X
(2i − 1) = (2i − 1) + (2(n + 1) − 1)
i=1 i=1
2
= n + (2n + 1) (by the induction hypothesis)
= (n + 1)2 ,

and hence P (n + 1) is true. By the Principle of Mathematical Induction,

one canPconclude that ∀n ≥ 1, P (n) is true, which means that for all
n
n ≥ 1, i=1 (2i − 1) = n2 .

Pn n(n+1)(2n+1)
2. Let P (n) be the statement “ i=1 i2 = 6 ”.

1(1+1)(2+1)
Base case Since 12 = 6 , P (1) is true.
Pn
Induction Step Assume that P (n) is true, i.e. we assume that i=1 i2 =
3.2. PRINCIPLE OF STRONG MATHEMATICAL INDUCTION 25

n(n+1)(2n+1)
6 . Then,
n+1
X n
X
i2 = i2 + (n + 1)2
i=1 i=1
n(n + 1)(2n + 1)
= + (n + 1)2 (by the induction hypothesis)
6
n(n + 1)(2n + 1) + 6(n + 1)2
=
6
(n + 1)(n(2n + 1) + 6(n + 1))
=
6
(n + 1)(2n2 + 7n + 6)
=
6
(n + 1)(n + 2)(2n + 3)
=
6
(n + 1)((n + 1) + 1)(2(n + 1) + 1)
=
6

and hence P (n + 1) is true. By the Principle of Mathematical Induction,

one can conclude that ∀n ≥ 1, P (n) is true, which means that for all
Pn
n ≥ 1, i=1 i2 = n(n+1)(2n+1)
6 .
3. exercise
4. exercise
5. exercise

3.2 Principle of Strong Mathematical Induction

Theorem 10: Principle of Strong Mathematical Induction

Let P (n) be a predicate where the variable takes integer values. Suppose
that there exists an integer k0 such that
P (k0 ) is true (the base case),

and
for all k ≥ k0 , P (k + 1) is true under the assumption that for all r ∈
{k0 , k0 + 1, . . . , k} P (r) is true (the induction step),
then for all n ≥ k0 P (n) is true (the conclusion).

Theorem 11: Fundamental Theorem of Arithmetic

Every positive integer greater than 2 can be written as a product of
primes. Furthermore, this product of primes is unique, except for the
order in which the factors appear.
26 CHAPTER 3. INDUCTION

Proof. Formally the statement says that for all integer n ≥ 2 there exists
p1 , p2 , . . . , pk prime numbers for some k ∈ N such that n = p1 p2 · · · pk . We
will show that it is indeed true using the principle of strong mathematical in-
duction. For n = 2 the statement is clearly true since 2 is a prime number.
Let n ≥ 2 and assume that for all integer r such that 2 ≤ r ≤ n, r is a prod-
uct of prime numbers. If n + 1 is prime then the conclusion holds. If n + 1
is not prime then there are integers 1 < a < n + 1 and 1 < b < n + 1 such
that n + 1 = ab . Since 2 ≤ a ≤ n and 2 ≤ b ≤ n, a and b are products of
prime numbers, say a = p1 p2 · · · pk and b = q1 q2 · · · qs for some prime num-
bers p1 , p2 , . . . , pk , q1 , q2 , . . . , qs . Thus, n + 1 = ab = (p1 p2 · · · pk )(q1 q2 · · · qs ) =
p1 p2 · · · pk q1 q2 · · · qs which is a product of prime numbers. We conclude by in-
voking the principle of strong mathematical induction.
Exercise 5. Consider the sequence (an )∞n=1 recursively defined as a1 = 1, a2 = 5
and for all n ≥ 2, an+1 = an + 2an−1 . Show that for all n ≥ 1, an = 2n + (−1)n .
Solution: For all n ∈ N, let P (n) be the predicate an = 2n + (−1)n .
Base case: Since a1 = 1 and 21 + (−1)1 = 2 − 1 = 1, one has that a1 =
21 + (−1)1 and P (1) is true.
Induction step: Let k ≥ 1 and assume that for all r ∈ {1, 2, . . . , k} P (r) is
true, i.e. we assume that for all r ∈ {1, 2, . . . , k} ar = 2r + (−1)r . We
want to show that P (k + 1) is true. In this problem, the case k = 1 has
to be treated separately. If k = 1, observe that P (2) is true (regardless
of the truth value of P (1)) since 22 + (−1)2 = 5 = a2 and thus in par-
ticular if P (1) is true then P (2) is true. Otherwise, if k ≥ 2, assuming
P (1), P (2), . . . , P (k) are true, then
ak+1 = ak + 2ak−1 (here we need k ≥ 2 since a0 is not defined)
= 2k + (−1)k + 2(2k−1 + (−1)k−1 ) (by the induction hypothesis)
= 2 · 2k + (−1)k−1 (−1 + 2)
= 2k+1 + (−1)k+1 (since (−1)k+1 = (−1)k−1 ),
and hence P (k + 1) is true.
Conclusion: By the Principle of Strong Mathematical Induction, one can con-
clude that for all n ≥ 1, P (n) is true, which means that for all n ≥ 1,
an = 2n + (−1)n .

The more traditional way to write your solution is as follows.

Alternate Solution: For all n ∈ N, let P (n) be the predicate an = 2n + (−1)n .
Since a1 = 1 and 21 + (−1)1 = 2 − 1 = 1, one has that a1 = 21 + (−1)1
and P (1) is true. Since 22 + (−1)2 = 5 = a2 , P (2) is also true. Let k ≥ 2, and
assume P (1), P (2), . . . , P (k) are true, then
ak+1 = ak + 2ak−1 (here we need k ≥ 2 since a0 is not defined)
= 2k + (−1)k + 2(2k−1 + (−1)k−1 ) (by the induction hypothesis)
= 2 · 2k + (−1)k−1 (−1 + 2)
= 2k+1 + (−1)k+1 (since (−1)k+1 = (−1)k−1 ),
3.2. PRINCIPLE OF STRONG MATHEMATICAL INDUCTION 27

and hence P (k + 1) is true. By the Principle of Strong Mathematical Induction,

one can conclude that for all n ≥ 1, P (n) is true, which means that for all n ≥ 1,
an = 2n + (−1)n .
28 CHAPTER 3. INDUCTION
Chapter 4

Introduction to Elementary
Set Theory

4.1 Sets and subsets

We won’t give a formal definition of the notion of a set but we will understand
the word set as an undefined term which refers to a collection of objects. The
objects in a set are called elements and we use the notation x ∈ X to express
that the element x is in the set X. The notion of membership is also not formally
defined and is part of the concept of a set. We use the abbreviation x ∈ / X for
¬(x ∈ X).

Axiom There is a set with no elements which is called the empty set and is
denoted by ∅.

Observe that x ∈ ∅ is always false regardless of the element x that is under

consideration, and thus x ∈
/ ∅ is always true.
Example 42. Classical sets.

1. N := {1, 2, 3, . . . }, the natural numbers.

2. Z := {. . . , −2, −1, 0, 1, 2, . . . }, the integers

3. Q := { pq | p ∈ Z, q ∈ N}, the rational numbers.

4. R, the real numbers

Definition 21: Truth set of a predicate

Let P (x) be a predicate and U be the ambient set. The set

A := {x ∈ U| P (x) is true}

is called the truth set of the predicate P (x).

Example 43. 1. {x ∈ Z | (∃k ∈ Z)[x = 5k]}

29
30 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

2. {x ∈ R | (x > 0) ∧ (x2 ∈ Z+ )}

Definition 22: Sets of the form nZ

Let n ∈ Z. We define a set denoted nZ as follows:

nZ := {x ∈ Z | (∃k ∈ Z)[x = nk]}

For instance, 5Z is the set {x ∈ Z | (∃k ∈ Z)[x = 5k]} which is also sometimes
simply described as {5k | k ∈ Z}.
Example 44. Let a < b be real numbers. There are 9 types of elementary
intervals of real numbers.

1. [a, b] the closed interval.

2. (a, b) the open interval.

3. (a, b] half-open, half-closed

4. [a, b) half-open, half-closed

5. [a, +∞) unbounded

6. (a, +∞) unbounded

7. (−∞, a] unbounded

8. (−∞, a) unbounded

9. (−∞. + ∞) = R unbounded

Definition 23: Subset

Let X and Y be sets. We say that X is a subset of Y , and write X ⊆ Y ,
if every element of X is also an element of Y . Formally,

X ⊆ Y ⇐⇒ (∀x)[x ∈ X =⇒ x ∈ Y ].

Remark 1. The expression X ⊆ Y is a very convenient abbreviation for the

statement (∀x)[x ∈ X =⇒ x ∈ Y ]. To prove that X ⊆ Y you need to prove an
implication with a universal quantifier.
Example 45. N ⊂ Z ⊂ Q ⊂ R
Example 46. We write X * Y for ¬(X ⊆ Y ). Give a formal statement express-
ing X * Y .

Solution:
4.1. SETS AND SUBSETS 31

Example 47. Let X = {n ∈ Z | n is a multiple of 4} and Y = {n ∈ Z | n is even}.

Prove that X ⊆ Y .

Solution:

Proposition 2

Let X be a set. Then,

1. ∅ ⊆ X.

2. X ⊆ X

Proof. 1. ∅ ⊂ X follows from the fact that the implication x ∈ ∅ =⇒ x ∈

X is always true (i.e. a tautology) since x ∈ ∅ is always false (i.e. a
contradiction).

2. X ⊆ X follows from the fact that (x ∈ X) =⇒ (x ∈ X) is always true

(indeed P =⇒ P is a tautology).

Proposition 3: Transitivity of the subset relation

Let X, Y , and Z be non-empty sets. If X ⊆ Y and Y ⊆ Z, then X ⊆ Z.

Proof. (Hint: Direct proof.) Assume that X ⊆ Y and Y ⊆ Z. Let x ∈ X then

it follows from X ⊆ Y that x ∈ Y . Moreover, it follows from Y ⊆ Z that x ∈ Z.
Therefore X ⊆ Z.

Definition 24: Equality between sets

We say that two sets X and Y are equal, written X = Y , if they have
the same elements. Formally,

X = Y ⇐⇒ (X ⊆ Y ) ∧ (Y ⊆ X).

Note that X = Y is logically equivalent to (∀x)[x ∈ X ⇐⇒ x ∈ Y ].

Example 48. Prove that X = {n ∈ Z | n + 5 is odd} is the set of all even
integers.

Solution:
32 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

Definition 25: Proper subsets

Let X be a subset of Y . We say that X is a proper subset of Y , and we

write X ⊂ Y , if X 6= Y . Formally,

X ⊂ Y ⇐⇒ (X ⊆ Y ) ∧ (X 6= Y ).

Example 49. Show that the set X = 33Z is a proper subset of Z.

4.2 Operation on sets

In this section we describe several natural operations on sets that can be used
to create new sets out of given sets.

4.2.1 Union and intersection of two sets

We start with the most natural operations on a pair of sets; union and intersec-
tion.
Definition 26: Union of two sets
Let X and Y be sets. The union of X and Y , denoted X ∪ Y , is the set
of all elements that belong to X or to Y . Formally,

X ∪ Y = {z | (z ∈ X) ∨ (z ∈ Y )}.

Taking the union of two sets provides a set that is “bigger” in the sense that
it contains both sets. The following two properties can be deduced from logical
principles.
Proposition 4

Let X, Y, Z be sets. Then,

1. X ∪ ∅ = X
2. X ∪ Y = Y ∪ X (commutativity of the union operation)

3. (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) (associativity of the union operation)

Proof. 1. X ∪ ∅ = X follows from the fact that (x ∈ X) ∨ (x ∈ ∅) is logically

equivalent to (x ∈ X) since (x ∈ ∅) is always false.
2. X ∪ Y = Y ∪ X follows from the fact that (z ∈ X) ∨ (z ∈ Y ) is logically
equivalent to (z ∈ Y ) ∨ (z ∈ X) (indeed P ∨ Q ≡ Q ∨ P ).
3. (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) follows from the fact that ((a ∈ X) ∨ (a ∈
Y )) ∨ (a ∈ Z) is logically equivalent to (a ∈ X) ∨ ((a ∈ Y ) ∨ (a ∈ Z))
(indeed (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)).
4.2. OPERATION ON SETS 33

Proposition 5

Let X and Y be sets. Then,

1. X ⊆ X ∪ Y
2. Y ⊆ X ∪ Y
3. X ⊆ Y ⇐⇒ X ∪ Y = Y

Proof. 1. If X = ∅ the inclusion holds, otherwise let x ∈ X. Then x ∈ X ∪ Y

by definition of the union, and thus X ⊆ X ∪ Y .

2. If Y = ∅ the inclusion holds, otherwise let y ∈ Y . Let y ∈ Y . Then

y ∈ X ∪ Y by definition of the union, and thus Y ⊆ X ∪ Y .

3. We first prove =⇒ :
Assume that X ⊆ Y . Observe first that X ⊆ X ∪ Y always holds. If
X ∪ Y = ∅ the reverse inclusion holds, otherwise let z ∈ X ∪ Y . Then
either z ∈ Y or z ∈ X. But in the latter case it follows from X ⊆ Y
that z ∈ Y . In all cases z ∈ Y and thus X ∪ Y ⊆ Y . Combining the two
inclusions we have X ∪ Y = Y .
We now prove ⇐=:
Assume that X ∪ Y = Y . If X = ∅ the inclusion holds, otherwise let
x ∈ X. Then x ∈ X ∪ Y by definition of the union and thus x ∈ Y follows
from the assumption X ∪ Y = Y . Therefore, X ⊆ Y .

Definition 27: Intersection of two sets

Let X and Y be sets. The intersection of X and Y , denoted X ∩ Y , is
the set is the set of all elements that belong to X and to Y . Formally,

X ∩ Y = {z | (z ∈ X) ∧ (z ∈ Y )}.

Taking the intersection of two sets provides a set that is “smaller” in the
sense that it is contained in both sets. The following two properties can be
deduced from logical principles.
Proposition 6

Let X, Y, Z be sets. Then,

1. X ∩ ∅ = ∅

2. X ∩ Y = Y ∩ X (commutativity of the intersection operation)

3. (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) (associativity of the union operation)

Proof. 1. X ∩ ∅ = ∅ follows from the fact that (x ∈ X) ∧ (x ∈ ∅) is always

false since (x ∈ ∅) is always false.
34 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

2. X ∩ Y = Y ∩ X follows from the fact that (z ∈ X) ∧ (z ∈ Y ) is logically

equivalent to (z ∈ Y ) ∧ (z ∈ X) (indeed P ∧ Q ≡ Q ∧ P ).

3. (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) follows from the fact that ((a ∈ X) ∧ (a ∈

Y )) ∧ (a ∈ Z) is logically equivalent to (a ∈ X) ∧ ((a ∈ Y ) ∧ (a ∈ Z))
(indeed (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)).

Proposition 7

Let X and Y be sets. Then,

1. X ∩ Y ⊆ X,

2. X ∩ Y ⊆ Y ,
3. X ⊆ Y ⇐⇒ X ∩ Y = X.

Proof. 1. If X ∩ Y = ∅ then X ∩ Y ⊆ X. Otherwise let z ∈ X ∩ Y , and then

z ∈ X by definition of the intersection, and thus X ∩ Y ⊆ X.

2. If X ∩ Y = ∅ then X ∩ Y ⊆ Y . Otherwise let z ∈ X ∩ Y , and then z ∈ Y

by definition of the intersection, and thus X ∩ Y ⊆ Y .

3. We first prove =⇒ :
Assume that X ⊆ Y . Observe first that X ∩Y ⊆ X always holds. If X = ∅
the reverse inclusion holds, otherwise let z ∈ X. Then z ∈ Y follows from
the assumption X ⊆ Y , and hence z ∈ X ∩ Y . Therefore X ⊆ X ∩ Y and
combining the two inclusions we have X ∪ Y = Y .
We now prove ⇐=:
Assume that X ∩ Y = X. If X = ∅ the inclusion holds, otherwise let
x ∈ X. Then it follows from the assumption X ∩ Y = X that x ∈ X ∩ Y ,
and hence x ∈ Y by definition of the intersection. Therefore, X ⊆ Y .

Definition 28: Disjoint sets

We say that two sets X and Y are disjoint if they have no element in
common, or equivalently if their intersection is the empty set. Formally,

X and Y are disjoint ⇐⇒ X ∩ Y = ∅.

The distributivity properties of the union operation over the intersection

operation, and vice versa, follow from the two logical equivalences P ∧(Q∨R) ≡
(P ∧ Q) ∨ (P ∧ R) and P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R), but you could try to
write “double-inclusion mathematician’s proofs”.
4.2. OPERATION ON SETS 35

Proposition 8: Distributivity Properties

Let X, Y , Z be sets. Then,

1. X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z),
2. X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z).

4.2.2 Complement
The notion of complement is described in this section.
Definition 29: Complement

Let X and Y be sets. The complement of X in Y , denoted Y − X, is

the set of elements that are in Y but not in X. Formally,

Y − X = {z | (z ∈ Y ) ∧ (z ∈
/ X)}.

For convenience, if U is the ambient set, the set U − X will be simply

denoted by X, and called the complement of X. Formally,

X = {z ∈ U | z ∈
/ X}.

Remark 2. The definition of the complement of X in Y does NOT assume that

either set be a subset of the other.
In the following proposition we record some elementary properties that can
be obtained from logical principles.
Proposition 9

Let X and Y be subsets of a universal set U . Then

1. U = ∅,

2. ∅ = U .
3. X − Y = X ∩ Y ,
4. ∅ − X = ∅,

5. X − ∅ = X.
6. X = X

Taking complements reverse the inclusion relationship.

Proposition 10: Complements of subsets

Let X and Y be subsets of some universal set U . Then X ⊆ Y if and

only if Y ⊆ X.
36 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

Proof. We first prove the “if” part. Assume that Y ⊆ X. If X = ∅ then X ⊆ Y .

Otherwise, let x ∈ X then x ∈ / X by definition of the complement, and it follows
from our assumption that x ∈ / Y . Therefore, x ∈ Y and thus X ⊆ Y .
The proof of the “only if” part goes as follows. Assume that X ⊆ Y . If
Y = ∅ then Y ⊆ X. Otherwise, let z ∈ Y then z ∈ / Y by definition of the
complement, and hence z ∈ / X by our assumption. Therefore, z ∈ X and thus
Y ⊆ X.

We now prove De Morgan’s laws, which state that the complement of the
union is the intersection of the complements, and that the complement of the
intersection is the union of the complements.
Theorem 12: DeMorgan’s Laws

Let X and Y be subsets of a universal set U . Then

1. X ∪ Y = X ∩ Y ,
2. X ∩ Y = X ∪ Y .

Proof. 1. We first prove the inclusion X ∪ Y ⊆ X ∩Y . If X ∪ Y = ∅ then the

inclusion holds, otherwise let z ∈ X ∪ Y . Then z ∈/ X ∪ Y (by definition
of the complement), and it follows that z ∈ / X and z ∈ / Y (by definition
of the union). Thus, z ∈ X and x ∈ Y (by definition of the complement),
which means that z ∈ X ∩ Y (by definition of the intersection).

For the reverse inclusion, if X ∩ Y = ∅ then the inclusion holds, otherwise

let z ∈ X ∩ Y . Then z ∈ X and z ∈ Y (by definition of the intersection),
and thus z ∈ / X and z ∈/ Y (by definition of the complement). It follows
that z ∈/ X ∪ Y (by definition of the union), and hence z ∈ X ∪ Y (by
definition of the complement).
Therefore, it follows from the definition of equality between sets that
X ∪Y =X ∩Y.

2. homework

Remark 3. The proof above of the De Morgan’s laws, which is a basic-double

inclusion proof and uses the logic of connectives implicitly, is the typical proof
a mathematician would write. However, a logician will argue that the equality
holds since he, or she, will recognize that the truth of the statement follows from
the logical equivalence of two statement forms. Indeed, consider the predicates
P (z) : “z ∈ X” and Q(z) : “z ∈ Y ”. From the logic standpoint X ∪ Y = X ∩ Y
is actually a convenient abbreviation for the proposition

(∀z ∈ U )[¬(P (z) ∨ Q(z)) ⇐⇒ (¬P (z) ∧ ¬Q(z))].

But, we have proven that ¬(P ∨ Q) is logically equivalent to (¬P ∧ ¬Q) no

matter what statements are substituted for P and we can conclude that the
equality actually holds! Similarly, the second equality holds since from the
4.2. OPERATION ON SETS 37

logic standpoint X ∩ Y = X ∪ Y is actually a convenient abbreviation for the

statement
(∀z ∈ U )[¬(P (z) ∧ Q(z)) ⇐⇒ (¬P (z) ∨ ¬Q(z))].
But, as we have proven that ¬(P ∧ Q) is logically equivalent to (¬P ∨ ¬Q) we
conclude as above.

4.2.3 Arbitrary unions and intersections

For all i ∈ I, where I is called the indexing set, let Xi be a subset of some
universal set. We use the notation {Xi | i ∈ I} or (Xi )i∈I to denote the
collection of such sets. In the previous section we defined the union of two sets.
Based on the definition of the union of two sets we can naturally recursively
define the union of Sfinitely many sets X1 , X2 , . . . , Xn , for n ≥ 2, this new set
n
will be denoted by k=1 Xk , as follows:
2
[
Xk = X1 ∪ X2 ,
k=1

and for n ≥ 3
n
[ n−1
[
Xk = ( Xk ) ∪ Xn .
k=1 k=1

Since the operation of taking union is associative these new sets are unam-
biguously defined. Using a similar approach we can define the intersection of
finitely many sets. Unfortunately, we cannot use a recursive definition to define
arbitrary infinite unions or intersections (e.g. if the index I = R) and we need
to proceed differently and define arbitrary unions as the truth set of a certain
predicate.
Definition 30: Arbitrary unions

Let I be a set and (Xi )i∈ISbe a collection of sets. The union of the
collection (Xi )i∈I , denoted i∈I Xi is the set of all elements that belong
to at least one set of the collection. Formally,
[
Xi = {x | (∃i ∈ I)[x ∈ Xi ]}.
i∈I

Remark 4. We Sn can easily show using the principle of mathematical

S induction
that the set k=1 Xk that was recursively defined and the set i∈{1,2,...,n} Xi
where I = {1, 2, . . . , n} defined S
using the truth
S set coincide and the two def-
n
initions are compatible. Since k=1 Xk = i∈{1,2,...,n} Xi we will use both
notations interchangeably.
S∞ S
Remark 5. If I = N we write n=1 Xn for n∈N Xi .

Proposition 11

S (Xi )i∈I be a collection of sets. Then, for all j ∈ I one has Xj ⊆

Let
i∈I Xi .
38 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

S∞
Exercise 6. Let Xn = [1, 1 + n1 ] for n ∈ N. Compute i=n Xn .

Solution:

S∞
Exercise 7. Let Xn = ( n3 , 5n] for n ≥ 1. Compute n=1 Xn .
S∞
Solution: We will show that n=1 Xn = (0, ∞).
S∞
• First, we show that n=1 Xn ⊆ (0, ∞).
S∞
Let x ∈ n=1 Xn , then there exists k ≥ 1 such that x ∈ Xk = ( k3 , 5k] and
hence k3 < x ≤ 5k. Since it follows from k ≥ 1 that k3S≥ 3 > 0 and 5k < ∞
∞
one has 0 < x < ∞ and thus x ∈ (0, ∞). Therefore n=1 Xn ⊆ (0, ∞)
S∞
• We now show that (0, ∞) ⊆ n=1 Xn .
Assume now that x ∈ (0, ∞), then x > 0 and also x5 > 0. On the one
hand, if follows from the Archimedean principle that there is some n1 ∈ N
such that n1 > x5 , so 5n1 ≥ x. On the other hand, x3 > 0 and it follows
from the Archimedean principle that there exists n2 ∈ N such that x3 < n2
and hence x > n32 . Let k = max{n1 , n2 } ≥ 1 then k3 ≤ n32 < x ≤ 5n1 ≤ k
S∞
and hence x ∈ Xk . Therefore, (0, ∞) ⊆ n=1 Xn .
S∞
By combining the two inclusions we get n=1 Xn ⊆ (0, ∞).

Using a similar approach we can define arbitrary intersections.

Definition 31: Arbitrary intersections

Let I be a set and {Xi | i T ∈ I} be a collection of sets. The intersection

of the collection, denoted i∈I Xi is the set of all elements that belong
to all sets of the collection. Formally,
\
Xi = {x | (∀i ∈ I)[x ∈ Xi ]}.
i∈I

T∞ T
Remark 6. If I = N we write n=1 Xi for n∈N Xn .
4.2. OPERATION ON SETS 39

Proposition 12
T
Let (Xi )i∈I be a collection of sets. Then, for all j ∈ I one has i∈I Xi ⊆
Xj .

T∞
Exercise 8. Let Xn = [1, 1 + n1 ] for n ∈ N. Compute n=1 Xn .

Solution:

T∞
Exercise 9. Let Xn = ( n3 , 4n] for n ≥ 1. Compute n=1 Xn .

Solution:

Theorem 13: DeMorgan’s Laws for arbitrary unions and inter-

sections

Let (Xi )i∈I be a collection of set. Then

S T
1. i∈I Xi = i∈I Xi ,
T S
2. i∈I Xi = i∈I Xi .

Proof. homework
40 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

4.2.4 Power set

We will now consider sets whose elements are sets themselves.
Definition 32: Power set of a set

Let X be a set. The power set of X, denoted P(X) or 2X , is the set of

all subsets of X. Formally,

P(X) = {Y | Y ⊆ X}.

Remark 4
• Do not forget the empty set and the set itself in the power set! In
particular, the power set of a set is never empty.
• If follows from the definition that

A ⊆ X ⇐⇒ A ∈ P(X).

Example 50. The power set of X = {1, 2, 3} is

P(X) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Example 51. The power set of X = ∅ is
P(∅) = {∅},
and 
P(P(∅)) = P ({∅}) = ∅, {∅} ,
and

P(P(P(∅))) = P(P({∅})) = P({∅, {∅}}) = ∅, {∅}, {{∅}}, {∅, {∅}} ,
etc...
Theorem 14
Let X and Y be sets. Then,

X ⊆ Y ⇐⇒ P (X) ⊆ P (Y ).

Proof. We will prove the two implications separately.

• =⇒ : Assume that X ⊆ Y . Let A ∈ P(X) then A ⊆ X and by transitivity
of the subset relation since X ⊆ Y one has A ⊆ Y . Therefore A ∈ P(Y ),
and P(X) ⊆ P(Y ).
• ⇐=: Assume that P(X) ⊆ P(Y ). Since X ⊆ X then X ∈ P(X) and thus
X ∈ P(Y ) by our assumption. Therefore, X ⊆ Y .

Exercise 10. Show that for all n ≥ 0, if X is a set with exactly n elements then
the number of sets in the power set of X is equal to 2n .
Hint. You could give a proof using induction.
4.2. OPERATION ON SETS 41

4.2.5 Cartesian products

To define the concept of Cartesian product we need to understand what is an

ordered pair. Consider a set with two elements {x, y}. This set does not convey
a notion of order since {x, y} = {y, x}. If one wants to introduce a notion of
order we can formally define the ordered pair (x, y) as the set {{x}, {x, y}}.
With this definition the characteristic property of ordered pairs holds. Indeed,

(x1 , y1 ) = (x2 , y2 ) ⇐⇒ (x1 = x2 ) ∧ (y1 = y2 ).

Also, with this definition it is clear that (x, y) 6= (y, x) since {{x}, {x, y}} is
obviously not the same set as {{y}, {y, x}} = {{y}, {x, y}}. We will not use the
formal definition of an order pair but we will use the concept of ordered pairs
as well as the characteristic property.

Definition 33: Cartesian product of two sets

Let X and Y be sets. The Cartesian product of X and Y , written X ×Y ,

is the set of all ordered pairs (x, y) with x ∈ X and y ∈ Y . Formally,

X × Y = {(x, y) | (x ∈ X) ∧ (y ∈ Y )}.

The Cartesian product is named after René Descartes. It is a generalization

of the Cartesian coordinate system in the context of arbitrary sets (not just the
real numbers).

Remark 5
It follows from the definition that

w ∈ X × Y ⇐⇒ (∃x ∈ X)(∃y ∈ Y )[w = (x, y)].

Example 52. The Cartesian product R × R is nothing else but the 2-dimensional
plane usually simply denoted by R2 .

The following property can be easily deduced form logical principles.

Proposition 13

Let X be a set. Then X × ∅ = ∅

42 CHAPTER 4. INTRODUCTION TO ELEMENTARY SET THEORY

Remark 6
In general, the Cartesian product is not a commutative operation. This
is clear by considering the following elementary example. Let X = {0, 1}
and Y = {2, 3} then

X × Y = {(0, 2), (0, 3), (1, 2), (1, 3)}

but
Y × X = {(2, 0), (2, 1), (3, 0), (3, 1)},
and clearly X × Y 6= Y × X.
In general, the Cartesian product is also not an associative operation but
this is slightly more subtle. Let X = {0}, Y = {1}, and Z = {2} then

(X × Y ) × Z = {((0, 1), 2)}

but
X × (Y × Z) = {(0, (1, 2))},
and clearly (X × Y ) × Z 6= X × (Y × Z).
However these two sets seem so similar that we want to identify them.
This will be done precisely using bijective functions in the next chapter.
Chapter 5

Functions

5.1 Definition and Basic Properties

A function between two sets is a correspondence between elements of these two
sets that enjoy some special properties.
Definition 34: Functions
Let X and Y be nonempty sets. A function from X to Y is a correspon-
dence that assigns to every element in X one and only one element in
Y . Formally, a function from X to Y is a subset F ⊆ X × Y such that

[(∀x ∈ X)(∃!y ∈ Y ) (x, y) ∈ F ].

Note that the logical formula [(∀x ∈ X)(∃!y ∈ Y ) (x, y) ∈ F ] is equivalent

to the logical formula

[(∀x ∈ X)(∃y ∈ Y ) (x, y) ∈ F ]

∧
[(∀x ∈ X)[((x, y1 ) ∈ F ) ∧ ((x, y2 ) ∈ F )] =⇒ (y1 = y2 )]].

Remark 7
Since functions play a central role in set theory and in mathematics in
general we use a specific terminology. A function is usually denoted by
f (instead of F ) and we write f : X → Y to say that f is a function
from X to Y (instead of F ⊆ X × Y ). Since for every x ∈ X there is
a unique element y ∈ Y such that (x, y) ∈ F , we prefer a much more
convenient functional notation. Therefore, we will denote by f (x) the
unique element that is in correspondence with x. If f (x) = y we say that
y is the image of x or that x is the preimage of y. We call X the domain
of f and Y the codomain.

To show that a correspondence f : X → Y is a function we must check that

(∀x ∈ X)(∃y ∈ Y )[f (x) = y]

43
44 CHAPTER 5. FUNCTIONS

and
(∀x1 ∈ X)(∀x2 ∈ X)[(x1 = x2 ) =⇒ (f (x1 ) = f (x2 ))].
Example 53. Let X = {1, 2, 3} and Y = {5, 8, 10}. The correspondence f
defined by f (1) = f (2) = 10, f (3) = 8 is a function from X to Y .
Example 54. The correspondence f : Z → Z that is defined by

0 if k is even,

f (k) = 1 if k is odd,

2 if k is a multiple of 4.


is not a function from Z to Z; why?

Example 55. The identity function on X is the function iX : X → X such that
for all x ∈ X, iX (x) = x.
Example 56. For all a, b ∈ R the functions fa,b : R → R, defined by fa,b (x) =
ax + b are called linear functions.
We now define what it means for two functions to be equal.
Definition 35: Equality for functions

Two functions f1 : X1 → Y1 and f2 : X2 → Y2 are equal, denoted f1 = f2 ,

if they have the same domain, the same codomain and their actions on
elements in X are the same. Formally,

f1 = f2 ⇐⇒ (X1 = X2 ) ∧ (Y1 = Y2 ) ∧ ((∀z ∈ X1 )[f1 (z) = f2 (z)]).

The next definition introduces the concept of image, or range, of a function.

Definition 36: Image (or range) of a function

Let f : X → Y be a function. The image (or the range) of the function

f is the set, denoted Im(f ), of all elements in the codomain that are the
image of an element in the domain. Formally,

Im(f ) = {f (x) | x ∈ X} = {y ∈ Y | (∃x ∈ X)[y = f (x)]}.

Remark 8
The image of a function is a subset of the codomain of the function. It
follows from the definition that

y ∈ Im(f ) ⇐⇒ (∃x ∈ X)[y = f (x)].

(
k − 1 if k is even,
Exercise 11. Let f : Z → Z defined by f (k) =
k + 3 if k is odd.
Determine the image of f .
The next definition introduces the concept of graph of a function.
5.2. COMPOSITION OF FUNCTIONS 45

Definition 37: Graph of a function

Let X and Y be nonempty sets and f : X → Y be a function. The graph

of the function f is the set, denoted Gf , of all ordered pairs (x, y) of
elements x ∈ X and y ∈ Y that are in correspondence. Formally,

Gf = {(x, y) ∈ X × Y | y = f (x)}.

Remark 9
The graph of a function is a subset of the Cartesian product of its domain
with its codomain. It follows from the definition that

z ∈ Gf ⇐⇒ (∃x ∈ X)[z = (x, f (x))].

3x + 5
Exercise 12. Let f (x) = . Determine the domain, codomain, and graph
x−2
of f .

Remark 10

Let X and Y be nonempty sets. We denote F (X, Y ) = {f | f : X → Y },

the set of all functions from X to Y . If X = Y , we simply write F (X).

5.2 Composition of Functions

Assume we are given two functions f and g. If the codomain of f coincides with
the domain of g then it is make sense to look at what element is obtained if we
first apply f and then g to an element in the domain of f . This procedure gives
a function from the domain of f in the codomain of g.
Definition 38: Composition of functions

Let X, Y, Z be nonempty sets, and let f : X → Y , g : Y → Z. We

define a function g ◦ f : X → Z, called the composition of f and g, by
g ◦ f (x) = g(f (x)), ∀x ∈ X.

Note that for the composition to be defined we just need the image of f to
be a subset of the domain of g.
Remark 11
In general, g ◦ f 6= f ◦ g and the composition is not a commutative
operation! Indeed, consider the function f : R → R defined for all x ∈ R
by f (x) = 3x and the function g : R → R defined for all x ∈ R by
g(x) = x2 . It is easy to see that g ◦ f and f ◦ g have the same domain
and codomain, but for instance g ◦ f (1) = 9 6= 3 = f ◦ g(1).
46 CHAPTER 5. FUNCTIONS

Proposition 14

Let f : X → Y be a function. Then f ◦ iX = f and iY ◦ f = f .

Proof. First we prove that (f ◦ iX ) = f . Observe that X is the domain of both

(f ◦ iX ) and f , and that Y is the codomain of both f ◦ iX and f . It remains to
show that for all x ∈ X, (f ◦ iX )(x) = f (x). By definition of the composition
operation and of iX , it follows that if x ∈ X then (f ◦iX )(x) = f (iX (x)) = f (x).
The proof is similar for the second statement. Observe that X is the domain
of both iY ◦f and f , and that X is the codomain of both iY ◦f and f . It remains
to show that for all x ∈ X, (iY ◦ f )(x) = f (x). By definition of the composition
operation and of iY , it follows that if x ∈ X then (iY ◦ f )(x) = iY (f (x)) = f (x),
since f (x) ∈ Y .

The composition operation is associative.

Proposition 15: Associativity of the composition

Let W, X, Y, Z be nonempty sets. Let f : W → X, g : X → Y , and

h : Y → Z. Then, (h ◦ g) ◦ f = h ◦ (g ◦ f ).

Proof. Observe that W is the domain of both (h ◦ g) ◦ f and h ◦ (g ◦ f ), and that

Z is the codomain of both (h ◦ g) ◦ f and h ◦ (g ◦ f ). It remains to show that for
all w ∈ W , ((h ◦ g) ◦ f )(w) = (h ◦ (g ◦ f ))(w). By definition of the composition
operation it follows that if x ∈ X then

((h ◦ g) ◦ f )(w) = (h ◦ g)(f (w)) = h(g(f (w)))

and
(h ◦ (g ◦ f ))(w) = h((g ◦ f )(w)) = h(g(f (w))).
Therefore, ((h ◦ g) ◦ f )(w) = h(g(f (w))) = (h ◦ (g ◦ f ))(w) and the two functions
are equal.

5.3 Surjective and Injective Functions

5.3.1 Definitions and examples
A surjective function (or onto function) is a function whose image fills in com-
pletely the codomain.
Definition 39: Surjective function

Let X and Y be nonempty sets. A function f : X → Y is surjective (or

onto, or a surjection) if every element in the codomain of f admits a
preimage in the domain of f . Formally,

f : X → Y is surjective ⇐⇒ (∀y ∈ Y )(∃x ∈ X)[y = f (x)].

5.3. SURJECTIVE AND INJECTIVE FUNCTIONS 47

The following proposition is a characterization of surjectivity in terms of the

image of the function.
Proposition 16: Characterization of surjectivity in terms of the
image

Let X and Y be nonempty sets. Let f : X → Y be a function. Then, f

is surjective if and only if Im(f ) = Y .

Proof. We know that Im(f ) ⊆ Y always holds, but the definition of injectivity
says that Y ⊆ Im(f ). Therefore Y = Im(f ).

Example 57. The identity function on X is surjective.

3x + 5
Example 58. Let f : (−∞, 2) ∪ (2, ∞) → R, defined by f (x) = . The
x−2
function f is not surjective since Im(f ) = (−∞, 3) ∪ (3, ∞).
However, the function g : (−∞, 2) ∪ (2, ∞) → (−∞, 3) ∪ (3, ∞), defined by
3x + 5
g(x) = is surjective.
x−2
(
k − 1 if k is even,
Exercise 13. Let f : Z → Z defined by f (k) =
k + 3 if k is odd.
Show that the function f is surjective.
Exercise 14. Let f : R → R, defined by f (x) = x + 2|x|. Is f surjective?
A function is injective (or one-to-one often abbreviated as 1 − 1) if no two
distinct elements in the domain are assigned the same element in the codomain.
Definition 40: Injective function

Let X and Y be nonempty sets. A function f : X → Y is injective (or

one-to-one, or an injection) if every two distinct elements in the domain
have distinct images in the codomain. Formally,

f : X → Y is injective
⇐⇒
(∀x1 ∈ X)(∀x2 ∈ X)[¬(x1 = x2 ) =⇒ ¬(f (x1 ) = f (x2 ))].

Remark 12
In practice, to show that a function is injective we need to prove ei-
ther one of the following two logically equivalent statements (the second
statement is the contrapositive of the first statement.):

• for all x1 , x2 ∈ X if x1 6= x2 then f (x1 ) 6= f (x2 ).

• for all x1 , x2 ∈ X if f (x1 ) = f (x2 ) then x1 = x2 .

Example 59. The identity function on X is injective.

48 CHAPTER 5. FUNCTIONS

Example 60. The projections πX : X × Y → X, (x, y) 7→ x and πY : X × Y →

Y, (x, y) 7→ y are surjective.
3x + 5
Example 61. Let f : (−∞, 2) ∪ (2, ∞) → R, defined by f (x) = . The
x−2
function f is injective?
(
k − 1 if k is even,
Exercise 15. Let f : Z → Z defined by f (k) =
k + 3 if k is odd.
Show that the function f is injective.
Exercise 16. Let f : R → R, defined by f (x) = x + 2|x|. Is f injective?

Definition 41: Bijective function

Let X and Y be nonempty sets. Let f : X → Y be a function. Then f is

bijective (or a bijection) if f is both injective and surjective. In the case
where X = Y a bijection is simply called a permutation.

Example 62. The identity function iX : X → X is a permutation.

3x + 5
Exercise 17. Let f : (−∞, 2) ∪ (2, ∞) → R, defined by f (x) = . Is f
x−2
bijective?

5.3.2 Injectivity, surjectivity and composition

In this section we show that injectivity, surjectivity, and bijectivity are stable
under composition.
Proposition 17: Stability of injectivity under composition

Let W, X, Y be nonempty sets. Let f : W → X, g : X → Y . If f and g

are injective, then g ◦ f is also injective.

Proof. Assume that f and g are injective. Let w1 , w2 ∈ W such that g ◦f (w1 ) =
g ◦ f (w2 ), then g(f (w1 )) = g(f (w2 )) (by definition of the composition) and
f (w1 ) = f (w2 ) (by injectivity of g). Now it follows from the injectivity of f
that w1 = w2 , and g ◦ f is injective.

Proposition 18: Stability of surjectivity under composition

Let W, X, Y be nonempty sets. Let f : W → X, g : X → Y . If f and g

are surjective, then g ◦ f is also surjective.

Proof. Assume that f and g are surjective. Let y ∈ Y , then there exists x ∈ X
such that g(x) = y (by surjectivity of g). Since x ∈ X, there exists w ∈ W
such that x = f (w) (by surjectivity of f ). And hence, y = g(x) = g(f (w)) =
g ◦ f (w) (by definition of the composition). We have just shown that for every
y ∈ Y there exists w ∈ W such that y = g ◦ f (w), which means that g ◦ f is
surjective.
5.4. INVERTIBLE FUNCTIONS 49

Proposition 19: Stability of bijectivity under composition

Let W, X, Y be nonempty sets. Let f : W → X, g : X → Y . If f and g

are bijective, then g ◦ f is also bijective.

Proof. Assume that f and g are bijective, then in particular they are both
injective . By Theorem 15, g ◦ f is then injective. A similar reasoning using
Theorem 16 will show that g ◦ f is surjective, and hence g ◦ f is bijective.

5.4 Invertible Functions

In this section we take a look at those functions whose actions can be “undone”.
Definition 42: Invertibility

Let X, Y be nonempty sets. Let f : X → Y be a function. We say that

f is invertible (or admits an inverse) if there exists a function g : Y → X
such that f ◦ g = iY and g ◦ f = iX .

Being invertible is closely connected to being bijective. Indeed, as we will

see shortly invertibility and bijectivity are actually equivalent notions! The goal
of this section is to prove this equivalence.
Theorem 15
Let X, Y be nonempty sets. Let f : X → Y be a function. If f is
invertible then f is injective.

Proof. Assume that f is invertible. Then there is a function g : Y → X such

that g ◦ f = iX and f ◦ g = iY . If x1 , x2 ∈ X and f (x1 ) = f (x2 ), then
x1 = g(f (x1 )) = g(f (x2 )) = x2 . Thus f is injective.

It follows from the injectivity of invertible functions that the inverse of an

invertible function is uniquely determined.
Proposition 20: Uniqueness of the inverse

Let X and Y be nonempty sets. Let f : X → Y be a function. If f is

invertible then f has a unique inverse.

Proof. Let f : X → Y be a function. Our goal is to show that if there are

two functions g1 , g2 : Y → X such that f ◦ g1 = iY , g1 ◦ f = iX , f ◦ g2 = iY ,
and g2 ◦ f = iX , then g1 = g2 . Let y ∈ Y then (f ◦ g1 )(y) = iY (y) = y and
(f ◦ g2 )(y) = iY (y) = y, thus (f ◦ g1 )(y) = (f ◦ g2 )(y). It follows from the
definition of the composition that f (g1 (y)) = f (g2 (y)) and since f is invertible,
f is injective (Theorem 15) and hence g1 (y) = g2 (y). Therefore, g1 = g2 .
50 CHAPTER 5. FUNCTIONS

Remark 13
If f is invertible, by Proposition 20 the unique function satisfying the
conditions of the definition is called the inverse of f and is denoted f −1 .

Proposition 21: Stability of invertibility under composition

Let X, Y, Z be nonempty sets. Let f : X → Y and g : Y → Z be invert-

ible functions. Then g ◦f : X → Z is invertible and (g ◦f )−1 = f −1 ◦g −1 .

Proof. Let g −1 and f −1 be the inverses of g and f respectively. It follows from

the associativity of the composition operation that,

(g ◦ f ) ◦ (f −1 ◦ g −1 ) = g ◦ (f ◦ f −1 ) ◦ g −1
= g ◦ iY ◦ g −1
= g ◦ g −1
= iZ

and similarly,

(f −1 ◦ g −1 ) ◦ (g ◦ f ) = f −1 ◦ (g −1 ◦ g) ◦ f )
= f −1 ◦ iY ◦ f )
= f −1 ◦ f
= iX .

Therefore, g ◦ f is invertible and (g ◦ f )−1 = f −1 ◦ g −1 .

Theorem 16
Let X, Y be nonempty sets. Let f : X → Y be a function. If f is
invertible then f is surjective.

Proof. Assume that f is invertible. Then there is a function g : Y → X such

that g ◦ f = iX and f ◦ g = iY . Let y ∈ Y , and put x = g(y). Then by definition
of g, one has x ∈ X, and thus

f (x) = f (g(y)) (because f is a function)

= (f ◦ g)(y) (by definition of the composition)
= iY (y) (since f ◦ g(y) = iY (y) by our assumption)
= y (by definition of the identity function on Y.)

Therefore f is surjective.
5.4. INVERTIBLE FUNCTIONS 51

Theorem 17
Let X, Y be nonempty sets. Let f : X → Y be a function. If f is bijective
then f is invertible.

Proof. Assume f is bijective. Given y ∈ Y , since f is surjective there is some

x ∈ X such that y = f (x), and since f is injective this x is unique. Indeed if
there are x1 , x2 ∈ X such that f (x1 ) = y = f (x2 ), then x1 = x2 by injectivity
of f . So for every y ∈ Y there is a unique xy ∈ X such that y = f (xy ). We will
define a function g : Y → X by assigning to every element y ∈ Y to the unique
element xy ∈ X such that f (xy ) = y, i.e. g(y) = xy . By uniqueness of xy , g is
a function.
Given y ∈ Y , then g(y) = xy where f (xy ) = y, and thus f (g(y)) = f (xy ) = y
(since f is a function). It follows from the definition of the composition that
(f ◦ g)(y) = y, and by definition of the identity function that (f ◦ g)(y) = iY (y).
Since y ∈ Y was arbitrary, one has f ◦ g = iY .
It remains to show that (g ◦ f ) = iX . Now given x ∈ X, g(f (x)) is the
element x0 ∈ X such that f (x0 ) = f (x). That is, g(f (x)) = x0 = x, since f is
injective. Thus g ◦ f = iX , and therefore f is invertible.

Combining the last three theorems we obtain the following corollary.

Corollary 1

Let X and Y be nonempty sets. Let f : X → Y . Then,

f is invertible if and only if f is bijective.

Proof. Assume that f is invertible, then it follows by Theorem 15 that f is

injectve and by Theorem 16 that f is surjective. Therefore, f is bijective. The
converse is Theorem 17.

We can also define the notion of right/left-inverse of a function.

Definition 43: Right-inverse

Let X, Y be nonempty sets. Let f : X → Y be a function. We say that

f is right-invertible (or admits a right-inverse) if there exists a function
g : Y → X such that f ◦ g = iY .

Definition 44: Left-inverse

Let X, Y be nonempty sets. Let f : X → Y be a function. We say that
f is left-invertible (or admits a left-inverse) if there exists a function
g : Y → X such that g ◦ f = iX .
52 CHAPTER 5. FUNCTIONS

5.5 Functions and Sets

Recall that the image of a function f : X → Y is the set Im(f ) = {y ∈ Y | (∃x ∈
X)[y = f (x)]}. We generalize this concept in the following definition.
Definition 45: Direct image of a set

Let X, Y be nonempty sets. Let f : X → Y be a function. If Z ⊆ X,

the image of Z under f is the set, denoted f (Z), of all elements in the
codomain that are the image of at least one element in Z. Formally,

f (Z) = {y ∈ Y | (∃z ∈ Z)[y = f (z)]}.

Remark 14

• Note that f (X) is simply the image of f , i.e., Im(f ) = f (X).

• It follows from the definition that

v ∈ f (Z) ⇐⇒ (∃z ∈ Z) [v = f (z)].

The following proposition states that inclusion is preserved under taking

direct images.
Proposition 22

Let X, Y be nonempty sets. Let f : X → Y be a function. Let W and

Z be subsets of X. If W ⊆ Z, then f (W ) ⊆ f (Z)

Proof. If f (W ) is empty then the conclusion holds. Otherwise, let v ∈ f (W )

then there exists w ∈ W such that v = f (w) (by definition of the direct image).
But since W ⊆ Z it follows that w ∈ Z and thus v ∈ f (Z) (by definition of the
direct image). Therefore, f (W ) ⊆ f (Z).

The following proposition states that the direct image of an union is the
union of the direct images.
Proposition 23

Let X, Y be nonempty sets. Let f : X → Y be a function and W and Z

be subsets of X. Then, f (W ∪ Z) = f (W ) ∪ f (Z)

Proof. The proof is a classical double inclusion argument (and we do not include
below the trivial cases when the sets are empty).

• We first show that f (W ∪ Z) ⊆ f (W ) ∪ f −1 (Z). Let y ∈ f (W ∪ Z),

then there exists x ∈ W ∪ Z such that y = f (x) (by definition of the
image) thus y = f (x) for some x ∈ W or y = f (x) for some x ∈ Z (by
definition of the union) and hence y ∈ f (W ) or y ∈ f (Z) (by definition of
the image) and y ∈ f (W ) ∪ f (Z) (by definition of the union). Therefore
f (W ∪ Z) ⊆ f (W ) ∪ f (Z).
5.5. FUNCTIONS AND SETS 53

• Now we show that f (W ) ∪ f (Z) ⊆ f (W ∪ Z)]. Let y ∈ f (W ) ∪ f (Z),

then y ∈ f (W ) or y ∈ f (Z) (by definition of the union) thus y = f (x) for
some x ∈ W or y = f (x) for some x ∈ Z (by definition of the image) and
y = f (x) for some x ∈ W ∪Z (by definition of the union) thus y ∈ f (W ∪Z)
(by definition of the inverse image). Therefore f (W ) ∪ f (Z) ⊆ f (W ∪ Z).

The situation is slightly different as far as intersection is concerned.

Proposition 24

Let X, Y be nonempty sets. Let f : X → Y be a function and W and Z

be subsets of X. Then,

f (W ∩ Z) ⊆ f (W ) ∩ f (Z).

Proof. Let y ∈ f (W ∩ Z), then there exists x ∈ W ∩ Z such that y = f (x) (by
definition of the image), thus y = f (x) for some x ∈ W and y = f (x) for some
x ∈ Z (by definition of the intersection), and hence y ∈ f (W ) and y ∈ f (Z) (by
definition of the image), and y ∈ f (W )∩f (Z) (by definition of the intersection).
Therefore f (W ∩ Z) ⊆ f (W ) ∩ f (Z).

Definition 46: Inverse image of a set

Let X and Y be nonempty sets and let f : X → Y be a function. Let

Z be a subset of Y . Then the inverse image of Z with respect to the
function f , denoted f −1 (Z), is the set of all elements in X that have
their image in Z. Formally,

f −1 (Z) := {x ∈ X | f (x) ∈ Z}.

Remark 15

• In this context the symbol f −1 does not refer to the inverse of the
function f (which might not exist in the first place).
• If follows from the definition that v ∈ f −1 (Z) ⇐⇒ f (v) ∈ Z.

The following proposition states that inclusion is preserved under taking

inverse images.
Proposition 25

Let X, Y be nonempty sets. Let f : X → Y be a function. Let W and

Z be subsets of Y . If W ⊆ Z, then f −1 (W ) ⊆ f −1 (Z)

Proof. If f −1 (W ) is empty then the conclusion holds. Otherwise, let v ∈

f −1 (W ) then f (v) ∈ W and it follows from W ⊆ Z that f (v) ∈ Z, and hence
v ∈ f −1 (Z). Therefore, f −1 (W ) ⊆ f −1 (Z).
54 CHAPTER 5. FUNCTIONS

The following proposition states that the inverse image of an union is the
union of the inverse images.
Proposition 26

Let X and Y be nonempty sets and let f : X → Y be a function. Let W

and Z be subsets of Y . Then,

f −1 (W ∪ Z) = f −1 (W ) ∪ f −1 (Z).

Proof. The proof is a classical double inclusion argument.

• We first show the inclusion f −1 (W ∪ Z) ⊆ f −1 (W ) ∪ f −1 (Z). Let x ∈
f −1 (W ∪ Z), then f (x) ∈ W ∪ Z (by definition of the inverse image)
thus f (x) ∈ W or f (x) ∈ Z (by definition of the union) and hence
x ∈ f −1 (W ) or x ∈ f −1 (Z) (by definition of the inverse image) and
x ∈ f −1 (W ) ∪ f −1 (Z) (by definition of the union). Therefore f −1 (W ∪
Z) ⊆ f −1 (W ) ∪ f −1 (Z).

• Then we show that f −1 (W ) ∪ f −1 (Z) ⊆ f −1 (W ∪ Z)]. Let x ∈ f −1 (W ) ∪

f −1 (Z), then x ∈ f −1 (W ) or x ∈ f −1 (Z) (by definition of the union)
and f (x) ∈ W or f (x) ∈ Z (by definition of the inverse image) and hence
f (x) ∈ W ∪ Z (by definition of the union) thus x ∈ f −1 (W ∪ Z) (by
definition of the inverse image). Therefore f −1 (W ) ∪ f −1 (Z) ⊆ f −1 (W ∪
Z).

The following proposition states that the inverse image of an intersection is

the intersection of the inverses images.
Proposition 27

Let X and Y be nonempty sets and let f : X → Y be a function. Let W

and Z be subsets of Y . Then,

f −1 (W ∩ Z) = f −1 (W ) ∩ f −1 (Z).

Proof. The proof is a classical double inclusion argument.

• First the inclusion f −1 (W ∩Z) ⊆ f −1 (W )∩f −1 (Z)]. Let x ∈ f −1 (W ∩Z),
then f (x) ∈ W ∩ Z (by definition of the inverse image) thus f (x) ∈ W and
f (x) ∈ Z (by definition of the intersection) and hence x ∈ f −1 (W ) and x ∈
f −1 (Z) (by definition of the inverse image) and x ∈ f −1 (W ) ∩ f −1 (Z) (by
definition of the intersection). Therefore f −1 (W ∩Z) ⊆ f −1 (W )∩f −1 (Z).

• Then, the inclusion f −1 (W ) ∩ f −1 (Z) ⊆ f −1 (W ∩ Z)]. Let x ∈ f −1 (W ) ∩

f −1 (Z), then x ∈ f −1 (W ) and x ∈ f −1 (Z) (by definition of the intersec-
tion) and f (x) ∈ W and f (x) ∈ Z by definition of the inverse image, and
hence f (x) ∈ W ∩Z (by definition of the intersection) thus x ∈ f −1 (W ∩Z)
5.5. FUNCTIONS AND SETS 55

(by definition of the inverse image). Therefore f −1 (W ) ∩ f −1 (Z) ⊆

f −1 (W ∩ Z).
56 CHAPTER 5. FUNCTIONS
Chapter 6

Relations

6.1 Definitions and basic properties

Definition 47: Relations
Let X and Y be sets. A relation R from X to Y is a subset of X × Y . If
(x, y) ∈ R we simply write xRy. We simply say that R is a relation on
X if it is a relation from X to X. In other words, a relation R on a set
X is a subset of X × X

Example 63. 1. Let R = {(x, y) ∈ Z × Z | y = kx, for some k ∈ Z}. Then

2R4, 19R0...

2. Let R on Z such that xRy ⇐⇒ x − y = 5k for some k ∈ Z.

3. Let R on F (R) such that f Rg ⇐⇒ f (0) = g(0).

4. let R on P (X) such that ARB ⇐⇒ A ⊆ B.

5. let R on P (X) such that ARB ⇐⇒ A ⊂ B.

Definition 48: Reflexive relation

A relation R on a set X is reflexive if every element in X is in relation
with itself. Formally,

R is a reflexive relation on X ⇐⇒ (∀x ∈ X) xRx.

Definition 49: Symmetric relation

A relation R on a set X is symmetric if for all elements x, y ∈ X such

that x is in relation with y then y is in relation with x. Formally,

R is a symmetric relation on X ⇐⇒ (∀x ∈ X)(∀y ∈ X)[xRy =⇒ yRx].

57
58 CHAPTER 6. RELATIONS

Definition 50: Transitive relation

A relation R on a set X is transitive if for all elements x, y, z ∈ X,
whenever x is in relation with y and y is in relation with z, then x is in
relation with z. Formally,

R is a transitive relation on X

⇐⇒
(∀x ∈ X)(∀y ∈ X)(∀z ∈ X)[((xRy) ∧ (yRz)) =⇒ (xRz)].

6.2 Equivalence relations and partitions

Definition 51: Equivalence relation

A relation R on a set X is an equivalence relation if it is reflexive, sym-

metric and transitive.

For an equivalent relation R, xRy is often denoted by x ∼ y and reads x is

equivalent to y.
Definition 52: Equivalence classes

If ∼ is an equivalence relation on X, and x ∈ X, the set [x] = {y ∈

X | y ∼ x} is called the equivalence class of x. Elements of the same
class are said to be equivalent.

The purpose of defining an equivalence relation is to classify elements of a set

according to a certain property. As we will see having an equivalence relation
provides a procedure to partition a set. We now introduce the concept S of a
partition.
S Let Y be a set and P a subset of P (Y ). We use
S the notation A∈P A
for A∈P XA where XA = A. In other words, the set A∈P A is the set of all
elements that belong to at least one set of P.
Definition 53: Partitions

Let X be a set. A partition of X is a subset P of P (X) such that

S
1. A∈P A = X, (covering)
2. if A, B ∈ P and A 6= B, then A ∩ B = ∅, (disjointness)

3. if A ∈ P then A 6= ∅. (non-empty clucters)

Theorem 18
If ∼ is an equivalence relation on a nonempty set X, then the set of
equivalence classes of ∼ forms a partition of X.
6.2. EQUIVALENCE RELATIONS AND PARTITIONS 59

Proof. Uses reflexivity and transitivity of the equivalence relation.

Theorem 19
Let P be a partition of a nonempty set X. Define a relation ∼P on X by
x ∼P y if and only if x and y are in the same element of the partition.
Then ∼P is an equivalence relation on X.

Proof. Definition based direct proof.

60 CHAPTER 6. RELATIONS
Chapter 7

Introduction to Abstract
Algebra

7.1 Binary Operations

Definition 54: Binary operations

A binary operation on a nonempty set X is a function f : X × X → X.

To avoid using the cumbersome functional notation f (x, y) we will use an

operation symbol analogous to + or ×, such as ⊥, to denote the binary operation
and write x ⊥ y instead of f (x, y).
Example 64. 1.
N×N → N
(n, m) 7→ n + m

2.
Q×Q → Q
(p, q) 7→ p × q

3.
R∗ × R ∗ → R∗
(x, y) 7 → x÷y

4.
F (R) × F (R) → F (R)
(f, g) 7→ f ◦g

5.
P (X) × P (X) → P (X)
(A, B) 7→ A∩B

6.
P (X) × P (X) → P (X)
(A, B) 7→ A∪B

61
62 CHAPTER 7. INTRODUCTION TO ABSTRACT ALGEBRA

7.
M2 (R) × M2 (R) → M2 (R)
(A, B) 7→ A + B

8.
M2 (R) × M2 (R) → M2 (R)
(A, B) 7→ A · B

Definition 55: Associative binary operations

A binary operation ⊥ on X is associative if for all x, y, z ∈ X, (x ⊥ y) ⊥

z = x ⊥ (y ⊥ z). Formally, ⊥ on X is associative if

(∀x ∈ X)(∀y ∈ X)(∀z ∈ X)[(x ⊥ y) ⊥ z = x ⊥ (y ⊥ z)].

Definition 56: Commutative binary operation

A binary operation ⊥ on X is commutative if for all x, y ∈ X, x ⊥ y =

y ⊥ x. Formally, ⊥ on X is commutative if

(∀x ∈ X)(∀y ∈ X)[x ⊥ y = y ⊥ x].

N×N → N
Example 65. 1. is associative and commutative.
(n, m) 7→ n + m

Q×Q → Q
2. is associative and commutative.
(p, q) 7→ p×q

R∗ × R∗ → R∗
3. is not associative and not commutative.
(x, y) 7→ x ÷ y

F (R) × F (R) → F (R)

4. is associative but not commutative.
(f, g) 7→ f ◦g

P (X) × P (X) → P (X)

5. is associative and commutative.
(A, B) 7→ A∩B

P (X) × P (X) → P (X)

6. is associative and commutative.
(A, B) 7→ A ∪ B

M2 (R) × M2 (R) → M2 (R)

7. is associative and commutative.
(A, B) 7→ A + B

M2 (R) × M2 (R) → M2 (R)

8. is associative but not commutative.
(A, B) 7→ A · B

Definition 57: Identity element of a binary operation

Let ⊥ be a binary operation on X. An element e ∈ X is an identity

element of X with respect to ⊥ if for all x ∈ X, x ⊥ e = e ⊥ x = x.
7.1. BINARY OPERATIONS 63

Proposition 28

Let ⊥ be a binary operation on X. If e ∈ X is an identity element of X

with respect to ⊥, then e is unique.

Proof. Direct proof or by contradiction.

N×N → N
Example 66. 1. 0 is the identity element of
(n, m) 7→ n + m

Q×Q → Q
2. 1 is the identity element of
(p, q) 7→ p×q

R∗ × R ∗ → R∗
3. there is no identity element for
(x, y) 7 → x÷y

F (R) × F (R) → F (R)

4. iR is the identity element of
(f, g) 7→ f ◦ g

P (X) × P (X) → P (X)

5. X is the identity element of
(A, B) 7→ A∩B

P (X) × P (X) → P (X)

6. ∅ is the identity element of
(A, B) 7→ A ∪ B
 
0 0 M2 (R) × M2 (R) → M2 (R)
7. is the identity element of
0 0 (A, B) 7→ A + B
 
1 0 M2 (R) × M2 (R) → M2 (R)
8. is the identity element of
0 1 (A, B) 7→ A · B

Definition 58: Invertible elements

Suppose ⊥ is a binary operation on X with identity element e, and let
x ∈ X. We say that x is invertible with respect to ⊥ if there exists y ∈ X
such that x ⊥ y = y ⊥ x = e. If y exists, we say that y is an inverse for
x with respect to ⊥.

Proposition 29

Let ⊥ be a binary operation on X with an identity element e ∈ X. If

x ∈ X has an inverse with respect to ⊥ then that inverse is unique.

Proof. Direct proof or by contradiction.

The inverse of an element x ∈ X is denoted by x−1 .

64 CHAPTER 7. INTRODUCTION TO ABSTRACT ALGEBRA

Proposition 30

Let ⊥ be a binary operation on X with an identity element e ∈ X. Then,

1. e is invertible and its inverse is e.

2. if x is invertible, then its inverse x−1 is invertible and (x−1 )−1 = x
3. if x and y are invertible then x ⊥ y is invertible and (x ⊥ y)−1 =
y −1 ⊥ x−1 .

Proof. Definition based direct proofs.

Definition 59
Let ⊥ be a binary operation on the set X, and suppose that Y ⊂ X. Y
is said to be closed in X under ⊥ if x ⊥ y ∈ Y , ∀x, y ∈ Y . In that case,
⊥ is also a binary operation on Y .

Definition 60: Groups

A group is a pair (X, ⊥) where X is a set and ⊥ is a binary operation

on X such that:

1. ⊥ is associative,
2. there exists an identity e on X with respect to ⊥,

3. every element of X has an inverse.

Chapter 8

Order Relations

Definition 61: Partial orders

A relation R on a set X is called a partial ordering if it is:
1. reflexive,
2. transitive,

3. antysymmetric.
A set X equipped with a partial ordering is called a partially ordered set
or poset.

Example 67. 1. Let R be the relation on Z+ defined by xRy if y is a multiple

of x, that is, if there exists n ∈ Z+ such that y = nx.
2. Let R be the relation on F (R) defined by f ≤ g ⇐⇒ f (x) ≤ g(x), ∀x ∈ R.

Definition 62: Linear orderings

Let X be a set and R be a partial ordering on X. We say that R is a

linear ordering on X (or a total order on X) if for all x, y ∈ X, either
xRy or yRx. A set X equipped with a linear ordering is called a linearly
ordered set.

The prototypical example of a linearly ordered set is R with the order relation
≤.

8.1 Exercises
Exercise 18. Are the following binary operations associative and/or commuta-
tive?
1. On Z+ , n ⊥ m = max{n, m}.
2. On R, x ⊥ y = 2xy .
3. On Z+ , n ⊥ m = nm .

65
66 CHAPTER 8. ORDER RELATIONS
  
a b
Exercise 19. 1. Show that S = ∈ M2 (R) | a = 0 is closed in
c d
M2 (R) under addition but not under multiplication.

2. Show that 2Z is closed in Z under addition and multiplication.

3. Show that 2Z + 1 = {x ∈ Z | ∃k ∈ Z 3 x = 2k + 1} is closed in Z under
multiplication but not under addition.
Exercise 20. Show that:
1. (S(R), ◦) is a group, where S(R) is the set of permutations of R. What
about (F (R), ◦)?
2. (M2 (R), +) is a group. What about (M2 (R), ·)?
3. (P (X), ∪) is not a group. What about (P (X), ∩)?

Exercise 21. Which of the relations from example 63 are reflexive, symmetric,
transitive, antisymmetric?
Exercise 22. Which of the following relations are equivalence relations?
1. Let n ∈ Z+ , the congruence relation mod n in Z is defined as xRy ⇐⇒
x − y = nk for some k ∈ Z.

2. Let R on F (R) be such that f Rg ⇐⇒ f (0) = g(0).

3. let R on P (X) be such that ARB ⇐⇒ A ⊆ B.
4. let R on P (X) be such that ARB ⇐⇒ A ⊂ B.
5. Let R on Z × Z be such that (a, b)R(c, d) ⇐⇒ ad = bc.

6. Let R on {(a, b) ∈ Z × Z | b 6= 0} be such that (a, b)R(c, d) ⇐⇒ ad = bc.

Chapter 9

From the Natural Numbers

to the Real Numbers

9.1 The Natural Numbers

9.1.1 Peano’s Axioms

Giuseppe Peano made the following postulates in 1889, before the axiomatiza-
tion of mathematics based on a formal logic language.

There is a set of natural numbers, denoted by N, satisfying the following five

axioms:

P A1 : The element zero, denoted by 0, is a natural number.

P A2 : Every natural number n, has a unique successor in N, denoted by S(n).

P A3 : The natural number 0 is not the successor of any natural number.

P A4 : Two natural numbers that have the same successor are equal.

P A5 : (Induction Axiom) If a subset of the natural numbers contains 0 and if

whenever an element is in this subset then its successor is also in this
subset, then this subset is equal to N.

The notion of successor is somehow vague and to overcome this issue we

consider the (more formal) notion of Dedekind-Peano structure.

67
68CHAPTER 9. FROM THE NATURAL NUMBERS TO THE REAL NUMBERS

Definition 63

A triple (X, x0 , f ) is called a Dedekind-Peano structure if it satisfies the

following properties:

DP1 : X is a set and x0 ∈ X.

DP2 : f is a function from X into X.
DP3 : x0 ∈
/ Im(f ).

DP4 : f is injective.
DP5 : (Induction Axiom) If Y is a subset of X containing x0 that is stable
by f (i.e. f (Y ) ⊆ Y ) then Y = X.

If a Dedekind-Peano structure were to exist and could be shown to be unique

(in a sense to be precised), then the set X would satisfy Peano’s (informal)
axioms with 0 being x0 and the successor operation being the function f . We
could then consider this set to be the set of natural numbers, and denote this
set by N, x0 by 0, and f by S.
Virtually all of modern mathematics can be derived from the formal ZFC
set theory (Zermelo-Fraenkel axioms+the Axiom of Choice), a set theory more
rigorous than the naive one that we have adopted in Chapter 4. In ZFC it is
fairly easy to show that a Dedekind-Peano structure exists, which proves the
formal existence of the set of natural numbers. Since we are implicitly doing
mathematics in the ZFC formalism (understanding this formalism is beyond the
goals of this course) we can use the following theorem which can be proven in
this formalism.
Theorem 20
There exists a Dedekind-Peano structure.

By construction the set of natural numbers is intuitively infinite (we will

define this notion in the next chapter). The set of natural numbers contains at
least the elements 0, S(0), S(S(0)), S(S(S(0)))... We shall use the following
convenient and classical notations. The unique successor of 0, S(0), is denoted
by 1, and the unique successor of 1 = S(0), S(S(0)), is denoted by 2, etc. As an
application of the Well-Ordering Principle we shall see that there are no other
elements in N.
Exercise 23. Let (X, x0 , f ) be a Dedekind-Peano structure. Show that for all
x ∈ X, f (x) 6= x.

Hint. Apply the Induction Axiom to the set {x ∈ X|f (x) 6= x}.

We will need the following result in the sequel.

Exercise 24. Let (X, x0 , f ) be a Dedekind-Peano structure. Show that Im(f ) =
X − {x0 }.

Hint. Apply the Induction Axiom to the set Im(f ) ∪ {x0 }.

9.1. THE NATURAL NUMBERS 69

9.1.2 Binary operations and order relations on N

One can define a binary operation on N, called addition and denoted by +.The
addition is defined recursively by posing for n, m ∈ N,

n+0=n

and
n + S(m) = S(n + m).
This definition recovers the intuitive fact that the successor of n should be n+1,
indeed S(n) = S(n + 0) = n + S(0) = n + 1. Note that 0 is the identity element
for + and it is straightforward to verify that the addition is associative and
commutative. The fact that the addition is well-defined can be justified thanks
to the Induction Axiom.
Proposition 31

The addition + on N, whose identity element is 0, is associative and

commutative. The addition is also regular. i.e.

∀n, m, k ∈ N, n + k = m + k =⇒ n = m.

Hint. Apply the Induction Axiom to the sets {n ∈ N|0 + n = n}, {k ∈ N|n +
(m + k) = (n + m) + k}, {m ∈ N|n + m = m + n}, {k ∈ N|n + k = m + k =⇒
n = m}.

We now define a relation R on N as follows:

mRn ⇐⇒ there exists k ∈ N such that m = n + k.

Proposition 32

The relation R is a partial ordering on N.

Proof. R is symmetric since for all n ∈ N, n + 0 = n. Now, assume that mRn

and nRr, then there exist k, t ∈ N such that m = n + k and n = r + t, but

r + (t + k) = (r + t) + k by associativity of +
=n+k
= m,

which shows that R is transitive. Finally assume that mRn and nRm, then there
exist k, t ∈ N such that m = n + k and n = m + t. Thus m + t + k = n + k = m,
and t + k = 0 (by regularity) and t = k = 0 (by Exercise 25), and the relation
is antisymmetric.

From now on this partial ordering will be denoted by 6. As another ap-

plication of the Well-Ordering principle we shall see that 6 is actually a total
ordering on N.
70CHAPTER 9. FROM THE NATURAL NUMBERS TO THE REAL NUMBERS

Definition 64: Least element

An element x of a partially ordered set (X, R) is said to be a least element

if for all y ∈ X, xRy where R is the partial ordering.

Proposition 33

If a partially ordered set has a least element, then this element is unique.

Hint. Use the antisymmetry property of the partial ordering.

Proposition 34

The natural number 0 is the least element of N

Hint. Use the fact that 0 is the identity element of N for +.

Proposition 35

The addition + is compatible with the partial ordering, i.e. ∀n, m, k ∈ N,

m 6 n =⇒ m + k 6 n + k.

Finally, using the addition operation on the natural numbers one can also
define recursively a multiplication, denoted by ·, by posing for n, m ∈ N,
n·0=0
and
n · S(m) = n · m + n.
Note that 1 is the identity element for ·. It is straightforward to verify that
the multiplication is associative, commutative and that the multiplication dis-
tributes over the addition.
Proposition 36

The multiplication · on N, whose identity element is 1, is associative,

commutative, distributive over the addition +, and

∀n, m ∈ N, ∀k ∈ N − {0}, n · k = m · k =⇒ n = m.

Proof. Exercise.

Proposition 37

The multiplication · is compatible with the partial ordering, i.e.

∀n, m, k ∈ N,
m 6 n =⇒ m · k 6 n · k.

Hint. Use the distributivity of the multiplication over the addition.

9.1. THE NATURAL NUMBERS 71

9.1.3 Basic properties of N

It follows from our discussion that there exist an element 0 and a set N, whose
elements are called natural numbers, that is equipped with an addition +, a
multiplication ·, and a partial ordering 6 such that:
P1 : 0 ∈ N.
P2 : ∀n ∈ N, n + 1 ∈ N
P3 : ∀n ∈ N, 0 6= n + 1.
P4 : ∀n, m ∈ N, m + 1 = n + 1 =⇒ m = n
P5 : (Induction Axiom) If Y is a subset of N such that
• 0∈Y
• n ∈ Y =⇒ n + 1 ∈ Y
then Y = N.
P6 : ∀m, n ∈ N, m + n ∈ N
P7 : ∀m, n ∈ N, m · n ∈ N
P8 : ∀m, n, k ∈ N, m + (n + k) = (m + n) + k
P9 : ∀m, n ∈ N, m + n = n + m
P10 : 0 is the identity element of +
P11 : ∀m, n, k ∈ N, m + k = n + k =⇒ m = k
P12 : ∀m, n, k ∈ N, m · (n · k) = (m · n) · k
P13 : ∀m, n ∈ N, m · n = n · m
P14 : 1 is the identity element of ·
P15 : ∀m, n ∈ N, ∀k ∈ N − {0}, m · k = n · k =⇒ m = k
P16 : ∀m, n, k ∈ N, m · (n + k) = m · n + m · k
P17 : 0 is the least element of N
P18 : ∀m, n, k ∈ N, m 6 n =⇒ m + k 6 m + k
P19 : ∀m, n, k ∈ N, m 6 n =⇒ m · k 6 m · k

9.1.4 Principle of Mathematical induction revisited

Theorem 21: Strong Induction Theorem

If Y is a subset of N such that:

1. 0 ∈ Y ,
2. for all k ∈ N, if {0, 1, . . . , k} ⊆ Y implies that k + 1 ∈ Y then
Y = N.
72CHAPTER 9. FROM THE NATURAL NUMBERS TO THE REAL NUMBERS

Proof. Apply the principle of mathematical induction to the statements

P (n) : {0, 1, . . . , n} ⊆ Y.

Proof. Follows from the Strong Induction Theorem.

9.1.5 The Well-Ordering Principle

Theorem 22: Well-Ordering Principle

Every nonempty subset X of N has a least element.

Proof. Assume by contradiction that X does not have a least element and apply
the Strong Induction Theorem to Y := N \ X.

Note that we deduced the Well-Ordering Principle from the Induction Ax-
iom. The Well-Ordering Principle is actually logically equivalent to the In-
duction Axiom. The Well-Ordering Principle has the following two important
applications.
We define a strict partial ordering, denoted by <, on N associated to the
partial ordering 6 by posing x < y ⇐⇒ (x 6 y) ∧ (x 6= y).
Proposition 38

There is no natural number n such that 0 < n < 1.

Hint. Apply the Well-Ordering Principle to the set

Proposition 39

(N, 6) is a totally ordered set.

Proof. Apply the Well-Ordering Principle to the set {x, y}.

9.2 The Integers

Besides 0, no element in N has an additive inverse in N. To remedy to this issue
we construct the set of integers. Informally one wants to symmetrize the set
N, in the sense that we want to augment the set by including additive inverses.
The formal way to do this is to define the integers as equivalent classes of pairs
of natural number with respect to an ad-hoc equivalence relation.
9.2. THE INTEGERS 73

9.2.1 Construction of Z

Proposition 40

Let Rint be the relation on N × N, defined by

(i, j)Rint (k, l) ⇐⇒ i + l = j + k.

Rint is an equivalence relation on N × N.

Proof. Straightforward from the definition of the relation.

Definition 65
The set of integers, denoted by Z, is defined as the set of equivalence
classes of the relation Rint on N × N, i.e.

Z := {[(n, m)]|(n, m) ∈ N × N}.

One defines an addition on Z (still denoted +) by posing [(i, j)] + [(k, l)] :=
[(i + k, j + l)]. Clearly, this addition is associative, commutative, and [(0, 0)] is
the unit element of + on Z. The only delicate point is to show that this addition
is well-defined, in the sense that if we had pick different representatives for the
equivalence classes, then the outcome would still be the same.
The following proposition states that this construction achieves what we
were aiming for.

Proposition 41

1. Every element [(n, m)] in Z has an additive inverse in Z which is

[(m, n)].
2. The map n 7→ [(n, 0)] is an injection from N into Z.

Proof. Straightforward.

The multiplication on N can be naturally extended to Z.

74CHAPTER 9. FROM THE NATURAL NUMBERS TO THE REAL NUMBERS

9.2.2 Basic properties of Z

9.2.3 Applications
9.2.3.1 The Division Algorithm and Greatest Common Divisors
9.2.3.2 Primes and Unique Factorization
9.2.3.3 Congruences

9.3 The Rational Numbers

9.3.1 Construction of Q
9.3.2 Basic properties of Q

9.4 The Real Numbers

9.4.1 Construction of R
9.4.2 Basic properties of R

9.5 Exercises
Exercise 25. Show that if m + n = 0 then m = n = 0.

Hint. Use Exercise 47 and the Induction Axiom.

Exercise 26. Deduce the Induction Axiom from the Well-Ordering Principle.
Chapter 10

Cardinality of Sets

10.1 Finite and Infinite sets

It is usual to denote by |X| the cardinality of X, i.e. the number of elements of
X. If we are dealing with finite sets we intuitively understand what |X| = |Y |
means, but what if the sets are infinite. Understanding a formal definition of
“cardinality” and the concept of “infinity” is the goal of this chapter.
Definition 66
A set X is said to be finite if there exist a natural number n ≥ 1 and
a bijection between X and {1, 2, . . . , n}. The number n is called the
cardinality of X, and is denoted by |X|.

Definition 67
A set X is said to be infinite if it is not finite, and we use the notation
|X| = ∞ to express that X is infinite.

Proposition 42

If X and Y are finite then |X × Y | = |X||Y |.

Proposition 43

Let X and Y be finite disjoint sets. Then |X ∪ Y | = |X| + |Y |.

Using the Principle of Mathematical Induction one can prove the following
corollary.
Corollary 1. Let X1 , X2 , . . . , Xn be a collection of finite mutually disjoint sets,
i.e. Xi ∩ Xj = ∅ if i 6= j. Then
n
[ n
X
Xi = |Xi |.
i=1 i=1

Corollary 2. Let X and Y be finite sets. Then |X ∪ Y | = |X| + |Y | − |X ∩ Y |.

75
76 CHAPTER 10. CARDINALITY OF SETS

10.1.1 The Pigeonhole Principle

The pigeonhole principle, in its simplest form, says that if k objects are places
in n containers and k > n, then at least one container will have more than one
object in it. The mathematical formulation is as follows.
Theorem 23: Pigeonhole Principle

Let X1 , X2 , . . . , Xn be a collection of finite mutually disjoint sets. Let

n
[
X= Xi . If |X| = k and k > n, then, for some i, |Xi | ≥ 2.
i=1

Theorem 24: Generalized Pigeonhole principle

Let X1 , X2 , . . . , Xn be a collection of finite mutually disjoint sets. Let

n
[
X = Xi . If |X| > nr for some positive integer r. Then, for some i,
i=1
|Xi | ≥ r + 1.

10.2 Countable Sets

10.3 Uncountable Sets
10.4 Collections of Sets