Relations and Functions

Flashcards on Relations and Functions based on lecture notes.

Relation (mathematical)

An arbitrary subset of A × B, where A and B are sets.

Empty Relation

A relation R in a set A where no element of A is related to any element of A, i.e., R = φ ⊂ A × A.

Universal Relation

A relation R in a set A where each element of A is related to every element of A, i.e., R = A × A.

Reflexive Relation

A relation R in a set A is reflexive if (a, a) ∈ R for every a ∈ A.

Symmetric Relation

A relation R in a set A is symmetric if (a1, a2) ∈ R implies that (a2, a1) ∈ R, for all a1, a2 ∈ A.

Transitive Relation

A relation R in a set A is transitive if (a1, a2) ∈ R and (a2, a3) ∈ R implies that (a1, a3) ∈ R, for all a1, a2, a3 ∈ A.

Equivalence Relation

A relation R in a set A is an equivalence relation if R is reflexive, symmetric, and transitive.

One-to-one Function (Injective)

A function f: X → Y is one-to-one if the images of distinct elements of X under f are distinct; i.e., for every x1, x2 ∈ X, f(x1) = f(x2) implies x1 = x2.

Onto Function (Surjective)

A function f: X → Y is onto if every element of Y is the image of some element of X under f; i.e., for every y ∈ Y, there exists an element x in X such that f(x) = y.

Bijective Function

A function f: X → Y is bijective if f is both one-to-one and onto.

Invertible Function

A function f: X → Y is invertible if there exists a function g: Y → X such that gof = IX and fog = IY. The function g is called the inverse of f and is denoted by f^{-1}.

Composition of Functions

Given two functions f: A → B and g: B → C, the composition of f and g, denoted by gof, is defined as the function gof: A → C given by gof(x) = g(f(x)), ∀ x ∈ A.