Part I

Logic elements and set theory

In mathematics, a fundamental activity is to establish theorems. Establishing
theorems is to make a mathematical statement and provide a proof that this
statement is true. The proof that this statement is correct is the demonstration
that it can be obtained by using some rules called rules of logical reasoning and
this by starting from other statements assumed to be true at the outset.

1 Logic elements
A proposition (or an assertion) P is the content of a declarative sentence. It is
either true or false, but cannot be both true and false at the same time. We
attribute to P the value 1 when P is true and the value 0 when it is false.

Example 1

1. The integer 4 is even.

2. Cairo is the capital of Egypt.
3. 5 2 = 11:
4. x + 2 = 2x:
5. How far is Algiers to Tripoli ?
6. Let us go to Annaba !

The …rst three sentences are propositions but the last three ones are not.

1.1 Logic connectors (Operators)

They are tools which can be used to create from given propositions new propo-
sitions whose truth values depend on the truth values of the old ones. There
are …ve logical connectors: not, and, or, if then, if and only if. Let P and Q be
two propositions:

1. The negation of the proposition P is the proposition denoted P (it reads

non P ) which is true when P is false and false when P is true. Its truth
table is
P P
1 0
0 1

1
 Example 2
P x odd x2Q x 0
P x even x2
=Q x>0

2. The conjunction of the propositions P and Q; is the proposition denoted

P ^ Q (it reads P and Q) which is true when both P , Q are true, and false
in all other cases. Its truth table is
P Q P ^Q
1 1 1
1 0 0
0 1 0
0 0 0

Example 3
P Q P ^Q
x 0 x 0 x=0
n odd n 3 n 2 f1; 3g

3. The disjunction of the propositions P and Q, is the proposition denoted

P _ Q (it reads P or Q) which is true if at least one of the two statements
P , Q is true, and false when both statements are false. Its truth table is

P Q P _Q
1 1 1
1 0 1
0 1 1
0 0 0

Remark 4 If we want to express an exclusive disjunction "either P or

Q" (i.e. one or the other, not both at the same time), we can use the
proposition: (P ^ Q) _ (P ^ Q).

4. The conditional connective (implication) of the propositions P and Q de-

noted by P ) Q; is the proposition which is false when P is true and Q is
false, and true in all other cases, (it reads P implies Q, if P then Q, P is
a su¢ cient condition for Q or Q is a necessary condition of P ), its truth
table is
P Q P )Q
1 1 1
1 0 0
0 1 1
0 0 1

In this statement, P is called the antecedent and Q is called the conse-

quent.

2
 5. The biconditional (equivalence) from P to Q, denoted P , Q, is de…ned
to be the proposition (P ) Q) ^ (Q ) P ); its truth table is

P Q P () Q
1 1 1
1 0 0
0 1 0
0 0 1

The proposition P , Q reads "P and Q are equivalent", "P is equivalent

to Q", "P if and only if Q" , or "P is a necessary and su¢ cient condition
for Q".

A tautology is a compound statement that is always true independently

of its components.
An antilogy is a compound statement which is always false independently
of its components.

Example 5 Let P and Q be two propositions. It is enough to dress the truth

table to show that:

1. The propositions P _ P and P ^ (P ) Q) =) Q are tautologies.

2. The propositions P ^ P and P () P are antilogies.

Let P; Q and R be three propositions. It is enough to dress the truth table

to get the following:

1. P () P:
2. P ^ Q () Q ^ P:
3. P _ Q () Q _ P:
4. P ^ (Q ^ R) () (P ^ Q) ^ R:

5. P _ (Q _ R) () (P _ Q) _ R:
6. P ^ (Q _ R) () (P ^ Q) _ (P ^ R):
7. P _ (Q ^ R) () (P _ Q) ^ (P _ R):
8. (P ) Q) () (P _ Q):
9. (P ) Q) () (Q ) P ):
10. (P ) Q) () (P ^ Q):
11. (P ^ Q) () (P _ Q):

3
 12. (P _ Q) () (P ^ Q):

We have also
(P ) Q) ^ (Q ) R) ) (Q ) R).
(P () Q) ^ (Q () R) ) (Q () R).

An axiom is a mathematical statement supposed true (that we have not

proof).
A de…nition is a statement which de…nes a mathematical object.
A theorem is a mathematical statement that we can prove by using another
true assertions and the logical connectors.
A corollary is a theorem that we can deduce from another theorem.
A predicate is a mathematical statement written by using variables x; y; z; :::
which for every …xed values for the variables we get a proposition (then it
will be true or false).

2 Some notions of set theory

2.1 De…nitions
A set is any collection of objects, these objects are called elements of the set.
The elements in a set can be …xed by a condition, or by a common characteristic,
or by enumeration. A set is denoted by a capital letter: A; B; C; D; E:::etc, and
the elements in a set are designated by lower-case letters: x; y; z; :::etc:
The notion of membership is a relation between objects and sets, where we
write x 2 S if x is an element of a set S and we say x belongs to the set S: We
write x 2 = S if x is not an element of S and we say x does not belong to S. In a
set the order of listing a set is not important.
There are two ways to de…ne a set: the …rst one is called by extension, it
concerns …nite sets, it consists to write between brackets all the elements, such as
f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g, fNouakchott, Rabat, Algiers, Tunis, Tripolig,fa; b; c; d; :::; zg :
The second one is said by comprehension. Let P (x) be a predicate. The
set of elements verifying P (x) is denoted fx j P (x)g : (We 8 read it: the9set of x
< =
such that P (x)). Note that for any set S we can write S = x j x | {z }; which
2 S
:
P (x)
means that every set can be de…ned by comprehension.

Example 6

1. The set of alphabet of the arabic language.

2. The set of natural integers N, the set of relative integers Z, the set of
rational numbers Q.

4
 3. The set of points in the plane belonging to the circle of center O and radius
1.
4. The set of all functions de…ned on R and with positive values.
5. The set of students of Algiers university.

2.2 Quanti…ers
Let S be a set, x a variable and P (x) a predicate whose statement depends on
the elements x of S.

1. "For any x element of S; P (x)" is denoted

8x 2 S; P (x)

which is true if P (x) is true for any element x of S. The symbol 8 reads
"for all" and is called the universal quanti…er.
2. "There exists an element x of S; P (x)" is denoted

9x 2 S; P (x)

which is true if P (x) is true for at least one element x of S. The symbol
9 reads "it exists" and is called the existential quanti…er. When we want
to specify that x is unique such that P (x) true we write

9 ! x 2 S; P (x):

Example 7

1. The square of a real number is positive is expressed as: 8x 2 R; x2 0:

2. The equation tan x = x possesses a solution in the interval is expressed
as: 9x0 2 2 ; 2 : tan x0 = x0 :

The negation of 8x 2 S; P (x) is 9x 2 S; P (x).

The negation of 9x 2 S; P (x) is 8x 2 S; P (x):
The negation of 8x 2 S; P (x) ) Q(x) is 9x 2 S; P (x)^ Q(x).
To show that the implication 8x 2 S; P (x) ) Q(x) is not true, it is
su¢ cient to …nd an element x of S such that (P (x) ^ Q(x)) is true.
If P (x) is false for all x 2 S, we write 8x 2 S; P (x):

5
 Let P be the statement

(8x 2 Q) x2 + x + 1 0
and Q the statement

(9x 2 Q) x2 + x + 1 < 0
2
Note that x2 + x +1 = x + 21 + 34 0; 8x 2 Q therefore P is true, and Q is
false. Consider the following proposition R:

(8x 2 Q) (9y 2 Q) (x + y = 0)
The proposition R is true. In fact, for x0 2 Q, x0 + y = 0 , y = x0 therefore
9y0 2 Q such that : x0 + y0 = 0: Now let us consider the proposition S:

(9y 2 Q) (8x 2 Q) (x + y = 0)
Assume that S is true. Let yb in Q verifying S, then S is true 8x 2 Q, it
must be true for x = 1, and x = 2 i.e.
8
< 1 + yb = 0
and
:
2 + yb = 0
8
< yb = 1
and
:
yb = 2
This is absurd. So S is false. We conclude that the order of the quanti…ers is an
essential part of a proposition, and changing the order can completely change
the proposition.

When S and T are two sets, x; y variables and P (x; y) a predicate de-
pending on x; y then: (9x 2 S; 8y 2 T; P (x; y)) =) (8y 2 T; 9x 2 S;
P (x; y)) (it is enough to take the previous example to see that the converse
is true) But the converse is not true and we have 8x 2 S; 9y 2 T; P (x; y)
is 9x 2 S; 8y 2 T; P (x; y) and 9x 2 S; 8y 2 T; P (x; y) is 8x 2 S; 9y 2 T;
P (x; y):

The statements (8x 2 S; P (x)) and (8y 2 S; P (y)) are equivalent and the
assertions (9x 2 S; P (x)) and (9y 2 S; P (y)) are also equivalent. We say
that x and y are mute.
8x 2 S; 8 y 2 T; P (x; y) and 8 y 2 T; 8x 2 S; P (x; y) are the equivalent.

9x 2 S; 9 y 2 T; P (x; y) and 9y 2 T; 9x 2 S; P (x; y) are equivalent.

In the statement 8x 2 S; P (x; y; z; :::); the variables y; z; ::: are free (we
can replace them by any values).

6
 The statement (8x 2 S; P (x) and Q(x)) is equivalent to the the statement
(8x 2 S; P (x)) and (8x 2 S; P (x)):
We have (8x 2 S; P (x) or 8x 2 S; Q(x)) =) (8x 2 S; P (x) or Q(x)) but
the converse is not true.
(S = R; P (x) : x < 3 Q(x) : x 3 we have 8x 2 R : x < 3 or x 3: But
we have not 8x 2 R : x < 3 or 8x 2 R : x 3):
We have (9x 2 S; P (x) and Q(x)) =) (9x 2 S; P (x)) and (9x 2 S; Q(x)):
But the converse is not true.
(9x 2 N; x even and 9x 2 N; x odd) does not imply 9x 2 N; x even and
odd).
The statement (9x 2 S; P (x) or Q(x)) is equivalent to (9x 2 S; P (x) or
9x 2 S; Q(x)):

2.3 Inclusion and equality

Let A and B be two sets.

We say that A is included in B, or that A is a subset of B, if the following

proposition is true.

8x 2 A; x 2 B:
In this case we write A B; which reads "A is included in B "

We say that A and B are equal if the following proposition is true:

(A B) ^ (B A) :

In which case we write A = B.

2.4 Set operations

Let A and B be two subsets of a set S.

The collection of all elements x of S that satisfy the condition: (x 2 A) ^

(x 2 B) true forms a set denoted A \ B. It reads "A intersection B "

A \ B = fx 2 S : (x 2 A) ^ (x 2 B)g :

The collection of all elements x of S that satisfy the condition: (x 2 A) _

(x 2 B) true forms a set denoted A [ B. It reads "A union B "

A [ B = fx 2 S : (x 2 A) _ (x 2 B)g

7
 The collection of all elements x of S that satisfy the condition: (x 2 A) ^
(x 2
= B) true forms a set denoted AnB. It reads "A less B "

AnB = fx 2 S : (x 2 A) ^ (x 2
= B)g :

The particular case, SnA is called the complementary of A in S. It is

S
denoted CA , A or AC

The set (AnB) [ (BnA) is denoted A 4 B; called the symmetrical di¤erence

of A and B:

We admit the existence of a set denoted ; verifying the condition:

For any set S we have ; S: Such a set cannot contain elements and it is
unique.The set ; is called the empty set.
Indeed, let A = fag and B = fbg be two sets, a and b being distinct. Assume
that ; has elements, then at least one element, denoted z is in ; . Since ; A;
so z 2 A; necessarily z = a: Since ; B, so z 2 B, necessarily z = b then a = b.
Contradiction. Then (8x) (x 2 = ;) : Hence ; is empty. Let us now show that if
such a set exists, then it must be unique. Suppose there are two sets ;1 ; ;2 that
verify: (;1 S) (8S) and (;2 S) (8S) : This leads for S = ;1 and for S = ;2
to ;1 ;2 and ;2 ;1 : We deduce then ;1 = ;2 : We can prove directly the
following:

Proposition 8 For any sets S; F and G we have

1. S \ ; = ;:
2. S [ ; = S:
3. S \ S = S:
4. S [ S = S:
5. Sn; = S:
6. S \ F = F \ F:
7. S [ F = F [ S:
8. (S [ F ) [ G = S [ (F [ G):
9. S \ (F \ G) = (S \ F ) \ G:
10. S \ (F [ G) = (S \ F ) [ (F \ G):
11. S [ (F \ G) = (S [ F ) \ (S [ G):

12. S = S:
13. (S [ F ) = S \ F :

8
 14. S \ F = S [ F :

Let S be a set. The set of all subsets of S is denoted P(S) and called
power set of S. We obviously have

X 2 P(S) if an only if X S:
It is clear that P(S) is never empty since it contains ; and S:

Example 9

1. Let S = ;: Then P(;) = f;g ; P(P(;)) = f;; f;gg ; P(P(P(;))) = f;; f;g ; ff;gg ; f;; f;ggg :
2. Let S = f1; 2; 3g : Then P(S) = f;; f1g ; f2g ; f3g ; f1; 2g ; f1; 3g ; f2; 3g ; f1; 2; 3gg :

Partition: Two subsets A and B of a set S are said to be disjoint if A\B =

;: Let S be set. A partition of S is a set whose elements are nonempty disjoint
subsets of S such that the union of all these subsets is all of S.
Cartesian product: Let E1 ; E2 ; :::; En be n nonempty sets. Any object
of the form (x1 ; x2 ; :::; xn ); where x1 2 E1 ; x2 2 E2 ; :::; xn 2 En is called a n
tuplet. This notion obeys to the following: (x1 ; x2 ; :::; xn ) = (y1 ; y2 ; :::; yn ) if
and only if xi = yi ; 1 i n: The Cartesian product of E1 ; E2 ; :::; En denoted
E1 E2 En is de…ned by

E1 E2 En = f(x1 ; x2 ; :::; xn ) : x1 2 E1 ; x2 2 E2 ; :::; xn 2 En g :

If Ei = Ej ; 1 i; j n; the Cartesian product E E E is denoted

| {z }
n tim es
En:

3 Methods of proof
In mathematics, the proof of a proposition consists in deducing its truth from
a set of mathematical statements (called hypotheses) that are assumed to be
true at the time of proof. This process is based on logic, but generally includes
elements of natural language and the use of axioms, theorems, propositions,
lemmas, corollaries, etc. Note that hypotheses are generally written explicitly
in the statement to be proved, which is not the case for the axioms, theorems,
propositions, lemmas, corollaries... used in the course of this proof. In general
to prove a proposition Q; we have to prove an implication P =) Q where P is
the hypothesis and we want to get Q true. To get a proof we have to:
i) respect the logic rules,
ii) know the di¤erent manners of proofs,
iii) have good sense, rigor.
In this section, we outline the main strategies for proving a mathematical
statement.

9
3.1 Proof by Deduction (direct proof)
Deductive reasoning is the most common type of proof. Starting with a hy-
pothesis, a logical line of reasoning is constructed, leading to a conclusion. This
method is based on the tautology

P ^ (P =) Q) =) Q:
The proposition P represents the set of hypotheses and Q the conclusion to
be reached, given that the implication P =) Q is true.

Example 10

1. Let us show that if a and b are odd integers, then a + b is an even integer.
Assume that a and b are odd integers. Then there are integers k and k 0
such that a = 2k+1 and b = 2k 0 +1: Then we have a+b = 2k+1+2k 0 +1 =
2(k + k 0 + 1), which shows that x + y is an even integer.
2. Let us show that any positive integer that is a square has an odd number
of divisors. Let a be a square integer. Then among the divisors of a we
have 1 and itself a. As a = b2 then a admits b as a divisor. This already
gives three divisors 1; a and b. On the other hand for any other c di¤ erent
from 1; a and b, divisor of a , there must be an integer d such that a = cd:
The integer d is also divisor of a and must also be di¤ erent from 1; a; b,
and c. So if there are divisors other than a and b, they must be di¤ erent
and exist in pairs. The total number of divisors is therefore odd.

3.2 Proof by Contrapositive

The proof by contrapositive takes advantage of the mathematical equivalence
(P =) Q) , (Q =) P ). In some cases, the implication Q =) P is simpler to
show than P =) Q. That is, a proof by contrapositive begins by assuming that
Q is false (i.e., Q is true). It then produces a series of direct implications leading
to the conclusion that P is false (i.e., P is true). It follows that Q cannot be
false when P is true, so P ) Q:

Example 11

1. Let n 2 N. We will show that if n2 is even, then n is even. Indeed, we

prove the contrapositive of this proposition. Assume that n is odd. Then
there exists k 2 N such that n = 2k + 1. Thus, n2 = (2k + 1)2 = (2k)2
0 0
+4k + 1 = 2(2k 2 + 2k) + 1. Let k = 2k 2 + 2k. Then k is odd. Thus, if
n is odd, then n2 is odd. By contrapositive, if n2 is even, then n is even.
2. Let m and n be two nonzero natural numbers. Let us show that if m n
is odd, then m and n are odd. Indeed, assume that m is even then there
exists k 2 N such that m = 2k: Then mn = 2kn which is even. The
case n is even is similar. Thus if m or n is even then mn is even. By
contrapositive if m n is odd, then m and n are odd.

10
3.3 Proof by Contradiction
This method is based on the mathematical equivalence (P =) Q) () P ^ Q.
In this case, we assume Q to be false and P to be true; if in the course of
reasoning we get a contradiction, P ^ Q cannot be true, then P =) Q is true,
we deduce that Q is true.
Example 12
p
1. Let us show that p 2 = Q for any prime p: Assume for contradiction
p p1 p2
p = q1 with p1 ; q1 2 Q and gcd(p1 ; q1 ) = 1. Hence q21 = p, it means
1
p21 = pq12 and, consequently, p1 is divisible by p. Let p1 = pr; r 2 N. Then
p21 = p2 r2 = pq12 , which gives pp2 = q12 then q1 is also divisible by p. This
contradicts the hypothesis on p1 ; q1 being coprime. So, the assumption that
p p
p can be expressed as pq11 with p1 ; q1 2 Q is false, then p 2= Q when p is
a prime:
2. Let us show that there is an in…nity of prime numbers. Suppose there is
only a …nite number of prime numbers say p1 ; p2 ; :::; pk . Put n = 1 +
p1 p2 pk . Since any positive integer di¤ erent from 1 is divisible by at
least one prime number, then n is divisible by some pi where 1 i k;
this is impossible, as otherwise pi = 1. Consequently, there is an in…nity
of prime numbers.

3.4 Proof by induction

We want to prove that (8n 2 N; n n0 ; P (n)) is true where P (n) is a property
depending on the nonnegative integer n. First, we prove for some positive integer
k0 that P (k0 ) is true. Then 8n 2 N; n n0 ; P (n) =) P (n + 1). is true. The
proof by induction consists in showing that P (n0 ) is true, and then assuming
that if P (n) is true with n n0 then P (n + 1)is true.
Example 13
1. Let us show that, for any natural number n, n3 n is a multiple of 3. For
n = 0: 03 0 = 0 which is divisible by 3 then P (0) is valid. Suppose P (k)
is valid, that is, k 3 k is a multiple of 3 and prove that P (k + 1) is valid,
in other words, we prove that (k + 1)3 (k + 1) is divisible by 3.

(k + 1)3 (k + 1) = (k + 1)(k + 1)2 k 1

= (k + 1)(k 2 + 2k + 1) k 1
= k 3 k + 3k 2 + 3k
Now, by induction hypothesis, k 3 k = 3q for some q 2 N:Thus,
(k + 1)3 (k + 1) = 3(q + (k 2 + 1)):
Then P (k + 1) is valid. Thus, for any n 2 N; n3 n is a multiple of 3:

11
 2. Let us show that for any n 2 N and for any positive real x, (1 + x)n
1 + nx: For n = 1: P (1) is true since (1 + x)1 1 + x: Assume that
(1 + x)k 1 + kx and prove that (1 + x)k+1 1 + (k + 1)x: Multiplying
the induction hypothesis (1 + x)k 1 + kx by (1 + x) we obtain

(1 + x)k+1 (1 + kx)(1 + x) (since (1 + x) > 0)

= 1 + (k + 1)x + kx2
1 + (k + 1)x ( since kx2 0)

Then P (k + 1) is valid. Thus, for any n 2 N and for any positive real x,
(1 + x)n 1 + nx:

3.5 Proof by counter-example

An example is not enough to prove that an assertion is true, but a counter-
example is enough to prove that an assertion is false. Then to reject an asser-
tion, it is sometimes enough to …nd a particular case that contradicts it. This
particular case is called a counter-example.

Example 14

1. If x and y are two real numbers such that x2 < y 2 then x < y. This
assertion is false. Counter-example: for x = 2 and y = 3 we have
22 < ( 3)2 but 2 > 3:
2. It is well-known that if 2n 1 is prime, then n is prime. The converse
of this statement is false. Counter-examples: for n = 11 or n = 23 which
are primes we have
211 1 = 2047 = 23 89
and
223 1 = 8388607 = 47 178481:

12