🧩Discrete Mathematics Unit 3 – Functions and Relations

Key Concepts

• Relations are sets of ordered pairs that define a relationship between elements from two sets
• Functions are special types of relations where each element in the domain is mapped to exactly one element in the codomain
• Domain refers to the set of all possible input values for a relation or function
• Codomain is the set of all possible output values for a relation or function
• Range is the set of actual output values produced by a relation or function
• One-to-one (injective) functions have distinct elements in the codomain for each element in the domain
• Onto (surjective) functions have every element in the codomain mapped to by at least one element in the domain
• Bijective functions are both one-to-one and onto

Types of Relations

• Reflexive relations have every element related to itself $(a, a)$ for all $a$ in the set
• Symmetric relations have the property that if $(a, b)$ is in the relation, then $(b, a)$ is also in the relation
• Antisymmetric relations have the property that if $(a, b)$ and $(b, a)$ are in the relation, then $a = b$
• Transitive relations have the property that if $(a, b)$ and $(b, c)$ are in the relation, then $(a, c)$ is also in the relation
• Equivalence relations are reflexive, symmetric, and transitive
  • Examples include equality $(=)$ and congruence $(\equiv)$
• Partial order relations are reflexive, antisymmetric, and transitive
  • Examples include less than or equal to $(\leq)$ and divisibility $(|)$

Properties of Relations

• Relations can be represented using ordered pairs, matrices, or graphs
• The matrix representation of a relation on a finite set is a square matrix with entries of 0 or 1
  • A 1 in the $(i, j)$ position indicates that $(a_i, a_j)$ is in the relation
• The graph representation of a relation uses vertices for elements and edges for ordered pairs in the relation
• Closure properties of relations include reflexive closure, symmetric closure, and transitive closure
  • These properties add the minimum number of ordered pairs to make the relation satisfy the respective property
• Equivalence classes partition a set into disjoint subsets based on an equivalence relation
  • Elements in the same equivalence class are related to each other by the equivalence relation

Functions: Definition and Basics

• Functions are relations where each element in the domain is mapped to exactly one element in the codomain
• Functions can be represented using equations, tables, or graphs
• The vertical line test determines if a graph represents a function
  • If any vertical line intersects the graph more than once, it is not a function
• Function notation $f(x)$ denotes the output value of the function $f$ for the input value $x$
• Evaluating functions involves substituting the input value into the function equation and simplifying
• The domain of a function can be determined by identifying the set of all possible input values
• The range of a function is the set of all output values produced by the function

Types of Functions

• Linear functions have the form $f(x) = mx + b$, where $m$ is the slope and $b$ is the y-intercept
• Quadratic functions have the form $f(x) = ax^2 + bx + c$, where $a$, $b$, and $c$ are constants and $a \neq 0$
• Polynomial functions are the sum of terms with non-negative integer exponents $(x^n)$
• Rational functions are the ratio of two polynomial functions $(\frac{P(x)}{Q(x)})$
• Exponential functions have the form $f(x) = a^x$, where $a$ is a positive constant not equal to 1
• Logarithmic functions have the form $f(x) = \log_a(x)$, where $a$ is a positive constant not equal to 1
• Trigonometric functions include sine $(sin)$, cosine $(cos)$, and tangent $(tan)$

Function Composition and Inverses

• Function composition combines two or more functions to create a new function
  • The composition of functions $f$ and $g$ is denoted $(f \circ g)(x) = f(g(x))$
• The domain of the composite function is the set of all $x$ in the domain of $g$ such that $g(x)$ is in the domain of $f$
• Function inverses "undo" the original function
  • The inverse of a function $f$ is denoted $f^{-1}$, where $f(f^{-1}(x)) = f^{-1}(f(x)) = x$
• For a function to have an inverse, it must be bijective (one-to-one and onto)
• To find the inverse of a function, swap $x$ and $y$, then solve for $y$
• The graph of a function and its inverse are reflections of each other over the line $y = x$

Applications in Discrete Math

• Relations and functions are used in various areas of discrete mathematics
• In set theory, relations and functions help define connections between elements of sets
• Graph theory uses relations to represent edges between vertices in a graph
• Cryptography relies on bijective functions for encryption and decryption
  • The function used for encryption should be easy to compute, while its inverse (decryption) should be difficult without the key
• Combinatorics uses functions to count the number of ways to arrange or select elements
• In computer science, functions are used to model input-output relationships and analyze algorithms

Common Mistakes and Tips

• Not checking the domain and codomain when determining if a relation is a function
• Confusing the range and codomain of a function
  • Remember that the range is a subset of the codomain
• Forgetting to use the vertical line test when determining if a graph represents a function
• Incorrectly applying function composition
  • Make sure to apply the "inside" function first, then the "outside" function
• Not verifying that a function is bijective before finding its inverse
• Misinterpreting the meaning of function notation $f(x)$
  • $f(x)$ represents the output value, not the function itself
• When in doubt, refer to the definitions and properties of relations and functions to guide your problem-solving approach