B Coordination SM-ST of Chapter I. Faculty of Mathematics Chapter 1 :and Logic, Sets Logic, MapsSets, Maps MATH 1 Module 1st year Licence SM-ST Academic year 2023-2024
I) Logic Logic enables us to model and study mathematical reasoning.
1) Definitions I Proposition : We call proposition a statement or expression that can be true or false. Every proposition has a truth value T (true) or F (false).. Example 1.
• Algiers is a coastal city. (T)
• The triangal rectangal has a right angle. (T) • 3 + 5 = 0. (F) • x, y two reals, x is greater than y. (This is not a proposition, it’s a statement) I Axiom : We call axiom any proposition considered as evident, accepted as true without demonstration. Example 2. Euclide’s Axiom asserts that through a given point A not on a line (D), there is one and only one line in the plane of A parallel to (D). I Theorem : We call theorem any proposition that is proven to be true.
I Corollary : A corollary is a direct consequence of a theorem.
I Lemma : We call lemma any true proposition preparatory to the establishment of a theorem of greater importance.
2) Logical connectives Logical connectives are used to define other propositions from one or more initial propositions. Let P and Q be two propositions, defined by :
I Negation : The negation of a proposition P is the proposition, denoted P , which is true when P is false and false otherwise. Example 3. P : 3 is an even number (F), P : 3 is not an even number (T). I Conjunction : The conjunction of two propositions P and Q is the proposition (P and Q), denoted (P ∧ Q), which is true if P and Q are both true at the same time. It is false otherwise. This is summarized in the following truth table : P Q P∧Q T T T T F F F T F F F F Example 4. 2 divides 9 and 136 is a multiple of 17. (F)
1 I Disjunction : The disjunction of two propositions P and Q is the proposition (P or Q), denoted (P ∨ Q), which is true if at least one of the two propositions are true. It is false otherwise. This is summarized in the following truth table : P Q P∨Q T T T T F T F T T F F F Example 5. 2 divides 9 or 136 is a multiple of 17. (T) I Implication : The proposition P implies Q, denoted (P ⇒ Q), is the proposition which is false when P is true and Q is false. It is true otherwise. In other words, it is the proposition (P ∨ Q). P Q P ⇒Q T T T T F F F T T F F T √ Example 6. 2 × 2 = 6 ⇒ 3 = 1. (T) (If P is false then P ⇒ Q is always true) Remark. From the implication (P ⇒ Q), we define : • The implication (Q ⇒ P ), called converse of the implication (P ⇒ Q). • The implication (Q ⇒ P ), called contrapositive of the implication (P ⇒ Q). • The negation (P ⇒ Q) is the proposition (P ∧ Q).
Example 7. Let be the following implication : (n2 is even )⇒ (n is even).
1. Its converse is : (n is even )⇒ (n2 is even). 2. Its contrapositive is : (n is odd ) ⇒ (n2 is odd). 3. Its negation is : (n2 is even ) and (n is odd). I Equivalence : The proposition P equivalent to Q, denoted (P ⇔ Q), is the proposition which is true when P and Q are both true or both false. It is false otherwise. In other words, it is the proposition (P ⇒ Q) ∧ (Q ⇒ P ). P Q P ⇔Q T T T T F F F T F F F T Example 8. Let x ∈ R. We have the following equivalence : 2x − 2 = 0 ⇔ x = 1 (the implication and its converse are both true). Remark. In mathematical practice, we’re only interested in true propositions. In other words, we’ll write P ⇔ Q or P ⇒ Q only when they’re true. Example 9. √ 1. 0 ≤ x ≤ 64 ⇒ x ≤ 8. (T) 2. Let x, y ∈ R. We have the following equivalence : x2 + y 2 = 0 ⇔ x = y = 0. (T) Proposition. Let P , Q two propositions. We have the following (true) equivalences : 1. P ⇔ P , 2. (P ∧ Q) ⇔ P ∨ Q, 3. (P ∨ Q) ⇔ P ∧ Q, 4. (P ⇒ Q) ⇔ (Q ⇒ P ).
2 3) Quantifiers Let P (x) the proposition dependant on the element x of a set E. We write • ∀x ∈ E, P (x) : when the proposition P is true for all the elements x ∈ E. ∀, which can be read whatever or for all, is called universal quantifier. • ∃x ∈ E, P (x) : when there exists at least an element x of the set E for which the proposition P is true. ∃, which can be read there is at least one, is called existential quantifier. • ∃ ! x ∈ E, P (x) : when there exists a unique element x of the set E for which the proposition P is true. There is jointly existence and uniqueness of the element x verifying the proposition P . Example 10. 1. ∀x ∈ [0, +∞[, x2 ≥ 0 (T) 2. ∀x ∈ R, x2 ≥ 4 (F) 3. ∃n ∈ N, n2 − n > n (T) (n=3, n=10, n=100). 4. ∃x ∈ R, x2 = −4 (F) (no squared real will give a negative numbe). 5. ∃!n ∈ N, n2 − n > n (F)
Negation of propositions depending on quantifiers
• The negation of (∀x ∈ E, P (x)) is (∃x ∈ E, P (x)). Example 11. The negation of (∀x ∈ [1, +∞[, x2 ≥ 1) is (∃x ∈ [1, +∞[, x2 < 1).
• The negation of (∃x ∈ E, P (x)) is (∀x ∈ E, P (x)).
Example 12. The negation of (∃n ≥ 0, n3 − n is a multiple of 3) is (∀n ≥ 0, n3 − n it is not a multiple of 3).
Remak. • We can find propositions that depend on two quantifiers. For example : ∀x ∈ R, ∃y > 0, x + y > 10. • The order of quantifiers is very important. Consider the following two propositions: ∀x ∈ R, ∃y ∈ R, y > x and ∃x ∈ R, ∀y ∈ R, y > x. The first is true and the second is false. Indeed, in the first case, you can always find a number greater than a given real number, because R is not bounded. For the second, however, you can’t find a real number that’s smaller than all the others, because R has no lower bound.
4) Modes of reasoning Here is some mode of reasoning in mathematics.
4.1 Direct reasoning
We want to show that the proposition P ⇒ Q is true. This reasoning consists in assuming that P is true and showing that Q is true. a b Example 13. Let a, b ≥ 0. Let us show that if = then a = b. 1+b 1+a a b We suppose that = then a(1 + a) = b(1 + b) so a + a2 = b + b2 d’où a2 − b2 = b − a. This leads 1+b 1+a to (a − b)(a + b) = −(a − b) that is to say (a − b)(1 + a + b) = 0 thus a = b or a + b = −1. As a, b ≥ 0 then their sum cannot be negative. Therefore, we conclude that a = b.
3 4.2 Contrapositive The reasoning by contrapositive is based on the following equivalence: (P ⇒ Q) ⇔ (Q ⇒ P ). So if we want to show P ⇒ Q, we just need to show Q ⇒ P . Example 14. Let n ∈ N. Let’s show that if n2 is even then n is even. First, let’s write the contrapositive: If n isn’t even, then n2 isn’t even. It is assumed that n is not even. We want to show that n2 is not even. Since n is not even, it is odd and so there exists k ∈ N such that n = 2k + 1. Then n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2l + 1 with l = 2k 2 + 2k ∈ N. . And so n2 is odd. Therefore, by contraposition, this is equivalent to: if n2 is even then n is even.
4.3 Contradiction Reasoning by contradiction to show that a proposition P is true is based on the following principle : We assume that P is true and look for a contradiction. Thus, if P is false, this means that P must be true. Example 15. Let’s show the following proposition: 0 has no inverse in R. Let’s reason by the absurd, i.e. suppose 0 admits an inverse in R. 1 Then ∃x0 ∈ R : 0 = 0 ⇒ 0.x0 = 1 ⇒ 0 = 1. Which is absurd, so 0 has no inverse in R. x
4.4 Counter-example This mode of demonstration is used to show that a proposition of the form: For any x in E, P (x) is false. To do this, we need only show that its negation is true, which means that: If there exists x in E, P (x) is true. Example 16. Let’s show the following proposition ∀x ∈ R, x2 + 1 = 0 is false. It suffices to show that its negation is true, i.e. ∃x ∈ R, x2 + 1 6= 0 is true. For x = 1, x2 + 1 = 2 6= 0 is true. So the proposition ∀x ∈ R x2 + 1 = 0 is false.
4.5 Induction The principle of induction makes it possible to show that a proposition P (n), depending on n, is true for all n ∈ N. Demonstration by induction involves three steps: Initialization: we show that P (0) is true. Heredity : Assume that P (n) is true for a given n ≥ 0 and show that the assertion at the next rank P (n + 1) is true. The conclusion: Recall that the induction principle P (n) is true for all n ∈ N. Remark. If we need to show that a proposition is true for all n ≥ n0 then we start the initialization at rank n0 . Example 17. Let’s show that : ∀n ∈ N, 2n > n. For n ≥ 0, let’s denote P (n) the following assertion: 2n > n. We’ll show by induction that P (n) is true for all n ≥ 0. Initialization: For n = 0 we have 20 = 1 > 0 so P (0) is true. Heredity: Set n ≥ 1. Assume that P (n) is true and show that P (n + 1) is true.
2n+1 = 2 · 2n = 2n + 2n > n + 2n car 2n > n > n + 1 car 2n ≥ 1 So P (n + 1) is true. Conclusion : by the induction principle of P (n) is true for each n ≥ 0, i.e. 2n > n ∀n ≥ 0.
