Université Paris 1 Panthéon-Sorbonne

Lecture notes

Master Mathematical Models in Economics and Finance (MMEF)

LOGIC AND SETS

Michel Grabisch

Source:

• Lecture notes of Stéphane Gonzalez

http://www.stephane.gonzalez.com/Logic-and-set/lecture notes.pdf
and Xavier Venel https://sites.google.com/site/xaviervenelsite/course-materials
• A first Course in Mathematical Logic and Set Theory, Michael L. O’Leary.
• Schaum’s Outline of Set Theory and Related Topics, Seymour Lipschutz

1
 Contents

1 Classical logic 4
1.1 Symbolic logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 First-order logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Reasoning in mathematics 8
2.1 Existential/Conditional statements and direct proof . . . . . . . . . . . . . . 8
2.2 More involved direct proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Indirect proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Basic set theory 16

3.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Constructing new sets from operations on sets . . . . . . . . . . . . . . . . . 17
3.3 Family of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Cartesian product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Functions 23
4.1 Definition of a function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Injection, Surjection, Bijection. . . . . . . . . . . . . . . . . . . . . . . . . . 25

5 Relations 29
5.1 Definition of a binary relation . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3 Order relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Cardinality 36
6.1 Cardinality of a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2 Generalized union and intersection . . . . . . . . . . . . . . . . . . . . . . . 37
6.3 Advanced properties of cardinality . . . . . . . . . . . . . . . . . . . . . . . . 38

2
6.4 The cardinality of the continuum . . . . . . . . . . . . . . . . . . . . . . . . 38

3
 Chapter
1
Classical logic

1.1 Symbolic logic

Definition 1. A proposition is a statement which is either true or false.
Example 1.
• “Paris is in France” or “2+2=4” (are true).
• “2+2=5” (is false).
• “What time is it?” is not a proposition.
Logic is all about propositions and relationships between them.
Definition 2. Let p and q be two propositions:
(i) p ∧ q, called the conjunction of p and q, is the proposition which is true if and only if
p is true and q is true.
(ii) p ∨ q, called the disjunction of p and q, is the proposition which is true if p is true or q
is true.
(iii) ¬p, called the negation of p, is the proposition which is true if and only if p is false.
(iv) The material implication p → q, “if p then q”, is the abbreviation of the proposition
¬p ∨ q (which is true unless p is true and q is false).
(v) The material equivalence p ↔ q, “p if and only if q”, is the abbreviation of the propo-
sition (p → q) ∧ (q → p).
We can use a truth value tabular to evaluate if a “complex” proposition is true or false.
For example :

p q p∧q p∨q ¬p ¬q p→q q→p p↔q p ∨ ¬p p ∧ ¬p

T T T T F F T T T T F
T F F T F T F T F T F
F T F T T F T F F T F
F F F F T T T T T T F

4
Definition 3. A tautology is a proposition which is always true regardless of which valuation
is used for the propositional variables.
Definition 4. The sentence “if p then q” or “p implies q” or “p is a sufficient condition for q”
or “q is a necessary condition for p” or “p only if q” is denoted by the abbreviation: “p ⇒ q”
which means:
“p → q” is true.
Example 2. Let p and q be the two following propositions:
• p: “1=2” (false)
• q: “2=3” (false)
p → q is true (see truth table). Hence we can write p ⇒ q.
Definition 5. The sentence “p if and only if q” or “p is equivalent to q” or “p is a necessary
and sufficient condition for q” is denoted by the abbreviation: “p ⇔ q” which means:
“p ↔ q” is true.
Theorem 1. Let p, q and r be three propositions. The following propositions are tautologies:

(i) p ∨ (¬p) (vi) ((p ∧ q) ∧ r) ↔ (p ∧ (q ∧ r))

(ii) p ↔ (¬(¬p)) (vii) ¬(p ∨ q) ↔ (¬p ∧ ¬q)
(iii) (p ∨ q) ↔ (q ∨ p) (viii) ¬(p ∧ q) ↔ (¬p ∨ ¬q)
(iv) (p ∧ q) ↔ (q ∧ p) (ix) (p ∨ q) ∧ r) ↔ (p ∧ r) ∨ (q ∧ r)
(v) ((p ∨ q) ∨ r) ↔ (p ∨ (q ∨ r)) (x) (p ∧ q) ∨ r) ↔ (p ∨ r) ∧ (q ∨ r)

Exercice : Find the negation of the proposition

“If there is a problem then there is a solution”.
Solution :
“There is a problem and there is no solution”
hint: use Theorem 1(vii) and (ii) with the propositions p:“there is a problem”, and q:“there
is a solution”.

5
1.2 First-order logic
We gave a mathematical formalism for the sentence: “Tuesday is a nice day”. We would like
now to construct from this sentence “Every day of the week is a nice day”.

Definition 6 (Naive definition of a set). A set is a well-defined collection of objects. The

objects in a set are called its elements. If A is a set,

(i) a ∈ A means that a belongs to the set A, or that a is an element of A, or that A

contains a.

(ii) a 6∈ A means that a does not belong to A or that a is not an element of A, or that A
does not contain a.

Example 3. The easiest way to define a set is to list all elements. For example, {α, β, γ} is
the set which contains the elements called α, β and γ.

Definition 7. A predicate on a set A is an expression which associates to every element

x ∈ A a proposition p(x).

Definition 8 (Universal Quantifier). Given the predicate p(x) on A, “∀x ∈ A, p(x)” is the
proposition which is true if and only if p(x) is true for every element x ∈ A.

Example 4.

• ∀x ∈ R, x2 ≥ 0,

• ∀x ∈ R, x + 1 = 2.

Definition 9 (Existential Quantifier). Given the predicate p(x) on A, “∃x ∈ A, p(x)” is the
proposition which is true if and only if p(a) is true for at least one element a ∈ A.

Example 5. Let p(α), p(β) and p(γ) be three propositions which define a predicate on the
set {α, β, γ}. We have “∃x ∈ {α, β, γ}, p(x)” if and only if p(α) ∨ p(β) ∨ p(γ).

Definition 10 (Negation of quantified statements). The negation of quantified statements

is based on the following rule:

(i) ¬(∀x ∈ A, p(x)) ⇔ (∃x ∈ A, ¬p(x))

(ii) ¬(∃x ∈ A, p(x)) ⇔ (∀x ∈ A, ¬p(x))

Example 6. Let A = {Lucy, Matthew, Lisa} and P (x) the predicate on A, “x wears a red
shirt”. Let us denote by p =“Lucy wears a red shirt”, q =“Matthew wears a red shirt”,
r =“Lisa wears a red shirt”, then we have

6
 p q r ∀x ∈ A, P (x) ¬(∀x ∈ A, p(x)) ¬p ¬q ¬r ∃x ∈ A, (¬p(x))
T T T T F F F F F
T T F F T F F T T
T F T F T F T F T
T F F F T F T T T
F T T F T T F F T
F T F F T T F T T
F F T F T T T F T
F F F F T T T T T

Definition 11. A predicate can concern several variables. Let p be a predicate on A × B

and QA and QB be two quantifiers then
• QA x ∈ A, p(x, y) is a predicate on B,
• QB y ∈ B, QA x ∈ A, p(x, y) is a proposition.
Example 7.
• ∀x ∈ R, ∃y ∈ R, x ≤ y,
• ∃y ∈ R, ∀x ∈ R, x ≤ y.
Proposition 1. Let p be a predicate on A × B then

∃y ∈ B, ∀x ∈ A, p(x, y) ⇒ ∀x ∈ A, ∃y ∈ B, p(x, y).

Remark 1. The order of quantifiers (if of different types) is important. If they are all of
the same type the order is not important.
Remark 2. (Negation of complex quantifiers) Let p be a predicate on A × B, then

¬ (∀x ∈ A, ∃y ∈ B, p(x, y)) ⇔ ∃x ∈ A, ¬(∃y ∈ B, p(x, y)),

⇔ ∃x ∈ A, ∀y ∈ B, ¬(p(x, y)).

Example 8. Let f be a function on an interval I, the function is said to be continuous on

I if
∀x ∈ I, ∀ε > 0, ∃δ > 0, s.t. ∀y ∈]x − δ, x + δ[, |f (x) − f (y)| ≤ ε.
By taking the negation and applying successively the rules of inference on the negations: f
is not continuous on I if

∃x ∈ I, ∃ε > 0, ∀δ > 0, s.t. ∃y ∈]x − δ, x + δ[, |f (x) − f (y)| > ε.

7
 Chapter
2
Reasoning in mathe-
matics

In this chapter, we will highlight several typical ways to prove a mathematical statement.
The type of proof will depend on the statement.

The main statements that you can find are of the following form:
• Universal statement: For every .....,... (is true).
• Conditional statement: If ....(is true) then .... (is true).
• Existential statement: There exists ... such that ... (is true).
• Equivalence statement: ...(is true) if and only if ... (is true).

Remark 3. Universal statements and conditional statements are in fact very similar: “Every
even number is followed by an odd number” is equivalent to “If n is an even number then it
is followed by an odd number” (the quantifier is omitted in this last formulation).
Remark 4. In the process of writing a proof there are several levels of formalism: the
intuition (where anything is allowed), a sketch of the proof with the order of the arguments,
a detailed formal proof where each step is written properly.

2.1 Existential/Conditional statements and direct proof

We start by introducing direct proofs. The intuition is to follow the direction of the state-
ment. The precise way will depend on the type of statements (conditional, existential or
equivalence).

Our example will concern integers (denoted by N), real numbers and divisibility. We first
introduce the definitions that we will use.
Definition 12. Let p and n be two integers. We say that p is dividing n or that p is a
divisor of n if there exists an integer k such that n = kp.

∃k ∈ N, n = kp.

Definition 13. An integer n is even if 2 is a divisor of n. Otherwise, the integer is said to

be odd.

8
Remark 5. Combining the two definitions, we obtain that the set of even numbers is

{n, such that n ∈ N and 2 is dividing n} = {n, s.t. there exists k ∈ N and n = 2k}
= {2k, k ∈ N}.

We will now look at two examples and give direct proof of the results.
Example 9. (Universal statement) For every number n divisible by 3, 9 is a divisor of n2 .
Example 10. (Conditional statement) Let n be an integer. If n is divisible by 3, then 9 is
a divisor of n2 .
Since it is a conditional statement, the proof goes as follows: assume the hypothesis,
deduce consequences logically until conclusion.
Proof. Let n be a number divisible by 3. We want to show that 9 is dividing n2 . By
assumption, there exists k ∈ N such that

n = 3k.

It follows that n2 = (3k)2 = 9k 2 . Since k 2 is an integer, 9 is dividing n2 .

Example 11. (Existential statement) There exists a number divisible by 9 and 10.
Since it is an existential statement, the direct proof goes as follows: introduce a candidate,
check that this candidate is indeed satisfying the conclusion.
Proof. Let us consider x = 900. We know that x = 9 ∗ 100 so 9 is indeed a divisor of x. On
the other hand x = 90 ∗ 10 , hence 10 is also a divisor of x.

Therefore there exists a number divisible by 9 and 10.

Example 12. (Equivalence statement) Let n be an integer. n is divisible by 3 if and only
if n + 6 is also divisible by 3.
There are two different ways to write a direct proof. The first one is to decompose the
statement into two implications and prove each of them.

The second one is to assume one of the two assumptions and follow a chain of known
equivalence. We will see such a proof in the next chapter.

2.2 More involved direct proofs

We now describe two reasonings that are often used in proofs. They are based on the
following logic tautologies.
Theorem 2. Let p, q and r be three propositions, then
(i) Disjunction of case : [(p ∨ q) ∧ (p → r) ∧ (q → r)] ⇒ r

9
 (ii) Transitivity: [(p → q) ∧ (q → r)] ⇒ (p → r)
Example 13. (Disjunction) Let a and b two real numbers. If ab = 0 then a = 0 or b = 0.
Proof. Let a and b be two real numbers such that ab = 0. Let us consider two cases:
• if a = 0 then the conclusion is true a = 0 or b = 0 and the implication is true.
• if a 6= 0 then c = a1 is well defined and we can multiply the equality ab = 0 on both
sides by c. We obtain

c(ab) = c0 = 0
1
(ab) = 0
a
b=0

so the conclusion is true.

By disjunction of cases, we proved the result.
Example 14. (Transitivity) For every integer n, if n is divisible by 3 then (n+6)2 is divisible
by 9.
Proof. We proved previously that
• for every integer n divisible by 3, n2 is divisible by 9.
• for every integer n divisible by 3, n + 6 is divisible by 3.
Let n be an integer divisible by 3, then by the second statement (left to right implication),
we know that n + 6 is also divisible by 3.

Applying now the first statement to m = n + 6, we know that m2 = (n + 6)2 is divisible

by 9. It concludes the proof.

2.3 Indirect proof

We now present two methods that are called indirect and that are linked to the two following
logic formulae.
Theorem 3. Let p, q and r be three propositions, then
(i) Contrapositive: (p → q) ⇔ (¬q → ¬p),
(ii) Contradiction: (p → q) ∧ ¬q ⇒ ¬p,
Remark 6. “¬q → ¬p” is called the contrapositive of “p → q”
Proof. Let us prove the contrapositive formula. It suffices to prove that for all propositions
p and q, the proposition (p → q) ↔ (¬q → ¬p) is true... use a truth table!!

10
 p q p→q ¬q ¬p ¬q → ¬p (p → q) → (¬q → ¬p) (¬q → ¬p) → (p → q) (p → q) ↔ (¬q → ¬p)
T T T F F T T T T
T F F T F F T T T
F T T F T T T T T
F F T T T T T T T

The proposition (p → q) ↔ (¬q → ¬p) is always true, hence (p → q) ⇔ (¬q → ¬p).

Exercice : Find the contrapositive of the proposition

“If there is a problem then there is a solution”.

Solution :

“If there is no solution then there is no problem” (Shadock’s motto).

Example 15. (Contrapositive) Let n be an integer. If n2 is odd then n is odd.

The proof by contrapositive goes as follows: assume that the conclusion is false and prove
that the assumption is false.

Proof. Let us describe first what would happen with a direct proof: let n ∈ N. Assume that
there exists k ∈ N such that
n2 = 2k + 1,
and we are stuck since we can not exploit the fact that n2 is a square.

Let us prove this result by the contrapositive. The contrapositive of the formula is “if n
is not odd then n2 is not odd” or equivalently “ if n is even then n2 is even”.

Let n be an even number. There exists k ∈ N such that n = 2k. Hence n2 = 4k 2 = 2∗(2k 2 )
and n2 is indeed even.

Example 16. (Contradiction) Consider a right-angle triangle. We denote by c the length

of the hypotenuse and by a and b the length of the two other sides. Then c ≤ a + b.

The proof by contradiction goes as follows: assume that the statement is false and deduce
a contradiction (that some other statement is both false and true).

Proof. We assume that

a + b < c.
Then by taking the square, we obtain that

a2 + 2ab + b2 < c2

By Pythagoras’ theorem, we know that a2 + b2 = c2 , hence 0 ≤ 2ab < 0. This is impossible,

hence the contradiction.

11
2.4 Induction
We denote by N = {0, 1, . . .} the set of natural numbers. Elementary facts about the ordered
set of natural numbers:
• (F1) Every n ∈ N has a successor n + 1 s.t.
∀m ∈ N, n < m ⇔ n + 1 ≤ m.

• (F2) 0 is the least number.

• (F3) For all m ∈ N \ {0}, there exists n ∈ N, such that m = n + 1.
Remark 7. There are different ways to construct the natural numbers:
• define real numbers and consider N as a subset of R and check that it satisfies the
previous facts.
• define N by the previous facts and then define operations (addition, multiplication) on
N.
Weak principle of induction. Let p(n) be a predicate on N. Suppose the two following
propositions hold
(i) p(0) is true (basis)
(ii) ∀ n ∈ N, p(n) ⇒ p(n + 1) (induction step).
Then for all n ∈ N, p(n) is true.

Remark 8. The weak principle of induction becomes a theorem if one admits the following
property of N: For all A ⊆ N, if 0 ∈ A and for all n ∈ A, then n + 1 ∈ A then A = N.
Indeed, let p(n) be a predicate on N such that p(0) is true and ∀ n ∈ N, p(n) ⇒ p(n + 1).
Let
A = {n ∈ N, p(n) is true}.
By assumption 0 ∈ A and if n ∈ A then n + 1 ∈ A. Therefore A = N.
Pn n(n+1)
Example 17. Prove that p(n) : 0 + 1 + · · · + n = t=0 t= 2
.
• Basis: p(0) is true since 0 = 0,
• Induction step: let n ∈ N such that p(n) is true. Then
n+1
X n(n + 1)
0 + 1 + · · · + (n + 1) = t= + (n + 1), by the induction assumption
t=1 2
n
 
= (n + 1) +1 ,
2
(n + 1)(n + 2)
= .
2
Therefore, p(n + 1) is true.

12
 • By the weak principle of induction, the formula is true for every n ∈ N.
To be correct, the weak induction principle must be used with some precaution:
(i) The initialization step (basis) may start at some number k 6= 0.
Example 18. Prove that n2 ≥ 3n for all n ≥ 3.
• Basis: p(3) is true since 9 ≥ 9,
• Induction step: let n ≥ 1 such that p(n) is true. Then

(n + 1)2 = n2 + 2n + 1 ≥ 3n + 2n + 1 ≥ 3n + 3,

hence p(n + 1) is true.

• By the weak principle of induction, the formula is true for every n ≥ 3. Observe
that it is false for n = 2.

(ii) Be careful not to overlook the basis!

Example 19. Consider the property p(n): n is greater than itself (n > n). From p(n)
it is easy to deduce p(n + 1): n > n implies n + 1 > n + 1. However, p(0) fails.

(iii) If the basis is p(n0 ), then do not forget to check that p(n) ⇒ p(n + 1) is shown for
every n ≥ n0 . The next example is Polya’s proof that there is no horse of a different
color. Find the mistake in the proof!
Example 20. For every n ≥ 1, in a set of n horses, all horses have the same color.
Polya’s proof:
• Basis p(1): if there is only one horse, there is only one color.
• Induction step: assume that for any set of n horses, there is only one color. Take
a set of n + 1 horses, numbered 1, 2, . . . , n + 1. Consider the sets {1, . . . , n},
{2, . . . , n + 1}. Each set is of one color and since they overlap, {1, . . . , n + 1} is of
one color. Hence p(n + 1) holds.

The mistake is that the proof that p(n) ⇒ p(n + 1) is valid only for n > 1. Hence the
step p(1) ⇒ p(2) is missing.

Strong principle of induction. Let p(n) be a predicate on N. Suppose the two following
propositions hold
(i) p(0) is true (basis)
(ii) for all n ∈ N, (∀m ≤ n, p(m)) ⇒ p(n + 1) (induction step).
Then for all n ∈ N, p(n) is true.

Example 21. Prove that any number n ≥ 2 has a prime divisor.

13
 • basis: p(2) is true.
• Let n ≥ 2 and assume that p(2), . . . , p(n) are true. Then, either n + 1 is prime, in
which case it has a prime divisor (itself). Or it is not, then there exist 2 ≤ d < n + 1
which divides n + 1. By induction hypothesis, d has a prime divisor, which is also a
prime divisor of n + 1.
Theorem 4. The strong principle of induction follows from the weak principle of induction.
Proof. Consider p(n) and assume that (i) and (ii) hold in the strong induction principle. We
denote by q(n) the predicate (∀m ∈ N s.t. m ≤ n, p(m)). Let us show by using the weak
induction principle that for every n ∈ N q(n) is true.

• Basis: q(0) = p(0), and therefore is true by (i).

• Induction step: let n ∈ N, such that q(n) is true. Then
– for every m ≤ n, p(m) is true (by definition of q(n))
– p(n + 1) is true (by (ii)).
Therefore q(n + 1) is true
• By the weak principle of induction, for every n ∈ N, q(n) is true, hence p(n) is true.

Least Number Principle (infinite descent of Fermat). The LNP states: If M ⊆ N

and M 6= ∅, then M has a least element.
√
Example 22. (proof that 2 is irrational
√ (discovered√by the ancient Greeks))
By contradiction, suppose that 2 were rational: 2 = pq with p, q ∈ N. Then 2q 2 = p2 .
It follows that p2 is even, and so is p. Hence, there exists r ∈ N such that p = 2r. Then

2q 2 = 4r 2

i.e., q 2 = 2r 2 , and so q is even, i.e., q = 2s for some integer s. We have obtained

p r
= , with r < p, s < q.
q s
The same reasoning can be pursued on r, s, and so ad infinitum:

p > r > r ′ > r ′′ > · · ·

q > s > s′ > s′′ > · · ·

which is not possible by the LNP.

Theorem 5. The Least Number Principle follows from the strong principle of induction.

14
Proof. We prove the result by contradiction. Assume that M ⊆ N, M 6= ∅ and M has no
least element.
Let p(n) be the predicate defined on N by p(n) : “n 6∈ M ′′ . We prove by the strong
induction principle that p(n) is true for all n ∈ N, which contradicts the assumption M 6= ∅.
• Basis: p(0) holds, otherwise 0 would be the least element.
• Induction step: assume that p(m) holds for every m ≤ n. This means that m 6∈ M for
every m ≤ n. Then n < m for all m ∈ M, which by Fact F1 is equivalent to n + 1 ≤ m
for all m ∈ M. It follows that n + 1 6∈ M, otherwise it would be the least element of
M, a contradiction. Hence, p(n + 1) holds.

Theorem 6. The weak induction principle follows from the LNP.

Proof. Let p(n) be a property such that p(0) is true and ∀n ∈ N, p(n) ⇒ p(n + 1). We prove
that ∀n ∈ N, p(n), which amounts to showing that the class

M := {n ∈ N s.t p(n) does not hold}

is empty. By the LNP, it is enough to show that M has no least element.

Suppose M has a least element, say m. Since p(0) holds, 0 6∈ M, hence m 6= 0. Therefore,
by (F3), there exists n ∈ N s.t. m = n + 1, hence n < m. Since m is a least element of M,
n 6∈ M, i.e., p(n) holds.
From our assumption, we have then p(n + 1) holds, i.e., p(m) holds, which means that
m 6∈ M, a contradiction.
As a consequence of Theorems 4, 5 and 6, all three principles are equivalent.

15
 Chapter
3
Basic set theory

3.1 Basic definitions

Definition 14 (Naive definition of a set; this is Def. 6). A set is a well-defined collection of
objects. The objects in a set are called its elements. If A is a set,
(i) a ∈ A means that a belongs to the set A, or that a is an element of A. Equivalently,
we write A ∋ a (A contains a).
(ii) a 6∈ A means that a does not belong to A or that a is not an element of A. Equivalently,
we write A 6∋ a (A does not contain a).
Example 23. Example of sets
• A = {1, 2, 4, 6},
• B = [a, b] = {x ∈ R | a ≤ x ≤ b},
• C = {1, 2, 4, 2, 6, 2} = {2, 1, 4, 6}.
• N, Z, Q and R.
• D = {{1, 2}, 3, a, {a, b}}
Definition 15. A set A is a subset of a set B if every element of A is an element of B; one
writes A ⊆ B (A is included in B). Equivalently, we write B ⊇ A (B includes A). Formally:

A ⊆ B ⇔ (∀x)(x ∈ A → x ∈ B).

Example 24.
• {1, 2} ⊂ {1, 2, Marc},
• {1, 2, John} is not a subset of {1, 2}.
Definition 16. Two sets A and B are equal, denoted by A = B, if A ⊆ B and B ⊆ A.
Two sets which are equal contain the same elements. Whenever two sets are not equal
we denote it by A 6= B. If A ⊆ B and A 6= B, we have strict inclusion, denoted by A ⊂ B.1
In order to prove that two sets A and B are equal, we have two methods:
1
Many textbooks write ⊂ for inclusion and ( for strict inclusion.

16
 (i) Prove that A ⊆ B and B ⊆ A: fix a ∈ A and show that it is in B, then fix b ∈ B and
show that it is in A.
(ii) Fix an element x and show that x ∈ A if and only if x ∈ B.
A set can be defined via a property (this is called specification). Let A be a set and
P be a predicate on A. There exists a set denoted {x ∈ A, P (x)} or {x ∈ A | P (x)} or
{x ∈ A : P (x)} or {x ∈ A s.t. P (x)} whose elements are the elements of x ∈ A such that
P (x) is true.
Example 25. Let X be the set of animals.
• P (x) : “the animal x has feathers”, {x ∈ X, P (x)} is the set of animals with feathers.
• Q(x) : “the animal x has 3 legs”, {x ∈ X, P (x)} is the set of animals with 3 legs.
By taking the predicate P (x) : x 6= x, we obtain the empty set, denoted by ∅:

∅ = {x ∈ A, x 6= x}.

This set contains no element, since the predicate is always false.

Theorem 7. If X is a set, then ∅ ⊆ X.
Proof. Recall that ∅ ⊆ X is the proposition

∀x, (x ∈ ∅ → x ∈ X).

Therefore its negation is ∃x, x ∈ ∅ ∧ x ∈

/ X. This proposition is false since the empty set has
no elements. Hence the initial proposition is true.

Remark 9. If the above naive approach to set theory is sufficient most of the time, it
cannot be used as a basis for the foundations of mathematics, as many paradoxes can be
built with this loose definition of a set. The most famous one was proposed by Bertrand
Russel: consider the set defined by the property that it contains only sets which do not
belong to themselves:
S = {x | x is a set such that x 6∈ x}
Then if S 6∈ S, it should belong to S (i.e., S ∈ S), and if S ∈ S, then it should not belong to
S (i.e., S 6∈ S). This is why a rigorous axiomatic approach to set theory was constructed by
Zermelo, and completed by Fraenkel, referred usually as the Zermelo-Fraenkel (ZF) axiomatic
set theory.

3.2 Constructing new sets from operations on sets

We will now list different operations that can be used on sets and define new sets.
Definition 17. Let A and B be two sets. One can define

17
 (i) (Pairing)2 The set {A, B} is the set with 2 elements A and B:

x ∈ {A, B} if and only if (x = A or x = B).

(ii) (Union) The set A ∪ B is the set containing both the elements of A and the elements
of B:
x ∈ A ∪ B if and only if (x ∈ A or x ∈ B).

(iii) (Intersection) The set A ∩ B is the set containing the elements that are both in A and
in B:
x ∈ A ∩ B if and only if (x ∈ A and x ∈ B).

(iv) (Relative complement) The set A \ B (or A − B) is the set containing the elements that
are in A and not in B:

x ∈ A \ B if and only if (x ∈ A and x ∈

/ B).

(v) (Complement) Suppose U is some universal set. If A ⊆ U,

Ac := U \ A.

(vi) (Symmetric difference) The set A∆B is the set containing the elements in A ∪ B and
not in A ∩ B.
A∆B := (A ∪ B) \ (A ∩ B).

Example 26. Union, intersection and relative complement are quite straightforward. One
must be careful with the pairing, especially when pairing a set with itself: a set A and the
singleton {A} = {A, A} are two different sets. For example,
• If A = ∅, the set ∅ does not contain any element, while the set {∅} contains exactly
one element: the element ∅ !
• A = ∅, B = {∅}, C = {B} = {{∅}}, are three different sets.
• A = {1, 2}, B = {2, 3} and {A, B} = {{1, 2}, {2, 3}}.
With the previous propositions and the results that we have shown in the chapter on
logic, we can show the following rules of computation. They are theorems, hence have to be
”proved” from definitions and previous results.
Theorem 8. The union ∪ satisfies the following properties:
(i) A ∪ ∅ = A;
(ii) A ∪ B = B ∪ A;
(iii) (A ∪ B) ∪ C = A ∪ (B ∪ C).
2
In ZF, pairing is an axiom permitting to construct a new set from two sets.

18
Theorem 9. The intersection ∩ satisfies the following properties:
(i) A ∩ ∅ = ∅;
(ii) A ∩ B = B ∩ A;
(iii) (A ∩ B) ∩ C = A ∩ (B ∩ C).
(iv) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(v) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Theorem 10 (De Morgan’s laws). Let A, B and C be three sets:
(i) A \ ∅ = A
(ii) ∅ \ A = ∅
(iii) C \ (A ∪ B) = (C \ A) ∩ (C \ B) in particular (A ∪ B)c = Ac ∩ B c .
(iv) C \ (A ∩ B) = (C \ A) ∪ (C \ B) in particular (A ∩ B)c = Ac ∪ B c
Proof. As exercice.
Theorem 11. The symmetric difference ∆ satisfies the following properties:
(i) A∆∅ = A;
(ii) A∆B = B∆A;
(iii) (A∆B)∆C = A∆(B∆C).
(iv) A∆A = ∅

3.3 Family of sets

We have already seen with the pairing axiom that one can consider sets whose elements are
also sets. These are “sets of sets”, usually called “collections of sets” or “family of sets”.
Example 27. Let A = {a, b}. We have:
• {{a, b}} is a set with one element which is A.
• {{a}, {a, b}} is a set with two elements.
• {∅, {a}, {b}} is a set with three elements.
In particular the following set, called the power set, is very important

{∅, {a}, {b}, {a, b}}.

It is the set of all subsets of A.

19
Definition 18. Given any set A, the set denoted by 2A (or P(A)) and called power set of
A is defined3 by:
B is a member of 2A if and only if B ⊆ A.
Formally:
P(A) = {B, B ⊆ A}
Note that we have always ∅ ∈ 2A and A ∈ 2A .
Example 28.
• 2∅ = {∅}.
• P({∅}) = {∅, {∅}}.
• 2{a,b,c} = {∅, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}}
• P(R) is the set of all subsets of R.
We can now extend the notion of union and intersection to family of sets.
Definition 19. Let F be a family of sets. The union and intersection of all sets in the
family is defined as follows:
[
F = {x, ∃A(A ∈ F ∧ x ∈ A)}
and \
F = {x, ∀A(A ∈ F → x ∈ A)}
Definition 20. Let F be a family of sets such that F = {Ai , i ∈ I}. The union and
intersection of all sets in the family is defined as follows:
[
Ai = {x, ∃i(i ∈ I ∧ x ∈ Ai )}
i∈I

and \
Ai = {x, ∀i(i ∈ I → x ∈ Ai )}
i∈I

Remark 10. When F can be indexed by some set I, both definitions are available and are
equivalent (union and intersection).
With these two new definitions, we can extend De Morgan’s Law and the distributivity
formulas.
Theorem 12. Let (Ai )i∈I a family of sets and B a set:
• ( Ai )c = Aci ,
S T
i∈I i∈I

• ( Ai )c = Aci ,
T S
i∈I i∈I

• B∩( Ai ) = i∈I (B ∩ Ai ),
S S
i∈I

• B∪( Ai ) = i∈I (B ∪ Ai ).
T T
i∈I
3
In ZF, this is an axiom saying that if A is a set, then 2A is also a set.

20
3.4 Cartesian product
Definition 21 (Naive definition of an ordered pair). An ordered pair (x, y), or simply a pair,
is a list of two objects x and y given in a definite order; x is said to be the first (or left)
coordinate of the pair, while y is the second (or right) coordinate.
A formal definition due to Kuratowski and using only sets is as follows: An ordered pair
(x, y) is the set which contains the singleton {x}, and the pair {x, y}:
A∪B
(x, y) = {{x}, {x, y}} ∈ 22 .

As pairs are ordered, equality of pairs means equality of their components “coordinate-
wise”:
(a, b) = (c, d) ⇔ (a = c) ∧ (b = d).
In the Kuratowski’s definition, this statement has to be proved4 .
Definition 22. The Cartesian product of two sets A and B, denoted by A × B, is the set of
all ordered pairs (a, b) where a ∈ A and b ∈ B, that is:

A × B = {x, (∃a ∈ A)(∃b ∈ B), x = (a, b)}.

• If A = B we simply denote A × A by A2 .
• The Cartesian product of three sets A, B and C, denoted A×B ×C, is the abbreviation
of the set (A × B) × C. The elements of A × B × C are called the ordered triplets of
A, B and C.
4
Here is a proof:
• ” ⇐ ” If a = c and b = d, then {{a}, {a, b}} = {{c}, {c, d}}. Thus (a, b) = (c, d).
• ” ⇒ ”: Two cases:
(i) If a = b:

(a, b) = {{a}, {a, b}} = {{a}, {a, a}} = {{a}},

(c, d) = {{c}, {c, d}} = {{a}}.

Thus {c} = {c, d} = {a}, which implies a = c and a = d. By hypothesis, a = b. Hence b = d.

(ii) If a 6= b, then (a, b) = (c, d) implies

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

– Suppose {a} = {c, d}. Then c = d = a, and so

{{c}, {c, d}} = {{a}, {a, a}} = {{a}, {a}} = {{a}}.

But then {{a}, {a, b}} would also equal {{a}}, so that b = a which contradicts a 6= b.
– Suppose {a} = {c}. Then a = c and we have

{{a}, {a, b}} = {{a}, {a, d}}

Since a 6= b, we have {a, b} = {a, d} and therefore b = d.

21
Proposition 2. (i) A × B = ∅ is equivalent to (A = ∅ ∨ B = ∅).
(ii) If A 6= ∅ and B 6= ∅ then
(a) A × B ⊆ A′ × B ′ is equivalent to (A ⊆ A′ ∧ B ⊆ B ′ ).
(b) (A × B) ∪ (A′ × B) = (A ∪ A′ ) × B.
(c) (A × B) ∩ (A′ × B) = (A ∩ A′ ) × B.
Proof. (i) ¬(A = ∅ ∨ B = ∅) ⇔ (A 6= ∅ ∧ B 6= ∅) ⇔ ((∃a ∈ A) ∧ (∃b ∈ B)) ⇔ ((a, b) ∈
A × B) ⇔ ¬(A × B = ∅)
(ii) Let A 6= ∅ and B 6= ∅:
(a) ”⇒”: Suppose A×B ⊆ A′ ×B ′ . Let a ∈ A and b ∈ B. By hypothesis (a, b) ∈ A×B
implies (a, b) ∈ A′ × B ′ which implies by definition of the cartesian product that:
(a ∈ A′ ) ∧ (b ∈ B ′ ).
”⇐”: Suppose (A ⊆ A′ ) ∧ (B ⊆ B ′ ). Let x ∈ A × B, then (∃a ∈ A) ∧ (∃b ∈ B)
such that x = (a, b), but (A ⊆ A′ ) ∧ (B ⊆ B ′ ) implies (a ∈ A′ ) ∧ (b ∈ B ′ ). Hence
x = (a, b) ∈ A′ × B ′ .

22
 Chapter
4
Functions

4.1 Definition of a function

Definition 23. • A mapping or function from the set A to the set B, denoted by f :
A → B, is a triplet (A, B, graph(f )) where A and B are two sets and graph(f ) is a
subset of A × B such that for every a ∈ A, there is one and only one b ∈ B such that
(a, b) ∈ graph(f ):

[∀x ∈ A, ∃y ∈ B, (x, y) ∈ graph(f )] ∧ [((a, b) ∈ graph(f )∧(a, c) ∈ graph(f )) ⇒ (b = c)].

In other words, for every a ∈ A there is exactly one element denoted f (a) ∈ B such
that the ordered pair (a, f (a)) ∈ graph(f ).

– The set A is called the domain of f ;

– The set B is called the codomain of f ;
– The set graph(f ) is called the graph of f ;
– The unique element f (a) such that (a, f (a)) ∈ graph(f ) is called the image of a
by f ;
– If C ⊆ A, the set f (C) := {b ∈ B | ∃a ∈ C, (a, b) ∈ graph(f )} = {b ∈ B | ∃a ∈
C, b = f (a)} is called the image of C by f .
1
– The set f (A) := {b ∈ B | (a, b) ∈ graph(f )} = {b ∈ B | ∃a ∈ A, b = f (a)} is
called the image of f .

• We denote by B A (or F (A, B)) the set of functions from A to B.

Observe that:
graph(f ) = {(a, b) ∈ A × B | b = f (a)}.

Note that
• C = ∅ is equivalent to f (C) = ∅.
• If f : A → B, f ({x}) = {f (x)} for every x ∈ A.
1
Observe that f (A) ⊆ B

23
Definition 24. Two mappings f and g from A to B are said to be equal if for every element
a ∈ A one has f (a) = g(a).
Example 29. Here are some examples of mappings:
• The identity mapping on A, denoted by idA , is the mapping from A to A defined by
idA (a) = a for every a ∈ A.
• A mapping f : A → B is said to be constant if for every a and a′ in A, one has

f (a) = f (a′ ).

In other words, there exist an element b ∈ B such that for every a ∈ A, f (a) = b.
• The mapping proj1 : A × B → A (resp. proj2 : A × B → B) which associates to the
pair (a, b) the element a (resp. b) is called the canonical projection of A × B on A
(resp., B).
• Let C ⊆ A. The restriction of the mapping f : A → B to C is the mapping f|C : C → B
defined by f|C (x) := f (x) for every x ∈ C.
• Let B ⊆ A. The characteristic function of the set B is the function χB : A −→ {0, 1}
defined by 
1, if a ∈ B
χB (a) =
0, otherwise.

Proposition 3. Let f : A → B and let A1 , A2 be two subsets of A. Then

(i) A1 ⊆ A2 implies f (A1 ) ⊆ f (A2 ),
(ii) f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 ),
(iii) f (A1 ∩ A2 ) ⊆ f (A1 ) ∩ f (A2 ).

Note that the above inclusion may not be an equality. Find a counter-example.

Definition 25. The inverse image of C ⊆ B by f : A → B is the set

f −1 (C) = {a ∈ A | f (a) ∈ C}.

Proposition 4. Let f : A → B and let B1 , B2 be two subsets of B. Then

(i) f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ),
(ii) f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 ).

24
4.2 Injection, Surjection, Bijection.
Given a function f from A to B that associates to a an element f (a), one could want to
define an inverse function from B to A that associates to f (a) the element a. Unfortunately,
two problems may arise when trying to define such a function
• an element of B may not be in relation with any element in A.
• an element of B may be in relation with several elements in A.
It is interesting to focus on functions where at least one of these problems do not occur.
This yields the two following definitions.
Definition 26. A mapping f : A → B is said to be surjective (or onto) if every point in B
is the image of a point in A, that is
• B = f (A),

or equivalently
• for all b ∈ B, there exists a ∈ A, such that f (a) = b.
Informally, if f is surjective every element of B has at least one “pre-image” by f .
Example 30.
• f : R → R+ defined by f (x) = x2 is surjective,
• f : R → R defined by f (x) = x2 is not surjective.
Definition 27. A mapping f : A → B is said to be injective (or one-to-one) if two distinct
elements of A have different images by f . That is,
• if a1 6= a2 then f (a1 ) 6= f (a2 ),

or equivalently
• if f (a1 ) = f (a2 ) then a1 = a2 (by using the contrapositive).
Informally, if f is injective, every element of B has at most one “pre-image” by f .
Example 31.
• f : R → R defined by f (x) = x2 is not injective,
• f : R+ → R defined by f (x) = x2 is injective.

Avoid the confusion between the definition of injectivity and the fact that every mapping
has the property that a1 = a2 implies that f (a1 ) = f (a2 ), which simply means that every
element has a unique image.

25
Definition 28. A mapping f : A → B is said to be bijective if it is both surjective and
injective.
Definition 29. Let f : A → B and g : B → C. The composition of f by g is the mapping
g ◦ f : A → C defined by
g ◦ f (a) = g(f (a)), ∀a ∈ A.
Proposition 5. Given f : A → B, g : B → C and h : C → D then

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

Indeed let a ∈ A,
h ◦ (g ◦ f )(a) = h((g ◦ f )(a)) = h(g(f (a))),
whereas
(h ◦ g) ◦ f (a) = (h ◦ g)(f (a)) = h(g(f (a)).
Recall the identity mapping idA we defined in Example 29.
Definition 30. A mapping f : A → B is invertible if there exists a mapping g : B → A
such that:
• g ◦ f = idA ,
• f ◦ g = idB .
When the mapping g exists, it is unique. One denotes it by f −1 , and calls it the inverse
mapping of f .
Proof. (Proof of uniqueness) Let us assume that f is invertible and there exists a least two
mappings satisfying the assumptions:
• g1 : B → A such that g1 ◦ f = idA and f ◦ g1 = idB .
• g2 : B → A such that g2 ◦ f = idA and f ◦ g2 = idB .
We now prove that g1 = g2 . Since g1 ◦ f = g2 ◦ f we have, by composition by f ,

(g1 ◦ f ) ◦ g1 = (g2 ◦ f ) ◦ g1 .

Hence
g1 ◦ (f ◦ g1 ) = g2 ◦ (f ◦ g1 ),
which implies
g1 ◦ (idB ) = g2 ◦ (idB ).
Hence g1 = g2 .

26
Note that the notation f −1 may have two different meanings:
• if C ⊆ B, f −1 (C) is the inverse image of a set C and is always defined.
• if y ∈ B, then f −1 (y) is the image of y ∈ B by the inverse mapping and is
only defined if f is invertible.

Proposition 6. Let f : A → B be a function. Then f is injective if and only if for every

A1 , A2 ⊆ A, we have
f (A1 ∩ A2 ) = f (A1 ) ∩ f (A2 ).
Proof. ⇒) the inclusion ⊆ is always true. We show the inclusion ⊇: let y ∈ f (A1 ) ∩ f (A2 )
and let us show that y ∈ f (A1 ∩ A2 ).
We have in particular that y ∈ f (A1 ), hence there exists x1 ∈ A1 such that f (x1 ) = y.
Similarly, we have y ∈ f (A2 ), hence there exists x2 ∈ A2 such that f (x2 ) = y.
Since f is injective and f (x1 ) = f (x2 ), we obtain x1 = x2 =: x and x is both in A1 and in
A2 , therefore x ∈ A1 ∩ A2 . Hence there exists x ∈ A1 ∩ A2 such that f (x) = y, which means
y ∈ f (A1 ∩ A2 ).
⇐) Let x 6= y. We have immediately

∅ = f (∅) = f ({x} ∩ {y}) = f ({x}) ∩ f ({y}),

which implies f (x) 6= f (y).

Proposition 7. Let f : A → B and g : B → C.
• f and g injective ⇒ g ◦ f injective
• f and g surjective ⇒ g ◦ f surjective
• g ◦ f injective ⇒ f injective
• g ◦ f surjective ⇒ g surjective
Proof. As exercice.
Proposition 8. A mapping f : A → B is bijective if and only if it is invertible.
Proof. ⇒): For every b ∈ B, we consider the set

f −1 ({b}) = {a ∈ A such that f (a) = b}.

Since f is surjective, we know that this set is non-empty. Since f is injective it is a singleton.
We denote by g(b) its unique element. By construction, for every b ∈ B, g(b) ∈ f −1 ({b})
so f (g(b)) = b. Moreover, for every a ∈ A, f (a) ∈ {f (a)} so a ∈ f −1 ({f (a)}) = {g(f (a))}.
Hence g(f (a)) = a.
⇐): Let g : B → A be a mapping which satisfies f ◦ g = idB and g ◦ f = idA .

27
• idA is bijective therefore it is injective. By Proposition 7, g ◦ f injective implies f
injective.
• idB is bijective therefore it is surjective. By Proposition 7, f ◦ g surjective implies f
surjective. We conclude that f is bijective.

28
 Chapter
5
Relations

5.1 Definition of a binary relation

Definition 31. A binary relation R on a set A is a subset of the Cartesian product A2 =
A × A.
If (x, y) ∈ R, it is common to write xRy, which is read “x is in relation with y (by R)”.
Example 32. • Let E be a set. The equality relation on E, denoted by =E , is the binary
relation defined by
=E := {(x, x) ∈ E 2 , x ∈ E}
(diagonal of E 2 ). We write x =E y if (x, y) ∈=E , or more commonly x = y.
• < on the set of real numbers is a relation.
• If X is the set of human beings, xRy if and only if x is a friend of y defines a relation
on X.
• Consider N the set of natural numbers. We define the relation R “divide” by aRb if a
divides b.
• Consider a set A. The the inclusion of sets, ⊆, is a binary relation defined on 2A .

One can represent a relation as a graph or a table. For example : the relation R on
{a, b, c, d, e} defined by

R := {(a, a), (e, e), (a, b), (b, a), (a, e), (b, c), (d, c), (e, b), (e, d)},

can be represented as follows:

a
a b c d e
a 1 1 0 0 1
b 1 0 1 0 0
b e
c 0 0 0 0 0
d 0 0 1 0 0
e 0 1 0 1 0
c d
29
Definition 32. Given a binary relation R, we define the dual relation denoted by Rd as
follows
Rd = {(x, y) ∈ A2 | (y, x) ∈ R}
or equivalently xRd y if and only if yRx.

Definition 33. A relation R on A is said to be:

• reflexive if:
∀x ∈ A, xRx

Example:
a

• transitive if:
∀(x, y, z) ∈ A3 , (xRy) ∧ (yRz) ⇒ (xRz)

Example:
d

a b

• symmetric if:
∀(x, y) ∈ A2 , xRy ⇔ yRx.

Example:

30
 a

• antisymmetric if
∀(x, y) ∈ A2 , xRy ∧ yRx ⇒ x = y.

Example: Let X be a set, one can see ⊆ as an antisymmetric relation on 2X .

• complete if
∀(x, y) ∈ A2 , xRy ∨ yRx is true.

Example:
a

5.2 Equivalence relation

Definition 34. An equivalence relation on E is a binary relation on E which is reflexive,
symmetric, and transitive.
Example 33. Here are some standard examples of equivalence relations:
• The equality relation =E .
• The equality between subsets of E, that is, the equality =2E .
• Given a set E and a mapping u : E → R (think of a utility function), the relation R
on E defined by u(x) = u(y).
Definition 35. Let R be an equivalence relation on E and x ∈ E. The equivalence class of
x for R is the subset of E:
R(x) = {y ∈ E | xRy}

31
 If there is no ambiguity, the equivalence class of x if usually denoted by [x].
Definition 36. We say that Π ⊆ 2E is a partition of a set E if it satisfies:
(i) Two distinct elements of Π are disjoint, that is:

∀P ∈ Π, ∀Q ∈ Π, (P 6= Q) ⇒ (P ∩ Q = ∅).

(ii) Every element x of E belongs to some P ∈ Π, that is

[
P =E
P ∈Π

Remark 11. In order to prove that some Π ⊂ 2E is not a partition, one has to prove one
of the two following results:
• there exists x ∈ E such that x ∈
/ ∪P ∈Π P
• there exists P ∈ Π and Q ∈ Π such that P 6= Q and P ∩ Q 6= ∅.
Example 34. Let E = {1, 2, 3, 4, 5}. Then
• Π = {{1, 2}, {3, 4}, {5}} is a partition.
• Π = {{1, 2}, {3, 4}} is not a partition.
• Π = {{1, 2}, {3, 4, 5}, {5}} is not a partition.
Proposition 9. Let x, y ∈ E such that xRy. Then R(x) = R(y).
Proof. Let x, y ∈ E such that xRy. We show the equality by double inclusion. Let z ∈ R(x).
By definition, we have
xRz
Since R is symmetric, we know that yRx. By transitivity, we deduce that yRz and thus
z ∈ R(y). We prove similarly that if z ∈ R(y) the z ∈ R(x) and therefore the two sets are
equal.
Theorem 13. Let E be a set. The two following propositions are equivalent:
(i) Π is a partition of E.
(ii) There exists an equivalence relation R on E such that Π = {R(x), x ∈ E}.
Proof. See Exercise.
Definition 37. Let R be an equivalence relation on E. The quotient set of E by R is the
set E/R of equivalence classes1 of R, that is, the set:

E/R := {R(x), x ∈ E} ⊆ 2E .
1
It is a partition of E.

32
5.3 Order relations
Definition 38. • A preorder on E is a transitive and reflexive binary relation;
• An order on E is a reflexive, transitive and antisymmetric binary relation;
• A total (or complete) preorder on E is a reflexive, transitive and complete binary
relation (and similarly for a complete or total order).
Instead of using the general notation R, it is common to use the notation < (or similar)
for orders and preorders. x < y reads “x is larger/greater than y”, however, be careful that
x, y are not necessarily numbers, and that < is not always the natural ordering of numbers
(see examples below). We use the notation x ≻ y when x < y and y 6< x.
An order is often called “partial order” to emphasize the fact that it may be not complete.
Considering a partial order <, if neither x < y nor y < x are true, then x, y are said to be
incomparable.
Example 35. • If E is a set, ⊆ is an order relation on 2E but not a total preorder:
assume E = {1, 2} then {1} and {2} are incomparable. It is a typical example of
partial order.
• =E is the unique preorder on E which is an order relation and an equivalence relation.
• Taking E = R, the natural ordering of numbers ≤ is a total order, defined by x ≥ y if
x − y ∈ R+ .
• Given a mapping u : E → R (utility function), the relation R defined by x < y if
u(x) ≥ u(y) is a complete preorder.
• Supposing E is finite and < is a partial order, it is convenient to represent E together
with its order (denoted by (E, <)) in a diagram, called Hasse diagram, with the fol-
lowing convention: 1) the nodes are the elements of E; 2) a link exists between x and
y if x < y, putting x above y; 3) Unnecessary links (reflexive, or which can be deduced
by transitivity) are not represented.
Example: E = {a, b, c, d, e}, with < defined by the matrix

a b c d e
a 1 0 1 1 1
b 0 1 0 1 1
c 0 0 1 0 1
d 0 0 0 1 1
e 0 0 0 0 1

It is easy to check that it is a (partial) order, and its Hasse diagram is given below.
Definition 39. Let < be an order on E, and X ⊆ E a nonempty subset of E.
(i) m ∈ E is a lower bound of X for < if for every element x ∈ X, we have x < m. When
X has a lower bound, it is said to be bounded from below.

33
 a b

c d

Figure 5.1: Hasse diagram of (E, <)

(ii) M ∈ E is an upper bound of X for < if for every element x ∈ X, we have M < x.
When X has an upper bound, it is said to be bounded from above.
Definition 40. Let < be an order on E, and X ⊆ E a nonempty subset of E.
(i) m ∈ X is a minimal element of X if no x ∈ X satifies m ≻ x.
(ii) M ∈ X is a maximal element of X if no x ∈ X satifies x ≻ M.
Definition 41. Let < be an order on E, and X ⊆ E a nonempty subset of E.
(i) m ∈ X is a least element of X if for every x ∈ X we have x < m.
(ii) M ∈ X is a greatest element of X if for every x ∈ X we have M < x.
Minimal, maximal elements, as well as least and greatest elements may not exist. How-
ever, if a least element (resp., a greatest element) exists, it is unique.
Definition 42. Let < be an order on E, and X ⊆ E a nonempty subset of E.
(i) The infimum of X, denoted by inf X or X, is the greatest element of the set of lower
V

bounds of X (greatest lower bound).

(ii) The supremum of X, denoted by sup X or X, is the least element of the set of upper
W

bounds of X (least upper bound).

Even if X is bounded from below (resp., from above), the infimum (resp, the supremum)
may not exist.
Example 36. • Taking (E, <) of Fig. 5.1, we have:
– Taking X = {c, d}, e is the unique lower bound and hence the infimum, while
a is the unique upper bound, hence its supremum. Observe that c, d are both
minimal elements, and both maximal elements, and there is neither least nor
greatest element.
– Taking X = {a, b, d}, there is no upper bound (hence no supremum), but a unique
lower bound (infimum) which is d (observe that it is also the least element of X).
a, b are maximal, but there is no greatest element.

34
 • Consider N with the natural ordering. Take X to be the set of prime numbers. It
has no upper bound, no maximal element, its unique lower bound is 1, which is the
infimum and the least element.
• Consider the power set 2E with the inclusion relation. Take A, B ∈ 2E and consider
X = {A, B}. Then the supremum of X is A ∪ B and the infimum of X is A ∩ B.
The existence of infimum and supremum on (R, ≥) is a fundamental axiom of the real
numbers (and not a theorem!).
Axiom 1 (Existence of supremum and infimum). Consider E = R, the natural ordering ≥,
and X ⊆ R a nonempty subset of R.
(i) If X is bounded from below, it has an infimum.
(ii) If X is bounded from above, it has a supremum.
Note that Q does not satisfy the supremum and infimum axiom (see exercises). An
important property of supremum and infimum on (R, ≥) is the following.
Theorem 14 (Characterization of supremum and infimum). Let A ⊆ R be nonempty and
bounded from above. Then L = sup A if and only if L is an upper bound of A and

∀ǫ > 0, ∃a ∈ A, L − ǫ < a ≤ A.

Similarly, if A ⊆ R is nonempty and bounded from below, L = inf A if and only if L is a

lower bound of A and
∀ǫ > 0, ∃a ∈ A, L + ǫ > a ≥ A.
Example 37. Consider E = R and the natural ordering.
• If X = [a, b], a and b are the infimum and supremum respectively, and they are also
least and greatest elements.
• If X = ]a, b[, a, b are still infimum and supremum respectively, but there is no least and
no greatest element.

35
 Chapter
6
Cardinality

We recall that N = {0, 1, . . .} is the set of natural numbers.

6.1 Cardinality of a set

We start with a simple observation.
Proposition 10. If f : E → {1, . . . , n} and g : E → {1, . . . , p} are two bijections, then
n = p.
Proof.
(i) Suppose p ≥ n. f is a bijection, then f −1 is a bijection, therefore h1 = g ◦ f −1 :
{1, . . . , n} → {1, . . . , p} is a bijection. Hence h1 is a surjection, therefore ∀j ∈
{1, . . . , p}, ∃i ∈ {1, . . . , n} such that h1 (i) = j which implies n ≥ p. ⇒ n = p.
(ii) Suppose n ≥ p, then applying the previous reasonning to g −1 ◦ f yields the same result.

Definition 43. A set E is finite if E = ∅ or if there exists n ∈ N \ {0} and a bijection

f : E → {1, . . . , n}. Otherwise, E is said to be infinite.
By the previous Proposition, such an n is unambiguously defined. It is called the cardi-
nality of E and is denoted by |E|. We put by convention |∅| = 0. Observe that a subset of
a finite set is also finite.
The next proposition gives elementary properties of the cardinality of finite sets.
Proposition 11. Suppose E to be finite, and consider A, B subsets of E. The following
holds:
(i) |A ∪ B| = |A| + |B| − |A ∩ B|
(ii) |A \ B| = |A| − |A ∩ B|
(iii) |Ac | = |E| − |A|
(iv) |A × B| = |A| · |B|
(v) |2A | = 2|A| .

36
 So far, cardinality is not defined for infinite sets. The key point here is to proceed by
comparison.
Definition 44. Two sets A and B have the same cardinality (or same power) (or are equipo-
tent) if there is a bijection between A and B.
Remark 12. For two finite sets, the existence of a bijection between A and B implies that
|A| = |B|, hence indeed they have same cardinality in both sense.
Example 38. • Z+ , Z− have same cardinality by the bijection f : Z+ → Z− , z 7→ −z.
• The set No of odd natural numbers and the set Ne of even natural numbers have same
cardinality by f : No → Ne , n 7→ n − 1 (assuming 0 is odd).
• More curiously, No (or Ne ) and N have same cardinality by f : N → No , n 7→ 2n + 1.
Definition 45. A set A has a cardinality at least as large as a set B if there is a bijection
from B to a subset of A (equivalently, an injection from B to A).
Theorem 15. (Cantor-Schröder-Bernstein) If A has cardinality at least as large as B, and
B has cardinality at least as large as A, then A and B have the same cardinality (are
equipotent).
Definition 46. A set equipotent with N is said to be countably infinite. Sets being finite or
countably infinite are called countable, otherwise they are uncountable.
The cardinality of N (and therefore of every countably infinite set) is denoted by ℵ0 (aleph
0).
We give two elementary properties:
(i) Subsets of countable sets are countable.
(ii) If a set contains an uncountable subset, it is uncountable.

6.2 Generalized union and intersection

We consider a family of subsets (Ai )i∈I of X, where I is the index set.
(i) The union of the Ai ’s, denoted by i∈I Ai , is the set of all x belonging at least to one
S

Aj , j ∈ I: [
Ai = {x ∈ X | ∃i ∈ I, x ∈ Ai }.
i∈I

(ii) The intersection of the Ai ’s, denoted by i∈I Ai , is the set of all x belonging to all Aj ,
T

j ∈ I: \
Ai = {x ∈ X | ∀i ∈ I, x ∈ Ai }.
i∈I

If I is finite (resp., countable, uncountable), we speak of finite (resp., countable, arbitrary)

union or intersection.
By convention, we put ∩i∈∅ Ai = X and ∪i∈∅ Ai = ∅ (reason: i∈I∪J Ai = i∈I Ai ∩
T T

i∈J Ai ).
T

37
6.3 Advanced properties of cardinality
Property 1. Countable unions of countable sets are countable.
Property 2. Finite Cartesian products of countable sets are countable.
In particular, the set of rational numbers Q is countable. Here is a direct proof, using
the Cantor-Schröder-Bernstein theorem: write q ∈ Q as q = np in irreducible form. Then
consider the injection f : Q → N defined by
n
q= 7→ 2n + 3p
p
Since no 3p can be a multiple of 2n , this is an injection. Conversely, consider the injection
N → Q given by n 7→ n. Therefore, Q and N are equipotent.
Property 3. The set of all finite subsets of a countable set is countable.
Sketch of the proof: the argument is similar as with Q. Given a finite subset of A, it
can be coded by elements of N, say i1 , . . . , in . Then it suffices to consider the injection f
mapping {i1 , . . . , in } to 2i1 + · · · + 2in .
Theorem 16. Let I ⊆ R, and f : I → R a nondecreasing function. Then f has at most
countably many points of discontinuity.
Proof. For every x ∈ I, since f is nondecreasing:

sup{f (y) | y < x} =: f (x− ) ≤ f (x) ≤ f (x+ ) := inf{f (y) | y > x},

f is continuous at x if f (x− ) = f (x) = f (x+ ). So, if x is a point of discontinuity, there

exists qx ∈ Q s.t. f (x− ) < qx < f (x+ ) (as Q is dense in R). Furthermore, if x, y are points
of discontinuity with x < y, we have qx < qy . As Q is countable, so is the set of points of
discontinuity.

6.4 The cardinality of the continuum

G. Cantor showed that the real interval [0, 1] is not countable by the argument of the diagonal:
Suppose [0, 1] were countable. Then we could list the decimal expansion (infinite
decimal expansion without infinitely many zeroes at the end) of the real numbers
in order:

N [0, 1]
1 0.a11 a12 a13 · · ·
2 0.a21 a22 a23 · · ·
3 0.a31 a32 a33 · · ·
4 0.a41 a42 a43 · · ·
.. ..
. .

38
 We now construct a real number in [0, 1] that does not appear in the list. For
every n, choose bn 6= ann , with bn ∈ {1, . . . , 8}. Then b = 0.b1 b2 b3 · · · belongs
to [0, 1] and so must have an index in the list, say k. But this cannot be as by
construction bk 6= akk .
The same kind of argument shows that NN (all sequences of natural numbers) is uncount-
able.
The cardinality of R is equal to the cardinality of [0, 1], and is called the cardinality of
the continuum, denoted by c. The continuum hypothesis says that there is no uncountable
set with a smaller cardinality, and therefore ℵ1 = c.
Example 39. The following sets have the cardinality of the continuum:
(i) any interval of R, open or closed
(ii) Rn (and therefore C)1
(iii) the set of irrational numbers in any nontrivial interval of R
(iv) 2A when A is countably infinite, e.g., 2N . For this reason on can write c = 2ℵ0 , so that
the continuum hypothesis can be written as: ℵ1 = 2ℵ0 .
(v) NN .

1
This result needs the axiom of choice.

39