Discrete Mathematics: Functions, Invertibility, Monotonicity, and Sequences

Foundations of Functions, Surjectivity, and Bijectivity

• Definition of a Function: A function $f: A \rightarrow B$ is a mathematical relation that assigns each element from the domain $A$ to exactly one element in the codomain $B$.

• Surjective (Onto) Functions:

  • A function $f: A \rightarrow B$ is onto (surjective) if every element in the codomain $B$ corresponds to at least one element in the domain $A$.
  • Equivalently, a function is onto when its range is strictly equal to its codomain ($\text{Range}(f) = B$). If the range is merely a proper subset of the codomain, the function fails to be onto.

• Bijective Functions (One-to-One and Onto):

  • A function $f$ is defined as a bijection (bijective) if and only if it satisfies two simultaneous criteria: it is one-to-one (injective) and it is onto (surjective).
  • Bijections establish a strict one-to-one correspondence between every element of the domain and every element of the codomain.

• Inverse Functions ($f^{-1}$):

  • A function possesses an inverse function $f^{-1}$ if and only if it is a bijection.
  • Procedure to Derive the Equation of an Inverse Function:
    • Step 1: Set the functional expression equal to the codomain variable: $y = f(x)$.
    • Step 2: Perform algebraic operations to solve the equation for the domain input variable $x$ in terms of $y$.
    • Step 3: Interchange the variables $x$ and $y$ to express the inverse function $f^{-1}(x)$ in terms of the standard independent variable $x$.
    • The mathematical convention assigns $x$ to denote elements in the domain and $y$ to denote elements in the codomain; swapping variables at the conclusion restores this convention.

• Function Well-Definedness Analysis (Section 2.3, Problem #2, Part C):

  • Proposed Function: $f(n) = \frac{1}{n^2 - 4}$ evaluated as a candidate mapping from the domain of integers $\mathbb{Z}$ to the codomain of real numbers $\mathbb{R}$ ($f: \mathbb{Z} \rightarrow \mathbb{R}$).
  • Evaluation Criterion: For every randomly selected integer $n \in \mathbb{Z}$, the expression $f(n)$ must be defined and produce an output that belongs to $\mathbb{R}$.
  • Singularity Analysis:
    • The denominator $n^2 - 4$ must be non-zero for real division to be defined: $n^2 - 4 \neq 0$.

• Solving the restriction gives $n^2 \neq 4$, which implies $n \neq 2$ and $n \neq -2$. * Because the inputs $2$ and $-2$ are elements of the domain $\mathbb{Z}$, evaluating $f(2)$ or $f(-2)$ results in division by zero ($\frac{1}{0}$), which is undefined in $\mathbb{R}$.

  • Conclusion: The relation is not a valid function from $\mathbb{Z}$ to $\mathbb{R}$.

• Criteria for Bijections on Real Numbers (Page 153, Problem 22):

  • To verify that a mapping $f: \mathbb{R} \rightarrow \mathbb{R}$ is a bijection, one must verify both injectivity (distinct real inputs map to distinct real outputs) and surjectivity (every real number in the codomain is mapped to).
  • If the range covers only a subset of $\mathbb{R}$, the function is not onto, precluding the existence of a standard inverse function across $\mathbb{R}$.

Monotonicity of Functions: Increasing and Strictly Increasing Mappings

• Monotonicity Definitions on Subsets of Real Numbers (Page 143):

  • Consider a function $f$ whose domain and codomain are subsets of the set of real numbers $\mathbb{R}$.
  • Increasing Function: A function is classified as increasing if, when moving across the graph from left to right, the output value never decreases. Mathematically, for any domain elements $x_1$ and $x_2$: if $x_1 < x_2$, then $f(x_1) \le f(x_2)$.
  • Strictly Increasing Function: A function is classified as strictly increasing if it satisfies a strict inequality. Mathematically, for any domain elements $x_1$ and $x_2$: if $x_1 < x_2$, then $f(x_1) < f(x_2)$.
  • Geometric Interpretation: Tracing a strictly increasing function from left to right shows a curve that continuously ascends without any horizontal plateaus or downward segments.

• Examples of Strictly Increasing Functions:

  • $f(x) = x + 1$
  • $f(x) = x^3$
  • Any linear function of the form $f(x) = mx + b$ where the slope is strictly positive ($m > 0$).

• Contrasting Increasing vs. Strictly Increasing Behavior:

  • Linear functions with negative slopes ($m < 0$) are decreasing.
  • Piecewise or step functions that contain horizontal segments: if there exists an interval where $f(x_1) = f(x_2)$ for distinct points $x_1 \neq x_2$, the function fails the definition of being strictly increasing on that interval, even if $f(x_1) < f(x_3)$ holds for a point $x_3$ situated further to the right.

• Proof: Strictly Increasing Real Functions are One-to-One (Page 153, Problem 26):

  • Theorem: If a function $f: \mathbb{R} \rightarrow \mathbb{R}$ is strictly increasing, then $f$ is one-to-one (injective).
  • Proof:
    • Let $x_1$ and $x_2$ be arbitrary elements in $\mathbb{R}$ such that $x_1 \neq x_2$.

• Without loss of generality, assume $x_1 < x_2$.

• By the definition of a strictly increasing function, the assumption $x_1 < x_2$ directly implies that $f(x_1) < f(x_2)$.

• Because $f(x_1) < f(x_2)$, it follows that $f(x_1) \neq f(x_2)$.

• Therefore, distinct inputs map to distinct outputs, establishing that $f$ is one-to-one.

Pre-Images Under Quadratic Mappings

• Distinction Between Inverse Function and Pre-Image (Page 153, Problem 22):

  • Consider the quadratic mapping $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = x^2$.
  • Because $f(-x) = f(x)$, the function is not one-to-one; because negative real numbers have no real square roots, the function is not onto. Thus, $f$ does not possess an inverse function $f^{-1}: \mathbb{R} \rightarrow \mathbb{R}$.
  • The notation $f^{-1}(S)$ or $f^{-1}(y)$ can denote the pre-image (inverse image) of an element or set, defined as the set of all inputs in the domain that map into the designated target: $f^{-1}(S) = \{x \in \text{Domain} \mid f(x) \in S\}$.

• Pre-Image of a Single Point:

  • To find $f^{-1}(1)$ under $f(x) = x^2$, identify all domain inputs $x \in \mathbb{R}$ such that $x^2 = 1$.
  • Solving $x^2 = 1$ yields two values: $x = 1$ and $x = -1$.
  • The pre-image is the discrete set $\{-1, 1\}$.

• Pre-Image of an Open Interval (Part B):

  • Determine the pre-image of the interval $(0, 1)$, denoted $f^{-1}((0, 1))$, which requires finding all $x$ such that $0 < x^2 < 1$.
  • Graphical Projection Method:
    • Project the codomain target interval $y \in (0, 1)$ horizontally onto the parabola $y = x^2$.
    • The upper boundary $y = 1$ corresponds to the inputs $x = 1$ and $x = -1$.
    • The lower boundary $y = 0$ corresponds to $x = 0$.
    • Because the inequality is strict, neither $0$ nor $1$ is included in the output range.
  • Resulting Domain Intervals:
    • The input $x$ must lie either between $-1$ and $0$ or between $0$ and $1$.
    • The solution set is $(-1, 0) \cup (0, 1)$, represented in set notation as:$\{x \in \mathbb{R} \mid -1 < x < 0 \text{ or } 0 < x < 1\}$

• Pre-Image of an Unbounded Interval (Part C):

  • Determine the pre-image for outputs satisfying $y > 4$, which requires solving the inequality $x^2 > 4$.
  • Taking the square root across the inequality yields the absolute value condition: $|x| > \sqrt{4} = 2$.
  • Testing Intervals:
    • For values less than $-2$ (e.g., $x = -3$): $(-3)^2 = 9 > 4$, which satisfies the condition.
    • For values greater than $2$ (e.g., $x = 4$): $4^2 = 16 > 4$, which satisfies the condition.
  • Resulting Solution Set:
    • Projecting this region onto the graph shows all $x$ from negative infinity up to $-2$ (non-inclusive) and from $2$ up to positive infinity (non-inclusive).
    • The boundary values $\pm 2$ are excluded due to the strict inequality ($> 4$).
    • The solution is expressed with the logical disjunction "or":$(-\infty, -2) \cup (2, \infty) = \{x \in \mathbb{R} \mid x < -2 \text{ or } x > 2\}$

Theory and Classification of Sequences

• Curricular Importance of Sequences (Section 2.4):

  • Sequences, recurrence relations, and methods for finding general solutions serve as core prerequisites for upper-level coursework (such as Course 344).
  • These concepts occupy approximately two-thirds of advanced coursework and are used for:
    • Analyzing recurrence relations.
    • Evaluating recursion trees and determining tree height.
    • Deriving time complexity functions for algorithms.

• Formal Definition of a Sequence:

  • A sequence is a function whose domain is a subset of the integers, typically the set of natural numbers ($\mathbb{N} = \{0, 1, 2, \dots\}$) or positive integers ($\mathbb{Z}^+ = \{1, 2, 3, \dots\}$), mapping to a target set.
  • Standard Notation: Sequences are denoted by indexed sets or ordered lists:$a_0, a_1, a_2, \dots, a_n, \dots \quad \text{or} \quad \{a_n\}$

• Representations of Sequences:

  • Enumerated Terms: Specifying the initial consecutive terms of a sequence (e.g., $1, 4, 9, 16, \dots$) to determine the underlying pattern.
  • Recurrence Relations: Specifying an equation where the $n$-th term $a_n$ is defined in terms of one or more previous terms, such as:$a_n = a_{n-1} + a_{n-2}$
  • Closed-Form Solution: An explicit algebraic formula that calculates the value of $a_n$ directly from its index $n$, without computing preceding terms.

• Deriving Closed Forms for Standard Patterns:

  • Sequence of Squares:
    • Given initial terms: $1, 4, 9, 16, \dots$
    • Indexed from $n = 1$ ($a_1 = 1, a_2 = 4, a_3 = 9, a_4 = 16$).
    • Closed-form solution: $a_n = n^2$.
  • Alternating Sign Sequences:
    • Given terms: $-1, 1, -1, 1, \dots$
    • Indexed from $n = 1$:
      • When $n$ is odd ($n = 1, 3, 5, \dots$), the term is negative ($-1$).
      • When $n$ is even ($n = 2, 4, 6, \dots$), the term is positive ($1$).
      • Closed-form solution: $a_n = (-1)^n$.
    • If the parity is reversed (positive for odd indices, negative for even indices: $1, -1, 1, -1, \dots$), the closed form is written as $a_n = (-1)^{n+1}$ or $a_n = (-1)^{n-1}$.

Fundamental Progression Types: Geometric and Arithmetic

• Geometric Sequences:

  • A sequence where each term after the first is obtained by multiplying the previous term by a fixed, non-zero constant.
  • General Pattern:$a, ar, ar^2, ar^3, \dots, ar^n, \dots$
  • Parameters:
    • Initial term: $a$ (or $a_1$), representing the starting value.
    • Common ratio: $r$, representing the constant factor between successive terms ($r = \frac{a_n}{a_{n-1}}$).
  • Closed-Form Equations:
    • For indexing starting at $n = 0$: $a_n = a \times r^n$
    • For indexing starting at $n = 1$: $a_n = a \times r^{n-1}$

• Arithmetic Sequences:

  • A sequence where each term after the first is obtained by adding a constant numerical difference to the preceding term.
  • General Pattern:$a, a + d, a + 2d, a + 3d, \dots$
  • Parameters:
    • Initial term: $a$, representing the first term.
    • Common difference: $d$, representing the fixed increment ($d = a_n - a_{n-1}$).
  • Closed-Form Equation:
    • For indexing starting at $n = 1$:$a_n = a + (n - 1) \times d$

• Application Example for an Arithmetic Progression:

  • Initial term: $a = 9$.
  • Common difference: $d = 5$.
  • General Form Derivation:
    • Substitute the parameters into the arithmetic formula:$a_n = 9 + (n - 1) \times 5$

Questions & Classroom Exchanges

• Exchange on Well-Defined Functions:

  • Question: For the rule $f(n) = \frac{1}{n^2 - 4}$, is it a function from $\mathbb{Z}$ to $\mathbb{R}$?
  • Response: No. If an input $n$ is chosen such that the denominator becomes zero (specifically $n = 2$ or $n = -2$), the evaluation produces a non-real, undefined result.

• Exchange on Strictly Increasing Examples:

  • Question: What are examples of functions that are strictly increasing?
  • Response: $f(x) = x + 1$, $f(x) = x^3$, and any linear function characterized by a positive slope ($m > 0$).

• Exchange on Point Pre-Images:

  • Question: For $f(x) = x^2$, what is the pre-image of $1$, denoted $f^{-1}(1)$?
  • Response: The values are $1$ and $-1$, because evaluating the function at either $1$ or $-1$ yields $1$.

• Exchange on Interval Boundaries:

  • Question: If $y = 1$ under the mapping $f(x) = x^2$, what are the corresponding $x$-values?
  • Response: The $x$-values are $1$ and $-1$. For the interval $y \in (0, 1)$, the inputs must satisfy $-1 < x < 0$ or $0 < x < 1$.

• Exchange on Closed-Form Recognition:

  • Question: What pattern describes the sequence terms $1, 4, 9, 16$?
  • Response: The sequence consists of squares ($n^2$), giving the closed form $a_n = n^2$.

• Exchange on Arithmetic Formula Construction:

  • Question: What is the general form of an arithmetic progression with a first term of $9$ and a common difference of $5$?
  • Response: The first term is $9$ and $d = 5$, yielding the expression $a_n = 9 + (n - 1) \times 5$.