集合・関係・関数：ステップごとの解答つき練習問題

1集合と集合演算

集合は、互いに異なる要素の集まりです：A = {1, 2, 3}。順序や重複は関係ありません。|A| は要素の数、U は議論の対象すべてを含む全体集合です。

• A ∪ B（和集合）：A または B、あるいは両方に属する要素。
• A ∩ B（共通部分）：両方に属する要素。
• A − B（差集合）：A の要素のうち B に属さないもの。
• A′（補集合）：U の要素のうち A に属さないもの。

ベン図では、2 つの円が U を 4 つの領域に分けます：A だけ、両方、B だけ、どちらでもない領域です。どの集合の式も、これらの領域のいくつかの和集合なので、いつでも領域ごとに数えられます。

ここでは |A| = 12 + 5 = 17、|A ∩ B| = 5、|A ∪ B| = 12 + 5 + 8 = 25、|(A ∪ B)′| = 15 です。

2包除原理で数える

|A| と |B| を足すと重なりを 2 回数えるので、1 回引きます：

3 つの集合では 2 つずつの重なりを引きますが、そうすると中心部分が 3 回引かれてしまうので、足し戻します：

文章題では、ベン図を中心から外へ向かって埋めるほうが安全なことが多いです：まず 3 つの集合すべてに属する要素、次に各組から中心を除いたもの、最後に各集合から、すでに置いた分を除いたものを入れます。

ほかにもよく出てくる個数があります：n 個の要素をもつ集合には 2ⁿ 個の部分集合があり（冪集合 𝒫(A)）、順序対は |A × B| = |A|·|B| 個です。

3例題

すべてのステップをたどりましょう。開く前に次のステップを予想してみましょう。

4関係

集合 X 上の関係 R は、x と y が X に属する順序対 (x, y) の集合です。有向グラフとして描くと、各組は矢印になり、(x, x) はループになります。

• 反射的：すべての x について (x, x) ∈ R：どの頂点にもループがある。
• 対称的：(x, y) ∈ R のとき、必ず (y, x) ∈ R も成り立つ。
• 反対称的：(x, y) と (y, x) の両方が R に属するのは x = y のときだけ。
• 推移的：(x, y) と (y, z) が R に属すれば、(x, z) ∈ R となる。

反射的・対称的・推移的である関係を同値関係といいます。同値関係は X を互いに素な類に分けます。たとえば「x ≡ y (mod 3)」なら、余りが 0、1、2 の類です。s 個の要素をもつ類は、s² 個の順序対を与えます。

ある性質を否定するには反例が 1 つあれば十分です。成り立つことを示すには、すべての組を確かめます。

5関数

関数 f: A → B は、A のすべての要素に、B の中の像をちょうど 1 つずつ対応させます。

• 単射（1 対 1）：異なる要素は異なる像をもつ。B のどの要素にも矢印が 2 本届くことはない。
• 全射（上への写像）：B のどの要素にも、少なくとも 1 本の矢印が届く。
• 全単射：その両方。このときに限り、f は逆関数 f⁻¹ をもちます。

図の関数は単射ですが全射ではありません：d には矢印が届いていません。単射には |A| ≤ |B|、全射には |A| ≥ |B| が必要です。

|A| = m、|B| = n のとき、関数は nᵐ 個、単射は n!/(n − m)! 個あります。合成 (g ∘ f)(x) = g(f(x)) では、f が先に作用します。

6よくある間違い

• 重なりを引かずに |A| + |B| としてしまう。
• 3 つの集合の包除原理で、中心部分を足し戻すのを忘れる。
• m 個の要素から n 個の要素への関数の個数を、nᵐ ではなく mⁿ と書いてしまう。
• 関係は対称的かつ反対称的にはなれないと思い込む：関係 {(1, 1)} は両方を満たします。
• g ∘ f の順序を間違える：先に働くのは f です。

7試験問題の例

• やさしい：ベン図と部分集合。ベン図から集合の式の個数を数える、式の領域をクリックする、冪集合・直積・部分集合の族の大きさを求める、といった問題です。
• ふつう：包除原理と関係。2 つや 3 つの集合の個数の問題を解く、領域ごとの合計から式の個数を求める、関係がもつ性質を判断する、閉包に必要な組の数を数える、といった問題です。
• むずかしい：関数と数え上げ。関数を単射・全射・全単射に分類する、関数・単射・全射の個数を数える、合成と逆関数を計算する、同値関係の組の数を数える、といった問題です。