1.4 Functions, Relations, and Sequences
Functions
Definition
A function ƒ from a set A domain to a set B codomain is a rule that assigns to each x∈A a unique ƒ(x)∈B. Denote ƒ:A→B.
Types of Functions
Injective (One-to-One): ƒ((x_1))=ƒ((x_2))→(x_1)=(x_2).
Surjective (Onto): ∀y∈B∃x∈A:ƒ(x)=y
Bijective: Both injective and surjective; has an inverse ƒ(-1):B→A.
Operations on Functions
Composition: Given ƒ:A→B, g:B→C, define g○ƒ:B→C by (g○ƒ)*(x)=g(ƒ(x)).
Inverse Function: If ƒ is bijective, then ƒ(-1):B→A satisfies (ƒ^-1)(ƒ(x))=x and ƒ((ƒ^-1)(y))=y.
Relations
Definition
A relation R on sets A and B is a subset R⊆A×B. If (a,b)∈R, we write a*R*b.
Properties of Relations on a Set A
Reflexive: ∀a∈A:(a,a)∈R.
Symmetric: If (a,b)∈R, then (b,a)∈R.
Antisymmetric: If (a,b)∈R and (b,a)∈R, then a=b.
Transitive: If (a,b)∈R and (b,c)∈R, then (a,c)∈R.
Special Relations
Equivalence Relation: Reflexive, symmetric, and transitive. Partitions A into equivalence classes.
Partial Order: Reflexive, antisymmetric, and transitive. Yields poset (A,≤).
Sequences
Definition
A sequence is a function a:ℕ→S, often denoted ((a_n))(n≧0) or {(a_n)}(n=0)∞.
Types of Sequences
Finite Sequence: Defined for n=0*1,⋯,N.
Infinite Sequence: Defined for all n∈ℕ.
Arithmetic Sequence
Defined by (a_n)=(a_0)+n*d. Sum of first n terms: (∑_k=0^n)((a_k))=(n+1)((a_0)+(a_n))/2.
Geometric Sequence
Defined by (a_n)=(a_0)*rn. Sum of first n terms: (∑_k=0^n)((a_0)*rk)=(a_0)(1-r(n+1))/(1-r) ;r≠1.
Recurrence Relations
A relation defining (a_n) in terms of previous terms, e.g. (a_n+1)=p*(a_n)+q*(a_n-1) with initial conditions. Use characteristic equations to solve.