Algebra Textbook: Book 1 - Set Theory/Functions and Mappings

Functions and Mappings Introduction to Functions Functions are one of the most fundamental concepts in mathematics, serving as a bridge between different mathematical structures. A function is a special type of relation that associates each element of one set, called the domain, with exactly one element of another set, called the codomain. Formally, a function from set to set , denoted , is a relation from to such that: 1. For every , there exists a such that (total) 2. If and , then (well-defined) For and , if , we write and say " maps to " or " is the image of under ." Terminology and Notation Several important terms are associated with functions: Domain: The set of all inputs to the function Codomain: The set that contains all possible outputs Range or Image: The set , denoted or Preimage of : The set , denoted Graph of : The set Notation Variations Functions can be specified in several ways: Mapping notation: , Arrow diagram: A visual representation with arrows connecting elements of to their images in Function table: A table listing inputs and their corresponding outputs Formula: An algebraic expression, e.g., Algorithm: A procedure that computes outputs from inputs Types of Functions Functions can be classified based on various properties: Injective Functions A function is injective (one-to-one) if for all , if , then . Equivalently, is injective if for all with , we have . Example: The function defined by is injective. Surjective Functions A function is surjective (onto) if for every , there exists an such that . Equivalently, is surjective if . Example: The function defined by is not surjective because negative numbers are not in the range. Bijective Functions A function is bijective (one-to-one and onto) if it is both injective and surjective. Example: The function defined by is bijective. Identity Function The identity function is defined by for all . Constant Function A constant function maps every element of to the same element . Characteristic Function For a subset , the characteristic function is defined by: Function Composition Given functions and , the composition is defined by for all . Properties of Composition 1. Composition is associative: 2. Identity functions are neutral: and 3. If and are injective, then is injective 4. If and are surjective, then is surjective 5. If and are bijective, then is bijective Inverse Functions If is bijective, then there exists a unique function such that for all and for all . The function is called the inverse of . Properties of Inverse Functions 1. and 2. 3. (when both inverses exist) Finding Inverse Functions To find the inverse of a function : 1. Write 2. Solve for in terms of 3. Interchange and to get Example: Find the inverse of . Solution: 1. 2. 3. 4. Image and Preimage For a function : Image of a Set For any subset , the image of under is: Preimage of a Set For any subset , the preimage of under is: Note that is defined even when is not invertible. Properties of Images and Preimages For subsets and : 1. 2. (equality holds if is injective) 3. 4. 5. Special Types of Mappings Restriction and Extension For a function and a subset , the restriction of to , denoted , is the function defined by for all . A function is an extension of if and . Partial Functions A partial function from to is a function where . The set is called the domain of definition of . Multivariate Functions A function is called an -ary function or a function of variables. Example: is a binary (2-ary) function from to . Functions in Set Theory Functions play a crucial role in set theory: Function Spaces For sets and , the set of all functions from to is denoted or . If has elements and has elements, then has elements. Families of Sets A family of sets indexed by a set is a function for some set , where is the power set of . The family is often denoted where . Choice Functions A choice function for a family of non-empty sets is a function such that for all . The Axiom of Choice asserts that every family of non-empty sets has a choice function. Applications of Functions Functions have numerous applications across mathematics and beyond: Mathematical Modeling Functions are used to model relationships between variables in science, engineering, economics, and many other fields. Example: The function models the distance (in feet) that an object falls in seconds due to gravity. Transformations In geometry, functions represent transformations such as translations, rotations, reflections, and scaling. Example: The function represents a rotation by angle in the plane. Homomorphisms In abstract algebra, homomorphisms are functions that preserve algebraic structure. Example: A group homomorphism satisfies for all . Computer Science In computer science, functions are fundamental to programming and algorithm design. Example: In functional programming languages, functions are first-class objects that can be passed as arguments, returned as values, and composed to build complex behaviors. Exercises 1. Let be defined by . Determine whether is injective, surjective, or bijective. If possible, find its inverse. 2. Let and . How many different functions are there from to ? How many of these are injective? 3. Let be defined by and be defined by . Find the formulas for and . 4. Prove that a function is injective if and only if there exists a function such that . 5. Let be a function. Prove that for any subsets , . Give an example where equality does not hold. 6. Let be defined by . Find the range of and determine whether is injective, surjective, or bijective. 7. Let and be functions. Prove that if is injective, then is injective. Is it necessarily true that is injective? 8. Let be defined by . Find all values of for which and determine whether is injective, surjective, or bijective. 9. Let be a function and let be the relation on defined by if . Prove that is an equivalence relation on . 10. Let be a non-empty set and let be defined by (the complement of ). Determine whether is injective, surjective, or bijective, and find .