Relations and Functions

Relations

• A relation R from set A to set B is a subset of A \times B. If (a, b) \in R, then a is related to b, written as a R b. Relations describe how elements of two sets are associated with each other.

• Key Aspects of Relations:

  • Domain: The set of all first elements from the ordered pairs in R. If R \subseteq A \times B, then the domain is a subset of A.

  • Range: The set of all second elements from the ordered pairs in R. If R \subseteq A \times B, then the range is a subset of B.

  • Representation: Relations can be represented using set-builder notation, roster form, arrow diagrams, and matrices.

• Types of Relations:

  • Empty Relation: No element of A is related to any element of A, i.e., R = \phi \subseteq A \times A. This means the relation contains no ordered pairs.

  • Universal Relation: Each element of A is related to every element of A, i.e., R = A \times A. Every possible pair of elements is in the relation.

  • Reflexive: (a, a) \in R for every a \in A. Each element is related to itself.

  • Example: On the set of real numbers, the relation "equal to" is reflexive because every number is equal to itself.

  • Symmetric: If (a1, a2) \in R, then (a2, a1) \in R for all a1, a2 \in A. If a is related to b, then b is related to a.

  • Example: If "is a sibling of" is a relation, and if Alice is a sibling of Bob, then Bob is a sibling of Alice.

  • Transitive: If (a1, a2) \in R and (a2, a3) \in R, then (a1, a3) \in R for all a1, a2, a_3 \in A. If a is related to b and b is related to c, then a is related to c.

  • Example: If "is an ancestor of" is a relation, and if Alice is an ancestor of Bob, and Bob is an ancestor of Charlie, then Alice is an ancestor of Charlie.

• Equivalence Relation: A relation R in a set A is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence relations partition the set into disjoint equivalence classes.

  • Example: The relation "congruence modulo n" on the set of integers is an equivalence relation.

• Equivalence Classes: For an equivalence relation R in a set X, the equivalence class containing a is the set of all elements related to a. These classes partition X into disjoint subsets.

  • Notation: The equivalence class of an element a is often denoted as [a] or \overline{a}.

  • Properties:

  • Every element of X belongs to exactly one equivalence class.

  • If two equivalence classes have an element in common, they are the same class.

Functions

A function f: X \rightarrow Y maps elements from set X (domain) to set Y (co-domain). For each element in X, there is a unique element in Y to which it is mapped.

• Key Terminologies:

  • Domain: The set X from which the function maps elements.

  • Co-domain: The set Y to which the function maps elements.

  • Range (Image): The subset of Y consisting of all actual output values of the function.

  • Preimage: For any y \in Y, the preimage of y is the set of all x \in X such that f(x) = y.

• Types of Functions:

  • One-to-one (Injective): Different elements in X have different images in Y. Formally, if f(x1) = f(x2), then x1 = x2. Each element in the range has a unique preimage.

  • Example: f(x) = x^3 is injective over the real numbers.

  • Onto (Surjective): Every element in Y is the image of some element in X. For every y \in Y, there exists an x \in X such that f(x) = y. The range of the function is equal to its co-domain.

  • Example: For f: \mathbb{R} \rightarrow \mathbb{R}, defined by f(x) = 2x, every real number can be obtained as an output.

  • Bijective: Function is both one-to-one and onto. There is a perfect pairing between elements of X and Y.

  • Example: f(x) = x is a bijective function from any set to itself.

Composition and Invertible Functions

• Composition of Functions: Given f: A \rightarrow B and g: B \rightarrow C, the composition g \circ f: A \rightarrow C is defined by (g \circ f)(x) = g(f(x)). The output of f becomes the input of g.

  • Properties:

  • Composition is associative: h \circ (g \circ f) = (h \circ g) \circ f.

  • Composition is not generally commutative: f \circ g is not necessarily equal to g \circ f.

• Invertible Function: A function f: X \rightarrow Y is invertible if there exists a function g: Y \rightarrow X such that g \circ f = IX and f \circ g = IY, where IX and IY are identity functions on X and Y, respectively. If f is invertible, then f is one-to-one and onto, and its inverse is denoted as f^{-1}.

  • Conditions for Invertibility:

  • A function must be bijective to be invertible.

  • Finding the Inverse:

  • To find the inverse of a function, solve for x in terms of y and then switch x and y.