Chapter 1 – Relations and Functions

Basic counting formulas

Number of relation(set A) : 2^n²
Total Relations from A to B: 2^mn

Relation Properties (Conditions)

Reflexive : (a,a) ∈ R
Symmetric : (a,b) ∈ R ⇒ (b,a) ∈ R
Transitive : (a,b) ∈ R, (b,c) ∈ R ⇒ (a,c) ∈ R

Types of Functions

One-one : f(a) = f(b) ⇒ a = b
Many-one : f(a) = f(b) ⇒ a ≠ b
Into : Range ⊂ Codomain
Onto : Range = Codomain

Function operations

(f + g)(x) = f(x) + g(x)
(f - g)(x) = f(x) - g(x)
(f · g)(x) = f(x) · g(x)
(f/g)(x) = f(x)/g(x), g(x) ≠ 0

inverse Functions

f⁻¹(f(x)) = x
f(f⁻¹(x)) = x

Binary Operations

closure : a * b ∈ S for all a, b ∈ S
commutative : a * b = b * a
associative : (a * b) * c = a * (b * c)

Identity & Inverse Elements

Identity element: e * a = a * e = a
Inverse element: a * a⁻¹ = a⁻¹ * a = e

Relations and Functions