Unit 1: Set Theory, Relation and Function

I. Orientation: The Language of Sets

Set theory (formalised by Georg Cantor, 1874) supplies the foundational vocabulary for relations and functions. A set is a well-defined collection of distinct objects, called its elements or members. "Well-defined" means membership is unambiguous: for any object, we can decide yes or no whether it belongs.

• Membership notation: if x belongs to set A, write x ∈ A; otherwise x ∉ A. Example: 3 ∈ {1,2,3}, 4 ∉ {1,2,3}.
• Distinctness: elements are never repeated; {1,1,2} is just {1,2}.
• Order-independence: {a,b} = {b,a}; sequence carries no meaning in a set.
• Cardinality: the number of elements is written n(A) or |A|. For A = {a,e,i,o,u}, n(A) = 5.
• Universal set (U): the fixed superset containing every element under discussion in a given context.

II. Describing and Classifying Sets

A. Description of a Set

A set can be specified two ways, and both must define membership unambiguously.

• Roster (tabular) form: list every element inside braces, separated by commas: A = {2,4,6,8}.
• Set-builder form: state the defining property: A = {x : x is an even natural number, x ≤ 8}. The colon reads "such that".
• Conversion example: {x : x² = 9, x ∈ ℤ} in roster form is {-3, 3}.

B. Types of Sets

Sets are classified by size and content.

• Empty (null) set: contains no element, written ∅ or {}; n(∅) = 0. Example: {x : x² = -1, x ∈ ℝ} = ∅.
• Singleton set: exactly one element, e.g. {0}.
• Finite set: countable, terminating membership; n(A) is a natural number.
• Infinite set: membership never terminates, e.g. ℕ = {1,2,3,…}.
• Equal sets: A = B iff they have exactly the same elements. {1,2,3} = {3,2,1}.
• Equivalent sets: same cardinality, n(A) = n(B), even if elements differ.
• Disjoint sets: share no element; A ∩ B = ∅.

C. Subsets

A subset relation orders sets by containment.

• Definition: A ⊆ B iff every element of A is also in B. Formally x ∈ A ⟹ x ∈ B.
• Proper subset: A ⊂ B when A ⊆ B but A ≠ B (B has an extra element).
• Standing facts: ∅ ⊆ A for every set; A ⊆ A (reflexive).
• Number of subsets: a set of n elements has 2ⁿ subsets and 2ⁿ − 1 proper subsets. For {a,b}: subsets are ∅, {a}, {b}, {a,b} — that is 2² = 4.

D. Power Set

The power set collects all subsets into one set.

• Definition: P(A) is the set whose elements are every subset of A.
• Cardinality: n(P(A)) = 2ⁿ where n = n(A).
• Example: for A = {1,2}, P(A) = {∅, {1}, {2}, {1,2}}, so n(P(A)) = 4.

E. Venn Diagrams

Venn diagrams (John Venn, 1880) picture sets as regions to make relations visible.

• Convention: the universal set U is a rectangle; each set is a circle inside it.
• Reading them: overlaps show A ∩ B; the total shaded region shows A ∪ B; the region of U outside A shows the complement Aᶜ.
• Use: they verify identities and count elements when regions are labelled with cardinalities.

III. Operations on Sets

A. Union, Intersection and Difference

These build new sets from given ones; each has a defining condition.

• Union: A ∪ B = {x : x ∈ A or x ∈ B} — every element in either set.
  • Example: {1,2,3} ∪ {3,4} = {1,2,3,4}.
• Intersection: A ∩ B = {x : x ∈ A and x ∈ B} — elements common to both.
  • Example: {1,2,3} ∩ {3,4} = {3}.
• Difference: A − B = {x : x ∈ A and x ∉ B} — in A but not B; note A − B ≠ B − A.
  • Example: {1,2,3} − {3,4} = {1,2}.
• Complement: Aᶜ = U − A, all elements of the universal set outside A.
• Inclusion–exclusion (counting): n(A ∪ B) = n(A) + n(B) − n(A ∩ B).

B. Laws of Set Theory

These algebraic identities let expressions be simplified; each holds for all sets in a universe U.

• Commutative: A ∪ B = B ∪ A; A ∩ B = B ∩ A.
• Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C); likewise for ∩.
• Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
• Identity: A ∪ ∅ = A; A ∩ U = A.
• Idempotent: A ∪ A = A; A ∩ A = A.
• Complement: A ∪ Aᶜ = U; A ∩ Aᶜ = ∅.
• De Morgan's laws: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ; (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

C. Cartesian Product of Sets

The Cartesian product pairs elements to build the ground on which relations live.

• Definition: A × B = {(a,b) : a ∈ A, b ∈ B}, a set of ordered pairs.
• Ordered pair: (a,b) = (c,d) iff a = c and b = d; order matters, so A × B ≠ B × A in general.
• Cardinality: n(A × B) = n(A) × n(B).
• Example: {1,2} × {x,y} = {(1,x),(1,y),(2,x),(2,y)}, four pairs.

IV. Relations

A. Relations as Subsets of a Product

A relation captures an association between two sets by selecting ordered pairs.

• Definition: a relation R from A to B is any subset R ⊆ A × B. If (a,b) ∈ R, write a R b.
• Domain and range: the domain is {a : (a,b) ∈ R}; the range is {b : (a,b) ∈ R}.
• Example: on A = {1,2,3}, R = {(a,b) : a < b} = {(1,2),(1,3),(2,3)}.
• Total count: since A × B has n(A)·n(B) pairs, there are 2^{n(A)·n(B)} possible relations.
• Key types (on a set A):
  • Reflexive: (a,a) ∈ R for all a ∈ A.
  • Symmetric: (a,b) ∈ R ⟹ (b,a) ∈ R.
  • Transitive: (a,b),(b,c) ∈ R ⟹ (a,c) ∈ R.

V. Functions

A. Functions as Special Relations

A function is a relation that assigns each input exactly one output.

• Definition: f : A → B is a relation from A to B such that every a ∈ A maps to one and only one b ∈ B, written f(a) = b.
• Domain, codomain, range: A is the domain, B the codomain, and the range is {f(a) : a ∈ A} ⊆ B.
• Vertical line test: a graph is a function iff no vertical line meets it more than once.
• Example: f(x) = x² on ℝ maps −2 and 2 both to 4 — allowed, since each input still has a single output.

B. Some Functions and Their Graphs

Each standard function is defined by its rule, and its graph reveals its behaviour.

1. Identity function: f(x) = x. Every input maps to itself; the graph is the straight line through the origin at 45°, slope 1. Domain and range are both ℝ.
2. Polynomial function: f(x) = aₙxⁿ + … + a₁x + a₀ with real coefficients and non-negative integer powers. A linear f(x) = 2x+1 graphs as a straight line; a quadratic f(x) = x² as an upward parabola.
3. Modulus function: f(x) = |x|, equal to x for x ≥ 0 and −x for x < 0. The graph is a V with vertex at the origin; range is [0, ∞).
4. Greatest integer function: f(x) = ⌊x⌋, the largest integer not exceeding x. So ⌊2.7⌋ = 2, ⌊−1.3⌋ = −2. Its graph is a step function of horizontal segments jumping by 1 at each integer.

C. One-One and Onto Functions

These properties classify how a function distributes its outputs; they decide invertibility.

1. One-one (injective): distinct inputs give distinct outputs — f(a₁) = f(a₂) ⟹ a₁ = a₂. Test on a graph with the horizontal line test (no horizontal line cuts twice). f(x) = 2x+3 is injective; f(x) = x² on ℝ is not, since f(−2) = f(2).
2. Onto (surjective): every element of the codomain is hit — range equals codomain, f(A) = B. f : ℝ → ℝ, f(x) = x³ is onto; f(x) = x² onto ℝ is not, since negatives are never reached.

• Bijective: a function both one-one and onto; it pairs A and B perfectly and admits an inverse f⁻¹.
• Counting for finite sets: if n(A) = n(B) = n, the number of bijections is n!; injections require n(A) ≤ n(B), surjections require n(A) ≥ n(B).