لخّصلي

In this chapter we are going to study three subjects, we start by a very important notion in mathematics it called logic in this section we are going to present some articles which are used in proof of theorem, proposition, corollary or lemma.1.1 Logic : 1.1.1 Statement "Proposition" - Assertion and Predicate: Definition 1.1.1. statement or proposition is the content of an assertion. It is either true or false, but cannot be true and false at the same time. Example 1.1.1. x = 1 is the solution of the equation 2x = 2 : it is a proposition, because this sentence is true. w is a natural number : it is not a proposition, because we cannot say this sentence is true or false. Remark 1.1.1. Two assertions P and R are logically equivalent (denoted P? R) if both true or false. Definition 1.1.2. Predicate is a sentence which is contain some variables, if we replace each one by a value of a set, we obtain an assertion. Example 1.1.2. m is a divisor of 18 : it is a predicate. If we take m=6, we obtain that 6 is a divisor of 18 : this assertion is true. If we take m=5, we observe that 5 is not a divisor of 18 : this assertion is false. 1.1.2 Sentential Connectives : In mathematical discourse and elsewhere one constantly encounters declarative sen?tences which have been formed by modifying a sentence with the word not or by connecting sentences with the words and, or, if ... then ... (or implies), and ... if and only if ... (or equivalent). These five words or combinations of words are called sentential connectives. Negation : Definition 1.1.3. In mathematics, a negation is an operator on the logical value of a proposition that sends true to false and false to true. The negation ( or logical Not) of P, denoted by !P or P?. Example 1.1.3. P : He is a student,P? : He is not a student. Q : 2 is a prime number, !Q : 2 is not a prime number. Conjunction : Definition 1.1.4. A logical conjunction is an operator on two logical propositions that produces a value of true if both statements are true, and false otherwise. The conjunction ( or logical and) of P and Q, denoted by P ? Q. Example 1.1.4. ( Algeria is an Africa country ) and ( Its mother language is English ) : The composite sentence is false. ( 2 is an even number ) and ( 2 is a natural number ) : The composite sentence is true. Disjunction : Definition 1.1.5. A logical disjunction is an operator on two logical propositions that is true if either statement is true or both are true, and it is false otherwise. The disjunction ( or logical or ) of P and Q, denoted by P ? Q. Example 1.1.5. ( 10 is an odd number ) or ( 10 is a real number ) : The composite sentence is true. ( ? is an integer number ) or ( ? is a rational number ) : The composite sentence is false. Conditional : Definition 1.1.6. The conditional connective P => Q is a logical statement that means ( if P then Q) or P implies Q. In this statement P is called the antecedent and Q is called the consequent. The composite sentence is false if the sentence P is true and the sentence Q is false, and it is true otherwise. Example 1.1.6. If n is an odd natural number then 2n is an even natural number. If x = 1 then 2x = 2. Biconditional : Definition 1.1.7. The logical biconditional is an operator connecting two logical propositions that is true if the statements are both true or both false, and it is false otherwise. The biconditional from P to Q, denoted by P <=> Q and we read ( P if and only if Q) or ( P is equivalent to Q. The phrase (if and only if) is often abbreviated as (iff). Example 1.1.7. 2x = 2 if and only if x = 1. 1.1.3 Truth Tables : Below are truth tables for the types of composite statements, we have already dis?cussed, as well as those for conditional and biconditional statements. 1.1.4 Tautology and Contradiction :

Tautology :

Definition 1.1.8. A tautology is a statement which is true in every valuation of its propositional variables, independent of the truth values assigned to these variables. Example 1.1.8. P !P P ? !P T F T F T T Contradiction : Definition 1.1.9. The negation of a tautology is a contradiction, it is a statement which is necessarily false regardless of the truth values of its propositional variables. Example 1.1.9. P !P P ? !P T F F F T F 1.1.5 Relations between statements : Theorem 1.1.1. Let A, B and C be statements. The next equivalences are true : (a) Commutativity : A ? B ? B ? A and A ? B ? B ? A; (b) Associativity : A?(B ? C) ? (A ? B)?C and A?(B ? C) ? (A ? B)?C; (c) Distributive : A?(B ? C) ? (A ? B)?(A ? C) and A?(B ? C) ? (A ? B)? (A ? C); (d) A ? (B ? A) ? A and A ? (B ? A) ? A; (e) A ? A ? A and A ? A ? A; (f) A ? F ? A and A ? T ? A such that : T represent truth statement and F represent false statement; (g) A ? T ? T and A ? F ? F; (h) A ? (!A) ? T and A ? (!A) ? F; (i) ! (!A) ? A; (j) De Morgan's law : ! (A ? B) ? (!A) ? (!B) and ! (A ? B) ? (!A) ? (!B);

(l) A => B ? (!A) ? B; (m) ! (A => B) ? A ? (!B); (n) (A => B) ? (B => C) ? (A => C); (o) (A <=> B) ? (A => B) ? (B => A). Proof. Using the truth tables. 1.1.6 Quantifiers : Let S be a nonempty set and x is a element in S. Let P(x) be a predicate, x is called a free variable because its value is not fixed in the sentence P(x). Universal quantifier : Definition 1.1.10. It is denoted by ? and informally read for all. The assertion ?x ? S : P(x) is true if P(x) is true for all values of x in S. Example 1.1.10. ?n ? N : n 2 - 4 >= 2n - 5. Existential quantifier : Definition 1.1.11. It is denoted by ? and informally read there exists an x. The statement ?x ? S : P(x) is true if P(x) is true for at least one value of x in S. Example 1.1.11. ?x ? N : x 2 + x - 2 = 0. Remarks 1.1.1. (1) ! (?x ? S : P(x)) <=> ?x ? S : (!P(x)). (2) ! (?x ? S : P(x)) <=> ?x ? S : (!P(x)). (3) ?!x ? S : P(x), we read " there exists a unique element x in S : P(x) ", this statement is true if P(x) is true just for one element x in S. (4) We can also define predicates with multiple free variables.They can be called theo?rems, propositions, lemmas, corollaries and exercises.1.1.7 Strategies for Proofs : True statements in mathematics have different names.That is a proof by contrapositive begins by assum?ing that Q is false ( i. e., !Q is true ).Show that, the sum of rational number and irrational num?ber is an irrational number.Z such that : x = c d ( where d 6= 0 ), then y = a b - c d , which is equivalent to y = ad-bc bd , implies ?e, f ?After produces a series of direct implications leading to the conclusion that P is false ( i. e., !P is true).Z, such that : x + y = a b ( where b 6= 0 ), because x ? Q, then ?c, d ? Z (e = ad - bc and f = bd) such that : y = e f , implies y ?(b) Proof by Contrapositive : A proof by contrapositive takes advantage of the mathematical equivalence (P => Q) <=> (!Q => !P).It follows that Q cannot be false when P is true.(c) Proof by Contradiction : A proof by contradiction is based on the mathematical equivalence !(P => Q) <=> (P ?We assume that there exists x1 and x2 (x1 6= x2) such that : P(x1) and P(x2) and we arrive that x1 = x

(d) Proof by Counterexample : A proof by counterexample of the proposition ( P => Q is false ) is based to find a particular case which is the proposition P => Q false.Is the following proposition true or false ?There are five different proofs for prove those statements.We assume that the proposition Q is false, that means n is an even number, then there exists k ?In a proof by contradiction, we start by assuming that both P and !Q are true.Than, a series of direct implications are given that lead to a logical contradiction.In the second section, we study set theory and finally, we are going to study the maps.Examples 1.1.1.S : P(x, y) is not equivalent to ?y ?(a) Direct Proof : The simplest form of proof for a statement of the form P => Q is the direct proof.First assume that P is true.Produce a series of steps, each one following from the previous ones, that eventually leads to conclusion Q. Example 1.1.12.N such that : n = 2k + 1, implies n 2 = (2k + 1)2 = 4k 2 +4k +1 = 2 (2k 2 + 2k)+1, putting k 0 = 2k 2 +2k then ?k 0 ?The proof has been completed.Remark 1.1.2.For prove a proposition as the form "?x ? S : P(x)", we start by : Let us x ?S and we finish by P(x) is true.N such that : n = 2k which is equivalent to n 2 = 4k 2 = 2 (2k 2 ), then n 2 is an even number.The proof has been completed.Hence, P ?!Q cannot be true and P => Q. Example 1.1.14.Q, so we have a contradiction.Hence, x + y /?Q. The proof has been completed.Remark 1.1.3.For prove that the following statement is true ?!x ?Usually we use the proof by contradiction.(1) !R : f(x) >= 0) <=> ?x ?R : f(x) < 0.(2) !(?x ? R : x 2 + 1 = 0) <=> ?x ?R : x 2 + 1 6= 0.(3) ?x ?S, ?y ?S : P(x, y).(4) ?y ?S, ?x ?S : P(x, y).Attention 1.1.1.?x ?S, ?y ?S, ?x ?S : P(x, y).Show that, if n ?N is an odd number then n 2 is also. !Q).Example 1.1.15.

In this chapter we are going to study three subjects, we start by a very important
notion in mathematics it called logic in this section we are going to present some
articles which are used in proof of theorem, proposition, corollary or lemma. In the
second section, we study set theory and finally, we are going to study the maps.
1.1 Logic :
1.1.1 Statement ”Proposition” - Assertion and Predicate:
Definition 1.1.1. statement or proposition is the content of an assertion. It is
either true or false, but cannot be true and false at the same time.
Example 1.1.1. x = 1 is the solution of the equation 2x = 2 : it is a proposition,
because this sentence is true.
w is a natural number : it is not a proposition, because we cannot say this sentence
is true or false.
Remark 1.1.1. Two assertions P and R are logically equivalent (denoted P≡
R) if both true or false.
Definition 1.1.2. Predicate is a sentence which is contain some variables, if we
replace each one by a value of a set, we obtain an assertion.
Example 1.1.2. m is a divisor of 18 : it is a predicate.
If we take m=6, we obtain that 6 is a divisor of 18 : this assertion is true.
If we take m=5, we observe that 5 is not a divisor of 18 : this assertion is false.
1.1.2 Sentential Connectives :
In mathematical discourse and elsewhere one constantly encounters declarative sen￾tences which have been formed by modifying a sentence with the word not or by
connecting sentences with the words and, or, if ... then ... (or implies), and ...
if and only if ... (or equivalent).
These five words or combinations of words are called sentential connectives.
Negation :
Definition 1.1.3. In mathematics, a negation is an operator on the logical value
of a proposition that sends true to false and false to true. The negation ( or logical
Not) of P, denoted by ¬P or P¯.
Example 1.1.3. P : He is a student,P¯ : He is not a student.
Q : 2 is a prime number, ¬Q : 2 is not a prime number.

Conjunction :
Definition 1.1.4. A logical conjunction is an operator on two logical propositions
that produces a value of true if both statements are true, and false otherwise. The
conjunction ( or logical and) of P and Q, denoted by P ∧ Q.
Example 1.1.4. ( Algeria is an Africa country ) and ( Its mother language is
English ) : The composite sentence is false.
( 2 is an even number ) and ( 2 is a natural number ) : The composite sentence is
true.
Disjunction :
Definition 1.1.5. A logical disjunction is an operator on two logical propositions
that is true if either statement is true or both are true, and it is false otherwise. The
disjunction ( or logical or ) of P and Q, denoted by P ∨ Q.
Example 1.1.5. ( 10 is an odd number ) or ( 10 is a real number ) : The composite
sentence is true.
( π is an integer number ) or ( π is a rational number ) : The composite sentence
is false.
Conditional :
Definition 1.1.6. The conditional connective P ⇒ Q is a logical statement
that means ( if P then Q) or P implies Q. In this statement P is called the
antecedent and Q is called the consequent. The composite sentence is false if the
sentence P is true and the sentence Q is false, and it is true otherwise.
Example 1.1.6. If n is an odd natural number then 2n is an even natural number.
If x = 1 then 2x = 2.
Biconditional :
Definition 1.1.7. The logical biconditional is an operator connecting two logical
propositions that is true if the statements are both true or both false, and it is false
otherwise. The biconditional from P to Q, denoted by P ⇔ Q and we read ( P if
and only if Q) or ( P is equivalent to Q.
The phrase (if and only if) is often abbreviated as (iff).
Example 1.1.7. 2x = 2 if and only if x = 1.
1.1.3 Truth Tables :
Below are truth tables for the types of composite statements, we have already dis￾cussed, as well as those for conditional and biconditional statements.

1.1.4 Tautology and Contradiction :

Tautology :

Definition 1.1.8. A tautology is a statement which is true in every valuation of its
propositional variables, independent of the truth values assigned to these variables.
Example 1.1.8.
P ¬P P ∨ ¬P
T F T
F T T
Contradiction :
Definition 1.1.9. The negation of a tautology is a contradiction, it is a statement
which is necessarily false regardless of the truth values of its propositional variables.
Example 1.1.9.
P ¬P P ∧ ¬P
T F F
F T F
1.1.5 Relations between statements :
Theorem 1.1.1. Let A, B and C be statements. The next equivalences are true :
(a) Commutativity : A ∨ B ≡ B ∨ A and A ∧ B ≡ B ∧ A;
(b) Associativity : A∨(B ∨ C) ≡ (A ∨ B)∨C and A∧(B ∧ C) ≡ (A ∧ B)∧C;
(c) Distributive : A∨(B ∧ C) ≡ (A ∨ B)∧(A ∨ C) and A∧(B ∨ C) ≡ (A ∧ B)∨
(A ∧ C);
(d) A ∨ (B ∧ A) ≡ A and A ∧ (B ∨ A) ≡ A;
(e) A ∨ A ≡ A and A ∧ A ≡ A;
(f) A ∨ F ≡ A and A ∧ T ≡ A such that : T represent truth statement and F
represent false statement;
(g) A ∨ T ≡ T and A ∧ F ≡ F;
(h) A ∨ (¬A) ≡ T and A ∧ (¬A) ≡ F;
(i) ¬ (¬A) ≡ A;
(j) De Morgan’s law : ¬ (A ∨ B) ≡ (¬A) ∧ (¬B) and ¬ (A ∧ B) ≡ (¬A) ∨
(¬B);

(l) A ⇒ B ≡ (¬A) ∨ B;
(m) ¬ (A ⇒ B) ≡ A ∧ (¬B);
(n) (A ⇒ B) ∧ (B ⇒ C) ≡ (A ⇒ C);
(o) (A ⇔ B) ≡ (A ⇒ B) ∧ (B ⇒ A).
Proof. Using the truth tables.
1.1.6 Quantifiers :
Let S be a nonempty set and x is a element in S. Let P(x) be a predicate, x is
called a free variable because its value is not fixed in the sentence P(x).
Universal quantifier :
Definition 1.1.10. It is denoted by ∀ and informally read for all. The assertion
∀x ∈ S : P(x) is true if P(x) is true for all values of x in S.
Example 1.1.10. ∀n ∈ N : n
2 − 4 ≥ 2n − 5.
Existential quantifier :
Definition 1.1.11. It is denoted by ∃ and informally read there exists an x. The
statement ∃x ∈ S : P(x) is true if P(x) is true for at least one value of x in S.
Example 1.1.11. ∃x ∈ N : x
2 + x − 2 = 0.
Remarks 1.1.1. (1) ¬ (∀x ∈ S : P(x)) ⇔ ∃x ∈ S : (¬P(x)).
(2) ¬ (∃x ∈ S : P(x)) ⇔ ∀x ∈ S : (¬P(x)).
(3) ∃!x ∈ S : P(x), we read ” there exists a unique element x in S : P(x) ”, this
statement is true if P(x) is true just for one element x in S.
(4) We can also define predicates with multiple free variables.
Examples 1.1.1. (1) ¬ (∀x ∈ R : f(x) ≥ 0) ⇔ ∃x ∈ R : f(x) < 0.
(2) ¬ (∃x ∈ R : x
2 + 1 = 0) ⇔ ∀x ∈ R : x
2 + 1 6= 0.
(3) ∀x ∈ S, ∃y ∈ S : P(x, y).
(4) ∃y ∈ S, ∀x ∈ S : P(x, y).
Attention 1.1.1. ∀x ∈ S, ∃y ∈ S : P(x, y) is not equivalent to ∃y ∈ S, ∀x ∈ S :
P(x, y).

1.1.7 Strategies for Proofs :
True statements in mathematics have different names. They can be called theo￾rems, propositions, lemmas, corollaries and exercises.
There are five different proofs for prove those statements.
(a) Direct Proof :
The simplest form of proof for a statement of the form P ⇒ Q is the direct
proof. First assume that P is true. Produce a series of steps, each one
following from the previous ones, that eventually leads to conclusion Q.
Example 1.1.12. Show that, if n ∈ N is an odd number then n
2
is also.
We assume that n ∈ N is an odd number, then ∃k ∈ N such that : n = 2k + 1,
implies n
2 = (2k + 1)2 = 4k
2 +4k +1 = 2 (2k
2 + 2k)+1, putting k
0 = 2k
2 +2k
then ∃k
0 ∈ N such that : n
2 = 2k
0 + 1. The proof has been completed.
Remark 1.1.2. For prove a proposition as the form ”∀x ∈ S : P(x)”, we
start by : Let us x ∈ S and we finish by P(x) is true.
(b) Proof by Contrapositive :
A proof by contrapositive takes advantage of the mathematical equivalence
(P ⇒ Q) ⇔ (¬Q ⇒ ¬P). That is a proof by contrapositive begins by assum￾ing that Q is false ( i. e., ¬Q is true ). After 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. then P ⇒ Q.
Example 1.1.13. Show that, if n
2 ∈ N is an odd number then n is also.
We assume that the proposition Q is false, that means n is an even number,
then there exists k ∈ N such that : n = 2k which is equivalent to n
2 = 4k
2 =
2 (2k
2
), then n
2
is an even number. The proof has been completed.
(c) Proof by Contradiction :
A proof by contradiction is based on the mathematical equivalence ¬(P ⇒
Q) ⇔ (P ∧ ¬Q). In a proof by contradiction, we start by assuming that both
P and ¬Q are true. Than, a series of direct implications are given that lead
to a logical contradiction. Hence, P ∧ ¬Q cannot be true and P ⇒ Q.
Example 1.1.14. Show that, the sum of rational number and irrational num￾ber is an irrational number.
Let x ∈ Q and y /∈ Q, we show that x + y /∈ Q.
We assume that x + y ∈ Q, then ∃a, b ∈ Z, such that : x + y =
a
b
( where
b 6= 0 ), because x ∈ Q, then ∃c, d ∈ Z such that : x =
c
d
( where d 6= 0 ), then
y =
a
b −
c
d
, which is equivalent to y =
ad−bc
bd , implies ∃e, f ∈ Z (e = ad − bc
and f = bd) such that : y =
e
f
, implies y ∈ Q but y /∈ Q, so we have a
contradiction. Hence, x + y /∈ Q. The proof has been completed.
Remark 1.1.3. For prove that the following statement is true ∃!x ∈ S : P(x).
Usually we use the proof by contradiction. We assume that there exists x1 and
x2 (x1 6= x2) such that : P(x1) and P(x2) and we arrive that x1 = x

(d) Proof by Counterexample :
A proof by counterexample of the proposition ( P ⇒ Q is false ) is based to
find a particular case which is the proposition P ⇒ Q false.
Example 1.1.15. Is the following proposition true or false ? ” all continuous
function is differentiable ”.
This proposition is false, because if we take the function f(x) = |x|, x ∈ [−1, 1],
this function is continuous on this interval but it is not differentiable at the
point x = 0. Indeed, limx→0+
f(x) − f(0)
x
= 1 and limx→0−
f(x) − f(0)
x
= −1,
then limx→0
f(x) − f(0)
x
exist but it is not unique.
(e) Proof by Induction :
Let P(n) be a logical statement for each n ∈ N. The principle of mathemat￾ical induction is :
,→ We show that P(n) is true for the initial value n0;
,→ We assume that P(n) is true for i = n0 + 1, ..., i = n;
,→ We show that P(n + 1) is true.
Example 1.1.16. Show by mathematical induction that :
∀n ∈ N
∗
: 12 + 23 + ... + n
3 =
n
2
(n + 1)2
4
,→ For n = 1, we have : 1
3 =
1
2
(1 + 1)2
4
= 1, then P(1) is true;
,→ We assume that P(n) is true for i = 2 until n, that means :
∀n ∈ N
∗
: 12 + 23 + ... + n
3 =
n
2
(n + 1)2
4
;
,→ We show that P(n + 1) is true, i. e. :
∀n ∈ N
∗
: 12 + 23 + ... + n
3 + (n + 1)3 =
(n + 1)2
(n + 2)2
4
.
Because P(n) is true for i = 2 until n, so we have :
∀n ∈ N
∗
: 12+23+...+n
3+(n+1)3 =
n
2
(n + 1)2
4
+(n+1)3 =
(n + 1)2
(n + 2)2
4
;
Therefore, P(n + 1) is true ∀n ∈ N
∗
. The proof has been completed.