Chapter 1: Logic and Theory of Sets PDF

Chapter 1: Logic and theory of sets 1 Logic Logic is the tool to reason about the truth and the falsity of mathematical statements. Definition 1.1. A statement or a proposition is an assertion which is either true or false but never both simultaneously. Example 1.1. 1. “1 + 0 = 1” is a...

Chapter 1: Logic and theory of sets 1 Logic Logic is the tool to reason about the truth and the falsity of mathematical statements. Definition 1.1. A statement or a proposition is an assertion which is either true or false but never both simultaneously. Example 1.1. 1. “1 + 0 = 1” is a true statement. 2. “x ≤ 9 ” is not a statement as x is not specified so we cannot determine if this is true or false. For every statement, we assign a truth value: the letter T if it is true and the letter F if it is false. A truth table is a table grouping statements and their truth values. Statements can be joined by logical connectors to form new statements called compound statements whose truth values depend on the truth values of the given statements. There exist 5 connectors which are: the negation, the conjunction, the disjunction, the implication and the equivalence. Definition 1.2. The negation of a statement P is the statement “ non P ”, denoted “ℸP ”. It is: false when P is true, true when P is false. The truth table of ℸP is given by: P ℸP T F F T Example 1.2. Let Q be the statement: “4 is an even number ”; Q is true. ℸQ: “4 is not an even number ”; ℸQ is false. Definition 1.3. Let P and Q be two statements. 1. The conjunction of P and Q is the statement “P and Q ”, denoted by “P ∧ Q ”. It is: true when P and Q are both true, 1  false otherwise. 2. The disjunction of P and Q is the statement “P or Q ”, denoted by “P ∨ Q ”. It is: false when P and Q are both false, true otherwise. P Q P ∧Q P ∨Q T T T T T F F T F T F T F F F F Example 1.3. Consider the statements P : “2 is a prime number ”, Q: “1 < 0 ” and R: “5 + 2 ̸= 8 ”. P ∧ Q is false. P ∨ Q is true. P ∧ R is true. Definition 1.4. Let P and Q be two statements. The implication of P and Q is the statement “P implies Q ”, denoted by “P =⇒ Q ”. It is: false when P is true and Q is false, true otherwise. P Q P =⇒ Q T T T T F F F T T F F T In the statement P =⇒ Q, P is called the hypothesis and Q is called the conclusion. The statement “Q =⇒ P ” is called the converse of P =⇒ Q. The statement “ℸQ =⇒ ℸP ” is called the contrapositive of P =⇒ Q. Remark 1.1. The implication P =⇒ Q can be read in multiple ways: P gives Q; If P , then Q; To have P , we must have Q; Q is a necessary condition for P ; To have Q, it suffices to have P ; 2  P is a sufficient condition for Q. Definition 1.5. Let P and Q be two statements. The equivalence of P and Q is the statement “P is equivalent to Q ”, denoted by “P ⇐⇒ Q ”. It is true when P and Q have the same truth value, false otherwise. P Q P ⇐⇒ Q T T T T F F F T F F F T Remark 1.2. The statement P ⇐⇒ Q can be read as P if and only if Q; P is a necessary and sufficient condition of Q. Example 1.4. Consider the statements P : “1 < 0 ” and Q : “2 is even”. 1. P =⇒ Q is true as P is false. 2. (ℸP ) =⇒ (ℸQ) is false. 3. P ⇐⇒ Q is false. 4. P ⇐⇒ (ℸQ) is true. Definition 1.6. 1. A tautology is a compound statement that is always true re- gardless of the truth values of the statements of which it is composed. 2. A contradiction is a compound statement that is always false regardless of the truth values of the statements of which it is composed. Proposition 1.1. Let P be a statement. 1. The statement P ∧ℸP is a contradiction (this is the principle of non-contradiction). 2. The statement P ∨ ℸP is a tautology (this is the law of the excluded middle). 3. The statement (P =⇒ Q) ⇐⇒ (ℸP ∨ Q) is a tautology. 4. The statement (P ⇐⇒ Q) ⇐⇒ [(P =⇒ Q) ∧ (Q =⇒ P )] is a tautology. Proof. 1, 2. P ℸP P ∧ ℸP P ∨ ℸP T F F T F T F T 3  3. P Q ℸP P =⇒ Q ℸP ∨ Q (P =⇒ Q) ⇐⇒ (ℸP ∨ Q) T T F T T T T F F F F T F T T T T T F F T T T T 4. Let R be the statement (P ⇐⇒ Q) ⇐⇒ [(P =⇒ Q) ∧ (Q =⇒ P )] P Q P ⇐⇒ Q P =⇒ Q Q =⇒ P (P =⇒ Q) ∧ (Q =⇒ P ) R T T T T T T T T F F F T F T F T F T F F T F F T T T T T Proposition 1.2. Let P , Q and R be three statements. The following statements are tautologies: 1. Double negation: ℸ(ℸP ) ⇐⇒ P. 2. Idempotence: (P ∧ P ) ⇐⇒ P ; (P ∨ P ) ⇐⇒ P. 3. Commutativity: (P ∧ Q) ⇐⇒ (Q ∧ P ); (P ∨ Q) ⇐⇒ (Q ∨ P ). 4. Associativity: [(P ∧ Q) ∧ R] ⇐⇒ [P ∧ (Q ∧ R)]; [(P ∨ Q) ∨ R] ⇐⇒ [P ∨ (Q ∨ R)]. 5. Distributivity: [P ∨ (Q ∧ R)] ⇐⇒ [(P ∨ Q) ∧ (P ∨ R)]; [P ∧ (Q ∨ R)] ⇐⇒ [(P ∧ Q) ∨ (P ∧ R)]. 6. De Morgan’s laws: ℸ(P ∨ Q) ⇐⇒ (ℸP ∧ ℸQ); ℸ(P ∧ Q) ⇐⇒ (ℸP ∨ ℸQ). 7. Transitivity of the implication: [(P =⇒ Q) ∧ (Q =⇒ R)] =⇒ (P =⇒ R). Remark 1.3. 1. The statement ℸ(P =⇒ Q) ⇐⇒ (P ∧ ℸQ) is a tautology. In fact, ℸ(P =⇒ Q) ⇐⇒ ℸ(ℸP ∨ Q) ⇐⇒ ℸ(ℸP ) ∧ ℸQ ⇐⇒ P ∧ ℸQ. 2. As ∧ is commutative, the equivalence is also commutative, i.e., [P ⇐⇒ Q] ⇐⇒ [Q ⇐⇒ P ] is a tautology. Proposition 1.3. Let P and Q be two statements. 1. (P ∧ Q) =⇒ P is a tautology. 2. If Q is true, then (P ∧ Q) ⇐⇒ P is a tautology. 3. P =⇒ (P ∨ Q) is a tautology. 4. If Q is false, then (P ∨ Q) ⇐⇒ P is a tautology. 4 Proof. 1. P Q P ∧ Q (P ∧ Q) =⇒ P T T T T T F F T F T F T F F F T 2. When Q is true, the two statements P and P ∧ Q have the same truth value, hence, (P ∧ Q) ⇐⇒ P is always true. Proposition 1.4. Let P , Q and R be three statements. The following statements are tautologies: 1. Contraposition: (P =⇒ Q) ⇐⇒ (ℸQ =⇒ ℸP ). 2. [(P ⇐⇒ Q) ∧ (Q ⇐⇒ R)] =⇒ (P ⇐⇒ R). 3. [P ⇐⇒ Q] ⇐⇒ [ℸP ⇐⇒ ℸQ]. Proof. 1. (P =⇒ Q) ⇐⇒ (ℸP ∨ Q) ⇐⇒ (Q ∨ ℸP ) ⇐⇒ [ℸ(ℸQ) ∨ ℸP ] ⇐⇒ (ℸQ =⇒ ℸP ). 2. h   i [(P ⇐⇒ Q) ∧ (Q ⇐⇒ R)] =⇒ (P =⇒ Q) ∧ (Q =⇒ P ) ∧ (Q =⇒ R) ∧ (R =⇒ Q) h   i =⇒ (P =⇒ Q) ∧ (Q =⇒ R) ∧ (R =⇒ Q) ∧ (Q =⇒ P )   =⇒ (P =⇒ R) ∧ (R =⇒ P ) =⇒ (P ⇐⇒ R). 3.   [P ⇐⇒ Q] ⇐⇒ (P =⇒ Q) ∧ (Q =⇒ P )   ⇐⇒ (ℸQ =⇒ ℸP ) ∧ (ℸP =⇒ ℸQ) ⇐⇒ [ℸQ ⇐⇒ ℸP ]. 5 2 Some methods of proof Direct proof: To show that the implication P =⇒ Q is true, assume P is true and show that Q is true. Example 2.1. Show that if a, b ∈ Q then a + b ∈ Q. p p′ Take a, b ∈ Q. Then, ∃ p, p′ ∈ Z, q, q ′ ∈ N∗ such that a = and b = ′. Hence, q q p p′ pq ′ + qp′ a+b= + ′ =. q q qq ′ As the numerator pq ′ + qp′ is an element of Z and the denominator qq ′ is an element of p′′ N∗ , then a + b is of the form ′′ with p′′ ∈ Z and q ′′ ∈ N∗. Thus, a + b ∈ Q. q Proof by contraposition: To show that the implication P =⇒ Q is true, we show that its contrapositive ℸQ =⇒ ℸP is true since (P =⇒ Q) ⇐⇒ (ℸQ =⇒ ℸP ) is a tautology. Example 2.2. Let x ∈ Z. Show that if x2 is even, then x is also even. By contraposition, show that if x is odd then x2 is also odd. Suppose that x is odd. Then x is of the form 2k + 1 where k ∈ Z. Then x2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1. Set p = 2k 2 + 2k ∈ Z. We get x2 = 2p + 1 where p ∈ Z and then x2 is odd. Proof by contradiction: To prove that a statement Q is true, we suppose it is false (i.e., that the negation of Q is true) and we look for a contradiction of the type R ∧ ℸR. Then the statement Q is true. Example 2.3. Prove there does not exist a smallest strictly positive real number. By contradiction, suppose there exists a smallest strictly positive real number x. x x x Consider the real number. We have > 0 and < x. We then have a strictly positive 2 2 2 real number and strictly smaller than x. This is a contradiction with the fact that x is the smallest strictly positive real number. Hence, there does not exist a smallest strictly positive real number. 3 Sets Definition 3.1. A set is an unordered collection of distinct objects called elements or members. Remark 3.1. 1. We admit being able to decide whether or not an object is an element of a set: if an element x belongs to a set A, we write “x ∈ A”; otherwise we write “x ̸∈ A”. 2. For any set S, we can never write S ∈ S. Example 3.1. 1. N is the set of all natural numbers N = {0, 1, 2, 3,...}. 6  2. Z is the set of all integers Z = {... , −3, −2, −1, 0, 1, 2, 3,...}. p , where p ∈ Z and q ∈ N∗.
3. Q is the set of all rational numbers of the form q 4. R is the set of all real numbers. We have: 5 5 3 ∈ N, 3 ∈ Z, 3 ∈ Q, 3 ∈ R, −2 ∈ Z, −2 ∈ / N, ∈ Q, ∈ / Z, π ∈ R, π ∈ / Q. 2 2 A set A can be defined in two different ways: Extensionally: when we write the elements of A between braces such that two consecutive elements are separated by a comma. The order in which the elements are listed does not matter. Intensionally: when we define the elements of A out of a property P that all and only all its members verify. We write A = {x/ P (x)} which is read “A is the set of all the elements x satisfying the property P ”. The property P is called the characteristic property of A. Example 3.2. The set A of all natural numbers between  1 and 7 can be written in two ways: A = {1, 2, 3, 4, 5, 6, 7} (extensionally) or A = x ∈ N /1 ≤ x ≤ 7 (intensionally). Definition 3.2. A singleton (respectively doubleton, respectively tripleton) is a set consisting of exactly one element (respectively two distinct elements, respectively three distinct elements). 4 Quantifiers Definition 4.1. A predicate is a mathematical assertion containing letters called vari- ables such that when we replace each of these variables by a given element of a set, we obtain a statement. Example 4.1. P (n) : “n is a multiple of 2” is a predicate such that P (10) is true but P (11) is false. Out of predicates and the quantifiers “for all” and “there exists”, we can construct new statements, called quantified statements. Definition 4.2. Let P (x) be a predicate defined on a set A. 1. The universal quantifier “for all”, denoted by “∀ ”, allows us to define the quantified statement “∀ x ∈ A, P (x)” which is read as “for every element x of A, we have P (x)”. 7  2. The existential quantifier “there exists”, denoted by “∃”, allows us to define the quantified statement “∃ x ∈ A/ P (x)” which is read as “there exists an element x of A such that we have P (x)”. Proposition 4.1. 1. ℸ[∀ x ∈ A, P (x)] ⇐⇒ [∃ x ∈ A / (ℸP )(x)]. 2. ℸ[∃ x ∈ A / P (x)] ⇐⇒ [∀ x ∈ A, (ℸP )(x)]. Remark 4.1. To prove that a statement of the type 1. “∀ x ∈ A, P (x)” is true, it suffices to show that for every element x of A, P (x) is true. For example, ∀ n ∈ N, (n + 3)n ≥ 0 is true. In fact, let n ∈ N, then n ≥ 0 and n + 3 ≥ 0 so n(n + 3) ≥ 0 then the property “(n + 3)n ≥ 0 ” is true for every n ∈ N. 2. “∃ x ∈ A / P (x)” is true, it suffices to find one element x of A, such that P (x) is true. √ √ For example, ∃ x ∈ R / x2 = 3 is true since ∃ x = 3 ∈ R; x2 = ( 3)2 = 3. 3. “∀ x ∈ A, P (x)” is false, it suffices to show that its negation “∃ x ∈ A / (ℸP )(x)” is true, i.e., it suffices to find one element x of A, such that P (x) is false. Any such element x is called a counter-example. For example, ∀ n ∈ N, (n − 3)n > 0 is false as ∃ n = 2 ∈ N; (n − 3)n = (2 − 3) × 2 = −2 ≤ 0. 4. “∃ x ∈ A / P (x)” is false, we either proceed by contradiction, or we prove that its negation “∀ x ∈ A, (ℸP )(x)” is true. For example, ∃ x ∈ Q / x2 = 3 is false since, by contradiction, suppose that it is 2 2 true, i.e., there exists x ∈ Q√that verifies √ x = 3. But the equation x = 3 has only two solutions that are 3 and − 3 and these two solutions are not in Q, contradiction. Another example: ∃ x ∈ R / x2 < 0 is false as its negation ∀ x ∈ R, x2 ≥ 0 is true. Remark 4.2. 1. If there exists a unique element x of A for which the property P (x) is true, we can write “∃! x ∈ A/ P (x)” (the symbol “!” indicates the uniqueness). For example, the statement “∃! x ∈ R/ x3 = 8” is true. 2. We can interchange two universal quantifiers or two existential quantifiers without changing the meaning. However, we cannot a priori interchange a universal quantifier with an existential quantifier. Definition 4.3. The empty set is a set that has no elements and is denoted by “∅”. Thus, the quantified statement “∃ x/ x ∈ ∅” is false so its negation “∀ x, x ∈ / ∅” is true. Remark 4.3. The notation {∅} doesn’t have the same meaning as ∅. ∅ describes a set that contains nothing while {∅} describes a set that contains one single element which is the empty set. 8 5 Subsets and power set Definition 5.1. Let A and B be two sets. We say that A is a subset of B (or A is contained in B) and we write “A ⊆ B” if every element of A is an element of B. Hence, (A ⊆ B) ⇐⇒ [∀ x, (x ∈ A =⇒ x ∈ B)]. If A is contained in B, we also say that B contains A and we write “B ⊇ A”. If A is not contained in B then we write “A ̸⊆ B”. Hence, A ̸⊆ B ⇐⇒ [∃ x / x ∈ A ∧ x ∈ / B]. B A Remark 5.1. To show that A ⊆ B, we choose an arbitrary element x and we show (x ∈ A =⇒ x ∈ B), i.e., IF x ∈ A THEN x ∈ B. Example 5.1. 1. N ⊆ Z ⊆ Q ⊆ R. 2. {−1, 6} ⊆ Z as −1 ∈ Z and 6 ∈ Z. 3. {0, π} ̸⊆ Q as ∃ x = π; x ∈ {0, π} but x ̸∈ Q. Remark 5.2. For any set A, we have ∅ ⊆ A and A ⊆ A. Proposition 5.1. Let A, B and C be three sets. If A ⊆ B and B ⊆ C then A ⊆ C (this is the transitivity of the inclusion). Proof. Suppose that A ⊆ B and B ⊆ C. Show that A ⊆ C. A⊆B B⊆C Let x ∈ A =⇒ x ∈ B =⇒ x ∈ C. Thus, A ⊆ C. Definition 5.2. 1. Two sets A and B are said to be equal and we write “A = B” if and only if they have the same elements. Otherwise, A and B are said to be distinct and we write “A ̸= B”. Thus, A = B ⇐⇒ [∀ x, (x ∈ A ⇐⇒ x ∈ B)] ⇐⇒ [(A ⊆ B) and (B ⊆ A)].   A ̸= B ⇐⇒ [∃ x; (x ∈ A and x ̸∈ B)] or [∃ x; (x ∈ B and x ̸∈ A)]. 2. We say that a set A is strictly contained in a set B and we write “A ⊊ B” if A ⊆ B and A ̸= B. Hence, we have   A ⊊ B ⇐⇒ (A ⊆ B) and [∃ y; (y ∈ B and y ∈ / A)]. Remark 5.3. A ̸= ∅ ⇐⇒ ∃ x/ x ∈ A. 9 Definition 5.3. Let A be a set. The sets ∅ and A are called the trivial subsets of A. Every subset of A that is different from ∅ and A is called a nontrivial subset of A. Every subset of A distinct from A is called a proper subset of A. Definition 5.4. Let A be a set. The power set of A, denoted by “P(A)”, is the set of all the subsets of A. Thus, P(A) = {X / X ⊆ A}.  Example 5.2. 1. If A = {a}, then P(A) = ∅, {a}.  2. If A = {a, b}, then P(A) = ∅, {a}, {b}, {a, b}. Remark 5.4. 1. X ∈ P(A) ⇐⇒ X ⊆ A. 2. a ∈ A ⇐⇒ {a} ⊆ A ⇐⇒ {a} ∈ P(A). 3. ∅ ∈ P(A) and A ∈ P(A). Hence, P(A) ̸= ∅. Proposition 5.2. Let A and B be two sets. We have: A ⊆ B ⇐⇒ P(A) ⊆ P(B). Proof. =⇒? Suppose that A ⊆ B. Show that P(A) ⊆ P(B). A⊆B Let X ∈ P(A) =⇒ X ⊆ A =⇒ X ⊆ B =⇒ X ∈ P(B). ⇐=? Suppose that P(A) ⊆ P(B). Show that A ⊆ B. We have A ∈ P(A). As P(A) ⊆ P(B), we get A ∈ P(B) and then A ⊆ B. 6 Operations on sets Definition 6.1. Let A and B be two sets. 1. The intersection of A and B, denoted by “A ∩ B”, is the set of the elements that belong to both A and B. Hence, we have A ∩ B = {x/ x ∈ A and x ∈ B} and x ∈ A ∩ B ⇐⇒ [x ∈ A and x ∈ B]. A B 2. If A ∩ B = ∅, then A and B are said to be disjoint. 10  3. The union of A and B, denoted by “A ∪ B”, is the set of the elements that belong to A or B. Hence, A ∪ B = {x/ x ∈ A or x ∈ B} and x ∈ A ∪ B ⇐⇒ [x ∈ A or x ∈ B]. A B Example 6.1. 1. {x ∈ Z/ x < 0} ∩ {x ∈ Z/ − 3 < x ≤ 4} = {x ∈ Z/ − 3 < x < 0} = {−2, −1}. 2. {x ∈ Z/ x < 0} ∪ {x ∈ Z/ − 3 < x ≤ 4} = {x ∈ Z/ x ≤ 4}. Proposition 6.1. Let A, B, C and D be four sets. We have the following properties: 1. A ∩ B ⊆ A and A ∩ B ⊆ B. 2. A ⊆ A ∪ B, B ⊆A∪B and A ∩ B ⊆ A ∪ B. 3. Idempotence: A ∩ A = A and A ∪ A = A. 4. Commutativity: A ∩ B = B ∩ A and A ∪ B = B ∪ A. 5. Associativity: A ∩ (B ∩ C) = (A ∩ B) ∩ C and A ∪ (B ∪ C) = (A ∪ B) ∪ C. 6. Distributivity of ∩ over ∪: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Distributivity of ∪ over ∩: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). 7. A ∩ ∅ = ∅ ∩ A = ∅ and A ∪ ∅ = ∅ ∪ A = A. 8. If A ⊆ B and C ⊆ D then A ∩ C ⊆ B ∩ D and A ∪ C ⊆ B ∪ D. 9. [A ⊆ B ⇐⇒ A ∩ B = A] and [A ⊆ B ⇐⇒ A ∪ B = B]. Proof. 1. Show that A ∩ B ⊆ A: x ∈ A ∩ B =⇒ [x ∈ A and x ∈ B] =⇒ x ∈ A. 2. Show that A ⊆ A ∪ B: x ∈ A =⇒ [x ∈ A or x ∈ B] =⇒ x ∈ A ∪ B. 4. Commutativity: x ∈ A ∩ B ⇐⇒ x ∈ A and x ∈ B ⇐⇒ x ∈ B and x ∈ A (as “and” is commutative) ⇐⇒ x ∈ B ∩ A. 11  6. Distributivity of ∩ over ∪: x ∈ A ∩ (B ∪ C) ⇐⇒ x ∈ A and x ∈ B ∪ C ⇐⇒ x ∈ A and (x ∈ B or x ∈ C) ⇐⇒ (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C) (“and” distr. over “or”) ⇐⇒ (x ∈ A ∩ B) or (x ∈ A ∩ C) ⇐⇒ x ∈ (A ∩ B) ∪ (A ∩ C). 7. Show that A ∩ ∅ = ∅ ∩ A = ∅. We have A ∩ ∅ = ∅ ∩ A, as ∩ is commutative. It remains to show that ∅ ∩ A = ∅. By contradiction, suppose that ∅ ∩ A ̸= ∅ =⇒ ∃ x; x ∈ ∅ ∩ A =⇒ ∃ x; x ∈ A and x ∈ ∅ =⇒ ∃ x; x ∈ ∅: contradiction. Therefore, A ∩ ∅ = ∅. Show that A ∪ ∅ = ∅ ∪ A = A. We have A ∪ ∅ = ∅ ∪ A, as ∪ is commutative. It remains to show that ∅ ∪ A = A. x ∈ ∅ ∪ A ⇐⇒ [x ∈ ∅ or x ∈ A] ⇐⇒ x ∈ A (as x ∈ ∅ is false). 8. Prove that if A ⊆ B and C ⊆ D then A ∩ C ⊆ B ∩ D. Suppose that A ⊆ B and C ⊆ D. Prove that: A ∩ C ⊆ B ∩ D. A⊆B and C⊆D x ∈ A ∩ C =⇒ x ∈ A and x ∈ C =⇒ x ∈ B and x ∈ D =⇒ x ∈ B ∩ D. 9. Show that A ⊆ B ⇐⇒ A ∩ B = A. =⇒? Suppose that A ⊆ B. Prove that A ∩ B = A. We always have A ∩ B ⊆ A. We still need to prove A ⊆ A ∩ B. x ∈ A =⇒ [x ∈ A and x ∈ B (as A ⊆ B)] =⇒ x ∈ A ∩ B. ⇐=? Suppose that A ∩ B = A. Show that A ⊆ B. We know that A ∩ B ⊆ B. Thus, the hypothesis A ∩ B = A gives that A ⊆ B. Prove that A ⊆ B ⇐⇒ A ∪ B = B. =⇒? Suppose that A ⊆ B. Prove that A ∪ B = B. We always have B ⊆ A ∪ B. Prove A ∪ B ⊆ B: let x ∈ A ∪ B =⇒ x ∈ A or x ∈ B. We have two cases: If x ∈ B, we are done. If x ∈ A, as A ⊆ B, then x ∈ B. ⇐=? We always have A ⊆ A ∪ B. As A ∪ B = B, then A ⊆ B. Definition 6.2. Let S be a set and A ⊆ S. The relative complement of A with respect to S, denoted by “∁S A” or “A”, is the set of all the elements of S that are not in A. Hence, we have ∁S A = A = {x ∈ S / x ∈ / A} and x ∈ ∁S A ⇐⇒ [x ∈ S and x ̸∈ A]. 12  S A Example 6.2. Let S = {1, 2, 3, 4, 5, 6, 7}, T = {1, 2, 3, 4} and A = {2, 3, 4} (note that A ⊆ S and A ⊆ T ). We have ∁S A = {1, 5, 6, 7} and ∁T A = {1}. Proposition 6.2. Let A and B be two subsets of a set S. We have:
1. ∁S ∁S A = A. 2. A ⊆ B ⇐⇒ ∁S B ⊆ ∁S A. 3. ∁S S = ∅ and ∁S ∅ = S. 4. A ∪ ∁S A = S and A ∩ ∁S A = ∅. 5. De Morgan’s Laws: ∁S (A ∪ B) = ∁S A ∩ ∁S B and ∁S (A ∩ B) = ∁S A ∪ ∁S B.
Proof. 1. Show ∁S ∁S A = A:
x ∈ ∁S ∁S A ⇐⇒ x ∈ S and x ̸∈ ∁S A ⇐⇒ x ∈ S and (x ̸∈ S or x ∈ A) dist. ⇐⇒ (x ∈ S and x ̸∈ S) or (x ∈ S and x ∈ A) | {z } contradiction ⇐⇒ x ∈ S and x ∈ A ⇐⇒ x ∈ S ∩ A = A, as A ⊆ S. 2. See the exercises. 3. Show that ∁S S = ∅. By contradiction, suppose ∁S S ≠ ∅. Then ∃ x / x ∈ ∁S S =⇒ x ∈ S and x ̸∈ S: contradiction. Thus, ∁S S = ∅. Now we show that ∁S ∅ = S.
1. We already have ∁S S = ∅ =⇒ ∁S ∁S S = ∁S ∅ =⇒ S = ∁S ∅. 4. Show that A ∪ ∁S A = S. For this, we prove that A ∪ ∁S A ⊆ S and S ⊆ A ∪ ∁S A. [A ⊆ S and ∁S A ⊆ S] =⇒ A ∪ ∁S A ⊆ S. Let x ∈ S. We have two cases: – If x ∈ A, then x ∈ A ∪ ∁S A. – If x ̸∈ A, as x ∈ S, then x ∈ ∁S A. Hence, x ∈ A ∪ ∁S A. 13  Show that A ∩ ∁S A = ∅. By contradiction, suppose that A ∩ ∁S A ̸= ∅ =⇒ ∃ x; x ∈ A ∩ ∁S A =⇒ ∃ x; x ∈ A and x ∈ ∁S A =⇒ ∃ x; x ∈ A and x ̸∈ A: contradiction. 5. Prove that ∁S (A ∪ B) = ∁S A ∩ ∁S B: x ∈ ∁S (A ∪ B) ⇐⇒ x ∈ S and x ̸∈ A ∪ B ⇐⇒ x ∈ S and (x ̸∈ A and x ̸∈ B) idem. ⇐⇒ (x ∈ S and x ∈ S) and (x ̸∈ A and x ̸∈ B) ass. and com. ⇐⇒ (x ∈ S and x ̸∈ A) and (x ∈ S and x ̸∈ B) ⇐⇒ x ∈ ∁S A and x ∈ ∁S B ⇐⇒ x ∈ ∁S A ∩ ∁S B. Prove that ∁S (A ∩ B) = ∁S A ∪ ∁S B: x ∈ ∁S (A ∩ B) ⇐⇒ x ∈ S and x ̸∈ A ∩ B ⇐⇒ x ∈ S and (x ̸∈ A or x ̸∈ B) dist. ⇐⇒ (x ∈ S and x ̸∈ A) or (x ∈ S and x ̸∈ B) ⇐⇒ x ∈ ∁S A or x ∈ ∁S B ⇐⇒ x ∈ ∁S A ∪ ∁S B. Definition 6.3. Let A and B be two sets. The difference of A and B, denoted by “A \ B” or “A − B”, is the set of the elements that belong to A but not to B. Thus, A \ B = A − B = {x/ x ∈ A and x ∈ / B}. A B Example 6.3. 1. We have N∗ = N − {0} and Z∗ = Z − {0}. 2. Let A = {2, 3, 4, 5} and B = {1, 2, 4, 6}. We have A − B = {x/ x ∈ A and x ∈ / B} = {3, 5}. Remark 6.1. Let A and B be subsets of a set S. Then 1. ∁S A = S − A. 2. A − B = A ∩ ∁S B. Definition 6.4. 1. An ordered pair is an ordered object of the form (x, y) such that (x, y) = (x′ , y ′ ) ⇐⇒ [ x = x′ and y = y ′ ]. 14  2. Let n be an integer such that n ≥ 2. An n-tuple is an object of the form (x1 , x2 ,... , xn ) where (x1 , x2 ,... , xn ) = (y1 , y2 ,... , yn ) ⇐⇒ [ ∀ i ∈ {1,... , n}, xi = yi ]. For any two distinct elements x and y corresponds a unique doubleton which is the set {x, y}, but two different ordered pairs: (x, y) and (y, x). Definition 6.5. 1. The cartesian product of two sets A and B, denoted by “A×B ”, is the set of all pairs (x, y), where x ∈ A and y ∈ B. Then, A × B = {(x, y) / x ∈ A and y ∈ B}. 2. The cartesian product of n sets A1 , A2 ,... , An , denoted by “A1 ×A2 ×...×An ”, is the set of all the n-tuples (x1 , x2 ,... , xn ), where x1 ∈ A1 , x2 ∈ A2 ,... , and xn ∈ An. Therefore,   A1 × A2 ×... × An = (x1 , x2 ,... , xn ) x1 ∈ A1 , x2 ∈ A2 ,... , xn ∈ An. n | ×A× In particular, if A is a set, then A {z· · · × A} is denoted by “A ”. n times  Example 6.4. If A = {1, 2} and B = {a, {b}}, then A×B = (1, a), (1, {b}), (2, a), (2, {b}). Remark 6.2. Let A and B be two sets. We have: A × B = ∅ ⇐⇒ [A = ∅ or B = ∅]. ℸ[A = ∅ or B = ∅] ⇐⇒ [A ̸= ∅ and B ̸= ∅] ⇐⇒ [∃ x ∈ A and ∃ y ∈ B] ⇐⇒ [∃ (x, y) ∈ A × B] ⇐⇒ A × B ̸= ∅ ⇐⇒ ℸ[A × B = ∅]. 7 Intersection and union of a family of sets Let I be a non-empty set. If for every i ∈ I, we associate a set Ai , then the set {Ai ; i ∈ I} is called a family of sets indexed by I and will be denoted by (Ai )i∈I. Definition 7.1. Let (Ai )i∈I be a family of sets indexed by I. \ 1. The intersection of the family (Ai )i∈I , denoted by “ Ai ”, is the set of the i∈I elements that belong to each Ai. Consequently, \   \ Ai = x ∀ i ∈ I, x ∈ Ai and x∈ Ai ⇐⇒ (∀ i ∈ I, x ∈ Ai ). i∈I i∈I [ 2. The union of the family (Ai )i∈I , denoted by “ Ai ”, is the set of the elements i∈I that belong to at least one Ai. Hence, [   [ Ai = x ∃ i ∈ I, x ∈ Ai and x∈ Ai ⇐⇒ (∃ i ∈ I/ x ∈ Ai ). i∈I i∈I 15 Definition 7.2. Let S be a family of sets, i.e., a set whose elements are also sets. \ 1. The intersection of the family S, denoted by “ X”, is the set of the elements X∈S that belong to each X in S. We thus have \   \ X = x ∀ X ∈ S, x ∈ X and x∈ X ⇐⇒ (∀ X ∈ S, x ∈ X). X∈S X∈S [ 2. The union of the family S, denoted by “ X”, is the set of the elements that X∈S belong to at least one X in S. Hence, [   [ X = x ∃ X ∈ S, x ∈ X and x∈ X ⇐⇒ (∃ X ∈ S; x ∈ X). X∈S X∈S Example 7.1. \ [ I = {1, 2, 3, 4} and define Ai = {i, 2i, 3i, 4i,... }. 1. Let Find Ai and Ai. i∈I i∈I We have A1 = {1, 2, 3, 4,... }, A2 = {2, 4, 6, 8,... }, A3 = {3, 6, 9, 12,... } and A4 = {4, \ 8, 12, 16,... }.     Thus, Ai = x ∀ i ∈ I, x ∈ Ai = x x ∈ A1 and x ∈ A2 and x ∈ A3 and x ∈ A4 \i∈I then, Ai = {12, 24, 36, 48,... }. i∈I [ Ai = x ∃ i ∈ I, x ∈ Ai = x x ∈ A1 or x ∈ A2 or x ∈ A3 or x ∈ A4 = N∗.     Also, i∈I \ S = {A, B, C, D} be a familyofsets, i.e., A, B, C and D are sets. We have 2. Let X = x ∀ X ∈ S, x ∈ X = x x ∈ A and x ∈ B and x ∈ C and x ∈ D. X∈S \ Thus, X = A ∩ B ∩ C ∩ D. X∈S [     Also, X = x ∃ X ∈ S, x ∈ X = x x ∈ A or x ∈ B or x ∈ C or x ∈ D. X∈S [ Hence, X = A ∪ B ∪ C ∪ D. X∈S 16  Chapter 2: Mappings 1 Correspondences and mappings Let A and B be two non-empty sets. Definition 1.1. A correspondence C from A to B is an ordered triple (A, B, G), where G ⊆ A × B. A is called the domain, B the codomain and G the graph of C. If (x, y) ∈ G, we say that the element y corresponds to the element x of A by C. Remark 1.1. For any correspondence (A, B, G), an element of A can have zero, one or multiple elements of B that correspond to it. Example 1.1. Consider the correspondence (Z, R, G), where G = {(x, y) ∈ Z×R / y 2 = x}. The element −2 ∈ Z has no corresponding element in the codomain while 1 ∈ Z has two corresponding elements which are 1 and −1. Definition 1.2. A mapping or a function or simply a map f from A to B is a correspondence f = (A, B, G) such that for every x of A corresponds a unique element y of B, i.e., ∀ x ∈ A, ∃ ! y ∈ B/ (x, y) ∈ G. The unique element y of B that corresponds to the element x of A is called the image of x by f and is written as “y = f (x)”. Moreover, x is called a preimage or an inverse image of y. Thus, y = f (x) ⇐⇒ (x, y) ∈ G, 
and G = x, f (x) / x ∈ A. A mapping f is usually denoted by f f : A −→ B A −→ B or x 7−→ f (x) x 7−→ f (x). Remark 1.2. 1. A correspondence f from A to B is a mapping if and only if (i) for every element of A corresponds an element of B, (ii) for every two equal elements of A correspond two equal elements of B (unique- ness of the image), i.e., ∀ x, x′ ∈ A, x = x′ =⇒ f (x) = f (x′ ). 2. The set of all the mappings from A to B is denoted by “B A ”. 1 Example 1.2. 1. The correspondence defined in Example 1.1 is not a mapping as −2 has no image (or 1 has two different images). 2. The correspondence IdA : A −→ A x 7−→ x is a mapping since ∀ x ∈ A, x has an image in A which is x itself, and ∀ x, x′ ∈ A, x = x′ =⇒ IdA (x) = IdA (x′ ). IdA is called the identity mapping of A. 3. The two correspondences pr1 : A × B −→ A pr2 : A × B −→ B and (x, y) 7−→ x (x, y) 7−→ y are two mappings that are respectively called the first projection and the second projection of the cartesian product A × B. Definition 1.3. Let f : A −→ B be a mapping. The image or range of f is the subset of B consisting of all the images of the elements of A and is denoted by “Imf ”. Hence,   Imf = f (x) / x ∈ A = y ∈ B/ ∃ x ∈ A, y = f (x) and y ∈ Imf ⇐⇒ ∃ x ∈ A; y = f (x). Definition 1.4. Two mappings f : A −→ B and g : A′ −→ B ′ are equal if A = A′ , B = B ′ and ∀ x ∈ A, f (x) = g(x). Example 1.3. The two mappings f : R −→ R g : R −→ R and x 7−→ f (x) = cos(x) x 7−→ g(x) = 2 cos2 (x/2) − 1 are equal since f and g have same domain (which is R), same codomain (which is R), and ∀ x ∈ R, f (x) = g(x). Definition 1.5. Let f : A −→ B be a mapping and X be a subset of A. The restriction of f to X is the mapping denoted by “f ” and defined on X by X f : X −→ B X x 7−→ f (x) = f (x). X Example 1.4. Consider f : R −→ R h : R+ −→ R and x 7−→ f (x) = x2 x 7−→ h(x) = x2. Then f = h. R+ 2 2 Composition of mappings Definition 2.1. Let f : A −→ B and g : B −→ C be two mappings such that the codomain of f is equal to the domain of g. f g A / B / @C g◦f The composite mapping of f and g is the mapping denoted by “g ◦ f ” and defined by g ◦ f : A −→ C x 7−→ g ◦ f (x) = g(f (x)). Note that the mapping f ◦ g is not defined unless C = A. Remark 2.1. If f, g ∈ AA , then the mappings f ◦ g and g ◦ f are both defined, but they are not equal in general. For example, consider f : R −→ R g : R −→ R and x 7−→ f (x) = x2 x 7−→ g(x) = 2x. We have g ◦ f : R −→ R f ◦ g : R −→ R and x 7−→ g ◦ f (x) = 2x2 x 7−→ f ◦ g(x) = 4x2 with g ◦ f ̸= f ◦ g since (g ◦ f )(1) ̸= (f ◦ g)(1). Proposition 2.1. For any mappings f : A −→ B, g : B −→ C and h : C −→ D, g /5 C ?B f h g◦f h◦g )/ A 8D h◦(g◦f ) (h◦g)◦f we have h ◦ (g ◦ f ) = (h ◦ g) ◦ f. We write h ◦ g ◦ f = h ◦ (g ◦ f ) = (h ◦ g) ◦ f. Proof. The two mappings h ◦ (g ◦ f ) and (h ◦ g) ◦ f have same domain A and same codomain D. In addition, we have:



∀ x ∈ A, h◦(g ◦f ) (x) = h (g ◦f )(x) = h g(f (x)) = (h◦g)(f (x)) = (h◦g)◦f (x). Remark 2.2. 1. If f : A −→ A is a mapping, we can define f ◦ f which is denoted by f 2. Moreover, we can define f ◦ f ◦ f which is denoted by f 3 and so on. In general, for any positive integer n > 0, we have fn = f ◦ f ◦ · · · ◦ f | {z } n times n and f : A −→ A. 3  2. For any mapping f : A −→ B, we have f ◦ IdA = f and IdB ◦ f = f. IdA f f IdB A / A / / / @B A B @B f ◦IdA IdB ◦f In fact, ˆ ∀ x ∈ A, (f ◦ IdA )(x) = f IdA (x) = f (x). Thus, f ◦ IdA = f.
ˆ ∀ x ∈ A, (IdB ◦ f )(x) = IdB f (x) = f (x). Thus, IdB ◦ f = f.
3 Surjection and injection Definition 3.1. A mapping f : A −→ B is said to be 1. surjective or a surjection if every element of the codomain B has at least one preimage by f in the domain A, i.e., if ∀ y ∈ B, the equation y = f (x) has at least one solution x in A. In other words, ∀ y ∈ B, ∃ x ∈ A / y = f (x). 2. injective or an injection if every element of the codomain B has at most one preimage by f in the domain A, i.e., if ∀ y ∈ B, the equation y = f (x) has at most one solution in A. Hence, f is injective if and only if ∀ x, x′ ∈ A, f (x) = f (x′ ) =⇒ x = x′. Remark 3.1. Let f : A −→ B be a mapping. 1. f is not surjective ⇐⇒ ∃ y ∈ B / ∀ x ∈ A, y ̸= f (x). 2. f is not injective ⇐⇒ ∃ x, x′ ∈ A / f (x) = f (x′ ) but x ̸= x′. Example 3.1. 1. For any set A, the identity mapping IdA is surjective as ∀ y ∈ A, ∃ x = y ∈ A such that IdA (x) = x = y. It is also injective since ∀ x, x′ ∈ A, IdA (x) = IdA (x′ ) =⇒ x = x′. 2. Let A and B be two non-empty sets. The first projection pr1 : A × B −→ A (x, y) 7−→ pr1 (x, y) = x is surjective. In fact, as B ̸= ∅, then ∃ y0 ∈ B. Thus, ∀ a ∈ A, ∃ (x, y) = (a, y0 ) ∈ A × B / pr1 (x, y) = x = a. Consequently, pr1 is surjective. Similarly, we show that the second projection pr2 is surjective. 4  3. Let X ⊆ A. The mapping i : X −→ A x 7−→ i(x) = x is injective since ∀ x, x′ ∈ X, i(x) = i(x′ ) =⇒ x = x′. This mapping is called the canonical injection of the subset X into A. 4. The mapping f : Z −→ N x 7−→ f (x) = |x| is surjective as ∀ n ∈ N, ∃ x = n ∈ Z; f (x) = |x| = |n| = n. But it is not injective as ∃ x = 1 ∈ Z and ∃ x′ = −1 ∈ Z such that f (x) = 1 = f (x′ ) but x ̸= x′. 5. The mapping f : R+ −→ R x 7−→ f (x) = x2 is injective since ∀ x, x′ ∈ R+ , f (x) = f (x′ ) =⇒ x2 = (x′ )2 =⇒ x = x′ or ′ | ={z−x} x =⇒ x = x′. impossible as x, x′ ≥ 0 However, it is not surjective as ∃ y = −1 ∈ R such that ∀ x ∈ R+ , f (x) = x2 ̸= −1. Proposition 3.1. A mapping f : A −→ B is surjective if and only if Imf = B. Proof. =⇒? Suppose that f is surjective. Show that Imf = B. We have Imf ⊆ B. It remains to show that B ⊆ Imf. Let y ∈ B. As f is surjective, ∃ x ∈ A; y = f (x), and then y ∈ Imf. ⇐=? Suppose that Imf = B. Show that f is surjective. Let y ∈ B. Then y ∈ Imf , so ∃ x ∈ A such that y = f (x), giving that f is surjective. Remark 3.2. Given a mapping f : A −→ B, the mapping g defined by g : A −→ Im f x 7−→ g(x) = f (x) is surjective. Indeed, by definition of Im f , we have ∀ y ∈ Imf, ∃ x ∈ A / y = f (x). But g has same definition as f , then ∀ y ∈ Imf, ∃ x ∈ A / y = g(x). This mapping g is called the reduction of f to its image. Proposition 3.2. Let f : A −→ B and g : B −→ C be two mappings. 1. f and g surjective (resp. injective) =⇒ g ◦ f surjective (resp. injective). 2. g ◦ f surjective =⇒ g surjective. 3. g ◦ f injective =⇒ f injective. 5 Proof. f g A / B / @C g◦f 1. Suppose that f and g are surjective and show that g ◦ f is surjective, i.e., ∀ z ∈ C, ∃ x ∈ A such that z = (g ◦ f )(x). Let z ∈ C. As g is surjective, ∃ y ∈ B / z = g(y). For this y ∈ B and as f is surjective, ∃ x ∈ A / y = f (x). Hence, z = g(y) = g(f (x)) = (g ◦ f )(x). Suppose that f and g are injective and show that g ◦ f is injective, i.e., ∀ x, x′ ∈ A, (g ◦ f )(x) = (g ◦ f )(x′ ) =⇒ x = x′. Let x, x′ ∈ A. g inj f inj (g ◦ f )(x) = (g ◦ f )(x′ ) =⇒ g(f (x)) = g(f (x′ )) =⇒ f (x) = f (x′ ) =⇒ x = x′. 2. Suppose that g ◦ f is surjective. Show that g is surjective, i.e., ∀ z ∈ C, ∃ y ∈ B such that z = g(y). Let z ∈ C. Since g ◦ f is surjective, ∃ x ∈ A / z = (g ◦ f )(x) = g(f (x)). Therefore, ∃ y = f (x) ∈ B / z = g(y). 3. Suppose that g ◦ f is injective. Show that f is injective, i.e., ∀ x, x′ ∈ A, f (x) = f (x′ ) =⇒ x = x′. Let x, x′ ∈ A. g map. g◦f inj f (x) = f (x′ ) =⇒ g(f (x)) = g(f (x′ )) =⇒ (g ◦ f )(x) = (g ◦ f )(x′ ) =⇒ x = x′. Remark 3.3. g ◦ f can be surjective without having f surjective. Similarly, g ◦ f can be injective without having g injective. For instance, consider the mappings g : N −→ N ( n f : N −→ N and if n is even n 7−→ f (n) = 2n n 7−→ g(n) = 2 n if n is odd 2n For any n ∈ N, we have (g ◦ f )(n) = g(f (n)) = g(2n) = = n. Then g ◦ f = IdN. 2 Hence, g ◦ f is surjective. However, f is not surjective as 1 has no preimage by f. Moreover, g ◦ f is injective even though g is not, as ∃ x = 6 ∈ N and ∃ x′ = 3 ∈ N such that g(x) = 3 = g(x′ ) but x ̸= x′. g1 f / / Proposition 3.3. Let A B /C be three mappings. We have g2   g1 ◦ f = g2 ◦ f and f surjective =⇒ g1 = g2. 6 Proof. Suppose that g1 ◦ f = g2 ◦ f and that f is surjective. Prove that g1 = g2 , i.e., ∀ y ∈ B, g1 (y) = g2 (y). Let y ∈ B. As f is surjective, ∃ x ∈ A / y = f (x). Then, g1 (y) = g1 (f (x)) = (g1 ◦ f )(x) = (g2 ◦ f )(x) = g2 (f (x)) = g2 (y). f1 / g /C Proposition 3.4. Let A / B be three mappings. we have f2   g ◦ f1 = g ◦ f2 and g injective =⇒ f1 = f2. Proof. Suppose that g ◦ f1 = g ◦ f2 and that g is injective. Prove that f1 = f2. g ◦ f1 = g ◦ f2 =⇒ ∀ x ∈ A, (g ◦ f1 )(x) = (g ◦ f2 )(x) =⇒ ∀ x ∈ A, g(f1 (x)) = g(f2 (x)) g inj. =⇒ ∀ x ∈ A, f1 (x) = f2 (x). 4 Bijective mappings Definition 4.1. A mapping f is said to be bijective or a bijection if it is at the same time surjective and injective. Consequently, f bijective ⇐⇒ every element of the codomain B has a unique preimage by f in the domain A ⇐⇒ ∀ y ∈ B, the equation y = f (x) has a unique solution in A ⇐⇒ ∀ y ∈ B, ∃ ! x ∈ A / y = f (x). Definition 4.2. Let f : A −→ B be a bijection. The correspondence from B to A that associates to every element y of B the unique element x of A solution of the equation y = f (x) is a mapping called the inverse mapping or the inverse function or simply the inverse of f and is denoted by “f −1 ”. Therefore, f −1 : B −→ A y 7−→ f −1 (y) = x  y = f (x). The inverse mapping f −1 satisfies y = f (x) ⇐⇒ x = f −1 (y).   ∀ x ∈ A, ∀ y ∈ B, Proposition 4.1. The identity mapping of a set A is a bijection equal to its inverse. Proof. We have already proved that IdA is both injective and surjective and ∀ y ∈ A, ∃ ! x = y ∈ A such that IdA (x) = y. Thus, IdA is bijective with Id−1 A : A −→ A y 7−→ Id−1 A (y) = x = y. Therefore, Id−1 A = IdA. 7 Proposition 4.2. Let f : A −→ B be a bijection. f f −1 f −1 f A / B / / / @A B A @B f −1 ◦f f ◦f −1 We have f −1 ◦ f = IdA and f ◦ f −1 = IdB. Proof. We have y = f (x) ⇐⇒ x = f −1 (y).   ∀ x ∈ A, ∀ y ∈ B, Thus, y=f (x) ˆ ∀ x ∈ A, (f −1 ◦ f )(x) = f −1 (f (x)) = f −1 (y) = x = IdA (x). Then, f −1 ◦ f = IdA. x=f −1 (y) ˆ ∀ y ∈ B, (f ◦ f −1 )(y) = f (f −1 (y)) = f (x) = y = IdB (y). Then, f ◦ f −1 = IdB. Proposition 4.3. Let f : A −→ B and g : B −→ A be two mappings such that g◦f = IdA and f ◦ g = IdB. Then, f and g are bijective with g = f −1 and f = g −1. Proof. ˆ We have g ◦ f = IdA and f ◦ g = IdB.  g ◦ f = IdA =⇒ g ◦ f bij. =⇒ f inj. and g surj. =⇒ f and g bijective. f ◦ g = IdB =⇒ f ◦ g bij. =⇒ g inj. and f surj. ˆ f is bijective, so f −1 exists. We have f ◦ g = IdB =⇒ f −1 ◦ (f ◦ g) = f −1 ◦ IdB =⇒ (f −1 ◦ f ) ◦ g = f −1 =⇒ IdA ◦ g = f −1 =⇒ g = f −1. ˆ g is bijective, so g −1 exists. [g ◦ f = IdA and g ◦ g −1 = IdA ] =⇒ g ◦ f = g ◦ g −1 =⇒ f = g −1 , as g is injective. Corollary 4.1. If f : A −→ B is a bijective mapping, then the inverse mapping f −1 is bijective and (f −1 )−1 = f. Proof. We have f −1 ◦ f = IdA and f ◦ f −1 = IdB. By Proposition 4.3, f −1 is bijective and (f −1 )−1 = f. Proposition 4.4. Let f : A −→ B and g : B −→ C be two mappings. f g A / B / @C g◦f If f and g are bijective, then g ◦ f is bijective and (g ◦ f )−1 = f −1 ◦ g −1. 8 Proof. f and g bijective =⇒ f −1 and g −1 exist. g −1 f −1 C / B / @A h=f −1 ◦g −1 Set h = f −1 ◦ g −1. We have h : C −→ A and g ◦ f : A −→ C. ˆ (g ◦f )◦h = (g ◦f )◦(f −1 ◦g −1 ) = g ◦(f ◦f −1 ) ◦g −1 = (g ◦IdB )◦g −1 = g ◦g −1 = IdC.
ˆ h◦(g◦f ) = (f −1 ◦g −1 )◦(g◦f ) = f −1 ◦(g −1 ◦g) ◦f = (f −1 ◦IdB )◦f = f −1 ◦f = IdA.
By Proposition 4.3, we deduce that g ◦ f and h are bijective and that h = (g ◦ f )−1. 5 Direct and inverse images of subsets Definition 5.1. Let f : A −→ B be a mapping and let X ⊆ A. The direct image of the subset X under f is the subset of B consisting of the images of the elements of X and is denoted by “f (X)”. Hence,   f (X) = f (x)/ x ∈ X = y ∈ B/ ∃ x ∈ X, y = f (x) ⊆ B. Remark 5.1. 1. y ∈ f (X) ⇐⇒ ∃ x ∈ X/ y = f (x). 2. f (A) = Imf. 3. If a ∈ A, then f ({a}) = {f (a)}. In fact, f ({a}) = {f (x)/x ∈ {a}} = {f (x)/x = a} = {f (a)}. 4. If a ∈ A such that f (a) ∈ f (X), we do not necessarily have a ∈ X. Example 5.1. Consider the mapping f : R −→ R defined by f (x) = x2. ˆ If X = {2, 4}, then f (X) = {f (x)/x ∈ X} = {f (2), f (4)} = {4, 16}. Note that f (−2) = 4 ∈ f (X) but −2 ∈ / X. ˆ If X = {1}, then f (X) = {f (x)/x ∈ X} = {f (1)} = {1}. ˆ If X = {−2, −1, 1, 2}, then f (X) = {f (x)/x ∈ X} = {f (−2), f (−1), f (1), f (2)} = {1, 4}. Proposition 5.1. Let f : A −→ B be a mapping and let X and X ′ be two subsets of A. We have 1. f (X) = ∅ ⇐⇒ X = ∅. 2. X ⊆ X ′ =⇒ f (X) ⊆ f (X ′ ). 3. f (X ∪ X ′ ) = f (X) ∪ f (X ′ ). 4. f (X ∩ X ′ ) ⊆ f (X) ∩ f (X ′ ). 9 Proof. 1. =⇒? Suppose that f (X) = ∅ and show that X = ∅. By contradiction, suppose that X ̸= ∅, then ∃ x ∈ A / x ∈ X so ∃ y = f (x) ∈ f (X). Thus, f (X) ̸= ∅: contradiction. ⇐=? Suppose that X = ∅ and show that f (X) = ∅. By contradiction, suppose that f (X) ̸= ∅, so ∃ y ∈ B / y ∈ f (X) then ∃ x ∈ X / y = f (x) giving that X ̸= ∅: contradiction. 2. Suppose that X ⊆ X ′ and prove that f (X) ⊆ f (X ′ ). X⊆X ′ y ∈ f (X) =⇒ ∃ x ∈ X/ y = f (x) =⇒ ∃ x ∈ X ′ / y = f (x) =⇒ y ∈ f (X ′ ). Thus, f (X) ⊆ f (X ′ ). 3. Show that f (X ∪ X ′ ) = f (X) ∪ f (X ′ ). ⊆? y ∈ f (X ∪ X ′ ) =⇒ ∃ x ∈ X ∪ X ′ / y = f (x). ˆ If x ∈ X, then y = f (x) ∈ f (X) so y ∈ f (X) ∪ f (X ′ ). ˆ If x ∈ X ′ , then y = f (x) ∈ f (X ′ ) so y ∈ f (X) ∪ f (X ′ ). Therefore, f (X ∪ X ′ ) ⊆ f (X) ∪ f (X ′ ). ⊇? Prove that f (X) ∪ f (X ′ ) ⊆ f (X ∪ X ′ ). ) 2. X ⊆ X ∪ X′ =⇒ f (X) ⊆ f (X ∪ X ′ ) 2. =⇒ f (X)∪f (X ′ ) ⊆ f (X∪X ′ ). X′ ⊆ X ∪ X′ =⇒ f (X ′ ) ⊆ f (X ∪ X ′ ) 4. Show that f (X ∩ X ′ ) ⊆ f (X) ∩ f (X ′ ). ) 2. X ∩ X′ ⊆ X =⇒ f (X ∩ X ′ ) ⊆ f (X) 2. =⇒ f (X ∩ X ′ ) ⊆ f (X) ∩ f (X ′ ). X ∩ X′ ⊆ X′ =⇒ f (X ∩ X ′ ) ⊆ f (X ′ ) Proposition 5.2. Let f : A −→ B be a mapping  \  and\let (Xi )i∈I be a family of subsets [  [ of A. Then f Xi = f (Xi ) and f Xi ⊆ f (Xi ) i∈I i∈I i∈I i∈I Definition 5.2. Let f : A −→ B be a mapping and Y ⊆ B. The inverse image or preimage of the subset Y under f is the subset of A consisting of the preimages of the elements of Y and is denoted by “f −1 (Y )”. Hence, f −1 (Y ) = x ∈ A/ f (x) ∈ Y ⊆ A.  Remark 5.2. 1. The notation f −1 (Y ) does not assume that f is bijective. 2. x ∈ f −1 (Y ) ⇐⇒ f (x) ∈ Y. 3. f −1 (∅) = ∅, since if f −1 (∅) ̸= ∅ then ∃ x ∈ A / x ∈ f −1 (∅) so f (x) ∈ ∅: contradiction. 4. f −1 (Y ) can be empty, even if Y is not empty. 10 Example 5.2. Consider the mapping f : N −→ R defined by f (x) = x2. ˆ If Y = {2, 4}, then f −1 (Y ) = {x ∈ N / f (x) ∈ Y } = {x ∈ N / x2 = 2 or x2 = 4} = {2}. ˆ If Y = {−1}, then f −1 (Y ) = {x ∈ N / f (x) ∈ Y } = {x ∈ N / x2 = −1} = ∅. Proposition 5.3. Let f : A −→ B be a mapping and let Y and Y ′ be two subsets of B. We have: 1. f −1 (B) = A. 2. Y ⊆ Y ′ =⇒ f −1 (Y ) ⊆ f −1 (Y ′ ). 3. f −1 (Y ∪ Y ′ ) = f −1 (Y ) ∪ f −1 (Y ′ ). 4. f −1 (Y ∩ Y ′ ) = f −1 (Y ) ∩ f −1 (Y ′ ). Proof. 1. We have f −1 (B) ⊆ A. It remains to prove that A ⊆ f −1 (B). Let x ∈ A, then f (x) ∈ B implying that x ∈ f −1 (B). 2. Suppose that Y ⊆ Y ′ and show that f −1 (Y ) ⊆ f −1 (Y ′ ). Y ⊆Y ′ x ∈ f −1 (Y ) =⇒ f (x) ∈ Y =⇒ f (x) ∈ Y ′ =⇒ x ∈ f −1 (Y ′ ). Hence, f −1 (Y ) ⊆ f −1 (Y ′ ). 3. Prove that f −1 (Y ∪ Y ′ ) = f −1 (Y ) ∪ f −1 (Y ′ ). x ∈ f −1 (Y ∪ Y ′ ) ⇐⇒ f (x) ∈ Y ∪ Y ′ ⇐⇒ f (x) ∈ Y or f (x) ∈ Y ′ ⇐⇒ x ∈ f −1 (Y ) or x ∈ f −1 (Y ′ ) ⇐⇒ x ∈ f −1 (Y ) ∪ f −1 (Y ′ ) Consequently, f −1 (Y ∪ Y ′ ) = f −1 (Y ) ∪ f −1 (Y ′ ). 4. Show that f −1 (Y ∩ Y ′ ) = f −1 (Y ) ∩ f −1 (Y ′ ). x ∈ f −1 (Y ∩ Y ′ ) ⇐⇒ f (x) ∈ Y ∩ Y ′ ⇐⇒ f (x) ∈ Y and f (x) ∈ Y ′ ⇐⇒ x ∈ f −1 (Y ) and x ∈ f −1 (Y ′ ) ⇐⇒ x ∈ f −1 (Y ) ∩ f −1 (Y ′ ) We deduce that f −1 (Y ∩ Y ′ ) = f −1 (Y ) ∩ f −1 (Y ′ ). Proposition5.4. Let f : A −→ B be a mapping  \ and  let\ (Yi )i∈I be a family of subsets of [  [ −1 −1 −1 B. Then f Yi = f (Yi ) and f Yi = f −1 (Yi ). i∈I i∈I i∈I i∈I 11 Proposition 5.5. Let f : A −→ B be a mapping. 1. ∀ X ∈ P(A), we have X ⊆ f −1 (f (X)). 2. ∀ Y ∈ P(B), we have f (f −1 (Y )) ⊆ Y. Proof. 1. Let X ∈ P(A). x ∈ X =⇒ f (x) ∈ f (X) =⇒ x ∈ f −1 (f (X)). Thus, X ⊆ f −1 (f (X)). 2. Let Y ∈ P(B). y ∈ f (f −1 (Y )) =⇒ ∃ x ∈ f −1 (Y ) / y = f (x) =⇒ f (x) ∈ Y and y = f (x) =⇒ y ∈ Y. Hence, f (f −1 (Y )) ⊆ Y. Proposition 5.6. Let f : A −→ B be a mapping. The following are equivalent: 1. f is injective. 2. ∀ X ∈ P(A), we have f −1 (f (X)) = X. 3. ∀ X, X ′ ∈ P(A), we have f (X ∩ X ′ ) = f (X) ∩ f (X ′ ). Proof. 1 =⇒ 2? Suppose that f is injective. Let X ∈ P(A) and show that f −1 (f (X)) = X. We always have X ⊆ f −1 (f (X)). It remains to prove that f −1 (f (X)) ⊆ X. f inj. x ∈ f −1 (f (X)) =⇒ f (x) ∈ f (X) =⇒ ∃ y ∈ X; f (x) = f (y) =⇒ x = y ∈ X. 2 =⇒ 3? Suppose that ∀ X ∈ P(A), we have f −1 (f (X)) = X. Let X, X ′ ∈ P(A). Show that f (X ∩ X ′ ) = f (X) ∩ f (X ′ ). We always have f (X ∩X ′ ) ⊆ f (X)∩f (X ′ ). It remains to show that f (X)∩f (X ′ ) ⊆ f (X ∩ X ′ ). y ∈ f (X) ∩ f (X ′ ) =⇒ y ∈ f (X) and y ∈ f (X ′ ) =⇒ ∃ x ∈ X and ∃ x′ ∈ X ′ ; y = f (x) = f (x′ ). But y ∈ f (X) and y = f (x′ ) so f (x′ ) ∈ f (X) and hence x′ ∈ f −1 (f (X)) = X. We obtain that x′ ∈ X ∩ X ′ giving y = f (x′ ) ∈ f (X ∩ X ′ ). 3 =⇒ 1? Suppose that ∀ X, X ′ ∈ P(A), we have f (X ∩ X ′ ) = f (X) ∩ f (X ′ ). Prove that f is injective, i.e., ∀ x, x′ ∈ A, f (x) = f (x′ ) =⇒ x = x′. Let x, x′ ∈ A such that f (x) = f (x′ ). Set X = {x} ∈ P(A) and X ′ = {x′ } ∈ P(A). Then f ({x} ∩ {x′ }) = f ({x}) ∩ f ({x′ }) = {f (x)} ∩ {f (x′ )} = {f (x)} ∩ {f (x)} = {f (x)}. Hence, f ({x} ∩ {x′ }) = ̸ ∅ giving that {x} ∩ {x′ } ̸= ∅, so ∃ a ∈ {x} ∩ {x′ } then a ∈ {x} and a ∈ {x }. We obtain a = x = x′ =⇒ x = x′. ′ Proposition 5.7. Let f : A −→ B be a mapping. The following are equivalent: 1. f is surjective. 2. ∀ Y ∈ P(B), we have f (f −1 (Y )) = Y. 12 Proof. 1 =⇒ 2? Suppose that f is surjective. Let Y ∈ P(B). Show that f (f −1 (Y )) = Y. We always have f (f −1 (Y )) ⊆ Y. It remains to show that Y ⊆ f (f −1 (Y )). Let y ∈ Y , then y ∈ B. As f is surjective, then ∃ x ∈ A; y = f (x). But y ∈ Y =⇒ f (x) ∈ Y =⇒ x ∈ f −1 (Y ) =⇒ y = f (x) ∈ f (f −1 (Y )). 2 =⇒ 1? Suppose that ∀ Y ∈ P(B), we have f (f −1 (Y )) = Y. Set Y = B, then f (f −1 (B)) = B. But f −1 (B) = A, always true. Thus, f (A) = B with f (A) = Imf , then Imf = B which gives that f is surjective. 13  Chapter 3: Binary operations 1 Definitions Definition 1.1. Let E be a non-empty set. A binary operation on E is a mapping denoted by > and defined by > : E × E −→ E (x, y) 7−→ >(x, y) The image of the pair (x, y) by > is an element of E that we usually denote by x>y and we call it the composite of x and y. A binary operation on a set E can also be denoted by “∗”, “+”, “.”, “◦”,... Remark 1.1. When the binary operation is denoted by the symbol “+” (resp., “.”), we say that it is additive (resp., multiplicative). Definition 1.2. A magma or a groupoid is a pair (E, >), where E is a non-empty set and > is a binary operation on E. Example 1.1. 1. Let E = N or Z or Q or R. The usual addition of numbers “+” and the usual multiplication of numbers “.” or “×” are binary operations on E. Then, (E, +) and (E,.) are magmas. 2. Let E = Z or Q or R. The subtraction is a binary operation on E. Then (E, −) is a magma. However, the subtraction is not a binary operation on N as ∃ x = 0 ∈ N and ∃ y = 1 ∈ N such tha x − y = −1 ∈/ N. 3. Let E be
a set. Then the
set P(E) is non-empty. P(E), ∩ and P(E), ∪ are magmas. 4. Let E be a non-empty set. (E E , ◦), where ◦ is the composition of mappings in E E , is a magma. Definition 1.3. Let (E, >) be a magma and a ∈ E. 1. The left translation by a is the mapping, that we denote by “γa ”, defined by γa : E −→ E x 7−→ γa (x) = a>x. 2. The right translation by a is the mapping, that we denote by “δa ”, defined by δa : E −→ E x 7−→ δa (x) = x>a. 1 2 Properties Definition 2.1. A magma (E, >) is called 1. associative (or the binary operation > is called associative) if ∀ x, y, z ∈ E, (x>y)>z = x>(y>z). 2. commutative (or the binary operation > is called commutative) if ∀ x, y ∈ E, x>y = y>x. Example 2.1. 1. Let E = N or Z or Q or R. The usual addition and multiplication on E are associative and commutative. However, the subtraction
on Z is neither associative as (2 − 3)
− 5 = −6 but 2 − (3 − 5) = 4 , nor commutative as 2 − 3 = −1 but 3 − 2 = 1.

2. Given a set E, the magmas P(E), ∩ and P(E), ∪ are associative and commu- tative. E E 3. Let E be a non-empty set. The
magma (E , ◦) is associative as ∀ f, g, h ∈ E , we have (f ◦ g) ◦ h = f ◦ (g ◦ h) but is not commutative in general. Proposition 2.1. Let (E, >) be a magma. The following three properties are equivalent: 1. The magma (E, >) is associative. 2. ∀ a, b ∈ E, γa>b = γa ◦ γb. 3. ∀ a, b ∈ E, δa>b = δb ◦ δa. Proof. 1 =⇒ 2? Let a, b ∈ E. Show that γa>b = γa ◦ γb. > associative Let x ∈ E. We have γa>b (x) = (a>b)>x = a>(b>x) = γa (b>x) = γa (γb (x)) = (γa ◦ γb )(x). Thus, γa>b = γa ◦ γb. 2 =⇒ 3? Let a, b ∈ E. Prove that δa>b = δb ◦ δa. In fact, ∀ x ∈ E, we have
δa>b (x) = x>(a>b)
= γx (a>b) = γx γa (b) = (γx ◦ γa )(b) = γx>a (b) = (x>a)>b = δb (x>a) = δb δa (x) = (δb ◦ δa )(x). Hence, δa>b = δb ◦ δa. 3 =⇒ 1? Let a, b, c ∈ E. Show that a>(b>c)
= (a>b)>c. a>(b>c) = δb>c (a) = (δc ◦ δb )(a) = δc δb (a) = δb (a)>c = (a>b)>c. Therefore, the magma (E, >) is associative. Proposition 2.2. A magma (E, >) is commutative if and only if ∀ a ∈ E, we have γa = δa. 2 Proof. (E, >) is commutative ⇐⇒ ∀ a, x ∈ E, a>x = x>a ⇐⇒ ∀ a ∈ E, ∀ x ∈ E, γa (x) = δa (x) ⇐⇒ ∀ a ∈ E, γa = δa. Definition 2.2. Let E be a set that is equipped with two binary operations ∗ and >. 1. The binary operation > is said to be left distributive with respect to ∗ if ∀ x, y, z ∈ E, x>(y ∗ z) = (x>y) ∗ (x>z). 2. The binary operation > is said to be right distributive with respect to ∗ if ∀ x, y, z ∈ E, (y ∗ z)>x = (y>x) ∗ (z>x). 3. The binary operation > is said to be distributive with respect to ∗ if it is left and right distributive with respect to ∗. Example 2.2. 1. For E = N or Z or Q or R, the usual multiplication is distributive with respect to the usual addition. 2. For any set E, the binary operation ∩ (resp., ∪) is distributive with respect to ∪ (resp., ∩) in P(E). 3 Particular elements Definition 3.1. Let (E, >) be a magma and a ∈ E. 1. a is called left regular for > if ∀ x, y ∈ E, a>x = a>y =⇒ x = y. 2. a is called right regular for > if ∀ x, y ∈ E, x>a = y>a =⇒ x = y. 3. a is called regular for > if it is both left and right regular for >. Remark 3.1. If (E, >) is commutative, then the notions of left regular and right regular elements coincide. Example 3.1. 1. For E = N or Z or Q or R, every element of E is regular for the addition and every nonzero element of E is regular for the multiplication.

E, ∅ is a regular element for P(E), ∪ and E is a regular element 2. For a given set for P(E), ∩. Definition 3.2. Let (E, >) be a magma and e ∈ E. 1. e is called neutral on the left or a left identity for > if ∀ x ∈ E, e>x = x. 2. e is called neutral on the right or a right identity for > if ∀ x ∈ E, x>e = x. 3  3. e ∈ E is called a neutral element or an identity for > if it is both a left identity and a right identity for >, i.e., ∀ x ∈ E, x>e = x = e>x. Definition 3.3. A magma (E, >) is called unitary if it has an identity element. Proposition 3.1. Let (E, >) be a magma and let e and e0 be two elements of E. If e is a left identity for > and e0 is a right identity for > then e = e0. Proof. We have e>e0 = e0 as e is a left identity  =⇒ e = e0. e>e0 = e as e0 is a right identity Corollary 3.1. If a magma (E, >) has an identity element then it is unique, and will be called “the” identity element of E. Example 3.2. 1. If E = N or Z or Q or R, then 0 is the identity element for the usual addition and 1 is the identity element for the usual multiplication. Thus, (E, +) and (E,.) are unitary. 2. For every set E, IdE is the identity element for (E E , ◦), since ∀ f ∈ EE , f ◦ IdE = f and IdE ◦ f = f.
3. For every set
E, E is the identity element for P(E), ∩ and ∅ is the identity element for P(E), ∪ since ∀ X ∈ P(E), X ∩ E = X and E ∩ X = X and ∀ X ∈ P(E), X ∪ ∅ = X and ∅ ∪ X = X. 4. The magma (2Z, ×) has no identity element. Indeed, by contradiction, suppose that (2Z, ×) has an identity element e, then e ∈ 2Z and ∀ x ∈ 2Z, x × e = e × x = x. In particular, 2 × e = 2 which gives that e = 1 ∈ 2Z: contradiction. 5. Consider the magma (N, ∗), where ∗ is defined by ∀ x, y ∈ N, x ∗ y = xy + y. 0 is a left identity for ∗ as ∀ x ∈ N, 0 ∗ x = 0 × x + x = x. However, no element of N is a right identity for ∗: by contradiction, suppose there exists an element e ∈ N a right identity for ∗. Then by Proposition 3.1, e = 0 and then ∀ x ∈ N, x ∗ 0 = x. In particular, 1 ∗ 0 = 1. But, by definition of ∗, 1 ∗ 0 = 0. Hence, 1 = 0 which is a contradiction. Consequently, (N, ∗) has no neutral element. Proposition 3.2. Let (E, >) be a magma. An element e of E is an identity for > if and only if γe = δe = IdE. 4 Proof. e is an identity element for > ⇐⇒ ∀ x ∈ E, e>x = x>e = x ⇐⇒ ∀ x ∈ E, γe (x) = δe (x) = IdE (x) ⇐⇒ γe = δe = IdE. Remark 3.2. If the binary operation is denoted by + (resp.,.) and if it admits an identity element, then it will be denoted by “0” (resp., “e” or “1”). Definition 3.4. Let (E, >) be a magma. An element a of E is said to be idempotent for > if a>a = a. Example 3.3. Every element of P(E) is idempotent for ∩ and for ∪. Definition 3.5. Let (E, >) be a unitary magma with identity element e and let a ∈ E. 1. a is called left invertible for > if ∃ a0 ∈ E; a0 >a = e. The element a0 is called a left inverse of a. 2. a is called right invertible for > if ∃ a00 ∈ E; a>a00 = e. The element a00 is called a right inverse of a. 3. a is called invertible for > if there exists an element a0 ∈ E such that a0 >a = e = a>a0. In this case, a0 is called an inverse of a in E. Example 3.4. 1. In (N, +), 0 is the only invertible element. In (N, ×), 1 is the only invertible element. 2. In (Z, +), every element is invertible. In (Z, ×), 1 and −1 are the only invertible elements. 4 Monoids Definition 4.1. A monoid is a magma (E, >) that is associative and unitary. If, in addition, the binary operation > is commutative, then the monoid (E, >) is said to be commutative. Proposition 4.1. Let (E, >) be a monoid. 1. If a ∈ E is invertible for >, then ∃ ! a0 ∈ E such that a>a0 = a0 >a = e. In this case, a0 is the inverse of a and a is the inverse of a0 in E. 2. If a ∈ E and b ∈ E are two invertible elements for > such that a0 is the inverse of a and b0 is the inverse of b, then the element a>b is invertible for > and its inverse is b0 >a0. 3. If a ∈ E is left (resp., right) invertible for >, then a is left (resp., right) regular for >. 5  4. If a ∈ E is invertible for >, then a is regular for >. Proof. Let e be the identity element of the monoid (E, >). 1. Let a ∈ E be an invertible element of (E, >), then ∃ a0 ∈ E; a0 >a = e = a>a0. We show the uniqueness of a0. Suppose there exists a00 ∈ E such that a>a00 = e = a00 >a. Then, e identity ass. e identity a0 = a0 >e = a0 >(a>a00 ) = (a0 >a)>a00 = e>a00 = a00. 2. We have a>a0 = a0 >a = e and b>b0 = b0 >b = e. Therefore, (a>b)>(b0 >a0 ) = a>[b>(b0 >a0 )] = a>[(b>b0 )>a0 ] = a>[e>a0 ] = a>a0 = e. (b0 >a0 )>(a>b) = b0 >[a0 >(a>b)] = b0 >[(a0 >a)>b] = b0 >[e>b] = b0 >b = e. Hence, (a>b)>(b0 >a0 ) = (b0 >a0 )>(a>b) = e. We deduce that a>b is invertible with inverse b0 >a0. 3. Suppose that a ∈ E is left invertible for >. Let a0 be a left inverse of a, i.e., we have a0 >a = e. Show that a is left regular: ∀ x, y ∈ E, a>x = a>y =⇒ a0 >(a>x) = a0 >(a>y) > ass. =⇒ (a0 >a)>x = (a0 >a)>y =⇒ e>x = e>y e identity =⇒ x = y. Similarly, we show that if a ∈ E is right invertible for > then a is right regular for >. Remark 4.1. In an additive (resp., multiplicative) monoid (E, +) (resp., (E,.)), the inverse of an invertible element a is called the opposite (resp., the inverse) of a and is denoted by “−a” (resp., “a−1 ”). Example 4.1. 1. Suppose E = Z or Q or R. The magma (E, +) is a commutative monoid whose identity element is the integer 0 and such that every element is invertible with inverse its opposite. 2. Suppose E = Q or R. The magma (E,.) is a commutative monoid whose identity element is the integer 1 and such that every nonzero element is invertible. 3. Let E be a set. The magma (E E , ◦) is a monoid that is not commutative in general, whose identity element is IdE and such that the invertible elements are the bijections. In fact, f ∈ E E is invertible ⇐⇒ ∃ f 0 ∈ E E , f ◦ f 0 = f 0 ◦ f = IdE ⇐⇒ f is a bijection from E to E. 6 5 Induced operation Definition 5.1. Let (E, >) be a magma. A non-empty subset A of E is said to be closed under > if ∀ x, y ∈ A, x>y ∈ A. Proposition 5.1. Let (E, >) be a magma and suppose that A is a subset of E that is closed under >. The correspondence >A : A × A −→ A (x, y) 7−→ >A (x, y) = x>y is a binary operation on A called the binary operation induced on A by >. Proof. Show that >A is a mapping. ∀ x, y ∈ A, we have x>y ∈ A, as A is closed under >, giving that >A (x, y) ∈ A. >map. ∀ (x, y), (x0 , y 0 ) ∈ A × A, (x, y) = (x0 , y 0 ) =⇒ x>y = x0 >y 0 =⇒ >A (x, y) = >A (x0 , y 0 ). Proposition 5.2. Let (E, >) be a magma and A a subset of E that is closed under >. 1. If > is associative (resp., commutative) then >A is also associative (resp., commu- tative). 2. If (E, >) is unitary with identity element e and if e ∈ A, then (A, >A ) is also unitary with identity element e. Proof. 1. Let a, b, c ∈ A. Then, a, b, c ∈ E. By hypothesis, > is associative, so a>(b>c) = (a>b)>c thus a>A (b>A c) = (a>A b)>A c. Consequently, >A is associa- tive. Similarly for the commutative case. 2. Let x ∈ A. Then, x ∈ E and as e is the identity element of (E, >), we have x>e = e>x = x. But e, x ∈ A, so we get x>A e = e>A x = x. Hence, e becomes the identity element of (A, >A ). Proposition 5.3. Let ∗ and > be two binary operations defined on E and let A be a subset of E that is closed under ∗ and >. 1. If > is left (resp., right) distributive with respect to ∗, then >A is left (resp., right) distributive with respect to ∗A. 2. If > is distributive with respect to ∗, then >A is distributive with respect to ∗A. 7 6 Magma homomorphism Definition 6.1. 1. Let (E, >) and (F, ∗) be two magmas. A magma homomor- phism or a homomorphism of magmas from (E, >) to (F, ∗) is a mapping f : E −→ F that satisfies ∀ x, y ∈ E, f (x>y) = f (x) ∗ f (y). 2. An endomorphism of the magma (E, >) is a magma homomorphism from (E, >) to itself, i.e., a mapping f : E −→ E that satisfies ∀ x, y ∈ E, f (x>y) = f (x)>f (y). 3. A magma isomorphism is a bijective magma homomorphism. 4. A magma automorphism is a bijective magma endomorphism, i.e., an isomor- phism from a magma to itself. Example 6.1. 1. The mapping f : N −→ N x 7−→ f (x) = 2x is a magma homomorphism from (N, +) to (N,.) as ∀ x, y ∈ N, f (x + y) = 2x+y = 2x.2y = f (x).f (y). 2. Let (E, >) be an associative magma. The mapping f : E −→ E E a 7−→ f (a) = γa is a magma homomorphism from (E, >) to (E E , ◦) since > ass. ∀ a, b ∈ E, f (a>b) = γa>b = γa ◦ γb = f (a) ◦ f (b). Proposition 6.1. Let (E, >), (F, ∗) and (G, ⊥) be three magmas. 1. If f : E −→ F and g : F −→ G are two magma homomorphisms from (E, >) to (F, ∗) and from (F, ∗) to (G, ⊥) respectively, then g ◦ f is a magma homomorphism from (E, >) to (G, ⊥). 2. If f : E −→ F is a magma isomorphism from (E, >) to (F, ∗), then f −1 : F −→ E is a magma isomorphism from (F, ∗) to (E, >).



Proof. 1. ∀ x, y ∈ E, (g◦f )(x>y) = g f (x>y) = g f (x)∗f (y) = g f (x) ⊥g f (y) = (g ◦ f )(x)⊥(g ◦ f )(y). 2. ∀ y, y 0 ∈ F , ∃ x, x0 ∈ E such that f (x) = y and f (x0 ) = y 0. Thus, f −1 (y ∗ y 0 ) = f −1 f (x) ∗ f (x0 ) = f −1 f (x>x0 )

= (f −1 ◦ f )(x>x0 ) = IdE (x>x0 ) = x>x0 = f −1 (y)>f −1 (y 0 ). 8  Chapter 4: Groups, rings and fields 1 Groups Definition 1.1. A group is a monoid (G, ⊤) in which every element is invertible. If, in addition, the binary operation ⊤ is commutative, then the group (G, ⊤) is called abelian (or commutative). Example 1.1. 1. (Z, +), (Q, +) and (R, +) are abelian groups with identity element the integer 0. However, (N, +) is not a group since, for example, the element 1 of N is not invertible in (N, +). 2. (Q∗ ,.) and (R∗ ,.) are abelian groups with identity element the integer 1. But (Z,.) and (Z∗ ,.) are not groups as, for instance, the element 2 of Z is not invertible in these groups. 3. Let X be a non-empty set and denote by S(X) the set of all bijections from X to X. S(X) is a non-empty set, since IdX ∈ S(X). The composition of mappings ◦ is a binary operation on S(X) : ∀ f, g ∈ S(X), f ◦ g ∈ S(X).

Thus, S(X), ◦ is a magma. Moreover, this magma S(X), ◦ is a group. In fact, ˆ the composition
of mappings, ◦, is always associative. Then, the magma S(X), ◦ is associative. ˆ the magma S(X), ◦ has IdX as its identity element, so it is a unitary magma.
ˆ every element of S(X), ◦ is invertible. Indeed, ∀ f ∈ S(X), f is bijective so
f −1 exists and f −1 : X −→ X. Hence, f −1 ∈ S(X) and f ◦f −1 = f −1 ◦f = IdX , the identity element of ◦. o f / X f −1 X. Consequently, ∀ f ∈ S(X), f is invertible and its inverse is f −1 ∈ S(X).
We finally conclude that S(X), ◦ is a group, called the symmetric group of X. Proposition 1.1. Let (G, T ) be a group, then every element of G is regular for ⊤. Proof. Since (G, ⊤) is a group, every element of G is invertible for ⊤, thus regular for ⊤, as (G, ⊤) is in particular a monoid. Remark 1.1. 1. In additive notation: when the binary operation of a group is de- noted by the symbol “+”, we say that the group (G, +) is additive. In this case, 1  ˆ the identity element of (G, +) is in general denoted by “0”. ˆ the inverse of an element a ∈ G is called the opposite of a and is denoted by “−a”. ˆ if a and b are two elements of G, we write a − b = a + (−b). Thus, denoted −(a + b) = (−b) + (−a) = −b − a. 2. In multiplicative notation: when the binary operation of a group is denoted by the symbol “.”, we say that the group (G,.) is multiplicative. In this case, ˆ the identity element of (G,.) is in general denoted by “e” or “1”. ˆ the inverse of an element a ∈ G is denoted by “a−1 ”. ˆ if a and b are two elements of G, we have (a.b)−1 = b−1.a−1. Definition 1.2. Let (G,.) be a group. A subgroup of G is a subset H of G that satisfies: 1. H ̸= ∅. 2. H is closed under the binary operation. of G, i.e., ∀ x, y ∈ H, x.y ∈ H. 3. The magma (H,.H ) is a group. Example 1.2. 1. If (G,.) is a group with identity element e, then {e} and G are two subgroups of G that we call the trivial subgroups of G. 2. Z is a subgroup of (R, +). 3. N is not a subgroup of (Z, +) as (N, +) is not a group. Proposition 1.2. Let H be a subgroup of a group (G,.). 1. The identity element of (H,.H ) is that of (G,.). 2. Let x ∈ H. The inverse of x in (H,.H ) is the same as the inverse of x in (G,.). Thus, x−1 ∈ H. Proof. Let e be the identity element of G. 1. H is a subgroup of (G,.) so (H,.H ) is a group and so it has an identity element that we denote by e′. Show that e′ = e. As e′ ∈ H then e′ ∈ G and we have e′.e = e′ , as e is the identity element of (G,.). On the other hand, e′.H e′ = e′ , as e′ is the identity element of (H,.H ), then e′.e′ = e′ Thus, e′.e = e′ = e′.e′. We obtain that e = e′ , as e′ is a regular element. 2  2. Let x′ be the inverse of x in the group (H,.H ). Show that x′ = x−1. We have x′ ∈ H and x.H x′ = x′.H x = e giving that x.x′ = x′.x = e. Hence, x′ is the inverse of x in the group (G,.). By the uniqueness of the inverse in the monoid (G,.), it follows that x−1 = x′. Proposition 1.3 (To admit). Let (G,.) be a group and H a subset of G. The following are equivalent: 1. H is a subgroup of the group (G,.). 2. H ̸= ∅ and ∀ x, y ∈ H, we have x.y ∈ H and x−1 ∈ H. 3. H ̸= ∅ and ∀ x, y ∈ H, we have x.y −1 ∈ H. Remark 1.2. To show that H is a subgroup of (G,.), the first thing to show is that H ̸= ∅ (if this is not already given). For that, we usually show that H contains the identity element of (G,.). Proposition 1.4. Let (G, +) be a group and H a subset of G. The following are equiv- alent: 1. H is a subgroup of the group (G, +). 2. H ̸= ∅ and ∀ x, y ∈ H, we have x + y ∈ H and −x ∈ H. 3. H ̸= ∅ and ∀ x, y ∈ H, we have x − y ∈ H.  Example 1.3. Let n ∈ Z and define nZ = {np / p ∈ Z} = x ∈ Z / ∃ p ∈ Z, x = np. nZ is a subgroup of (Z, +). ˆ nZ ̸= ∅, as 0 = n × 0 ∈ nZ. ˆ ∀ x, y ∈ nZ, show that x − y ∈ nZ. In fact, x, y ∈ nZ =⇒ ∃ p, q ∈ Z / x = np and y = nq =⇒ x − y = np − nq = n(p − q), with p − q ∈ Z =⇒ x − y ∈ nZ. Thus, nZ is a subgroup of the group (Z, +). Proposition 1.5. Let (G,.) be a group. The intersection of a family of subgroups of G is a subgroup of G. Proof. Let \ (Hi )i∈I be a family of subgroups of (G,.). Show that Hi is a subgroup of (G,.). i∈I \ \ ˆ ∀ i ∈ I, e ∈ Hi (as Hi is a subgroup) =⇒ e ∈ Hi =⇒ Hi ̸= ∅. i∈I i∈I \ ˆ Let x and y ∈ Hi. Then ∀ i ∈ I, x and y ∈ Hi. But Hi is a subgroup of (G,.), i∈I \ so x.y −1 ∈ Hi , ∀ i ∈ I. Consequently, x.y −1 ∈ Hi. i∈I 3 Definition 1.3. Let (G, ⊤) and (G′ , ∗) be two groups. 1. A mapping f : G −→ G′ is called a group homomorphism or a homomorphism of groups from (G, ⊤) to (G′ , ∗) if f is a magma homomorphism from (G, ⊤) to (G′ , ∗), i.e., ∀ x, y ∈ G, f (x⊤y) = f (x) ∗ f (y). 2. An endomorphism of the group (G, ⊤) is a group homomorphism from (G, ⊤) to itself. 3. A group isomorphism is a bijective group homomorphism. 4. A group automorphism is a bijective group endomorphism, i.e., an isomorphism from a group to itself. Definition 1.4. Let (G, ⊤) and (G′ , ∗) be two groups with identity elements e and e′ respectively. Let f : (G, ⊤) −→ (G′ , ∗) be a group homomorphism. The kernel of f is the subset of G denoted by “ker f ” and defined by ker f = f −1 {e′ } = x ∈ G / f (x) = e′.
 Hence, ker f ⊆ G and ∀ x ∈ G, x ∈ ker f ⇐⇒ f (x) = e′.   Proposition 1.6. Let (G,.) and (G′ ,.) be two groups with identities e and e′ respectively, and let f : (G,.) −→ (G′ ,.) be a group homomorphism. We have: 1. f (e) = e′.
−1 2. ∀ x ∈ G, f (x−1 ) = f (x). 3. If H is a subgroup of G, then f (H) is a subgroup of G′. In particular, Imf is a subgroup of G′. 4. If H ′ is a subgroup of G′ , then f −1 (H ′ ) is a subgroup of G. In particular, ker f is a subgroup of G. 5. f is injective ⇐⇒ ker f = {e}. f hom. e identity e′ identity Proof. 1. Let x ∈ G, then f (x).f (e) = f (x.e) = f (x) = f (x).e′ =⇒ f (e) = e′ , as f (x) is a regular element of G′. f hom. 2. ∀ x ∈ G, we have x.x−1 = x−1.x = e =⇒ f (x.x−1 ) = f (x−1.x) = f (e) =⇒ f (x).f (x−1 ) = f (x−1 ).f (x) = e′.
−1 Thus, f (x−1 ) is the inverse of f (x) in G′ , i.e., f (x−1 ) = f (x). 3. Let H be a subgroup of G. Show that f (H) is a subgroup of G′. ˆ f (H) ̸= ∅, as H ̸= ∅. 4  ˆ Let y, y ′ ∈ f (H). Show that y.y ′−1 ∈ f (H). y, y ′ ∈ f (H) =⇒ ∃ x, x′ ∈ H, such that y = f (x) and y ′ = f (x′ ).
−1 f hom. y.y ′−1 = f (x). f (x′ ) = f (x).f (x′−1 ) = f (x.x′−1 ) ∈ f (H), as x.x′−1 ∈ H (H is a subgroup of G). It follows that f (H) is a subgroup of G′. In particular, as G is a subgroup of G, then f (G) = Imf is a subgroup of G′. 4. Let H ′ be a subgroup of G′. Show that f −1 (H ′ ) is a subgroup of G. ˆ We have e′ ∈ H ′ , as H ′ is a subgroup of G′. Since e′ = f (e), then f (e) ∈ H ′ =⇒ e ∈ f −1 (H ′ ) =⇒ f −1 (H ′ ) ̸= ∅. ˆ Let x, y ∈ f −1 (H ′ ). Show that x.y −1 ∈ f −1 (H ′ ). This is equivalent to showing that f (x.y −1 ) ∈ H ′. x, y ∈ f −1 (H ′ ) =⇒ f (x), f (y) ∈ H ′. f hom.
−1 f (x.y −1 ) = f (x).f (y −1 ) = f (x). f (y) ∈ H ′ , as f (x), f (y) ∈ H ′ and H ′ is a subgroup of G′. Therefore, f −1 (H ′ ) is a subgroup of G. In particular, as {e′ } is a subgroup of G′ , then f −1 {e′ } = ker f is a subgroup of
G.   5. Show that f is injective ⇐⇒ ker f = {e}. ˆ =⇒? Suppose that f is injective and show that ker f = {e}. As f (e) = e′ , then e ∈ ker f. Thus, {e} ⊆ ker f. f inj. Let x ∈ ker f =⇒ f (x) = e′ =⇒ f (x) = f (e) =⇒ x = e =⇒ x ∈ {e}. Hence, ker f ⊆ {e}. Consequently, ker f = {e}. ˆ ⇐=? Suppose that ker f = {e} and show that f is injective.
−1
−1 ∀ x, y ∈ G, f (x) = f (y) =⇒ f (x). f (y) = f (y). f (y) =⇒ f (x).f (y −1 ) = e′ f hom. =⇒ f (x.y −1 ) = e′ =⇒ x.y −1 ∈ ker f = {e} =⇒ x.y −1 = e =⇒ x.y −1.y = e.y
ass. =⇒ x. y −1.y = e.y =⇒ x.e = e.y =⇒ x = y.
Therefore, f is injective. 2 Rings and fields Definition 2.1. A ring is a non-empty set R together with two binary operations de- noted by “+” and “.” such that 1. (R, +) is an abelian group (whose identity element is denoted by “0”), 5  2.. is associative and distributive with respect to +. In this case, we write (R, +,.) is a ring. If the binary operation “.” is commutative, we say that the ring (R, +,.) is commutative. If R has an identity element with respect to the binary operation “.”, we say that the ring (R, +,.) is unitary. In this case, the identity element with respect to the binary operation “.” is called the identity element of the ring R and is denoted by “1R ” or just “1”. Example 2.1. (Z, +,.), (Q, +,.) and (R, +,.) are commutative and unitary rings with 1Z = 1Q = 1R = 1. Proposition 2.1. If (R, +,.) is a ring, then ∀ x ∈ R, we have x.0R = 0R = 0R.x. Proof. On the one hand, we have x.0R = x.(0R + 0R ) = x.0R + x.0R. On the other hand, x.0R = x.0R + 0R , as 0R is the identity element of (R, +).
Thus, we find x.0R + x.0R = x.0R + 0R. But x.0R is regular for + as (R, +) is a group , so we get x.0R = 0R. Similarly, we prove that 0R.x = 0R. Proposition 2.2. If (R, +,.) is a ring, then ∀ x, y ∈ R, we have x.(−y) = −(x.y) = (−x).y. Proof. Let x, y ∈ R. We have
x.y + x.(−y) = x. y + (−y) = x.0R = 0R and
x.(−y) + x.y = x. (−y) + y = x.0R = 0R. Thus, the opposite of x.y is x.(−y), which means that −(x.y) = x.(−y). Similarly, we show that −(x.y) = (−x).y. Definition 2.2. Let (R, +,.) be a ring. A subring of R is a subset S of R such that 1. S ̸= ∅, 2. S is closed under + and., 3. (S, +S ,.S ) is a ring. Proposition 2.3 (To admit). Let (R, +,.) be a ring. A subset S of R is a subring of R if and only if 1. S is a subgroup of the group (R, +)