Sets, functions and relations
導入済み| English | 意味 |
|---|---|
| injective/ɪnˈdʒektɪv/ | Describing a function in which distinct inputs have distinct outputs. |
| surjective/sɜːˈdʒektɪv/ | Describing a function that reaches every element of its target set. |
| set/set/ | セット |
| relation/rɪˈleɪʃn/ | relation |
| member/ˈmembə/ | member |
| power set | The set of all subsets of a given set, including the empty set. |
| bijective | Describing a function that is both injective and surjective. |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | A relation that is reflexive, symmetric and transitive. |
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}.
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
{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?
難易度 2/5 · 140 コイン + 今日初回達成時の小ボーナス
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.
難易度 2/5 · 140 コイン + 今日初回達成時の小ボーナス
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)?
難易度 2/5 · 140 コイン + 今日初回達成時の小ボーナス
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 —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
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.
難易度 2/5 · 140 コイン + 今日初回達成時の小ボーナス
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.