Zählen Sie eine Teilmenge einer endlichen Menge

Question

Endliche Mengen sind als Mengen definiert, die bijektiv auf [n] = {1,2, ... n} abgebildet werden können. Man beweise, dass eine Teilmenge T einer endlichen Menge S endlich ist. Das ist das angegebene Problem.

Mir ist nicht klar, was als gegebene Axiome angesehen werden kann.

Die Auflösung besteht eindeutig darin, die Existenz einer Bijektion von einer Teilmenge von [n] nach [m] zu zeigen, wobei m <n ist.

Es ist trivial, einen Algorithmus zu beschreiben, der dies tut: Beginnen Sie mit dem kleinsten Element und ordnen Sie es 1 zu. Fahren Sie mit S fort und ordnen Sie jedes Element einem Element von [m] zu. Wenn beispielsweise T = {2,5,6 ...} ist, ordnen Sie es {1,2,3 ...} zu. Ordnen Sie das k + 1-te Element von S dem Nachfolger des Bildes des k-ten Elements von S zu. (Mit Nachfolger meine ich das Hinzufügen eines)

Das klingt nach Induktion.

Frage: Ist es zulässig, diese Beschreibung eines Algorithmus zu verwenden und als Beweis zu bezeichnen?

Answer 1

Zuerst sollten Sie versuchen, den speziellen Fall zu beweisen "wenn $a \in X$, $X$ ist dann endlich $X \setminus \{a\}$ ist endlich ". Dies folgt aus dem folgenden Lemma, das einen einfachen Beweis hat

"Wenn $f:X \to Y$ ist eine Bijektion, $x \in X$, $y \in Y$ dann gibt es eine bijektion $g:X \to Y$ so dass $g(x)=y$. "

Dann lass $f:\{1, \cdots, n\} \to X$ Sei eine Bijektion und nimm an, dass $f(n)=a$. Also wenn$n=1$, $X \setminus \{a\}=\emptyset$ und wenn $n >1$, die Beschränkung $f |_{\{1, \cdots, n-1\}}:\{1, \cdots, n-1\} \to X \setminus \{a\}$ ist eine Bijektion.

Für den allgemeinen Fall nehmen wir an $X$ ist endlich und lass $S \subseteq X$. Nehmen Sie eine Bijektion$f:\{1, \cdots, n\} \to X$und lassen Sie uns das Ergebnis durch Induktion beweisen. Zum$n=1$, $S=X$ oder $S = \emptyset$und das Ergebnis folgt. Nun lautet die Induktionshypothese "If$X$ ist endlich, $f:\{1, \cdots, n\} \to X$ ist eine Bijektion und $S \subseteq X$ dann $S$ ist endlich " $f:\{1, \cdots, n+1\} \to X$eine Bijektion sein. Wenn$S=X$ Es gibt nichts zu beweisen $S \neq X$. Wählen$a \in X$ so dass $x \notin S$. Daher$S \subseteq X \setminus \{a\}$. Aus dem besonderen Fall gibt es eine Bijektion zwischen$\{1, \cdots, n\}$ und $X \setminus \{a\}$. Dann$S$ ist durch die Induktionshypothese endlich.