J. Munkres. Topology (2013) Chapter I: Set Theory and Logic. 6: Finite Sets

Definition: Finite

A set \(A\) is finite iff it is bijective with \(S_n\) for some positive integer \(n\), in which case we say its cardinality is \(n-1\).

Lemma 6.1

Let \(n\) be a positive integer. Let \(A\) be a set. Let \(a_0 \in A\). The set \(A\) is bijective with \(S_{n+2}\) if and only if \(A - \{a_0\}\) is bijective with \(S_{n+1}\).

Proof

  • If \(A\) is bijective with \(S_{n+2}\) then \(A - \{a_0\}\) is bijective with \(S_{n+1}\).
    • Assume \(f : A \rightarrow S_{n+2}\) is a bijection.
    • Define \(g : A - \{a_0\} \rightarrow S_{n+1}\) by \(g(x) = f(x)\) if \(f(x) < n+1\), and \(g(x) = f(a_0)\) if \(f(x) = n+1\).
      • Let \(x \in A - \{a_0\}\), and assume \(f(x) = n+1\). Then \(f(a_0) < n+1\) since \(f\) is injective.
    • \(g\) is injective.
      • Let \(x,y \in A - \{a_0\}\). Assume \(g(x) = g(y)\). Prove: \(x = y\).
      • Case \(f(x) < n+1\) and \(f(y) < n+1\).
        • We have \(f(x) = g(x) = g(y) = f(y)\) and so \(x = y\) since \(f\) is injective.
      • Case \(f(x) < n+1\) and \(f(y) = n+1\).
        • We have \(f(x) = g(x) = g(y) = f(a_0)\), contradicting the fact that \(f\) is injective.
      • Case \(f(x) = n+1\) and \(f(y) < n+1\).
        • Similar.
      • Case \(f(x) = n+1\) and \(f(y) = n+1\).
        • Then \(x = y\) since \(f\) is injective.
    • \(g\) is surjective.
      • Let \(y \in S_{n+1}\). Prove: there exists \(x \in A - \{a_0\}\) such that \(g(x) = y\).
      • Let \(x\) be the element of \(A\) such that \(f(x) = y\).
      • Case \(x = a_0\)
        • Let \(x'\) be the element of \(A\) such that \(f(x) = n+1\)
        • \(x' \neq a_0\)
          • Since \(f\) is injective.
        • \(g(x') = y\)
          • \(g(x') = f(a_0) = f(x) = y\)
      • Case \(x \neq a_0\)
        • Then \(g(x) = y\)
  • If \(A - \{a_0\}\) is bijective with \(S_{n+1}\) then \(A\) is bijective with \(S_{n+2}\).
    • Let \(f : A - \{a_0\} \rightarrow S_{n+1}\) be a bijection. Then \(f \cup \{(a_0,n+1)\}\) is a bijection between \(A\) and \(S_{n+2}\).
  • \(\Box\)

Theorem 6.2

Let \(A\) be a set. Assume that \(A\) is bijective with \(S_{n+1}\) for some \(n \in \mathbb{Z}_+\). Let \(B\) be a proper subset of \(A\). Then there is no bijection \(B \rightarrow S_{n+1}\); but there does exist a bijection \(h : B \rightarrow S_{m+1}\) for some \(m < n\).

Solution

  • Let \(P(n)\) be the property: For any sets \(A\) and \(B\), if \(A\) is bijective with \(S_{n+1}\) and \(B\) is a proper subset of \(A\), then there is no bijection \(B \rightarrow S_{n+1}\); but there is a bijection \(B \rightarrow S_{m+1}\) for some \(m < n\).
  • \(P(1)\) holds.
    • Let \(A\) and \(B\) be any sets. Assume \(f : A \rightarrow \{1\}\) is a bijection and \(B\) is a proper subset of \(A\).
    • Let \(a\) be the element of \(A\) such that \(f(a) = 1\).
    • \(A = \{a\}\)
    • \(B = \emptyset\)
    • There is no bijection \( \emptyset \rightarrow S_2\), but there is a bijection \(B \rightarrow S_1\)
  • For any positive integer \(n\), if \(P(n)\) holds then \(P(n+1)\) holds.
    • Let \(n\) be a positive integer. Assume \(P(n)\) holds.
    • Let \(A\) and \(B\) be any sets. Assume \(f : A \rightarrow S_{n+2}\) is a bijection and \(B\) is a proper subset of \(A\).
    • Assume w.l.o.g. \(B \neq \emptyset\)
    • Pick \(a_0 \in B\) and \(a_1 \in A - B\).
    • Pick a bijection \(g : A -\{a_0\} \rightarrow S_{n+1}\).
      • Lemma 6.1
    • \(B-\{a_0\}\) is a proper subset of \(A - \{a_0\}\).
    • \(\langle 2 \rangle 1\) There is no bijection between \(B-\{a_0\}\) and \(S_{n+1}\).
      • From the induction hypothesis.
    • \( \langle 2 \rangle 2 \) Pick \(p < n\) such that there exists a bijection \(k : B - \{a_0\} \rightarrow S_{p+1}\).
      • From the induction hypothesis.
    • There is no bijection between \(B\) and \(S_{n+2}\).
      • From \(\langle 2 \rangle 1\) and Lemma 6.1
    • There is a bijection between \(B\) and \(S_{p+2}\).
      • From \(\langle 2 \rangle 2\) and Lemma 6.1
  • \(\Box\)

Corollary 6.3

If \(A\) is finite, there is no bijection between \(A\) and a proper subset of \(A\).

Corollary 6.4

\(\mathbb{Z}_+\) is not finite.

Corollary 6.5

The cardinality of a finite set is unique.

Corollary 6.6

If \(A\) is a finite set and \(B \subseteq A\), then \(B\) is finite, and the cardinality of \(B\) is \(\leq\) the cardinality of \(A\).

Corollary 6.7

Let \(B\) be a nonempty set. Then the following are equivalent.

  1. \(B\) is finite.
  2. There exists a surjection \(S_n \rightarrow B\) for some \(n\).
  3. There exists an injection \(B \rightarrow S_n\) for some \(n\).

Proof

  • \(1 \Rightarrow 2\)
    • Immediate from the definition of finite.
  • \(2 \Rightarrow 3\)
    • Let \(f : S_n \rightarrow B\) be surjective.
    • Define \(g : B \rightarrow S_n\) by: \(g(x)\) is the least element of \(S_n\) such that \(f(g(x)) = x\).
    • \(g\) is injective.
  • \(3 \Rightarrow 1\)
    • Let \(f : B \rightarrow S_n\) be injective.
    • Pick \(m \leq n\) such that \(f(B)\) is bijective with \(S_m\).
      • By Theorem 6.2.
    • \(B\) is bijective with \(S_m\).

Corollary 6.8

The union of two finite sets is finite.

Proof

  • Let \(A\) and \(B\) be finite.
  • Pick positive integers \(m\) and \(n\) and bijections \(f : S_m \rightarrow A\) and \(g : S_n \rightarrow B\).
  • Define \(h : S_{m+n} \rightarrow A \cup B\) by \(h(i) = f(i)\) for \(i < m\), and \(h(i) = g(i-m)\) for \(i \geq m\).
  • \(h\) is surjective.
  • \(A \cup B\) is finite.
    • Corollary 6.7

Corollary

The union of a finite set of finite sets is finite.

Proof

By induction on the number of sets.

Corollary 6.8

The Cartesian product of two finite sets is finite.

Proof

  • Let \(A\) and \(B\) be finite.
  • For all \(a \in A\), the set \(\{a\} \times B\) is finite.
    • It is bijective with \(B\).
  • \(A \times B\) is finite.
    • It is the union of \(\{\{a\} \times B \mid a \in A\}\).
  • \(\Box\)

Exercises

Exercise 1

(a)

Make a list of all the injective maps

\[ f : \{1,2,3\} \rightarrow \{1,2,3,4\} \enspace . \]

Show that none of them is bijective. (This constitutes a direct proof that a set \(A\) of cardinality three does not have cardinality four.)

Solution

  • \(\{(1,1),(2,2),(3,3)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,1),(2,2),(3,4)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,1),(2,3),(3,2)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,1),(2,3),(3,4)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,1),(2,4),(3,2)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,1),(2,4),(3,3)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,2),(2,1),(3,3)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,2),(2,1),(3,4)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,2),(2,3),(3,1)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,2),(2,3),(3,4)\}\) --- not bijective because 1 is not in its range.
  • \(\{(1,2),(2,4),(3,1)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,2),(2,4),(3,3)\}\) --- not bijective because 1 is not in its range.
  • \(\{(1,3),(2,1),(3,2)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,3),(2,1),(3,4)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,3),(2,2),(3,1)\}\) --- not bijective because 4 is not in its range.
  • \(\{(1,3),(2,2),(3,4)\}\) --- not bijective because 1 is not in its range.
  • \(\{(1,3),(2,4),(3,1)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,3),(2,4),(3,2)\}\) --- not bijective because 1 is not in its range.
  • \(\{(1,4),(2,1),(3,2)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,4),(2,1),(3,3)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,4),(2,2),(3,1)\}\) --- not bijective because 3 is not in its range.
  • \(\{(1,4),(2,2),(3,3)\}\) --- not bijective because 1 is not in its range.
  • \(\{(1,4),(2,3),(3,1)\}\) --- not bijective because 2 is not in its range.
  • \(\{(1,4),(2,3),(3,2)\}\) --- not bijective because 1 is not in its range.

(b)

How many injective maps

\[ f : \{1, \ldots, 8\} \rightarrow \{1, \ldots, 10\} \]

are there? (You can see why one would not wish to prove directly that there is no bijective correspondence between these sets.)

Solution

There are \(10 \times 9 \times \cdots \times 3 = 1814400\) such injective maps.

Exercise 2

Show that if \(B\) is not finite and \(B \subseteq A\) then \(A\) is not finite.

Solution

This is just the contrapositive of Corollary 6.6.

Exercise 3

Let \(X\) be the two-element set \(\{0,1\}\). Find a bijective correspondence between \(X^\omega\) and a proper subset of itself.

Solution

Define \(f : X^\omega \rightarrow X^\omega\) by \(f(x_1, x_2, \ldots) = (0, x_1, x_2, \ldots)\). Then \(f\) is a bijection between \(X^\omega\) and \(\{(x_1, x_2, \ldots) \mid x_1 = 0\}\).

Exercise 4

Let \(A\) be a nonempty finite linearly ordered set.

(a)

Show that \(A\) has a largest element.

Solution

  • Any finite linearly ordered set of cardinality 1 has a largest element.
    • If \(A = \{a\}\) then of course \(a\) is the largest element.
  • Let \(n\) be a positive integer. Assume that every linearly ordered set of cardinality \(n\) has a largest element. Then every linearly ordered set of cardinality \(n+1\) has a largest element.
    • Let \(n\) be a positive integer. Assume that every linearly ordered set of cardinality \(n\) has a largest element.
    • Let \(A\) be a linearly ordered set of cardinality \(n+1\).
    • Pick \(a \in A\).
    • Let \(b\) be the greatest element of \(A - \{a\}\).
    • If \(a < b\) then \(b\) is the greatest element of \(A\). If \(b < a\) then \(a\) is the greatest element of \(A\).
  • \(\Box\)

(b)

Show that \(A\) is isomorphic to a section of the positive integers.

Solution

  • If \(A\) has cardinality 1 then \(A\) is order isomorphic to \(S_2\).
    • Easy.
  • Let \(n\) be a positive integer. Assume that every linearly ordered set of cardinality \(n\) is isomorphic to \(S_{n+1}\). Then every linearly ordered set of cardinality \(n+1\) is isomorphic to \(S_{n+2}\).
    • Assume induction hypothesis.
    • Let \(A\) be a linearly ordered set of cardinality \(n+1\).
    • Let \(a\) be the greatest element in \(A\).
    • Let \(f\) be an isomorphism between \(A - \{a\}\) and \(S_{n+1}\).
    • \(f \cup \{(a,n+1)\}\) is an isomorphism between \(A\) and \(S_{n+2}\).

Exercise 5

If \(A \times B\) is finite, does it follow that \(A\) and \(B\) are finite?

Solution

If \(A = \emptyset\) and \(B\) is infinite then \(A \times B = \emptyset\) which is finite. But if we assume \(A \times B\) is finite and \(A\) and \(B\) are nonempty, then we can conclude \(A\) and \(B\) are finite. Pick \(b \in B\); then the function that maps \(x\) to \((x,b)\) is an injection \(A \rightarrow A \times B\), so \(A\) is finite. Similarly \(B\) is finite.

Exercise 6

(a)

Let \(A = \{1, \ldots, n\}\). Show that there is a bijection between \(\mathcal{P} A\) with the Cartesian product \(X^n\), where \(X\) is the two-element set \(X = \{0,1\}\).

Solution

Define \(f : \mathcal{P} A \rightarrow X^n\) by \(f(S) = (a_1, \ldots, a_n)\), where \(a_i = 1\) if \(i \in S\) and \(a_i = 0\) if \(i \notin S\). Then \(f\) is a bijection.

(b)

Show that if \(A\) is finite then \(\mathcal{P} A\) is finite.

Solution

Prove by induction on \(n\) that if \(A\) has cardinality \(n\) then \(\mathcal{P} A\) has cardinality \(2^n\).

Exercise 7

If \(A\) and \(B\) are finite, show that the set of all functions \(A \rightarrow B\) is finite.

Solution

Prove by induction on \(n\) that, if \(A\) has cardinality \(n\) and \(B\) has cardinality \(m\), then \(B^A\) has cardinality \(m^n\).

Comments

Post a Comment

Popular posts from this blog

J. Munkres. Topology (2013) Chapter 4: Countability and Separation Axioms. 32: Normal Spaces

Theorem 32.1 Every second countable regular space is normal. Proof Let \(X\) be a second countable regular space. Pick a countable basis \(\mathcal{B}\). Let \(A\) and \(B\) be disjoint closed sets in \(X\). Pick a countable covering \(\{U_1, U_2, \ldots\}\) of \(A\) by open sets whose closures are disjoint from \(B\). Let \(\{U_1, U_2, \ldots\} = \{U \in \mathcal{B} \mid \overline{U} \cap B = \emptyset\}\). Prove: this covers \(A\). Let \(x \in A\). Prove: there exists \(U \in \mathcal{B}\) such that \(x \in U\) and \(\overline{U} \cap B = \emptyset\). Pick disjoint open sets \(U\) and \(V\) such that \(x \in U\) and \(B \subseteq V\). By regularity. Pick \(U' \in \mathcal{B}\) such that \(x \in U' \subseteq U\). \(x \in U'\) and \(\overline{U'} \cap B \subseteq \overline{U} \cap B \subseteq (X - V) \cap B = \emptyset\) Pick a countable covering \(\{V_1, V_2, \ldots\}\) of \(B\) by open sets whose ...
Read more

J. Munkres. Topology (2013) Chapter 3: Connectedness and Compactness. 27: Compact Subspaces of the Real Line

Theorem 27.1 Let \(X\) be a linearly ordered set with the least upper bound property in the order topology. Every closed interval in \(X\) is compact. Proof Let \(a,b \in X\) with \(a Let \(\mathcal{A}\) be a covering of \([a,b]\) by sets open in \(X\). \( \langle 1 \rangle 1 \) For any \(x \in [a,b)\), there exists \(y \in (x,b]\) such that \([x,y]\) can be covered by at most two elements of \(\mathcal{A}\). Let \(x \in [a,b)\). Pick \(U \in \mathcal{A}\) such that \(x \in U\). Pick \(y > x\) such that \([x,y) \subseteq U\). Assume w.l.o.g. \(y \leq b\). Pick \(V \in \mathcal{A}\) such that \(y \in V\). \([x,y]\) is covered by \(U\) and \(V\). Let \(C = \{y \in (a,b] \mid [a,y] \text{ can be covered by finitely many elements of } \mathcal{A} \}\). Let \(c = \sup C\). \(C\) is nonempty. Pick \(y \in (a,b]\) such that \([a,y]\) can be covered by at most two elements of \(\mathcal{A}\). \(\...
Read more

J. Munkres. Topology (2013) Chapter 4: Countability and Separation Axioms. 31: The Separation Axioms

Definition A topological space \(X\) is regular iff it is \(T_1\) and, for any point \(x \in X\) and closed set \(B\) such that \(x \notin B\), there exist disjoint open sets \(U\) and \(V\) with \(x \in U\) and \(B \subseteq V\). A topological space \(X\) is normal iff it is \(T_1\) and, for any disjoint closed sets \(A\) and \(B\), there exist disjoint sets \(U\) and \(V\) with \(A \subseteq U\) and \(B \subseteq V\). Lemma 31.1 Let \(X\) be a \(T_1\) space. \(X\) is regular if and only if, for every point \(x \in X\) and neighbourhood \(U\) of \(x\), there exists a neighbourhood \(V\) of \(x\) such that \(\overline{V} \subseteq U\). \(X\) is normal if and only if, for every closed set \(A\) and open set \(U\) including \(A\), there exists an open set \(V\) including \(A\) such that \(\overline{V} \subseteq U\). Proof If \(X\) is regular then, for every point \(x \in X\) and neighbourhood \(U\) of \(x\), there exists a neighbourhood \(V\) of \(x\) such th...
Read more