Beweise folgenden Satz: Jede nichtleere Teilmenge ´A´ der Menge ´NN´ der natürlichen Zahlen besitzt ein kleinstes Element.

Hint 1
Zeige mit vollständiger Induktion, dass für alle ´n in NN´ und alle ´A sube NN´ folgendes gilt: ´((EE m <= n) m in A) => sf "A hat ein kleinstes Element"´

Solution
  • Zu beweisen: ´AA A sube NN : AA n in A: EE m in A: m <= n´

    Vollständige Induktion:

    Anfang:

    Hat ´A´ nur ein einziges Element ´m´, dann ist ´m <= m´ und somit das kleinste Element.

    Vorraussetzung:

    Es sei ´A´ eine beliebige aber bestimmte nichtleere Teilmenge von ´NN´ mit ´n´ Elementen. <mark>Nicht endliche Teilmengen müssen auch noch beachtet werden!</mark>

    ´AA n in A: EE m in A: m <= n´

    Behauptung:

    Die Vorraussetzung gilt auch für ´A'´ mit ´n + 1´ Elementen

    Beweis:

    Sei ´x´ eine beliebige aber feste natürliche Zahl mit ´x !in A´. Dann gilt entweder ´x < n_min´ oder ´n_min < x´. Somit ist in der Menge ´A' = A uu {x}´ unter Annahme der Induktionsvorraussetzung entweder ´n_min´ oder ´x´ das neueste kleinste Element.

    <mark>Fehlt: Jedes ´A'´ kann als ´A uu {x}´ dargestellt werden, wenn ´A´ ´n in NN^+´ Element hat.</mark>

    Nach dem Prinzip der vollständigen Induktion ist durch die Anwendung des Induktionsbeweises auf den Induktionsanfang damit die ursprüngliche Aussage bewiesen.

  • URL:
  • Language:
  • Subjects: math
  • Type: Proof
  • Duration: 30min
  • Credits: 3
  • Difficulty: 0.6
  • Tags: hpi induction
  • Note:
    HPI, 2014-04-07, Mathe 2, Blatt 1, Aufgabe 2
  • Created By: adius
  • Created At:
    2014-07-25 19:55:22 UTC
  • Last Modified:
    2014-07-25 19:56:13 UTC