Sets, Relations, and Functions

Basic operations:

• Union: $A \cup B = \\{x : x \in A \mathrm{ or} x \in B\\}$
• Intersection: $A \cap B = \\{x : x \in A \mathrm{ and} x \in B\\}$
• Difference: $A \setminus B = \\{x : x \in A \mathrm{ and} x \notin B\\}$
• Complement: $A^c = U \setminus A$ (where $U$ is the universal set)

De Morgan’s Laws:

Power set: $\mathcal{P}(A) = \\{B : B \subseteq A\\}$. If $|A| = n$ Then $|\mathcal{P}(A)| = 2^n$.

A binary relation $R$ from set $A$ to set $B$ is a subset of $A \times B$.

A relation $R$ on $A$ is:

• Reflexive: $\forall a \in A$, $(a,a) \in R$.
• Symmetric: $(a,b) \in R \implies (b,a) \in R$.
• Antisymmetric: $(a,b) \in R$ and $(b,a) \in R \implies a = b$.
• Transitive: $(a,b) \in R$ and $(b,c) \in R \implies$(a,c) \in R$.

Equivalence relation: reflexive, symmetric, transitive. Partitions the set into equivalence classes.

Partial order: reflexive, antisymmetric, transitive. Written $(A, \preceq)$.

A Hasse diagram is a graphical representation of a finite poset $(A, \preceq)$: an element $a$ is drawn below $b$ whenever $a \prec b$ (i.e., $a \preceq b$ and $a \neq b$), and an edge is drawn from $a$ to $b$ whenever $b$ covers $a$ (there is no $c$ with $a \prec c \prec b$).

Worked Example. Show that $R$ on $\mathbb{Z}$ defined by $a\,R\,b$ iff $a \equiv b \pmod{5}$ is An equivalence relation. Describe the equivalence classes.

Worked Example. Let $\preceq$ be divisibility on $A = \\{1, 2, 3, 4, 6, 12\\}$: $a \preceq b$ iff $a \mid b$. Verify this is a partial order and identify the cover relations.

A function $f : A \to B$ is a relation where each $a \in A$ appears exactly once as a first element.

• Injective (one-to-one): $f(a_1) = f(a_2) \implies a_1 = a_2$.
• Surjective (onto): for every $b \in B$ There exists $a \in A$ with $f(a) = b$.
• Bijective: both injective and surjective.

Theorem 2.1. If $A$ and $B$ are finite sets, $f : A \to B$ is:

• Injective if and only if $|A| \leq |B|$.
• Surjective if and only if $|A| \geq |B|$.
• Bijective if and only if $|A| = |B|$.

Theorem 2.2 (Pigeonhole Principle). If $|A| \gt{} |B|$ Then no function $f : A \to B$ is injective. Equivalently, placing $n$ items into $m$ boxes with $n \gt{} m$ forces at least one box to contain at least $\lceil n/m \rceil$ items.

Function composition. Given $f : A \to B$ and $g : B \to C$ The composition $g \circ f : A \to C$ is defined by $(g \circ f)(a) = g(f(a))$ for all $a \in A$.

Theorem 2.3. If $f : A \to B$ and $g : B \to C$ are both injective, then $g \circ f$ is injective.

Proof. Suppose $(g \circ f)(a_1) = (g \circ f)(a_2)$. Then $g(f(a_1)) = g(f(a_2))$. Since $g$ is Injective, $f(a_1) = f(a_2)$. Since $f$ is injective, $a_1 = a_2$. Hence $g \circ f$ is injective. $\blacksquare$

Theorem 2.4. If $f : A \to B$ and $g : B \to C$ are both surjective, then $g \circ f$ is surjective.

Proof. Let $c \in C$. Since $g$ is surjective, $\exists\, b \in B$ with $g(b) = c$. Since $f$ is Surjective, $\exists\, a \in A$ with $f(a) = b$. Then $(g \circ f)(a) = g(f(a)) = g(b) = c$. Hence $g \circ f$ is surjective. $\blacksquare$

Corollary 2.5. The composition of two bijections is a bijection.

A function $f : A \to B$ is invertible if there exists $f^{-1} : B \to A$ such that f^{-1} \circ f = \mathrm{id{}_A and f \circ f^{-1} = \mathrm{id{}_B. A function is invertible If and only if it is bijective.

Definition. A set $S$ is countable if it is finite or countably infinite. A set is countably infinite if there exists a bijection $\mathbb{N} \to S$. A set that is not countable Is uncountable.

Theorem 2.6. $\mathbb{Z}$ is countably infinite.

Proof. The function $f : \mathbb{N} \to \mathbb{Z}$ defined by

Is a bijection, enumerating $0, -1, 1, -2, 2, -3, 3, \ldots$ $\blacksquare$

Theorem 2.7. $\mathbb{Q}$ is countably infinite.

Proof. Every positive rational can be written as $p/q$ with $p, q \in \mathbb{N}^+$. Arrange the Pairs $(p, q)$ in an infinite grid and traverse them diagonally:

$1/1,\; 1/2,\; 2/1,\; 3/1,\; 1/3,\; 1/4,\; 2/3,\; 3/2,\; 4/1, \ldots$

Skipping duplicates (where $p/q = p'/q'$ in reduced form) yields an enumeration of $\mathbb{Q}^+$. Extending with negatives and zero gives an enumeration of $\mathbb{Q}$. $\blacksquare$

Theorem 2.8 (Cantor, 1891). $\mathbb{R}$ is uncountable.

Proof (Diagonal argument). Suppose for contradiction that $\mathbb{R}$ is countable. Then the Interval $[0, 1)$ can be listed as $r_1, r_2, r_3, \ldots$ where each $r_i$ has a unique decimal Expansion $r_i = 0.d_{i1}d_{i2}d_{i3}\ldots$ with each $d_{ij} \in \\{0, 1, \ldots, 9\\}$ (choosing the expansion that does not end in all 9s to avoid dual representations).

Define $s = 0.s_1 s_2 s_3 \ldots$ by

Then $s \in [0, 1)$ and $s$ differs from $r_i$ in the $i$-th decimal place for every $i$ So $s \notin \\{r_1, r_2, \ldots\\}$ Contradicting the assumption that the list was complete. Therefore $\mathbb{R}$ is uncountable. $\blacksquare$

Sets are unordered collections of distinct elements. Relations connect elements from different sets, with properties like reflexivity, symmetry, and transitivity. Functions are special relations where each input maps to exactly one output. These concepts underpin database theory (relations), type systems (functions), and abstract algebra (groups, rings). Understanding set operations (union, intersection, complement) is essential for query languages and logic.

Confusing reflexivity with symmetry. A reflexive relation requires $(a, a) \in R$ for every $a \in A$, while symmetry requires that if $(a, b) \in R$ then $(b, a) \in R$. These are independent properties: a relation can be reflexive without being symmetric, and vice versa. Always verify each property separately.

Misapplying the Pigeonhole Principle. Students often state that placing $n$ items into $m$ boxes guarantees one box has at least $n/m$ items, but forget the ceiling function. The correct bound is $\lceil n/m \rceil$, not $n/m$. For example, 5 items into 3 boxes guarantees at least 2 in one box, not 1.67.

Assuming injectivity from surjectivity (or vice versa). For finite sets, a function $f: A \to B$ is injective if and only if $|A| \leq |B|$, and surjective if and only if $|A| \geq |B|$. These are not interchangeable: an injective function from a smaller set to a larger set cannot be surjective.

• [[1-discrete-mathematics/1_propositional-and-predicate-logic]] - Logic foundations
• [[1-discrete-mathematics/3_proof-techniques]] - Proof techniques
• [[2-systems/databases]] - Relational database theory
• [[1-discrete-mathematics/4_combinatorics]] - Counting and sets

• Discrete Mathematics
• Propositional and Predicate Logic
• Proof Techniques

• Combinatorics
• Graph Theory
• Problem Set
• Proof Techniques