Discrete Mathematics Flashcards: Functions, Induction, and Relations

Flashcards covering key definitions and theorems from days 13 through 22 of Math 199, including function types, the Principle of Mathematical Induction, and equivalence relations.

Injective (One-to-One)

A function $f : X \rightarrow Y$ is injective if and only if $\forall x_1, x_2 \in X$, if $f(x_1) = f(x_2)$ then $x_1 = x_2$. Only one element of the domain maps to each element of the image.

Surjective (Onto)

A function $f : X \rightarrow Y$ is surjective if and only if $\forall y \in Y$, $\exists x \in X$ such that $f(x) = y$. Every element in the codomain is reached by the function.

Bijective

A function that is both injective (one-to-one) and surjective (onto); also referred to as a one-to-one correspondence.

Invertible

A function $f : X \rightarrow Y$ is invertible if and only if there exists a function $g : Y \rightarrow X$ such that $g \circ f = I_X$ ($\forall x \in X, g(f(x)) = x$) and $f \circ g = I_Y$ ($\forall y \in Y, f(g(y)) = y$). In this case, $g$ is called the inverse of $f$.

The Invertibility Theorem

A theorem stating that a function $f : X \rightarrow Y$ is invertible if and only if $f$ is a bijection.

Direct Image

Let $f : X \rightarrow Y$ be a function and $A \subseteq X$. The direct image of $A$ under $f$, denoted $f(A)$, is the subset of $Y$ defined by $f(A) = \{f(x) \mid x \in A\}$. Note that $y \in f(A) \iff \exists x \in A$ such that $f(x) = y$.

Inverse Image (Preimage)

Let $f : X \rightarrow Y$ be a function and $B \subseteq Y$. The inverse image of $B$ under $f$, denoted $f^{-1}(B)$, is the subset of $X$ defined by $f^{-1}(B) = \{x \in X \mid f(x) \in B\}$. This set exists regardless of whether $f$ is invertible.

Induced Function

Starting with a function $f : X \rightarrow Y$, the induced function $\mathbf{ind}(f) : P(X) \rightarrow P(Y)$ is defined by $(\mathbf{ind}(f))(A) = f(A)$, where it takes a subset of $X$ as input and returns its direct image in $Y$.

Principle of Mathematical Induction (PMI - Version a)

Let $P(n)$ be a statement about a natural number variable $n$. If (i) $P(1)$ is true, and (ii) $\forall k \ge 1, P(k) \text{ is true} \implies P(k + 1) \text{ is true}$, then $\forall n \in \mathbb{N}, P(n)$ is true.

Least Number Principle (LNP)

Also called the Well-Ordering Principle (WOP), it states that every nonempty subset of $\mathbb{N}$ has a smallest element. It is equivalent to the Principle of Mathematical Induction.

Base Step

The first step of a proof by induction where one shows that the statement $P(n)$ holds for the initial value (usually $n = 1$ or $n = n_0$).

Inductive Hypothesis

In the context of a proof by induction, this is the assumption that the statement $P(n)$ is true for some arbitrary integer $k$.

Inductive Step

The part of an induction proof where one shows that if the statement holds for $k$, then it must also hold for $k + 1$.

Strong Induction

A form of induction where the inductive hypothesis assumes that the statement $P(i)$ is true for all integers $i$ such that $n_0 \le i \le k$ in order to prove $P(k + 1)$. This is useful when the recurrence depends on multiple previous terms.

Relation (on a set X)

A subset $R$ of the Cartesian product $X \times X$. If $(a, b) \in R$, we say element $a$ is related to $b$, often written as $aRb$, $a \sim b$, or $a \equiv b \pmod R$.

Reflexive Relation

A relation $R$ on a set $X$ is reflexive if $\forall x \in X, (x, x) \in R$. Every element is related to itself.

Symmetric Relation

A relation $R$ on a set $X$ is symmetric if $(x, y) \in R \implies (y, x) \in R$. If $x$ is related to $y$, then $y$ is related to $x$.

Transitive Relation

A relation $R$ on a set $X$ is transitive if $(x, y) \in R$ and $(y, z) \in R \implies (x, z) \in R$.

Equivalence Relation

A relation on a set $X$ that is simultaneously reflexive, symmetric, and transitive.

Equivalence Class

Given an equivalence relation $R$ on $X$, the equivalence class of an element $x \in X$, denoted $[x]$, is the set of all elements in $X$ related to $x$, i.e., $[x] = \{y \in X \mid (x, y) \in R\}$. Every $(x, y) \in R \iff [x] = [y]$.

Quotient of X by R (X/R)

The set of all distinct equivalence classes produced by an equivalence relation $R$ on a set $X$, defined as $X/R = \{[x] \mid x \in X\}$. It is a subset of the power set $P(X)$.

Canonical Mapping

Also called the natural projection, it is the function $f : X \rightarrow X/R$ defined by $f(x) = [x]$, which maps each element to its corresponding equivalence class. This function is always surjective.

Partition

A collection $P$ of nonempty subsets (cells) of $X$ such that every element of $X$ belongs to exactly one cell in $P$. Formally: (1) $\forall x \in X, \exists A \in P \text{ s.t. } x \in A$ and (2) $\forall A, B \in P, A \neq B \implies A \cap B = \emptyset$.