Mathematics Foundations/1.3 Relations and Functions

Relations and Functions 1.3 Relations and Functions 1.3.1 Relations A relation between two sets A and B is a subset of the Cartesian product . In other words, a relation R from A to B is a set of ordered pairs where and . Properties of Relations Let R be a relation on a set A (i.e., R is a subset of ). We say that R is: Reflexive if for all Symmetric if implies for all Antisymmetric if and implies for all Transitive if and implies for all Special Types of Relations Equivalence Relation: A relation that is reflexive, symmetric, and transitive Partial Order: A relation that is reflexive, antisymmetric, and transitive Total Order: A partial order where any two elements are comparable Example: The relation "is equal to" on the set of real numbers is an equivalence relation. Example: The relation "is less than or equal to" on the set of real numbers is a total order. 1.3.2 Functions A function f from a set A to a set B, denoted , is a relation from A to B with the property that for each , there exists exactly one such that . Function Terminology The set A is called the domain of f The set B is called the codomain of f For each , the unique element such that is denoted by and is called the image of a under f The set is called the range of f Types of Functions Injective (One-to-One): If implies for all Surjective (Onto): If for every , there exists an such that Bijective (One-to-One and Onto): If f is both injective and surjective Example: The function from to is neither injective nor surjective. Example: The function from to is bijective. 1.3.3 Function Composition and Inverse Functions Function Composition Given functions and , the composition of g and f, denoted , is the function from A to C defined by for all . Inverse Functions A function has an inverse if and only if f is bijective. In this case, the inverse function is defined by if and only if . Properties of Inverse Functions: (the identity function on B) (the identity function on A) 1.3.4 Special Functions Identity Function: for all Constant Function: for all , where c is a fixed element of B Characteristic Function: For a subset S of A, the characteristic function is defined by if and if 1.3.5 Binary Operations A binary operation on a set A is a function from to A. Common examples include addition, multiplication, and composition. Properties of Binary Operations Let * be a binary operation on a set A. We say that * is: Associative if for all Commutative if for all Has an identity element e if for all For each , there is an inverse element such that 1.3.6 Exercises 1. Prove that the composition of two injective functions is injective. 2. Prove that the composition of two surjective functions is surjective. 3. Let R be the relation on defined by if and only if is divisible by 3. Prove that R is an equivalence relation. 4. Let be defined by . Find . 5. Let . How many different relations are there on A? 6. Prove that a function is injective if and only if it has a left inverse. 7. Prove that a function is surjective if and only if it has a right inverse.