Understanding Complete Relations and Functions

Relations and functions constitute foundational concepts in higher mathematics, particularly within set theory. These notions precisely describe how elements from one set are associated with elements of another, providing the groundwork for mathematical analysis and algebraic structure.

Formal Definition of Relations as Subsets of Cartesian Products

Let $A$ and $B$ be non-empty sets. The Cartesian product $A\times B$ is defined as the set of all ordered pairs $(a,b)$ such that $a\in A$ and $b\in B$. Explicitly,

$A\times B = \{\, (a,b)\mid a\in A,\, b\in B\,\}$

A relation $\mathcal{R}$ from $A$ to $B$ is any subset of $A\times B$, i.e.,

$\mathcal{R}\subseteq A\times B$

If $(a,b)\in \mathcal{R}$, it is stated that $a$ is related to $b$ under the relation $\mathcal{R}$.

Domain, Co-domain, and Range of a Relation

Given a relation $\mathcal{R}\subseteq A\times B$:

Domain: The domain of $\mathcal{R}$ is the set of all $a\in A$ for which there exists $b\in B$ such that $(a,b)\in \mathcal{R}$. $$ \operatorname{Dom}(\mathcal{R}) = \{\, a\in A\mid \exists\, b\in B,\ (a,b)\in \mathcal{R}\,\} $$

Co-domain: The co-domain of $\mathcal{R}$ is the set $B$ itself.

Range: The range of $\mathcal{R}$ is the set of all $b\in B$ for which there exists $a\in A$ such that $(a,b)\in \mathcal{R}$. $$ \operatorname{Ran}(\mathcal{R}) = \{\, b\in B\mid \exists\, a\in A,\ (a,b)\in \mathcal{R}\,\} $$

Enumeration of the Total Number of Relations Between Two Finite Sets

If $|A|=m$ and $|B|=n$, then $|A\times B| = mn$. Since a relation from $A$ to $B$ is any subset of $A\times B$, the total number of distinct relations from $A$ to $B$ is $2^{mn}$.

Classification of Relations: Universal, Empty, Identity, Inverse, Reflexive, Symmetric, and Transitive

Universal Relation: For a set $A$, the relation $\mathcal{R}=A\times A$ is called a universal relation, as every possible ordered pair $(a_1,a_2)$ appears in $\mathcal{R}$.

Empty Relation: For sets $A$ and $B$, the relation $\mathcal{R} = \varnothing$ (with no elements) is termed the empty or void relation.

Identity Relation: If $A$ is a set, then the identity relation is $\mathcal{I} = \{\, (a,a)\mid a\in A\,\}$, containing all ordered pairs with identical elements from $A$.

Inverse Relation: For a relation $\mathcal{R}\subseteq A\times B$, its inverse relation is defined by $\mathcal{R}^{-1} = \{\, (b, a)\mid (a, b)\in \mathcal{R} \,\}$.

Reflexive Relation: A relation $\mathcal{R}$ on $A$ is reflexive if, for every $a\in A$, $(a,a)\in \mathcal{R}$.

Symmetric Relation: A relation $\mathcal{R}$ on $A$ is symmetric if $(a,b)\in \mathcal{R}$ implies $(b,a)\in \mathcal{R}$ for all $a,b\in A$.

Transitive Relation: A relation $\mathcal{R}$ on $A$ is transitive if $(a,b)\in \mathcal{R}$ and $(b,c)\in \mathcal{R}$ together imply $(a,c)\in \mathcal{R}$ for all $a,b,c\in A$.

Relations And Functions Overview

Equivalence Relations and Complete Relation Structure

Equivalence Relation: A relation $\mathcal{R}$ on $A$ is said to be an equivalence relation if and only if it is reflexive, symmetric, and transitive. Such relations partition the set $A$ into equivalence classes.

Complete Relation: Let $A$ and $B$ be sets. A relation $\mathcal{R}\subseteq A\times B$ is complete if for every $a\in A$, there exists at least one $b\in B$ such that $(a,b)\in \mathcal{R}$. This is also referred to as a total or full relation from $A$ to $B$.

If $A = B$ and $\mathcal{R}=A\times A$, the complete relation is simultaneously universal, reflexive, symmetric, and transitive.

Definition of Functions as Particular Relations

A function $f$ from set $A$ to set $B$ is a relation $f\subseteq A\times B$ such that for every $a\in A$, there exists a unique $b\in B$ for which $(a,b)\in f$. This is denoted as $f: A \to B$.

The element $b$ is called the image of $a$ under $f$, and $a$ is the pre-image of $b$.

The set $A$ is the domain of $f$, $B$ is the codomain, and the set of all images $f(A)$ is called the range.

Sets Relations And Functions

Types of Functions: Identity, Constant, Polynomial, Modulus, Signum, Greatest Integer

Identity Function: $f: \mathbb{R}\rightarrow\mathbb{R}$ defined by $f(x) = x$ for all $x\in\mathbb{R}$.

Constant Function: $f: \mathbb{R}\rightarrow\mathbb{R}$ given by $f(x) = c$, where $c$ is fixed and $x\in\mathbb{R}$.

Polynomial Function: $f: \mathbb{R}\rightarrow\mathbb{R}$, $f(x)=a_0+a_1x+\cdots+a_nx^n$, with $a_0,\ldots,a_n\in\mathbb{R}$, $n\in\mathbb{N}_0$.

Modulus Function: $f: \mathbb{R}\to\mathbb{R}$, $f(x) = |x|$, where $f(x) = x$ if $x\geq 0$, $f(x) = -x$ if $x<0$.

Signum Function: $f: \mathbb{R}\to\mathbb{R}$, defined as $$ f(x) = \begin{cases} 1,& x>0 \\ 0,& x=0 \\ -1,& x<0 \\ \end{cases} $$

Greatest Integer Function: $f: \mathbb{R}\to\mathbb{Z}$, $f(x) = [x]$, where $[x]$ is the largest integer less than or equal to $x$.

Types Of Functions

Relations and Functions: Distinction with Explicit Example

A relation $\mathcal{R}\subseteq A\times B$ may associate an element $a\in A$ with multiple elements in $B$ or none. In contrast, a function $f: A \to B$ assigns exactly one $b\in B$ to each $a\in A$.

Example: Let $A = \{1,2\}$, $B = \{3,4\}$.

Given: Relation $\mathcal{R}_1 = \{(1,3), (1,4)\}$; here, $1$ maps to both $3$ and $4$, so this relation is not a function.

Given: Relation $\mathcal{R}_2 = \{(1,3), (2,4)\}$. Here, each element of $A$ maps to a unique element of $B$, so $\mathcal{R}_2$ is a function.

Revision Notes On Relations

Properties of Functions: Injectivity, Surjectivity, Bijectivity

Injective Function (One-to-One): $f: A\to B$ is injective if $$ f(a_1) = f(a_2)\implies a_1=a_2,\quad \forall a_1,a_2\in A $$

Surjective Function (Onto): $f: A\to B$ is surjective if for every $b\in B$, there exists at least one $a\in A$ such that $f(a) = b$.

Bijective Function: A function $f$ is bijective if it is both injective and surjective; that is, $f$ is a one-to-one correspondence from $A$ to $B$.

Worked Example: Equivalence Relation on $\mathbb{N}\times \mathbb{N}$

Given: Define relation $\mathcal{R}$ on $\mathbb{N}\times\mathbb{N}$ by $(a,b)\,\mathcal{R}\,(c,d)\iff ad=bc$.

To Prove: $\mathcal{R}$ is an equivalence relation.

Reflexive: For any $(a,b)\in \mathbb{N}\times\mathbb{N}$, $$ ab = ba $$ which always holds. Therefore, $(a,b)\,\mathcal{R}\,(a,b)$ for all $(a,b)$.

Symmetric: Assume $(a,b)\,\mathcal{R}\,(c,d)$. $$ ad = bc $$ Both sides are equal, so $cb = da$, thus $(c,d)\,\mathcal{R}\,(a,b)$.

Transitive: Assume $(a,b)\,\mathcal{R}\,(c,d)$ and $(c,d)\,\mathcal{R}\,(e,f)$. Thus, $$ ad = bc \quad\text{and}\quad cf = de $$ From $ad=bc$, rearrange: $a d = b c$. From $cf=de$, rearrange: $c f = d e$. Multiply $ad=bc$ by $f$: $$ (ad) f = (bc) f \implies a d f = b c f $$ Multiply $cf=de$ by $b$: $$ b (c f) = b (d e) \implies b c f = b d e $$ Set $a d f = b d e$. If $d\neq0$, divide both sides by $d$: $$ \frac{a d f}{d} = \frac{b d e}{d} \implies a f = b e $$ So $(a,b)\,\mathcal{R}\,(e,f)$. Thus, $\mathcal{R}$ is transitive.

Result: The relation is reflexive, symmetric, and transitive; therefore, $\mathcal{R}$ is an equivalence relation.

Important Questions On Relations

Worked Example: Domain and Range Calculation

Given: $y = \sqrt{5-2x}$

Substitution: The expression under the root must be non-negative, $$ 5-2x \geq 0 $$

Simplification: Rearranging, $$ 5-2x \geq 0 \implies -2x \geq -5 \implies 2x \leq 5 \implies x \leq \frac{5}{2} $$

Final Result: The domain is $(-\infty, 5/2]$.

Worked Example: Range Calculation for a Translated Trigonometric Function

Given: $f(x) = 3-\cos x$

Substitution: Since $-1 \leq \cos x \leq 1$ for all $x$, $$ 3 - 1 \leq f(x) \leq 3 - (-1) $$

Simplification: $$ 2 \leq f(x) \leq 4 $$

Final Result: The range of $f(x)$ is $[2,4]$.

Key Formulas and Algebraic Tests Associated with Relations and Functions

For $A, B$ finite, relation $\mathcal{R}\subseteq A\times B$:

$\operatorname{Dom}(\mathcal{R}) = \{ a \mid (a,b)\in\mathcal{R} \}$
$\operatorname{Ran}(\mathcal{R}) = \{ b \mid (a,b)\in\mathcal{R} \}$
$\operatorname{CoDom}(\mathcal{R}) = B$
$\text{No. of relations } = 2^{|A||B|}$
$\text{Vertical Line Test:}$ Any vertical line crosses the graph of $f: A\to B$ at most at one point $\implies$ relation $f$ is a function.

One-to-one (injective): $f(a_1)=f(a_2)\implies a_1=a_2$
Onto (surjective): $\forall b \in B,\ \exists a\in A,\ f(a)=b$
Bijective: Both injective and surjective
Composition: If $f:A\to B,\ g:B\to C$, $(g\circ f)(x) = g(f(x))$

Mock Test For Relations

Conclusion: Structural Summary of Relations and Functions

Relations structure mathematical associations as subsets of Cartesian products, while functions constitute relations providing unique output for each input. The properties of relations, including reflexivity, symmetry, and transitivity, lead to equivalence and complete relations. The formal language of relations and functions, along with associated algebraic criteria, is foundational for advanced mathematical reasoning.