Sets, functions and relations
Introduced| English | Meaning |
|---|---|
| injective/ɪnˈdʒektɪv/ | injective |
| surjective/sɜːˈdʒektɪv/ | surjective |
| set/set/ | A collection of distinct elements. |
| relation/rɪˈleɪʃn/ | relation |
| member/ˈmembə/ | member |
| power set | power set |
| bijective | bijective |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | equivalence relation |
One student ID, one student
- A university gives every student an ID. Two students must never share one, and an ID that belongs to nobody is wasted. Those two demands are exactly "injective" and "surjective".
- Sets, functions and relations are the data model under databases, type systems and graphs. This lesson gives each one a precise test.
Sets and their algebra
- A set 集合 is an unordered collection with no repeats. $A \cup B$ (union), $A \cap B$ (intersection), $A - B$ (difference) and the complement build new sets.
- $x \in A$ means $x$ is a member 元素 of $A$; $B \subseteq A$ means every member of $B$ is in $A$. $\{1\} \subseteq \{1, 2\}$, but $\{1\} \notin \{1, 2\}$.
{1} ⊆ {1, 2}, and also {1} ∈ {1, 2}.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
{1} is a subset of {1, 2}, but it is not a member: the members are the numbers 1 and 2.
The power set pairs with bit strings
- The power set 幂集 $\mathcal{P}(A)$ is the set of all subsets of $A$. For $A = \{a, b, c\}$, each element is either in a subset or out: one bit each.
- So subsets match bit strings of length $|A|$ one-to-one, and $|\mathcal{P}(A)| = 2^{|A|}$. Here that is $2^3 = 8$, counting $\varnothing$ and $A$ itself.
How many subsets does a set with 5 elements have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each element is in or out, one bit each, so $2^5 = 32$, counting the empty set and the whole set.
Classify a function by its arrows
- Injective 单射: no two inputs share an output. Surjective 满射: every output is hit. Bijective 双射: both, a perfect pairing that can be reversed.
- On the integers, $f(n) = 2n$ is injective but not surjective (odd numbers are never hit); $h(n) = -n$ is bijective and is its own inverse.
Match each function on the integers to its type.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Doubling never hits odd numbers; halving down sends 4 and 5 to 2; negation pairs perfectly; squaring sends 2 and −2 to 4 and never hits 3.
Composition reads right to left
- $(g \circ f)(x) = g(f(x))$: apply $f$ first, then $g$. With $f(x) = x + 1$ and $g(x) = 2x$, $(g \circ f)(3) = g(4) = 8$ but $(f \circ g)(3) = f(6) = 7$.
- A bijection between $A$ and $B$ proves $|A| = |B|$ without listing either set. Finding one is a counting proof.
f(x) = x + 1 and g(x) = 2x. What is (g ∘ f)(5)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Apply f first: f(5) = 6, then g(6) = 12.
Relations and their four properties
- A relation 关系 on $A$ is a set of ordered pairs. Reflexive: every $(a, a)$ is in it. Symmetric: $(a, b)$ brings $(b, a)$. Transitive: $(a, b)$ and $(b, c)$ bring $(a, c)$.
- Antisymmetric: $(a, b)$ and $(b, a)$ together force $a = b$. An equivalence relation 等价关系 is reflexive, symmetric and transitive; it splits $A$ into classes.
On $\{1, 2, 3\}$, $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$. Reflexive: all three loops ✓. Symmetric: $(1,2)$ and $(2,1)$ ✓. Transitive: the only chains are $(1,2),(2,1)$, which need $(1,1)$, and $(2,1),(1,2)$, which need $(2,2)$; both are present ✓. So $R$ is an equivalence relation with classes $\{1, 2\}$ and $\{3\}$.
A relation's matrix equals its own transpose. The relation is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Entry (a, b) equals entry (b, a) for every pair, which is exactly symmetry.
Which properties must an equivalence relation have? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Reflexive, symmetric and transitive. Antisymmetry belongs to orderings such as ≤.
Marks that slip away
- $\in$ for $\subseteq$. A member is not a subset: $2 \in \{1, 2\}$ but $\{2\} \subseteq \{1, 2\}$.
- Composition backwards. $g \circ f$ applies $f$ first.
- Checking one pair. Symmetry and transitivity must hold for every pair and every chain.
You've got it
- $|\mathcal{P}(A)| = 2^{|A|}$, because subsets pair with bit strings.
- Injective: no shared outputs; surjective: every output hit; bijective: both, so it inverts.
- $g \circ f$ applies $f$ first; an equivalence relation is reflexive, symmetric and transitive.