Algebra I Past Paper PDF November 2024

Algebra I November 1, 2024 Contents 1 Sets and Functions 2 1.1 Sets...................................................... 2...

Algebra I November 1, 2024 Contents 1 Sets and Functions 2 1.1 Sets...................................................... 2 1.1.1 Definition and Notations....................................... 2 1.1.2 Notation for Describing a Set..................................... 3 1.1.3 Some Popular Sets.......................................... 3 1.1.4 Subsets................................................ 3 1.2 Set operations................................................. 5 1.2.1 Union, Intersection, Difference................................... 5 1.2.2 Cartesian product.......................................... 6 1.2.3 Venn Diagrams............................................ 7 1.2.4 Indexed sets.............................................. 8 1.3 Function (Mappings)............................................. 10 1.3.1 Function................................................ 10 1.3.2 Injections, surjections and bijection................................. 12 1.3.3 Inverse functions........................................... 14 1 Chapter 1 Sets and Functions In this chapter we introduce and discuss fundamental notions in mathematics: sets, functions and axioms. Sets and functions show up everywhere in mathematics and science, and are common tools used in mathematical arguments. Moreover, proving statements about sets and functions can further develop our proof-writing and communication skills. 1.1 Sets 1.1.1 Definition and Notations Definition 1.1.1. A set is a collection of objects. The objects are referred to as elements or members of the set. Notation: ˆ Use capital letters to denote sets, A; B; C; X; Y etc. ˆ Use lower case letters to denote elements of the sets a;b; c; x; y. Remark 1.1.1. : The elements of a set can be just about anything: numbers, points in space, or even other sets. Notation: ˆ If x is a member or element of the set S, we write x ∈ S. ˆ If x is not an element of S we write x ̸∈ S. Definition 1.1.2 (Empty set). The empty set (or null set ) is the set which contains no elements. It is denoted ∅. For any object x, we always have x ̸∈ ∅; hence ∅ = {}. cardinality Definition 1.1.3. Let A be a set. If there are exactly n distinct elements in A where n is a nonnegative integer, we say that A is a finite set and that n is the cardinality of A. The cardinality of A is denoted by |A|. Example 1.1.1. : 1. Let A be the set of letters in the English alphabet.Then |A| = 26. 2. Let B = {n | n = 2k + 1, k ∈ Z+ and n ≤ 10}. Then |B| = 5. 3. Because the null set has no elements, it follows that |∅| = 0. Definition 1.1.4. A set is said to be infinite if it is not finite. Example 1.1.2. The set of positive integers is infinite. 2 1.1.2 Notation for Describing a Set. The conventional way to write down a set is to list the elements inside braces. For example, A = {a, b, c, d} = {c, a, b, d} A represents the set with the four elements a, b, c, and d. (Order is not supposed to be significant) Sometimes we Use brace notation with ellipses. For example, the set of powers of 2 can be expressed as {2, 4, 8, 16,...} Ellipses (...) are used when the general pattern of the elements is obvious. For large or infinite sets, it helps to use set builder notation. For example, the even integers can be expressed as E = {n | n is an even integer} = {n | n = 2k is an even integerk ∈ Z} = {2n | n ∈ Z} 1.1.3 Some Popular Sets Mathematicians have devised special symbols to represent some common sets. ˆ N = {0, 1, 2, 3,...}, the set of all natural numbers ˆ Z = {..., −2, −1, 0, 1, 2,...}, the set of all integers ˆ Z+ = {1, 2, 3,...} the set of all positive integers   p ˆ Q= | p, q ∈ Z, and q ̸= 0 , the set of all rational numbers q ˆ R, the set of all real numbers ˆ R+ , the set of all positive real numbers ˆ R∗ = R − {0}, the set of all non-zero real numbers ˆ C, the set of all complex numbers. Intervals The sets studied in calculus and other subjects are intervals, sets of all the real numbers between two numbers a and b, with or without a and b. If a and b are real numbers with a ≤ b, we denote these intervals by ˆ [a, b] = {x | a ≤ x ≤ b} ˆ (a, b] = {x | a < x ≤ b} ˆ [a, b) = {x | a ≤ x < b} ˆ (a, b) = {x | a < x < b} Note that [a, b] is called the closed interval from a to b and (a, b) is called the open interval 1.1.4 Subsets Definition 1.1.5. Let A and B be sets. We say that A is a subset of B if every element of A is also an element of B. We denote this A ⊆ B. If A is not a subset of B, then we denote this as A ̸⊆ B. Further, if A is a subset of B but there is at least one element of B that is not in A then we say that A is a proper subset of B. We denote this by A ⊂ B. 3 Definition 1.1.6. Two sets A and B are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ⇐⇒ x ∈ B). We write A = B if A and B are equal sets. Remark 1.1.2. : ˆ The empty set is a subset of every set. That is, for any set A, we always have that ∅ ⊆ A. ˆ (A ⊆ B) ≡ (∀x ∈ A, x ∈ B) ˆ (A ̸⊆ B) ≡ (∃x ∈ B, x ̸∈ A) ˆ (A = B) ≡ ((A ⊆ B) ∧ (B ⊆ A)) Proposition 1.1.1. Let A = {n ∈ Z | 6 | n} and B = {n ∈ Z | 3 | n}. Then A ⊆ B. First lets write a few elements of these sets A = {..., −18, −12, −6, 0, 6, 12, 18,...} and B = {..., −9, −6, −3, 0, 3, 6, 9,...} We are trying to prove that A ⊆ B. This is equivalent to showing that if x ∈ A then x ∈ B Proof. Let A; B be the sets defined in the proposition. Assume that x ∈ A. Hence we can write x = 6k where k ∈ Z. But now since 6k = 3(2k) and 2k is an integer, we know that x ∈ B. Thus A ⊆ B. Theorem 1.1.1. For any set, A, ˆ ∅ ⊆ A. ˆ A ⊆ A. Theorem 1.1.2. For any sets, A; B; C, If A ⊆ B and B ⊆ C ,then A ⊆ C. Proof. Assume that A ⊆ B and B ⊆ C We wish to show that now A ⊆ C, so let a ∈ A. Since we know that A ⊆ B we know that a ∈ B. And since we know that B ⊆ C, we know that a ∈ C. Hence we have shown that A ⊆ C Power Sets Definition 1.1.7. Let A be a set. The power set of A, denoted P(A), is the set of all subsets of A. Note that the elements of P(A) are themselves sets, and X ∈ P(A) ⇐⇒ X ⊆ A Example 1.1.3. : ˆ P {a, b} = {∅, {a} , {b} , {a, b}} ; ˆ P {1, 2, 3} = {∅, {1} , {2} , {3} , {1, 2} , {1, 3} , {2, 3} , {1, 2, 3}} and ˆ P(∅) = {∅} Theorem 1.1.3. Let A; B be sets. Then A ⊆ B if and only if P(A) ⊆ P(B). Since this is a biconditional we need to prove both directions. Lets start with the forward implication and then turn to the converse. Proof. We prove each implication in turn. ˆ Assume that A ⊆ B, and let X ∈ P(A). Hence X ⊆ A. By our result above, this, in turn, implies that X ⊆ B. By the definition of the power set, this tells us that X ∈ P(B). Thus we have shown that P(A) ⊆ P(B). ˆ Now turn to the converse and assume that P(A) ⊆ P(B). Since A ∈ P(A), this implies that A ∈ P(B). But, by the definition of the power set, this tells us that A ⊆ B, and we are done. Since we have proved both implications we have proved the result. Theorem 1.1.4. If A is a finite set with |A| = n, then |P(A)| = 2n. 4 1.2 Set operations 1.2.1 Union, Intersection, Difference Definition 1.2.1. The union of sets A and B, denoted by A ∪ B (read ” A union B”), is the set consisting of all elements that belong to either A or B or both. In symbols A ∪ B = {x | x ∈ A ∨ x ∈ B} Definition 1.2.2. The intersection of sets A and B, denoted by A ∩ B (read ”A intersection B”), is the set consisting of all elements that belong both A and B. In symbols A ∩ B = {x | x ∈ A ∧ x ∈ B} Definition 1.2.3. Sets A; B are said to be disjoint if their intersection is empty, i.e.,A ∩ B = ∅. Definition 1.2.4. The difference or relative compliment of two sets A and B, denoted by A − B is the set of all elements in A that are not in B.In symbols A − B = {x | x ∈ A ∧ x ̸∈ B} Notation: Another common notation for the difference between sets is A \ B Definition 1.2.5. The symmetric difference of A and B, denoted by A△B, is the set containing those elements in either A or B, but not in both A and B.In symbols A△B = (A \ B) ∪ (B \ A) Example 1.2.1. Suppose A = {a, b, c, d, e}, B = {d, e, f } and C = {1, 2, 3}. 1. A ∪ B = {a, b, c, d, e, f } 2. A ∩ B = {d, e} 3. A \ B = {a, b, c} 4. B \ A = {f } 5. A ∩ C = ∅ 6. A ∪ C = {a, b, c, d, e, 1, 2, 3} 7. A△B = {a, b, c, f } Theorem 1.2.1. The binary operations union and intersection are commutative, associative and distribute over each other. That is, A∪B =B∪A and A ∩ B = B ∩ A; (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C); (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) and (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) Moreover, with the difference they satisfy a sort of De Morgan’s Laws: A \ (B ∪ C) = (A \ B) ∩ (A \ C); A \ (B ∩ C) = (A \ B) ∪ (A \ C). 5 Complement Often all the sets being considered are subsets of a known set called the univeral set U , that is understood from the context. Definition 1.2.6. Let A be a set with a universal set U. The complement of A, denoted Ā,(or Ac ) is the set Ac = U \ A. The complement satisfies a few nice properties, and it really acts like negation. So, for example, (Ac )c = A. And it satisfies De Morgan’s Laws (A ∪ B)c = Ac ∩ B c , (A ∩ B)c = Ac ∪ B c. Theorem 1.2.2. For any sets A; B from a universe set U ˆ A⊆A∪B ˆ A∩B ⊆A ˆ A∩∅=∅ ˆ A∪∅=A ˆ if A ⊆ B, then B c ⊆ Ac ˆ A ∩ Ac = ∅ ˆ A ∪ Ac = U ˆ A∩U =A ˆ A∪U =U 1.2.2 Cartesian product Given two sets A and B, it is possible to “multiply” them to produce a new set denoted as A × B. This operation is called the Cartesian product. To understand it, we must first understand the idea of an ordered pair. Definition 1.2.7. An ordered pair is a list (x, y) of two things x and y, enclosed in parentheses and separated by a comma. For example, when we considered points in the plane in algebra and calculus, we used to represent them by a pair of real numbers, like (a, b) where a is the horizontal offset from the origin, and b is the vertical offset. It is clear that (0, 1) ̸= (1, 0), so order matters. Definition 1.2.8. The Cartesian product of two sets A and B is another set, denoted as A × B and defined as A × B = {(a, b) | a ∈ A, b ∈ B}. Thus A × B is a set of ordered pairs of elements from A and B. For example,if A = {0, 1} and B {1, 2, 3}, then A × B = {(0, 1) , (0, 2) , (0, 3) , (1, 1) , (1, 2) , (1, 3)} 6 Fact :If A and B are finite sets, then |A × B| = |A| · |B|. Of course, we can form multiple Cartesian products to get order triples, or more generally, order n-tuples. For example, A × B × C = {(a, b, c) | a ∈ A, b ∈ B and c ∈ C} When we take the Cartesian product of a set with itself, we use exponential notation for convenience, i.e., A × A × × A = An. | {z } n Theorem 1.2.3. Suppose A, B, C, D are sets. Then 1. A × (B ∪ C) = (A × B) ∪ (A × C) 2. A × (B ∩ C) = (A × B) ∩ (A × C) 3. A × ∅ = ∅ 4. (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D) 5. (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D) 1.2.3 Venn Diagrams Sets can be represented graphically using Venn diagrams, named after the English mathematician John Venn, who introduced their use in 1881. In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle. (Note that the universal set varies depending on which objects are of interest.) Inside this rectangle, circles or other geometrical figures are used to represent sets. Sometimes points are used to represent the particular elements of the set. Venn diagrams are often used to indicate the relationships between sets. We show how a Venn diagram can be used in the following example. A B A B A∪B A\B U U A B A A∩B Ac U U 7 1.2.4 Indexed sets Our usual set notation works well when we have a small number of sets; if our work involves three sets, we can just denote them A; B and C. However, this quickly becomes inconvenient when we have even a moderate number of sets; what should we use to denote the 20th set? One solution it to use indices to distinguish between sets: A1 , A2 , A3 ,... More generally, our indices do not need to be natural numbers, but instead come from any set. So, for example, we could define a family of sets indexed by elements of another set F = {Aα | α ∈ I} In this context we call I the indexing set, and the sets Aα the indexed sets. Typically, the indexing set is a subset of the natural numbers. Definition 1.2.9. Suppose A1 , A2 ,..., An are sets. Then A1 ∪ A2 ∪ A3 ∪... ∪ An = {x | x ∈ Ai for at least one set Ai , for 1 ≤ i ≤ n} , A1 ∩ A2 ∩ A3 ∩... ∩ An = {x | x ∈ Ai for every set set Ai , for 1 ≤ i ≤ n}. Notation: Given sets A1 , A2 ,..., An , we define n [ = A1 ∪ A2 ∪ A3 ∪... ∪ An , i=1 n \ = A1 ∩ A2 ∩ A3 ∩... ∩ An. i=1 Example 1.2.2. Suppose A1 = {0, 2, 5} , A2 {1, 2, 5} and A3 {2, 5, 7}. Then 3 [ = {0, 1, 2, 5, 7} , i=1 3 \ = {2, 5}. i=1 This notation is also used when the list of sets A1 , A2 , An ,... is infinite: ∞ [ = A1 ∪ A2 ∪ A3 ∪... ∪ An = {x | x ∈ Ai for at least one set Ai , for 1 ≤ i} , i=1 ∞ \ = A1 ∩ A2 ∩ A3 ∩... ∩ An = {x | x ∈ Ai for every set Ai , for 1 ≤ i}. i=1 partitions Definition 1.2.10. for a nonempty set A. A partition of A is a collection S of nonempty subsets of A such that every element of A belongs to exactly one subset in S. Furthermore, a partition of A can be defined as a collection S of subsets of A satisfying the three properties: 1. X ̸= ∅ for every set X ∈ S; 2. for every two sets X, Y ∈ S, either X = Y or X ∩ Y = ∅; S 3. X∈S X = A. 8 Example 1.2.3. Consider the following collections of subsets of the set A = {1, 2, 3, 4, 5, 6} S1 = {{1, 3, 6} , {2, 4} , {5}} ; S2 = {{1, 2, 3} , {4} , ∅, {5, 6}} ; S3 = {{1, 2} , {3, 4, 5} , {5, 6}} ; S4 = {{1, 4} , {3, 5} , {2}}. Determine which of these sets are partitions of A. 9 1.3 Function (Mappings) 1.3.1 Function Definition 1.3.1. Let A; B be non-empty sets. A function f from A to B, denoted f : A −→ B, is a non-empty subset of A × B , such that for every x ∈ A there exists a unique y ∈ B for whcih (x, y) ∈ f. Instead, we use the more familiar notation f (x) = y to mean the same thing. In this context, x is called the argument, y the value. We could also refer to f as a q (or mapping ). So, functions are just special relations, and relations are just sets. Thus, all your familiar mathematical objects are turning into sets! Now, since functions are just sets, what we mean when we say that two functions are equal is that they are equal as sets! Thankfully, the following theorem establishes that this means precisely what we would expect. Theorem 1.3.1. Functions f ; g are equal if and only if f and g have the same domain A, and for all x ∈ A, f (x) = g(x). Terminology Related to Functions. Let A and B be sets and suppose f : A −→ B. 1. The set A is called the domain of f. 2. The set B is called the codomain of f. 3. If f (x) = y, then x is a preimage of y. Note, there may be more than one preimage of y, but only one image (or value) of x. 4. The set f (A) = {f (x) | x ∈ A} is called the range of f. 5. If S ⊆ A, then the image of S under f is the set f (S) = {f (x) | x ∈ S}. 6. If T ⊆ B, then the preimage of T under f is the set f −1 (T ) = {x ∈ A | f (x) ∈ T } Example 1.3.1. Let f : Z −→ Z assign the square of an integer to this integer. Then, f (x) = x2 , where the domain of f is the set of all integers, the codomain of f is the set of all integers, and the range of f is the set of all integers that are perfect squares, namely, {0, 1, 4, 9,...} Remark 1.3.1. Note that the preimage of a set containing a single element of B is a (possibly) set of elements of A that may contain zero, one, two or even more elements. For example, consider the function f : R −→ R defined by f (x) = x2. Then f −1 ({0}) = {0} ; f −1 ({1}) {1, −1}; f −1 ({−1}) = ∅ Theorem 1.3.2. Let f : A −→ B, and let C ⊆ A and D ⊆ B. Further, let C1 , C2 be subsets of A and let D1 , D2 be subsets of B. The following are true (i) C ⊆ f −1 (f (C)) (ii) f (f −1 (D)) ⊆ D (iii) f (C1 ∩ C2 ) ⊆ f (C1 ) ∩ f (C2 ) (iv) f (C1 ∪ C2 ) = f (C1 ) ∪ f (C2 ) (v) f −1 (D1 ∩ D2 ) = f −1 (D1 ) ∩ f −1 (D2 ) (vi) f −1 (D1 ∪ D2 ) = f −1 (D1 ) ∪ f −1 (D2) Proof of (i) Let x ∈ C. We need to show that x ∈ f −1 (f (C)). So what is this set by the definition it is {a ∈ A | f (a) ∈ f (C)} Since x ∈ C we have, by definition, f (x) ∈ f (C). Since f (x) ∈ f (C) it follows that x ∈ f −1 (f (C)). 10 Proof of (iii) We need to show that if an element is in the set on the left then it is in the set on the right. Let b ∈ f (C1 ∩ C2 ). Hence there is a ∈ C1 ∩ C2 such that f (a) = b. This means that a ∈ C1 and a ∈ C2. It follows that f (a) = b ∈ f (C1 ) and f (a) = b ∈ f (C2 ), and hence b ∈ f (C1 ) ∩ f (C2 ). Proof of (vi) Let a ∈ f −1 (D1 ∪ D2 ) and so f (a) ∈ D1 ∈ D2. This means that f (a) ∈ D1 or f (a) ∈ D2. If f (a) ∈ D1 it follows that a ∈ f −1 (D1 ). Similarly if f (a) ∈ D2 then a ∈ f −1 (D2 ). Since a lies in one of these two sets, it follows that a ∈ f −1 (D1 ) ∪ f −1 (D2 ). Let a ∈ f −1 (D1 ) ∪ f −1 (D2 ). Then a is an element of one of these two sets. If a ∈ f −1 (D1 ), then f (a) ∈ D1. Similarly if a ∈ f −1 (D2 ) then f (a) ∈ D2. In either case f (a) ∈ D1 ∪ D2 and so a ∈ f −1 (D1 ∪ D2 ). restrictions and extensions Some functions are related to others by changing only the domain. For example, one could have a larger domain than the other, but on the smaller domain, the functions are equal. The next definition provides us the means to talk about such functions. Definition 1.3.2. Let f : A −→ B and suppose D ⊆ A. The restriction of f to D is the function f |D = {(x, y) | x ∈ D, y = f (x)}. If g, h are functions and g is a restriction of h, we also say that h is an extension of g. Composition Functions can be combined to create new functions. Let A, B and C be sets, f : A −→ B and g : B −→ C. Then define the composition of g with f , denoted g ◦ f , by g ◦ f = {(a, c) : a ∈ A, c ∈ C, c = g(f (a))}. Since f takes elements of A and “sends” them to B, and g takes elements of B and “sends” them to C, we can put these two actions together into one function: g ◦ f takes elements of A and “sends” them to C via f and g. We can see that g ◦ f ⊆ A × C and hence g ◦ f is a relation. We now prove that g ◦ f is a function from A to C. Theorem 1.3.3. Let A, B and C be sets, f : A −→ B and g : B −→ C. Then g ◦ f is a function from A to C. Proof. Let A, B and C be sets, f : A −→ B and g : B −→ C. Then g ◦ f = (a, c) : a ∈ A, c ∈ C, c = g(f (a)). Let a ∈ A. Then f (a) ∈ B, so g(f (a)) ∈ C. Let c = g(f (a)). Then (a, c) ∈ g ◦ f. Hence, for all a ∈ A there exists a c ∈ C such that (a, c) ∈ g ◦ f. To prove that there is exactly one c ∈ C such that (a, c) ∈ g ◦ f for all a ∈ A, suppose a ∈ A and that (a, c1 ) ∈ g ◦ f and (a, c2 ) ∈ g ◦ f. Then g(f (a)) = c1 and g(f (a)) = c2 , and so c1 = c2. Hence, for all a ∈ A there is a unique c in C such that (a, c) ∈ g ž f. Therefore, g ◦ f : A −→ C. Example 1.3.2. Let A = {a, b, c, d}, B = {r, s, t, u}, and C = {v, w, x}. Define f = {(a, s), (b, t), (c, s), (d, u)} and g = {(r, v), (s, w), (t, v), (u, x)}. Then f : A −→ B, g : B −→ C and g ◦ f = {(a, w), (b, v), (c, w), (d, x)}. 11  A B C g a r v f b s w c t x d u Theorem 1.3.4. Let f : A −→ B, g : B −→ C and h : C −→ D be functions. Then h ◦ (g ◦ f ) = (h ◦ g) ◦ f. Remark 1.3.2. It is important to note that composition is not, in general, commutative: g ◦ f ̸= f ◦ g 1.3.2 Injections, surjections and bijection Injections Definition 1.3.3. Let a1 , a2 ∈ A and let f : A −→ B be a function. We say that f is injective or one-to-one when if a1 ̸= a2 then f (a1 ) ̸= f (a2 ). Remark 1.3.3. It is helpful to also write the contrapositive of this condition. We say that f is injective or one-to-one when if f (a1 ) = f (a2 ) then a1 = a2. Example 1.3.3. The function f : R −→ R defined by f (x) = 3x − 5 is one-to-one. Assume that f (a) = f (b), where a, b ∈ R. Then 3a − 5 = 3b − 5. Adding 5 to both sides, we obtain 3a = 3b. Dividing by 3, we have a=b and so f is one-to-one. Example 1.3.4. Let the function f : R −→ R be defined by f (x) = x2 − 3x − 2. Since f (0) = −2 and f (3) = −2, it follows that f is not one-to-one. Definition 1.3.4. A function f whose domain and codomain are subsets of the set of real numbers is called increasing if f (x) ≤ f (y), and strictly increasing if f (x) < f (y), whenever x < y and x and y are in the domain of f. Similarly, f is called decreasing if f (x) ≥ f (y), and strictly decreasing if f (x) > f (y), whenever x < y and x and y are in the domain of f. From these definitions, it can be shown that a function that is either strictly increasing or strictly decreasing must be one-to-one. However, a function that is increasing, but not strictly increasing, or decreasing, but not strictly decreasing, is not one-to-one. 12 surjection Let f : A −→ B be a function. We say that f is surjective, or onto, when for every b ∈ B there is some a ∈ A such that f (a) = b. Example 1.3.5. The function f : R −→ R defined by f (x) = 7x − 3 is surjective y+3 Let y ∈ R. Choose x = , then 7   y+3 f (x) = 7 − 3 = y. 7 Hence f is surjective. Example 1.3.6. : ˆ The function f : R −→ R defined by f (x) = x2 is not injective. Injective means ∀a1 , a2 ∈ A, f (a1 ) = f (a2 ) ⇒ a1 = a2 and hence non-injective is just the negation of this, namely ∃a1 , a2 ∈ A, f (a1 ) = f (a2 ) ∧ a1 ̸= a2 So we need a counter-example; there exists some pair of distinct a1 , a2 ∈ R that map to the same value. Since −1; 1 are in the domain of f and f (−1) = f (1) = 1 the function is not injective. ˆ The function f : R −→ R defined by f (x) = x2 is not surjective. Since surjective means ∀b ∈ B, ∃a ∈ A, f (a) = b its negation is ∃b ∈ B, ∀a ∈ A, f (a) ̸= b : So in order to show that f is not surjective, we have to find (at least one) b ∈ R (in the co-domain) that is not the image of any a ∈ R (in the domain). Sometimes this can be tricky to prove, but for the example above we can use the fact that the square of a real is non-negative. Let b = −1 ∈ R. Since the square of any real number is non-negative, we know that f (x) = x2 ≥ 0 for any x ∈ R. Hence there is no x ∈ R such that f (x) = −1. Thus the function is not surjective. bijection Definition 1.3.5. Let f : A −→ B be a function. If f is injective and surjective then we say that f is bijective, or a one-to-one correspondence. √ Example 1.3.7. Let f : [0, 1) −→ [0, 1) be defined by f (x) = x. This function is an injection and a surjection and so it is also a bijection. Theorem 1.3.5. The composition of injective functions is injective and the compositions of surjective functions is surjective, thus the composition of bijective functions is bijective. That is, let f : A −→ B and g : B −→ C. 1. If f and g are injective, then so is g ◦ f. 2. If f and g are surjective, then so is g ◦ f. 3. If f and g are bijective, then so is g ◦ f. 13 Proof. ˆ Suppose f and g are injective and suppose (g ◦ f )(x) = (g ◦ f )(y). That means g(f (x)) = g(f (y)). Since g is injective, f (x) = f (y). Since f is injective, x = y. Thus g ◦ f is injective. ˆ Suppose f and g are surjective and suppose z ∈ C. Since g is surjective, there exists some y ∈ B with g(y) = z. Since f is surjective, there exists some x ∈ A with f (x) = y. Therefore z = g(f (x)) = (g ◦ f )(x) and so z ∈ rng(g ◦ f ). Thus g ◦ f is surjective. ˆ If f and g are bijective then g ◦ f is also bijective by what we have already proven. Theorem 1.3.6. Let f : A −→ B and g : B −→ C be functions. Then 1. If g ◦ f is injective then f is injective 2. If g ◦ f is surjective then g is surjective Proof. We prove each in turn. ˆ Assume that g ◦ f is injective, and let a1 , a2 ∈ A so that f (a1 ) = f (a2 ). To show that f is injective it suffices to show that a1 = a2. Since f (a1 ) = f (a2 ), we know that g(f (a1 )) = g(f (a2 )) , and since g ◦ f is injective we have that a1 = a2. ˆ Now assume that g ◦ f is surjective and let c ∈ C. To prove that g is surjective it suffices to find b ∈ B so that g(b) = c. Since g ◦ f is surjective, we know that there is a ∈ A so that g(f (a)) = c. Now set b = f (a). Then g(b) = g(f (a)) = c as required. 1.3.3 Inverse functions Identity function Definition 1.3.6. Given a non-empty set A we define the identity function iA : A −→ A by iA (a) = a for all a ∈ A. left-inverse and right-inverse let f : A −→ B and g : B −→ A be functions. 1. If g ◦ f = iA then we say that g is a left-inverse of f. 2. Similarly, if f ◦ g = iB then we say that g is a right-inverse of f. Lemma 1.3.1. Let f : A −→ B, then f has a left-inverse if and only if f is injective. Proof. We prove each implication in turn. 14  ˆ Assume that f has a left-inverse, g. Now let a1 , a2 ∈ A so that f (a1 ) = f (a2 ). Then g(f (a1 )) = g(f (a2 )), but since g is the left-inverse of f , we know that g(f (a1 )) = a1 and g(f (a2 )) = a2. Thus a1 = a2 and so f is injective. ˆ Now let f be injective. We construct a left-inverse of f in two steps. First pick any α ∈ A. Then consider the preimage of a given point b ∈ B. That preimage, f −1 ({b}), is empty or not. ° If f−1 ({b}) = ∅, then define g(b) = α °Now assume that f −1 ({b}) ̸= ∅. Since f is injective, the preimage f −1 ({b}) contains exactly one element a So define g(b) = a the unique element in the preimage. ( α if preimage empty To summarise. g(b) = a otherwise take unique a in the preimage Now let a ∈ A, under f it maps to some b ∈ B with b = f (a). Hence (as argued above) a is the unique element in the preimage of b, and so g(f (a)) = g(b) = a. Thus g is a left-inverse of f. Lemma 1.3.2. Let f : A −→ B, then f has a right-inverse if and only if f is surjective. Proof. We prove each implication in turn. ˆ Assume that f has a right-inverse, g. Now let b ∈ B and set a = g(b). Then f (a) = f (g(b)) = b and so f is surjective. ˆ Now let f be surjective and let b ∈ B. Let us denote the preimage of b as f −1 (b) = {a ∈ A | f (a) = b} Since f is surjective, we know that f −1 (b) ̸= ∅ for every b ∈ B. So now define g(b) to be element of f −1 (b). Now let b ∈ B, then under g it maps to some a ∈ A so that (by construction) f (a) = b. Hence f (g(b)) = f (a) = b and thus g is a right-inverse as required. These lemmas tell us that a function has both a left inverse and right inverse if and only if it is bijective. We can go further those one-sided inverses are actually the same function. Lemma 1.3.3. Let f : A −→ B have a left-inverse, g : B −→ A and a right inverse h : B −→ A, then g = h. Further, the function f has a left and right inverse if and only if f is bijective. Proof. Let f , g, h be as stated. Then we know that g ◦ f = iA and f ◦ h = iB. Now starting with g we can write: g = g ◦ iB = g ◦ (f ◦ h) = (g ◦ f ) ◦ h = iA ◦ h = h and thus g = h as required. The last part of the lemma follows by combining the previous two lemmas. So this lemma tells us conditions under which a function will have both a left- and right-inverse, and that those one-sided inverses are actually the same function. A function that is a left- and right-inverse is a (usual) inverse. 15 Definition 1.3.7. Let f : A −→ B and g : B −→ A be functions. If g ◦ f = iA and f ◦ g = iB then we say that g is an inverse of f. and denote it f −1. Lemma 1.3.4. If a function f : A −→ B has an inverse, then that inverse is unique. Proof. Let g : B −→ A and h : B −→ A both be inverses to the function f. Then g = g ◦ iB = g ◦ (f ◦ h) = (g ◦ f ) ◦ h = iA ◦ h = h and so g = h. Thus the inverse is unique. Theorem 1.3.7. Let f : A −→ B. ˆ The function f has an inverse function if and only if it is bijective ˆ The inverse of f , if it exists, is unique. Proof. Assume that f has an inverse. Then that inverse is both a left-inverse and a right-inverse. Then implies that f is both injective and surjective, and so is bijective. Now assume that f is bijective. Then there exists a function g that is a left-inverse and right-inverse for f. Then, by definition g is an inverse for f. Example 1.3.8. The function f : R −→ R defined by f (x) = 7x − 3 is bijective and so has an inverse function. And its inverse is f −1 : R −→ R defined by y+3 f −1 (y) = 7 To verify that this is correct it suffices to show that f −1 ◦ f is the identity function: f −1 ◦ f = f −1 (7x − 3) (7x − 3) + 3 = =x 7 Example 1.3.9. Let a, b,c, d ∈ R with ad ̸= bc. d nao The function h : R − −→ R − defined by c c ax − b h(x) = cx − d is bijective. ˆ Injective. Let x, y ∈ R \ d c and assume h(x) = h(y). Then ax − b ay − b = cx − d cy − d (cy − d)(ax − b) = (ay − b)(cx − d) since denominator ̸= 0 caxy − cyb − adx + db = acxy − ady − bcx + bd (ad − bc)y = (ad − bc)x Hence x = y. Thus if h(x) = h(y) we must have x = y and so h is injective. 16  ˆ Surjective. Let y = h(x), now find x ax − b y= cx − d cxy − dy = ax − b cxy − ax = dy − b x(cy − a) = dy − b dy − b x= cy − a d We now need to show that x ̸= c (and so is in the domain and we can do so by considering d dy − b d x− = − c cy − a c dcy − bc − dcy + da = c(cy − a) ad − bc = c(cy − a) a Since ad ̸= bc and y ̸= c this is never zero. Hence this choice of x really does lie in the domain of the function. dy−b Now let y ∈ R \ ac. Pick x = cy−a = dc + c(cy−a) ad−bc . Since ad − bc ̸= 0 for any a y ∈ R \ c , this choice of x is in the domain of the function. Now dy−b a cy−a −b h(x) = dy−b c cy−a − d a(dy − b) − b(cy − a) = c(dy − b) − d(cy − a) y(ad − bc) = ad − bc =y Hence for any y in the co-domain, there is an x in the range such that h(x) = y. So the function is surjective. Since the function is both injective and surjective, it is bijective as required. The above result tells us that it has an inverse function. We can verify that the inverse is nao   d h−1 : R \ −→ R \ c c defined by dy − b h−1 (y) = cy − a which we computed while proving the result. We simply need to show that h−1 ◦ h is the identity: ax − b h(x) = h−1 ( ) cx − d ax − b d( )−b = cx − d ax − b c( )−a cx − d d(ax − b) − b(cx − d) = c(ax − b) − a(cx − d) (ad − bc)x ad − bc =x 17 as required. Floor and Ceiling Functions. Definition 1.3.8. The floor function, denoted f (x) = ⌊x⌋ or f (x) = f loor(x); is the function that assigns to x the greatest integer less than or equal to x. Definition 1.3.9. The ceiling function, denoted f (x) = ⌈x⌉ or f (x) = ceiling(x); is the function that assigns to x the smallest integer greater than or equal to x. Example 1.3.10. : (a) ⌊3.5⌋ = 3 (b) ⌈3.5⌉ = 4 (c) ⌊−3.5⌋ = −4 (d) ⌈−3.5⌉ = −3 Example 1.3.11. Let h : [0, 1) −→ R be defined by h(x) = ⌊3x − 1⌋. Let A = {x ∈ R | 4 < x < 10}. 1. The domain is [0, 1) 2. The codomain is R 3. The range is {−1, 0, 1, 2,...} 4. h(A) = {11, 12, 13, 14,..., 28} 11 5. h−1 (A) = [2, ) 3 Characteristic Function Definition 1.3.10. Let U be a universal set and A ⊆ U. The Characteristic Function of A is defined by ( 1 if s ∈ A XA (s) = 0 if s ̸∈ A Example 1.3.12. Consider the set of integers as a subset of the real numbers. Then XZ (s) will be 1 when x is an integer and will be zero otherwise. 1. XZ (0) = 1 2. XZ−1 ({1}) = Z 3. XZ ([3, 5]) = {0, 1} 4. XZ−1 ([3, 5]) = ∅ 18