Cours preparatoire pour le BASI

Lecture notes on elementary logic

and set theory
by Jean-Marc Schlenker1

Mathematical Research Unit, University of Luxembourg

1
Translated into English by Sergei Merkulov
 Contents

Chapter 1. Elementary logic 5

Some history 5
Objectives 5
1. Statements 5
2. Operations on statements 6
3. Implication and equivalence 10
4. Proofs 11
5. Quantifiers 12
6. Exercices 13
Chapter 2. Sets 17
Some history 17
Objectives 17
1. What is a set? 17
2. Operations on sets and subsets 19
3. Relations and maps 21
4. Cardinals 22
5. Exercises 25
Bibliography 29

3
 CHAPTER 1

Elementary logic

Some history
The elements of elementary logic presented here have a long history and are known in some
form or another since Ancient Greece with some notions being formalized by Aristotle (384-322
BC) or even by his predecessors, hence the term the “Aristotelian logic”.
The mathematical logic has undergone nevertheless an important evolution, even a revolution,
in the last decades of the nineteenth century. The discovery of paradoxes in mathematics has
obliged mathematicians of that time to question the very foundations of their discipline, and put
both the logic and the set theory on a solid basis. One can mention, for example, the introduction
of quantifiers by Gottlob Frege (1848-1925) in 1879, or the work By Bertrand Russell (1872-1970)
in the early twentieth century. We refer to [1] for a historical overview of the logic and the set
theory developments at that time given in the form of comics.
Another important innovation was the discovery in 1854 by George Boole (1815-1864) of a
certain algebra which bears nowadays his name. The Boolean algebra allows us to treat logical
statements and propositions algebraically as we used to do with other mathematical objects such
as numbers or polynomials.
The elementary elements of the logic presented in this chapter are essential to both mathematics
and computer science. Beyond that, understanding in somewhat more formal way the foundations
of reasoning is essential for anyone who wants to be rigorous in any topic, scientific or not. We
refer to [2] for a more in-depth introduction.

Objectives
By the end of this chapter you will know the notions of conjunction, disjunction, negation
and the notation used to designate them. You will know how to treat predicates algebraically, for
example, how to write the negation of an assertion involving conjunctions and disjunctions.
Some definitions given in this chapter are deliberately informal with priority shifted towards
the practical usage of logical tools in future applications. Giving rigorous definitions of some even
elementary logical notions can lead to serious difficulties.

1. Statements

In this section we learn how to operate logically with statements.

Definition 1.1. A statement (or assertion, or proposition) is a sentence that may be true or
false.
5
6 1. ELEMENTARY LOGIC

Statements can be mathematical or more general. For example, consider the following math-
ematical statements:
• 3≤4
• 6≤8
• Any two lines in the plane intersect at precisely one point.
Here are examples of non-mathematical statements :
• All cats are grey.
• If it’s fine tomorrow, I’ll go for a walk.
We will use the capital letters A, B, . . . to designate mathematical statements.
One can notice that a sentence in “natural language” may be true or false, or may not have a
well-defined truth/false value. For example, the sentences:
All sheeps are black.
or
Paul is older than Jacques.
have a well-defined truth/false value (under the assumption that the variables “Paul” and
“Jacques” are well-defined). By contrast, the sentences :
It is beautiful weather today.
or
Marie sings better than Pauline.
can be regarded by some people as true and by other people as false.
Analogously, almost all mathematical statements you will encounter are true or false, but there
are exceptions. According to famous Gödel’s Incompleteness Theorem (1931), in every mathemat-
ical system (more precisely, in every formal axiomatic system containing basic arithmetic) there
exist mathematical statements which are undecidable, that is to say, the ones which can not be
proven true or false within the system. In the following chapter we will see an example of an
undecidable statement in the context of the usual set theory.

Tautologies. A tautology is an assertion that is true by its very construction. The following
statement is an example of tautology :
Two days before his death, he was still alive.

2. Operations on statements

2.1. Definitions. We have three natural operations on the statements.

Definition 2.1. • The negation of a statement A, denoted by ¬A (“not A”), is the
statement that is true if A is false, and false if A is true.
• The conjunction of two statements A and B, denoted by A ∧ B (“A and B”), is the
statement which is true if and only if A is true and B is true. We read it as “and”.
• The disjunction of two statements A and B is a statement A ∨ B which is true if and
only if A is true or B is true. We read it as “or”.
 2. OPERATIONS ON STATEMENTS 7

In the composition of the operations, the negation is given the priority over ∨ and ∧. Thus
the expression
¬A ∧ B
is equivalent to
(¬A) ∧ B
but not to
¬(A ∧ B) .
Some authors (especially in the field of informatics) assume1 similarly that the operation ∧ has
priority over the operation ∨, but it is also a common practice to use parentheses to decompose
non-ambiguously a composite statement. For example, one writes (A ∨ B) ∧ B instead A ∨ B ∧ B.
We note that ∧ corresponds nicely to the usual “and” while by contrast ∨ does not necessarily
corresponds to usual “or”. In fact, the operation ∨ is or inclusive — it is true if A and B are both
true. The usual “or” can be either inclusive or exclusive depending on the context, so if you read
in the menu of a restaurant the sentence:
Cheese or dessert
it has to be understood that one can take cheese or a dessert, but not both. It behaves as or
exclusive. This difference between “or” exclusive and “or” inclusive can also be illustrated by the
following joke (in which mathematician uses “or” inclusive as is always done in mathematics) :
A mathematician has just gave birth to a baby. She meets a friend who asks:
“Is it a girl or a boy?”.
“Yes!”, answers the mathematician.
One can use operations ∧, ∨ and ¬ to construct new statements from existing ones. For
example, if A and B are some statements, then (A ∨ B) ∧ B is a statement. The statements that
can be either true or false and can not be obtained as compositions of other statements are called
atomic statements (or assertions), or propositional variables. Propositional variables are the basic
building-blocks of propositional formulas used in logic.
2.2. Truth tables. Truth tables give us an effective way to analyze a statement composed of
several atomic statements A, B, . . .. These tables consist of rows of all possible truth values of the
statements A, B, . . . which appear in C, together with the corresponding truth values of C. These
values are obtained from the values of the propositional variables by using truth tables defined for
operations ∧, ∨ and ¬ (see Tables 1 to 3), and by using the priority rules on operations. It is a
common practice to represent the value “true” by 1 and the value ”false” by 0, and speak about
truth values.
A B A∧B
0 0 0
0 1 0
1 0 0
1 1 1
Table 1. Truth table of the conjunction ∧.

Example 2.2. The truth table of the statement (A ∨ B) ∧ B is given in Table. 4. We conclude
that this statement is equivalent to the statement B.
1This convention is justified by the fact that ∧ behaves as a multiplication and ∨ as an addition.
8 1. ELEMENTARY LOGIC

A B A∨B
0 0 0
0 1 1
1 0 1
1 1 1
Table 2. Truth table of the disjunction ∨.

A ¬A
0 1
1 0
1 1
Table 3. Truth table of the negation ¬.

A B (A ∨ B) (A ∨ B) ∧ B
0 0 0 0
0 1 1 1
1 0 1 0
1 1 1 1
Table 4

Thus we can recognize tautologies as those statements whose truth tables contain only 1, and
the contradictions as the ones whose truth tables contain only 0.
2.3. Intuitive recipes for handling assertions. Composing statements with the help of
the logical operations introduced in the previous section, we obtain a so called Boolean algebra
of propositions, described in the next section. To understand better the rules which govern this
algebra, let us first describe some of them in a natural language. —
• We can combine two and in any order. Thus the assertion
It’s nice and hot, and it’s late.
is equivalent to
It’s nice and it’s late, and it’s hot.
• In the same way one can combine two or in any order so that
My next car will be blue or red, or green
is equivalent to
My next car will be blue or green, or red.
• The order of the parts connected by “and” also plays no role so that
The university is large and beautiful
is equivalent to
The university is beautiful and large.
• Similarly for the order of the parts connected by or plays no role.
• One can ”distribute” and located in front of an assertion containing or. Hence
My favorite bike is fast, and moreover it is grey or black
is equivalent to
My favorite bike is fast and grey, or it is fast and black.
 2. OPERATIONS ON STATEMENTS 9

• The negation of an assertion consisting of two parts connected by one and can be
obtained by taking the negations of each of its parts and connecting them by or. Thus
the negation of
Albert speaks English and German
is
Albert does not speak English or German.
• The negation of an assertion consisting of two parts connected by one or can be obtained
by taking the negations of each of its parts and connecting them by and. Thus the negation
of
The winner of the tournament will be Pierre or Marie
is
The winner of the tournament will be neither Peter nor Marie (i.e. will not be
Peter and will not be Marie).
The assertions that we have just seen apply only to objects that are uniquely determined such
as “Paul”, “Pierre” or “ the University”. We can considerably extend our expression capabilities
by using quantifiers : “for everything (everyone)” or “there exists”. Thus an assertion
At night all cats are grey
applies not to a particular cat, but to all cats. Similar phenomenon happens in the expression :
Last year there was a month when it was raining every day.
This statement contains two quantifiers.
It is worth noting that the order of quantifiers is important. For example, we should not
confuse:
Every day, there is a man who is touched by lightning
with
There is a man who is touched by lightning every day.
We shall see this distinction again when we study quantifiers in more detail below.
2.4. Boolean algebra: the “calculus” of logic. The operations ∧ and ∨ satisfy certain
algebraic properties (rules) which make it possible to operate on logical “formulae”. These prop-
erties are similar to those satisfied by arithmetical operations + and × (compare respectively to ∨
and ∧) and formalize the “intuitive” rules discussed in the previous section. They can be formally
verified (which is a good exercise) with the help of the truth tables of the assertions that make
them up. For example, the first rule says that A ∧ (B ∧ C) = (A ∧ B) ∧ C meaning that the
statements A ∧ (B ∧ C) and (A ∧ B) ∧ C have the same truth tables. Here is a small list of such
properties.
• associativity of ∧ : A ∧ (B ∧ C) = (A ∧ B) ∧ C.
• associativity of ∨ : A ∨ (B ∨ C) = (A ∨ B) ∨ C.
• commutativity of ∧ : A ∧ B = B ∧ A.
• commutativity of ∨ : A ∨ B = B ∨ A.
• distributivity of ∧ with respect to ∨ : A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C).
• the true statement 1 is a neutral element for the operation ∧, and the false statement 0
is a neutral element for ∨ : for any statement A we always have
A∧1=A , A∨0=A .
• 0 annuls all statements : for any assertion A we have A ∧ 0 = 0.
Some properties have no direct analogues for + and ×, for example :
10 1. ELEMENTARY LOGIC

• distributivity of ∨ with respect to ∧ : A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).

In each case the rules can be checked directly by comparing the truth tables of both sides of
the equality for all possible values of the variables A, B, C.
We also have an operation ¬, the negation of an assertion. It satisfies important properties
related to ∧ and ∨.
• ¬(¬A) = A.
• ¬(A ∨ B) = (¬A) ∧ (¬B),
• ¬(A ∧ B) = (¬A) ∨ (¬B) (these two laws are called “De Morgan’s laws”).
• (¬A) ∧ A = 0.
• (¬A) ∨ A = 1.
Finally, we have two simple rules that simplify logical expressions,
• (A ∧ B) ∨ B = B,
• (A ∨ B) ∧ B = B.
They are called “absorption laws”.

3. Implication and equivalence

Using operators ¬, ∧ and ∨ we can introduce other useful logical operators.

Definition 3.1. One denotes by ⇒ the operator “implication” defined for any two assertions
A and B as follows
(A ⇒ B) if and only if (¬A) ∨ B .
We say that A implies B if the assertion A ⇒ B is true, i.e. if B is true whenever A is true.
One says in this case that A is the antecedent, and that B is the consequent of the implication
A ⇒ B.
Definition 3.2. The implication B ⇒ A is called reciprocal of the implication A ⇒ B.
It follows from the definition that A ⇒ B is true for all values of A and B except in the case
where A is true and B is false. This corresponds to the implication used in the common language.
For example, the sentence
If the hens had teeth, I would be pope
is true, because the antecedent (“the hens have teeth”) is false.
We also use the implication written in the opposite direction ⇐, that is B ⇐ A which is
equivalent to A ⇒ B.
We thus notice that A ⇒ B is equivalent to B ⇐ A, but not to B ⇒ A!

Definition 3.3. The implication (¬B) ⇒ (¬A) is called contrapositive of the implication
A ⇒ B.
Proposition 3.4. Any implication is equivalent to its contrapositive.
Proof. We want to show that A ⇒ B is true if and only if (¬B) ⇒ (¬A). Now A ⇒ B is
false if and only if A is true and B is false. But (¬B) ⇒ (¬A) is false if and only if (¬B) is true
and (¬A) is false, i.e. if and only if A is true and B is false. The two assertions have exactly the
same truth values, so they are equivalent. 
 4. PROOFS 11

Alternatively, one can prove the above proposition by showing that the two assertions A ⇒ B
and (¬B) ⇒ (¬A) have identical truth tables.
Definition 3.5. One denotes by ⇔ the equivalence relation : A ⇔ B if and only if A ⇐ B
and A ⇒ B.
In other words, A ⇔ B is true if and only if A and B have the same truth values: either A
and B are both true, or A and B are both false.
In some cases the following notation is also used.
Definition 3.6. The exclusive disjunction, or “or exclusive”, denoted A ⊕ B, is defined as
follows : A ⊕ B is true if and only if
• either A is true and B is false,
• or A is false and B is true.
Thus the expression
Cheese or dessert
in a restaurant menu corresponds to or exclusive.

4. Proofs

A mathematical proof is a sequence of mathematical statements, each logically following from

the previous one. In this sequence one goes from statementss accepted as being true towards a
final statement that one wishes to prove.
When writing a proof one follows a very clear rule: start with something which is known —
say, a theorem in the course or a statement from an exercise — and arrive at the conclusion along
the steps, each one following in a perfectly clear way from the previous one. If the passage from
one step to the next one is not perfectly clear, then this is not a proof!
Proof by contradiction. In some cases one uses “reduction to absurdity” (or “argument
by contradiction”): one assumes that the conclusion to be reached is false, and then deduces a
contradiction. Thus to argue (prove) by contradiction is the same as to show
(¬B) ⇒ (¬A)
in order to deduce A ⇒ B.
Example. Let us show that there exist infinity many prime numbers (a strictly positive integer
is said to be prime if it is not equal to 1 and is divisible only by 1 and by itself). It will be assumed
here that any non-prime number is divisible by a prime number.
Let us argue by contradiction and assume that there are only finitely prime numbers, and
denote them by p1 , p2 , · · · , pn . Let p be their product, p = p1 p2 · · · pn ; it is known that n ≥ 2 as 2
and 3 are prime numbers.
One notices that p + 1 is not divisible by p1 , because p1 can not divide two successive numbers.
Similarly, p + 1 is not divisible by any of the pi , 1 ≤ i ≤ n. Thus p + 1 is not divisible by any
prime number. Now any non-prime number is divisible by a prime number. Hence p + 1 is a
prime. Moreover, p + 1 is strictly greater than any of pi . This contradicts our hypothesis that
p1 , p2 , · · · , pn are all prime numbers.
We can therefore conclude that the starting assumption is false, and that there are infinitely
many prime numbers.
12 1. ELEMENTARY LOGIC

Proof by induction. This particular type of proof can be applied to statements depending
on a natural number n. Let (An ) be the n-th assertion. To prove that the statement (An ) is true
for any n, it is sufficient to show that:
• (A0 ) is true,
• for any n ≥ 0, (An ) ⇒ (An+1 ).
In some cases one can start with n = 1 instead of n = 0.
Example. Let us show by induction that for any n ∈ N>0 one has
n(n + 1)
1 + 2 + ··· + n = .
2
Let us call this assertion (An ).
One first checks that (A1 ) is true. Indeed, for n = 1 both sides of the above equality are equal
to 1.
Next consider an arbitrary n ≥ 1, assume (An ) is true, and try to show that (An+1 ) is true.
One notices that
1 + 2 + 3 + · · · + n + (n + 1) = (1 + 2 + · · · + n) + (n + 1)
n(n + 1)
= + (n + 1)
2
(n + 2)(n + 1)
=
2
(n + 1)((n + 1) + 1)
=
2
which implies (An+1 ). Hence the statement (An ) is true for any n ≥ 1.

5. Quantifiers

5.1. Definitions. One uses the following quantifiers in mathematical language.

Definition 5.1. The universal quantifier, ∀, reads “for all”. If E is a set and P is a predicate
defined on elements of E (that is, a Boolean-valued function P : E → {true, false}), then the
assertion
∀x ∈ E, P (x)
states that P (x) is true for all elements x of E.
Definition 5.2. The existential quantifier, ∃, reads “it exists”. If E is a set and P is a
predicate defined on the elements of E, then the assertion
∃x ∈ E, P (x)
states that there exists an element x of E such that P (x) is true.

Example 5.3. Let P (n) be a predicate defined on the set of integers by “n is even”. The
assertion ∃n, P (n) states that there exists an even integer. The assertion ∀n, P (n), which is false,
states that all integers are even.
We will sometimes use a modified version of ∃ which states existence of a unique element of a
set satisfying a given predicate.
 6. EXERCICES 13

Definition 5.4. The existential quantifier followed by the exclamation point, ∃!, reads “there
is a unique”. If E is a set and P a predicate defined on elements of E, then the assertion
∃!x ∈ E, P (x)
states that there exists a unique element x of E such that P (x) is true.
5.2. Negation of quantifiers. If P (x) is a predicate, then ∃x, P (x) and ∀x, P (x) are
statements. We can therefore combine these statements using the logical operations ∨, ∧ and ¬
to form more complex statements. It should be noted that the following rules should be applied
when determining the negation of a quantified statement.

Proposition 5.5. Let E be a set, and P a predicate defined on the elements of E. Then
(1) ¬(∀x ∈ E, P (x)) = ∃x ∈ E, ¬P (x).
(2) ¬(∃x ∈ E, P (x)) = ∀x ∈ E, ¬P (x).
Thus if E and F are two sets and P a predicate of two variables x ∈ E and y ∈ F , the negation
of
∀x ∈ E, ∃y ∈ F, P (x, y)
is
∃x ∈ X, ∀y ∈ F, ¬P (x, y) .
Therefore the negation of
All sheeps are black
is the statement :
There exists a sheep that is not black
and reversely.
Similarly, the negation of
All men have at least one friend
is
There is a man who has no friends.
Indeed, if E is the set of men and P (x, y) denotes “y is a friend of x” then the first statement
translates into
∀x ∈ E, ∃y ∈ E, P (x, y) ,
and its negation is therefore
∃x ∈ E, ∀y ∈ E, ¬P (x, y) .

6. Exercices

6.1. Truth values. Determine truth values of the following statements:

(1) (5 is a positive integer )
(2) (3 < 4) ∧ (9 − 2 = 6)
(3) (4 ≤ 4) ∨ (9 − 2 = 6)
(4) (4 > 5) ∨ ¬(9 − 2 = 6)
(5) (2 + 2 = 4) ⇒ (2 = 4 − 2)
(6) (5 > 3) ⊕ (2 < 4)
(7) (5 > 3) ⇔ (1 6= 0)
14 1. ELEMENTARY LOGIC

6.2. Reciprocal and contrapositive implications. Write reciprocal and contrapositive

statements to each of the following implications:
(1) If the weather is not nice, then I go to the cinema
(2) (A ∨ B) ⇒ C
(3) If x > y, then f (x) > f (y) and I am the best in math
(4) (A ∧ B) ⇒ (C ∨ D)
6.3. Truth tables. Let A, B and C be statements. Construct truth tables of the following
composite statements:
(1) (A ∧ B) ∨ (¬A ∨ C)
(2) (A ⇐ C) ⇒ B
(3) (A ⇒ B) ⇔ ¬(A ⊕ B)
(4) (A ⇒ ¬(B ∨ C)) ⇒ (B ∧ (A ⇒ ¬C))
6.4. “Or exclusive”. Recall the truth table of “or exclusive” for two statements A eand B,
or “xor” denoted by ⊕:
A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
Show that for n assertions A1 , ..., An ,
truth ⊕ A1 ⊕ A2 ⊕ ... ⊕ An = truth ⇔ card({i | Ai = truth}) is even.
Hint: One can use induction on n.
6.5. Simplification of logical expressions. Let A, B, C and D be statements. Simplify
the following logical expressions as much as possible:
(1) (C ∨ D) ∧ (A ∨ B) ∧ ¬C ∧ ¬D
(2) ((A ∧ ¬B) ∧ (B ∧ C))(∨(A ∧ B) ∨ (¬B ∧ C))
(3) B ∨ ¬(¬A ∨ ¬C) ∨ ¬(C ∧ B) ∨ ¬(A ∨ ¬C)
Check the results using truth tables.
√
6.6. Proof by contradiction. Show that 2 is irrational.
6.7. Proof by induction.
(1) Prove the following formulas (where n is an integer greater than or equal to 1):
n n
X n(n + 1)(2n + 1) X n2 (n + 1)2
i2 = , i3 = .
i=1
6 i=1
4
(2) Show that for any non-negative integer n the number 23n − 1 is divisible by 7.
6.8. Generalization of De Morgan’s laws. Let A1 , ..., An be some statements. Prove the
following two statements for all n ≥ 2:
n
! n
^ _
(1) ¬ Ai = ¬Ai , that is to say ¬(A1 ∧ A2 ∧ ... ∧ An ) = ¬A1 ∨ ¬A2 ∨ ... ∨ ¬An
i=1 ! i=1
_n ^n
(2) ¬ Ai = ¬Ai , that is to say ¬(A1 ∨ A2 ∨ ... ∨ An ) = ¬A1 ∧ ¬A2 ∧ ... ∧ ¬An
i=1 i=1
 6. EXERCICES 15

6.9. Construction of logical expressions. Let A, B and C be some statements. Find a

logical expression e whose truth table is given by:

A B C e(A, B, C)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

6.10. *Connectors.
(1) Prove that it is impossible to express all the logical operations as compositions of the
operations ∨ and ⇒.
(2) One denotes by ↑ and ↓ the operations whose truthe tables are given by
A B A↑B A↓B
0 0 1 1
0 1 1 0
1 0 1 0
1 1 0 0
(a) Show that it is possible to express the set of operations on logical statements using
only the operation ↑.
(b) Show that it is possible to express the set of operations on logical statements using
only the operation ↓.
 CHAPTER 2

Sets

Some history
The notion of set in mathematics is ancient. However the modern theory of sets was born
in the 1870s under the impetus of mathematicians like Georg Cantor (1845-1918) and Richard
Dedekind (1831-1916). The discoveries of paradoxes such as Russell’s one (presented below) led in
the beginning of the 20th century to a formalization of the theory of sets and a discovery of different
axiomatic formulations, including that of Zermelo-Frankel which is the most widely used nowadays.
The introduction by Cantor of the Theory of Cardinals for infinite sets has been considered as a
genuine revolution in the late nineteenth century.
The theory of sets has undergone considerable progress during the 20th century. We can
mention for example the Incompleteness Theorem by Kurt Gödel (1906-1978) or the proof in 1963
of the Continuum hypothesis (see below) by Paul Cohen (1934-2007).

Objectives
Our presentation is deliberately chosen to be simple and naive. The objectives are to learn
• and understand how to use the main notation of theory of sets (intersection, union, etc.),
• how to use the quantifiers ∀ and ∃,
• how to work with expressions using quantifiers, for example, write the negation of a
quantified proposition,
• and understand how to work with the notions of relation, map, injectivity, surjectivity
and bijectivity.

1. What is a set?
1.1. A (non-)definition. One might be tempted to define a set as any collection of elements
without any further deliberation. This is what mathematicians used to do for a long time. One
might thus speak about the set of all the positive integers N, about the set of subsets of the set of
positive integers, or about the set of all sets containing N.
Unfortunately this naive approach leads to paradoxes and is not mathematically useful. It is
therefore really important to proceed with caution.

1.2. Russell’s paradox. Russell’s paradox, attributed to Bertand Russell (1872-1970), can
be formulated as follows. Let E be the set of all sets that do not contain themselves as elements,
that is, the set of all sets F such that F is not an element of F . Consider next the following
assertion A :
E is an element of E.
Then:
17
18 2. SETS

• E is not an element of E as otherwise E would be an element of E and hence would

contradict its very definition. Therefore, A is false.
• But then, again by the very definition, E is an element of E. Therefore A is true.
We have thus defined an assertion A which is both true and false. This leads us to a very
serious problem because one can then prove that any assertion B is both true and false. Indeed,
since A is false, the assertion A ⇒ B is true, but since A is true, we can deduce that B is true
(similarly one deduces that ¬B is true, i.e. B is false).
1.3. Some important sets. In order to avoid problems originating in Russell’s paradox we
will consider only sets defined according to certain fixed rules free of paradoxes1. Thus we will
consider only certain “well-known” sets such as the ones defined by enumerating their elements,
the ones obtained from the latters by applying certain operators (in particular taking the set of
their subsets), and finally the sets obtained from another set by selecting some of its elements by
a predicate. The elements of a set are pairwise distinct and are not necessarily ordered.
1.4. Some important sets in mathematics. We assume existence and main properties of
the following sets
• N, the set of natural numbers (non-negative integers) 0, 1, 2, · · · .
• Z, the set of all integers · · · , −2, −2, 0, 1, 2, · · · .
• Q, the set of rational numbers, i.e. the ones of the form pq where p and q are integers with
q not equal to zero.
• R, the set of real numbers.
1.5. Defining a set via enumeration. A set can be defined via the complete listing (enu-
meration) of its elements. These are sets of the form
E = {A, B, . . . , Z} ,
where A, B, . . . , Z are its elements.
A particular notation is used for the empty set, that is, the set that has no elements; it is
denoted ∅. Since the elements of a set are pairwise distinct we have {1, 1, 2} = {1, 2} for example.
1.6. Membership and inclusion. The following two symbols are used very often, and it is
worth memorizing their different meanings.
Definition 1.1 (membership). If E is a set, we write x ∈ E if x is an element of E.
Definition 1.2 (inclusion). A set F is a subset of a set E, denoted by F ⊂ E, if every element
of F is also an element of E.2
For example, one has
A ∈ {A, B, C} ,
and
{A} ⊂ {A, B, C} .
We can then define a subset of a given set.
Definition 1.3. A subset of a set E is a set F whose every element is an element of E. One
then writes F ⊂ E.
1Or at least we think so. In fact it is essentially impossible to prove that the obtained system contains no
contradiction ...
2In English literature one often uses the notation F ⊆ E.
 2. OPERATIONS ON SETS AND SUBSETS 19

Example 1.4. N ⊂ Z ⊂ Q ⊂ R : any natural number is an integer, any integer is a rational

number, any rational number is a real number.
1.7. The set of subsets of a set. One can build from a given set E a new set which is
“bigger” than E.
Definition 1.5. Given a set E, we denote by P(E) the set of subsets of E. It is called the
power set of E.
For example, P(∅) = {∅} is a set with one element while P(P(∅)) = {∅, {∅}} is a set with two
elements.
1.8. Predicates. A predicate is an assertion P (x) which specifies a property of an element
x of a given set (in the case of a unary predicate), or of an n-plet of elements (that is, an ordered
sequence of n elements) of this set (in the case of a n-ary predicate with n ≥ 2). In the predicate
P (x) we treat x as a variable taking values in arbitrary elements of the given set, and P (x) as
the truth value of the predicate at x. Thus a unary predicate on a set E is nothing but a map
(function) from E to the set of truth values {0, 1} (recall that 0 means “false ” and 1 means “true”).

Example 1.6. The predicate P (n) defined on the set of natural numbers by “n is even” takes
the following values upon evaluation on n : P (0) = 1, P (1) = 0, P (2) = 1, P (3) = 0, etc.
The binary predicate R(a, b) defined on the set of real number by “a is smaller than b” is true
for a = 0 and b = 1 and false for a = 4 and b = 2. Of course, one would prefer to write the
predicate R(a, b) simply as a < b.
1.9. Defining a set via predicates. Given a predicate P on a set E, one can define a new
set whose elements are precisely those elements of E on which P takes value 1 (“truth”). It is
denoted by
{x ∈ E | P (x)} .
Example 1.7. Consider again the predicate P “is even” from the previous example. The set
{n ∈ N | P (n)}
is the set of even natural numbers, and the set
{n ∈ N | ¬P (n)}
is the set of odd natural numbers.

2. Operations on sets and subsets

2.1. Union, intersection, complement. The following operations are often used on sets
and their subsets.
Definition 2.1. The union of two sets A and B, denoted by A ∪ B, is a set whose elements
are either elements of A or elements of B.
Definition 2.2. The intersection of two sets A and B, denoted by A ∩ B, is a set whose
elements are those elements of A which also belong to B.
20 2. SETS

Definition 2.3. Let E be a set and A a subset of E. The complement of A in E, denoted by

ĀE , is the subset of those elements of E which are not elements of A.
Example 2.4. Consider for example the set P of even numbers and the set I of odd numbers.
One has P ⊂ N and I ⊂ N. On the other hand, P ∩ I = ∅ and P ∪ I = N. In fact P̄ N = I.

When considering the complement of a subset, there is often no ambiguity about the set of
which it is a subset. We write in this case simply Ā instead of ĀE .
It is worth noting that ∪, ∩ and ¯ are analogous to respectively operators ∨, ∧ and ¬ for the
logical statements. Therefore the algebraic operations below are analogous to the rules of the
Boolean algebra of the first chapter.

2.2. Algebraic operations on subsets. The operations ∪, ∩ satisfy certain algebraic prop-
erties similar to those satisfied by ∨ and respectively ∧ (which are comparable respectively to ∪
and ∩)
• associativity of ∩ : A ∩ (B ∩ C) = (A ∩ B) ∩ C.
• associativity of ∪ : A ∪ (B ∪ C) = (A ∪ B) ∪ C.
• commutativity of ∩ : A ∩ B = B ∩ A.
• commutativity of ∪ : A ∪ B = B ∪ A.
• distributivity of ∩ with respect to ∪ : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Other properties have no direct analogue for + and ×, for example :
• distributivity of ∪ with respect to ∩ : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
The equalities can be checked in each case directly by showing that both sides contain the same
elements.
We have also seen the operation ¯of taking the compliment, an analogue of the negation of a
statement. It satisfies the following important properties with respect to the operations ∩ and ∪:
• Ā¯ = A.
• A ∪ B = Ā ∩ B̄.
• A ∩ B = Ā ∪ B̄.
• ĀE ∩ A = ∅.
• ĀE ∪ A = E.
Definition 2.5. The difference of two sets, denoted by \ , is defined as follows : E \ F is the
set of elements of E which are not elements of F .
2.3. Product of sets. There exists an operation of product of two sets often called the
“Cartesian product”.
Definition 2.6. Let E and F be sets. The (Cartesian) product of E and F , denoted E × F ,
is the set of all ordered pairs (x, y), where x is an element of E and y is an element of F .
Note that a pair of objects x and y, denoted by (x, y), is a sequence of two objects. It assumes
the order of the two elements. We distinguish the ordered pair (x, y) from the unordered one
{x, y}, i.e. the one in which we do not assume any ordering of the elements x and y.
One can easily generalize this notion to product of more than two sets. Thus if E, F and G are
three sets, the (Cartesian) product E × F × G is the set of the triplets (x, y, z) with x ∈ E, y ∈ F
and z ∈ G.
 3. RELATIONS AND MAPS 21

Definition 2.7. Given a set E and a natural number n ∈ N, one denotes

En = E × E × · · · × E
(with n factors) the set of n-plets of elements of E.

3. Relations and maps

3.1. Relations. We start with the notion of a relation between two sets and then proceed
with its special case corresponding to maps.
Definition 3.1. A relation between two sets E and F is a subset R of E × F .
Given a relation R ⊂ E × F between E and F , we say that x ∈ E is related to y ∈ E, or x
and y are in the relation, if (x, y) ∈ R.
One employs the notions of domain and image of a relation.
Definition 3.2. Let R ⊂ E × F be a relation. The domain of R is
D(R) = {x ∈ E | ∃y ∈ F, (x, y) ∈ R} .
and the image of R is
Im(R) = {y ∈ F | ∃x ∈ E, (x, y) ∈ R} .
Thus the domain of R is the set of elements of E that are in the relation with at least one
element of F , and the image of R is the set elements of F that are related to at least one element
of E.

3.2. Maps.
Definition 3.3. Let E and F be sets. A map from E to F is a relation f ⊂ E × F such that
any x ∈ E is related to precisely one element of F denoted by f (x). One writes f : E → F for a
map from E to F .
Example 3.4. Let E be a set. One calls the identity map of E, denoted idE , a map from E
to E such that x ∈ E is related to itself, x.
The following notions are used often.
Definition 3.5. Let f : E → F be a map. The image of f is the image of f as of a relation,
that is,
Im(f ) = {y ∈ F | ∃x ∈ E, f (x) = y} .
For any y ∈ F one calls x a pre-image of y under f if f (x) = y, and one denotes by f −1 ({y}) the
set of all pre-images of y under f .
The following vocabulary is used very often so it is good to memorize it.
Definition 3.6. A map f : E → F is :
• injective, if every element of F has at most one pre-image under f ,
• surjective, if every element of F has at least one pre-image under f ,
• bijective, if it is injective and surjective.
22 2. SETS

Thus a map f : E → F is injective if and only if

∀x, x0 ∈ E, x 6= x0 ⇒ f (x) 6= f (x0 ) ,
and surjective if and only if Im(f ) = F . It is bijective if and only if any element of the target set
has precisely one pre-image.
Definition 3.7. Let f : E → F be a bijective map. One denotes by f −1 : F → E a map
which relates to any element of F its unique pre-image in E. One calls f −1 the map inverse to f .
It is also possible to compose maps as explained below.
Definition 3.8. Let E, F, G be three sets, and let f : E → F and g : F → G be two maps. We
call their composition the map g ◦ f : E → G such that every x ∈ E gets related to g(f (x)) ∈ G.
Note the order of the functions in g ◦ f : we put on the first place the map which is applied
last.
For example, we note that if f : E → F is a bijection, then f ◦ f −1 = idF and f −1 ◦ f = idE .
The composition law satisfies the following associativity property.
Proposition 3.9. Let f : E → F , g : F → G and h : G → H be three maps. Then
(h ◦ g) ◦ f = h ◦ (g ◦ f ).
Proof. We leave the proof as an exercise. 

The proof of the following proposition is also left as an exercise.

Proposition 3.10. The composition of two injective maps is injective. The composition of
two surjective maps is surjective.

4. Cardinals

4.1. Cardinalities of finite sets. A set is called finite if it has a finite number of elements,
i.e. if there exists a bijection between this set and a set of the form
{1, 2, · · · , n}
for some n ∈ N.
Definition 4.1. The cardinality (or the cardinal) of a finite set is the number of its elements.
Let E be a finite set, its cardinal(ity) is denoted by |E| or #E.
If E and F are two finite sets, then :
• if there exists an injective map from E to F , then #E ≤ #F ,
• if there exists a surjective map from E to F , then #E ≥ #F ,
• if there exists a bijective map from E to F , then #E = #F .
We have the following rule of addition.
Proposition 4.2. Let E and F be finite sets. Then
|E ∪ F | + |E ∩ F | = |E| + |F | .
 4. CARDINALS 23

Proof. One can decompose E ∪ F into the union of three disjoint sets :
E ∪ F = (E ∩ F ) ∪ (E \ F ) ∪ (F \ E) .
Hence,
|E ∪ F | = |E ∩ F | + |E \ F | + |F \ E| .
However one also has a disjoint union decomposition
E = (E ∩ F ) ∪ (E \ F ) ,
implying the equality
|E| = |E ∩ F | + |E \ F | ,
as well as a similar disjoint union decomposition
F = (E ∩ F ) ∪ (F \ E) ,
implying in turn
|F | = |E ∩ F | + |F \ E| ,
By adding the last two equations for cardinalities and subtracting the first one, one obtains the
required result. 
Proposition 4.3. Let E and F be finite sets. Then |E × F | = |E| × |F |.
Proof. Proof is left as an exercise. 
Given a finite set E, the cardinality of the set of its subsets can be given as a simple function
of the cardinality of E.
Proposition 4.4. If E is a finite set, then #P(E) = 2#E .
Proof. Denote n = #E and let e1 , · · · , en be the elements of E. Consider next a map
φ : {0, 1}n → P(E) which relates n-plet (1 , · · · , n ) ∈ {0, 1}n to the subset φ(1 , · · · , n ) ⊂ E
which contains ei if and only if i = 1.
One can check that this map φ is injective and surjective, hence bijective. Therefore one
concludes that |P(E)| = |{0, 1}|n = 2n . 
One notices in particular that |P(E)| > |E| for any finite set E.
4.2. * Infinite cardinalities *. One of the greatest discoveries of the 19th century was the
realization by Georg Cantor (1845-1918) that there are exist different types of infinities: some
infinite sets are “bigger” than others.
We state the following result without proof (though its proof is not that particular difficult).
Theorem 4.5 (Without proof). Let E and F be two (possibly infinite) sets. If there exists an
injective map from E to F and an injective map from F to E, then there exists a bijective map
from E to F .
This result allows us to make the following definitions.
Definition 4.6. Given two sets E and F , we say that
• E has smaller cardinality (or cardinal) than F , if there exists an injective map from E
to F ,
• E has greater cardinality (or cardinal) than F , if there exists a surjective map from E to
F,
24 2. SETS

• E and F have the same cardinality (or cardinal), if there exists a bijective map from E
to F .
We can easily check that this notion of cardinality (or cardinal) for the infinite sets satisfies
the main desirable properties, for example if E has smaller cardinality than F and F has a smaller
cardinality that G, then E has smaller cardinality than G.
Definition 4.7. A set E is called countable if E has the same cardinality as N, i.e. if there
exists a bijection between N and E.

(0,1)

0,0) (1,0)

Figure 1. N × N is countable

Some examples :
• Z is countable because one can enumerate its elements, for example as follows :
0, 1, −1, 2, −2, 3, −3, · · · .
• N2 is countable because one can enumerate its elements as explained in Figure 1. In a
similar manner one shows that Nn is countable for any n ≥ 1.
• as a consequence Z2 is countable, and the same is true for Zn for any n ≥ 1.
• It follows that Q is countable; indeed there is a surjective map from the countable subset
of Z2 consisting of pairs (p, q) with q 6= 0 to Q which relates (p, q) to p/q.
More generally,
• The union of two countable sets is countable : given E = {e1 , e2 , · · · } and F =
{f1 , f2 , · · · }, then E ∪ F = {e1 , f1 , e2 , f2 , · · · }.
 5. EXERCISES 25

• The union of any number of countable sets is countable : if E1 , E2 , · · · , En , · · · are count-

able sets, then their union
∪n∈N Ei
is again countable.
• If E and F are countable, then E × F is countable.

The following theorem claims existence of a large number of distinct infinite cardinalities.
Theorem 4.8. Let E be a set, then the cardinality of #P(E) is strictly larger than that of E,
that is to say, it is larger and not equal to the cardinality of E.
Idea of the proof. The proof is based on Cantor’s diagonal argument. Let φ : E → P(E)
be any map, it is suffices to prove that it can not be surjective. For this, let us define a subset
F ⊂ E as follows: for any e ∈ E, e ∈ F if and only if e 6∈ φ(e). Then we note that for all
e ∈ E, F 6= φ(e), which shows that φ is not surjective. 

For example, the set of subsets of N is not countable.

Proposition 4.9. The set [0, 1] has the same cardinality as P(N).
Sketch of the proof. One can associate to any subset E ⊂ N a real number R(E) which
is defined by its writing in base 2 as follows : R(E) = 0, r1 r2 · · · with ri ∈ {0, 1} and ri = 1 if and
only if i ∈ E. One notices that this map is surjective. It is not injective, because some numbers
can have two different representations in base 2, for example :
0.01 = 0.0100000000 · · · = 0.0011111111111 · · ·
However those numbers that have two pre-images under r form a countable set. 

One can conclude that |R| = |P(N)|.

This leads naturally to the following question posed in 1878 by Cantor.
Question 4.10 (The Continuity Hypothesis). Is it true that |R| is the smallest cardinal which
is strictly larger than |N|, i.e. every infinite set that is not countable has the cardinal greater or
equal to that of R?
The answer was given only in 1963 by Paul Cohen : this statement is undecidable in the
framework of the usual theory sets, that is, it can be neither proved to be true nor proved to be
false.

5. Exercises
5.1. ∆ Truth values. Which of the following statements are true?
(1) ∅ ∈ {∅, {∅}}.
(2) ∅ ⊂ {∅, {∅}}.
(3) 4 ∈ {{4}}.
(4) ∀x ∈ Z : (x 6= x2 ).
(5) (x ∈ A ∧ ¬(x ∈ B)) √ ⇒ x ∈ A ∩ B.
(6) ∀x ∈ N : ∃y ∈ N : x − y = x.
26 2. SETS

5.2. ∆ Definition of a set.

(1) Define via enumeration the set of even numbers between 3 and 9.
(2) Define via enumeration the set {x ∈ N \ {0} | ∃k ∈ Z : x = 2k}.
(3) Define the following set via a predicate: {2, 4, 8, 16, 32, 64, 128, ...}.
(4) Define the following set via a predicate: {−2, −1, 0, 1, 2}.
5.3. Predicates.
(1) Formulate the following assertions using variables, logical connectors and quantifiers:
(a) Nobody is perfect.
(b) The absent party is not always to blame.
(c) All integers are real numbers.
(2) Write negations to the following statements:
(a) ∀x, p(x) ⇒ q(x).
(b) ∃x, p(x) ∧ q(x).
(c) ∃x, ∀y : p(x, y) ⇒ q(x, y) ∨ r(x, y).
(d) ∀x > 0∃y((y > 0 ∨ y = 1) ⇒ x + x < y).
(e) ∃x∀y(x + x = y ⇒ ∀z(z + y = x)) ⇒ ∃z∀y(z ≤ y).
(3) * Define the quantifier ∃! in terms of other quantifiers and logical operations.
(4) Using only the symbol =, quantifiers and logic operations, write an assertion stating that :
(a) a set has at least three elements,
(b) a set has strictly less than three elements,
(c) a set has precisely three elements.
5.4. Equality, inclusion, operations, cardinality.
(1) Consider the following sets:
A = {1, 2, 5}, B = {{1, 2}, 5}, C = {{1, 2, 5}}, D = {∅, 1, 2, 5},
E = {5, 1, 2}, F = {{1, 2}, {5}}, G = {{1, 2}, {5}, 5}, H = {5, {1}, {2}}.
(a) Which sets are related by equality and which by inclusion?
(b) Compute the cardinality of each of these sets.
(c) Determine A ∩ B, G ∪ H and E \ G.
(2) Consider next the following four subsets of N:
I = {1, 2, 3, 4, 5, 6, 7}, J = {1, 3, 5, 7}, K = {2, 4, 6}.
¯
(a) Determine J and K̄ I .
I

(b) A symmetric difference of two sets A and B, denoted by A∆B, is the set of elements
that are either in A or in B, but not in A ∩ B. Determine I∆J and J∆K.
5.5. Sets of subsets. Find elements of:
(1) P({0, 1, 2}).
(2) P(P(P(∅))).
(3) P(P({1, 2})).
5.6. Relations.
(1) Let E = F = R and R = {(x, y) ∈ E × F | x2 + y 2 ≤ 1}. Determine the domain of R.
(2) Let f be a map from N to Z defined by f (n) = n3 and g a map from Z to N defined by
g(n) = n2 . Calculate the image of 2 under f and determine f ◦ g.
(3) Let f be a map from E = {1, 2, 3, 4} to F = {0, 1, 3, 5, 7, 10} such that f (1) = 3, f (2) =
5, f (3) = 5 and f (4) = 0. Determine f −1 ({5}), f −1 ({0, 1, 3}) and f −1 ({1, 10}). Is f
injective, surjective, bijective?
 5. EXERCISES 27

(4) Give an example of a map from N to N which is

(a) bijective (but different from idN ).
(b) injective but not surjective.
(c) surjective but not injective.
(5) * Consider a function

|x + 1| si x < 0
f : R → R : x 7→
|x − 1| si x ≥ 0.
(a) Is the function f a bijection?
(b) Determine the restriction g of f such that g becomes invertible.
(c) Find the inverse of g.
(6) Let E be a non-empty set and A and B its subsets.
(a) One defines
f : 2E → 2E : X 7→ (A ∩ X) ∪ (B ∩ X̄).
Analyze and solve the equation f (X) = ∅. Deduce a necessary condition for f to be
bijective.
(b) Consider the case B = Ā in the previous definition. Prove that in this case f ◦ f = id
and conclude that f is bijective.
5.7. * Proofs. Let A, B, C and D be four subsets.
(1) Show that if A ⊂ B and C ⊂ D then A ∩ C ⊂ B ∩ D and A ∪ C ⊂ B ∪ D.
(2) Show that A ⊂ B ∩ C if and only if A ⊂ B and A ⊂ C.
(3) Show that (A \ B) \ C = A \ (B ∪ C).
(4) Show that the composition of two injective maps is itself injective.
(5) Show that if f is a bijective map from E to F and g is a bijective map from F to G then
(g ◦ f )−1 = f −1 ◦ g −1 .
5.8. Increasing maps.
(1) Let I ⊂ R and J ⊂ R be two intervals in R. Let f : I −→ J be a strictly increasing
function.
(a) Show that f is injective.
Hint: Argue by contradiction and use the fact that x1 6= x2 is equivalent to x1 < x2
or x2 < x1 .
(b) Determine the set K such that f : I −→ K is bijective.
Maps from N to N. Consider a map u : N → N and assume that
∀k ∈ N, u(k + 1) > u(k) .
(1) Show rigorously (justifying each step of your argument) that for any k, l ∈ N with k < l,
one has u(k) < u(l).
(2) Is u necessarily injective? Justify your answer by a precise argument or by a counter-
example.
(3) Is u necessarily surjective? Justify your answer by a precise argument or by a counter-
example.
 Bibliography

[1] Apostolos Doxiadis and Christos H. Papadimitriou. Logicomix. Bloomsbury Press, New York, 2009. An epic
search for truth, Character design and drawings by Alecos Papadatos, color by Annie Di Donna.
[2] Alfred Tarski. Introduction to logic and to the methodology of deductive sciences. Dover Publications, Inc., New
York, 1995. Translated from the 1936 Polish original by Olaf Helmer, Reprint of the 1946 translation.

29