Functions in Set Theory

Cartesian Product

The Cartesian Product of sets X and Y (written X × Y) contains all possible ordered pairs (x, y) where x ∈ X and y ∈ Y.

💡 Think of it as a table: every possible combination of elements from X with elements from Y.

Relations

A relation R is a subset of the Cartesian product X × Y.

Relations can represent any rule or connection: greater than, less than, subset, "loves", "donates money to", etc.

Key Properties of Relations

• Reflexive: Every element is related to itself
• Symmetric: If (x,y) is in R, then (y,x) is also in R
• Transitive: If (x,y) and (y,z) are in R, then (x,z) is in R
• Anti-symmetric: If (x,y) and (y,x) are both in R, then x = y

Functions

Definition

A function is a special type of relation with two critical requirements:

1. Every x must have a y: For each element in the domain, there exists a corresponding element in the codomain
2. Each x maps to exactly one y: If f(x) = y and f(x) = z, then y = z (no branching)

Key insight: Every function is a relation, but not every relation is a function.

Terminology

• Domain: The set of all input values (X)