Functions and Equivalence Relations

Functions

In mathematics, a function is a fundamental concept that describes a relationship between two sets. It's like a rule that assigns each element from a first set (called the domain) to exactly one element in a second set (called the codomain). Think of it as a machine: you put something in, and it gives you exactly one specific output.

Definition of a Function

Let A and B be two non-empty sets. A function from A to B, denoted by $f: A \to B$, is a rule that assigns to each element $x \in A$ a unique element $y \in B$. The element $y$ is called the image of $x$ under $f$, and it is denoted by $f(x)$.

• Set A is called the domain of the function $f$.
• Set B is called the codomain of the function $f$.
• The set of all images of elements in A is called the range of the function $f$. The range is a subset of the codomain, i.e., Range$(f) \subseteq B$.

Conditions for a Relation to be a Function

A relation R from a set A to a set B is a function if and only if:

1. The domain of the relation is A. (Every element in A must be related to some element in B).
2. No element in A is related to more than one element in B. (Each element in A has a unique image).

Types of Functions

Functions can be classified based on how they map elements between their domain and codomain.

1. One-to-One (Injective) Functions

A function $f: A \to B$ is said to be one-to-one or injective if distinct elements in the domain A map to distinct elements in the codomain B. In other words, if $x_1, x_2 \in A$ and $x_1 \neq x_2$, then $f(x_1) \neq f(x_2)$. An equivalent way to state this is: if $f(x_1) = f(x_2)$, then $x_1 = x_2$.

Example: Let $f: \mathbb{Z} \to \mathbb{Z}$ be defined by $f(x) = 2x$. If $f(x_1) = f(x_2)$, then $2x_1 = 2x_2$, which implies $x_1 = x_2$. Thus, $f(x) = 2x$ is a one-to-one function.

2. Onto (Surjective) Functions

A function $f: A \to B$ is said to be onto or surjective if every element in the codomain B is the image of at least one element in the domain A. This means the range of the function is equal to its codomain: Range$(f) = B$.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^3$. For any $y \in \mathbb{R}$ (codomain), there exists an $x = \sqrt[3]{y} \in \mathbb{R}$ (domain) such that $f(x) = (\sqrt[3]{y})^3 = y$. Thus, $f(x) = x^3$ is an onto function.

3. Bijective Functions

A function $f: A \to B$ is said to be bijective if it is both one-to-one (injective) and onto (surjective). Bijective functions are important because they establish a perfect pairing between the elements of the domain and the codomain. This means there's a unique inverse function.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = 3x + 2$. To check if it's one-to-one: If $f(x_1) = f(x_2)$, then $3x_1 + 2 = 3x_2 + 2$, which implies $3x_1 = 3x_2$, so $x_1 = x_2$. It is one-to-one. To check if it's onto: For any $y \in \mathbb{R}$, let $x = (y-2)/3$. Then $f(x) = 3((y-2)/3) + 2 = (y-2) + 2 = y$. So, for every $y$ in the codomain, there's an $x$ in the domain that maps to it. It is onto. Since it's both one-to-one and onto, $f(x) = 3x + 2$ is a bijective function.

4. Into Functions

A function $f: A \to B$ is called an into function if it is not onto. This means there is at least one element in the codomain B that is not the image of any element in the domain A. In other words, Range$(f) \subsetneq B$.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^2$. The range of this function is $[0, \infty)$, which is a proper subset of the codomain $\mathbb{R}$. For example, $-1 \in \mathbb{R}$ is not the image of any real number $x$ since $x^2 \geq 0$. Thus, $f(x) = x^2$ is an into function.

5. Constant Functions

A function $f: A \to B$ is called a constant function if all elements in the domain A map to the same single element in the codomain B. That is, there exists a $c \in B$ such that $f(x) = c$ for all $x \in A$.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = 5$. For every real number $x$, the output is always 5. This is a constant function.

6. Identity Functions

An identity function $f: A \to A$ on a set A is a function where every element maps to itself. That is, $f(x) = x$ for all $x \in A$. The identity function is always bijective.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x$. This is the identity function on the set of real numbers.

Composition of Functions

If we have two functions, $f: A \to B$ and $g: B \to C$, we can compose them to create a new function from A to C. This is denoted by $g \circ f$. The composition $g \circ f$ is defined as $(g \circ f)(x) = g(f(x))$ for all $x \in A$. It's important to note that the order of composition matters. In general, $g \circ f \neq f \circ g$. The inner function's codomain must match the outer function's domain.

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be $f(x) = x+1$ and $g: \mathbb{R} \to \mathbb{R}$ be $g(x) = x^2$. Then $(g \circ f)(x) = g(f(x)) = g(x+1) = (x+1)^2$. And $(f \circ g)(x) = f(g(x)) = f(x^2) = x^2+1$. As you can see, $(g \circ f)(x) \neq (f \circ g)(x)$ in this case.

Inverse Functions

A function $f: A \to B$ has an inverse function, denoted by $f^{-1}: B \to A$, if and only if $f$ is bijective (one-to-one and onto). The inverse function $f^{-1}$ reverses the mapping of $f$. If $f(x) = y$, then $f^{-1}(y) = x$.

For a function $f$ to have an inverse $f^{-1}$, the following conditions must hold:

• $(f^{-1} \circ f)(x) = x$ for all $x \in A$ (identity on A)
• $(f \circ f^{-1})(y) = y$ for all $y \in B$ (identity on B)

Example: Let $f: \mathbb{R} \to \mathbb{R}$ be $f(x) = 3x + 2$. We found this is bijective. To find the inverse, let $y = 3x + 2$. We solve for $x$ in terms of $y$: $y - 2 = 3x$ $x = (y-2)/3$ So, the inverse function is $f^{-1}(y) = (y-2)/3$. If we use $x$ as the variable, $f^{-1}(x) = (x-2)/3$. Let's check: $(f^{-1} \circ f)(x) = f^{-1}(f(x)) = f^{-1}(3x+2) = ((3x+2)-2)/3 = (3x)/3 = x$. $(f \circ f^{-1})(x) = f(f^{-1}(x)) = f((x-2)/3) = 3((x-2)/3) + 2 = (x-2) + 2 = x$. The inverse function exists and is correctly found.

Equivalence Relations

An equivalence relation is a specific type of binary relation on a set that satisfies three properties: reflexivity, symmetry, and transitivity. These properties mean that the relation behaves in a way that partitions the set into disjoint subsets, where elements within each subset are related to each other, and elements from different subsets are not related.

Definition of a Relation

A relation R on a set A is a subset of the Cartesian product $A \times A$. If $(a, b) \in R$, we say that 'a is related to b' and write $a R b$.

Properties of Relations

Let R be a relation on a set A.

1. Reflexive Property

R is reflexive if for every element $a \in A$, $(a, a) \in R$. In simpler terms, every element is related to itself.

Example: The relation "$\leq$" (less than or equal to) on the set of real numbers is reflexive because for any real number $a$, $a \leq a$ is true. The relation "is a sibling of" on a set of people is not reflexive, as a person is not their own sibling.

2. Symmetric Property

R is symmetric if for every $a, b \in A$, whenever $(a, b) \in R$, then $(b, a) \in R$. If a is related to b, then b must also be related to a.

Example: The relation "is married to" on a set of married couples is symmetric. If person A is married to person B, then person B is married to person A. The relation "is taller than" on a set of people is not symmetric. If person A is taller than person B, person B is not taller than person A.

3. Transitive Property

R is transitive if for every $a, b, c \in A$, whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. If a is related to b, and b is related to c, then a must be related to c.

Example: The relation "<" (less than) on the set of real numbers is transitive. If $a < b$ and $b < c$, then it is always true that $a < c$. The relation "is the parent of" on a set of people is not transitive. If A is the parent of B, and B is the parent of C, then A is the grandparent of C, not the parent of C.

Definition of an Equivalence Relation

A relation R on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

Equivalence Classes

If R is an equivalence relation on a set A, then for any element $a \in A$, the equivalence class of $a$, denoted by $[a]$ or $\bar{a}$, is the set of all elements in A that are related to $a$. $[a] = \{x \in A \mid x R a\}$.

Properties of Equivalence Classes:

• For any $a \in A$, $a \in [a]$. (This follows from reflexivity).
• If $b \in [a]$, then $[b] = [a]$. (If $b$ is related to $a$, their equivalence classes are the same).
• For any $a, b \in A$, either $[a] = [b]$ or $[a] \cap [b] = \emptyset$. (Equivalence classes are either identical or disjoint).

The set of all distinct equivalence classes of A under R is called the quotient set of A by R, denoted by $A/R$. The collection of equivalence classes forms a partition of the set A.

Examples of Equivalence Relations

Example 1: Equality Relation Let A be any set. The equality relation, $R = \{(a, a) \mid a \in A\}$, where $a R b$ if and only if $a = b$.

• Reflexive: For any $a \in A$, $a=a$, so $(a,a) \in R$.
• Symmetric: If $a=b$, then $b=a$. If $(a,b) \in R$, then $a=b$, so $b=a$, hence $(b,a) \in R$.
• Transitive: If $a=b$ and $b=c$, then $a=c$. If $(a,b) \in R$ and $(b,c) \in R$, then $a=b$ and $b=c$, so $a=c$, hence $(a,c) \in R$.

This is an equivalence relation. The equivalence class of any element $a$ is just $\{a\}$. The quotient set $A/R$ is the set of all singleton sets, which is essentially the set A itself.

Example 2: Congruence Modulo n Let $n$ be a positive integer. Define a relation R on the set of integers $\mathbb{Z}$ such that $a R b$ if and only if $a - b$ is divisible by $n$. This is written as $a \equiv b \pmod{n}$.

• Reflexive: For any integer $a$, $a - a = 0$, which is divisible by $n$. So $a \equiv a \pmod{n}$.
• Symmetric: If $a \equiv b \pmod{n}$, then $a - b = kn$ for some integer $k$. Then $b - a = -(a - b) = -kn = (-k)n$. So $b - a$ is divisible by $n$, which means $b \equiv a \pmod{n}$.
• Transitive: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a - b = k_1n$ and $b - c = k_2n$ for integers $k_1, k_2$. Adding these equations: $(a - b) + (b - c) = k_1n + k_2n$. This simplifies to $a - c = (k_1 + k_2)n$. Since $k_1 + k_2$ is an integer, $a - c$ is divisible by $n$, so $a \equiv c \pmod{n}$.

Thus, congruence modulo $n$ is an equivalence relation. The equivalence class of an integer $a$ is the set of all integers $x$ such that $x \equiv a \pmod{n}$. This set is $\{ \dots, a-2n, a-n, a, a+n, a+2n, \dots \}$. These are the numbers that have the same remainder when divided by $n$. The equivalence classes are typically represented by the remainders $0, 1, 2, \dots, n-1$. So, the quotient set is $\mathbb{Z}/n\mathbb{Z} = \{[0], [1], \dots, [n-1]\}$, which has $n$ elements.

Example 3: Parallel Lines Consider the set of all lines in a plane. Define a relation R such that line $L_1 R L_2$ if and only if $L_1$ is parallel to $L_2$.

• Reflexive: Every line is parallel to itself. $L_1 R L_1$.
• Symmetric: If $L_1$ is parallel to $L_2$, then $L_2$ is parallel to $L_1$. If $L_1 R L_2$, then $L_2 R L_1$.
• Transitive: If $L_1$ is parallel to $L_2$, and $L_2$ is parallel to $L_3$, then $L_1$ is parallel to $L_3$. If $L_1 R L_2$ and $L_2 R L_3$, then $L_1 R L_3$.

This is an equivalence relation. The equivalence class of a line is the set of all lines parallel to it.

Equivalence Relations and Partitions

There is a deep connection between equivalence relations and partitions of a set. A partition of a set A is a collection of non-empty, pairwise disjoint subsets of A whose union is A.

• Theorem: If R is an equivalence relation on a set A, then the set of equivalence classes $A/R$ forms a partition of A.
• Theorem: If $\mathcal{P} = \{A_1, A_2, \dots, A_k\}$ is a partition of a set A, then the relation R defined by $a R b$ if and only if $a$ and $b$ belong to the same subset $A_i$ in the partition is an equivalence relation.

This means that equivalence relations and partitions are two ways of looking at the same concept: dividing a set into mutually exclusive and exhaustive categories.

Applications

Equivalence relations are used extensively in various branches of mathematics, including abstract algebra (e.g., defining quotient groups and rings), number theory (e.g., modular arithmetic), and topology. They provide a systematic way to classify objects based on specific properties.