Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Vollständige Induktion

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Mathematik für Informatiker » Vollständige Induktion « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Coldstone2509 (Coldstone2509)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Junior Mitglied
Benutzername: Coldstone2509

Nummer des Beitrags: 15
Registriert: 10-2003
Veröffentlicht am Sonntag, den 16. November, 2003 - 10:39:   Beitrag drucken

Beweisen sie mittels vollständiger Induktion folgende Aussage:
Die Potenzmenge P(M)einer endlichen Menge M mit n Elementen besitzt 2 (hoch n) Elemente!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 258
Registriert: 10-2001
Veröffentlicht am Sonntag, den 16. November, 2003 - 13:26:   Beitrag drucken

Hallo Coldstone,

Induktionsanfang:
für n = 1 Elemente besteht die Potenzmenge aus der 1-elementigen Menge und der leeren Menge, also hat sie 2^1 Element.

Induktionsannahme: die Potenzmenge einer n-elementigen Menge hat 2^n Elemente

Induktionsschritt: n |-> n + 1
Die Potenzmenge einer n+1 - elementigen Menge kann man in zwei Teile gliedern : alle Mengen, die das "neue" Element nicht enthalten, das sind nach Induktionsanname 2^n Mengen. Zu jeder dieser Mengen kann man das neue hinzufügen, das ergibt
2^n + 2^n = 2*2^n = 2^(n+1) Elemente der Potenzmenge.

q.e.d

Tamara
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Niels2 (Niels2)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Niels2

Nummer des Beitrags: 899
Registriert: 06-2001
Veröffentlicht am Sonntag, den 16. November, 2003 - 16:03:   Beitrag drucken

Hallo,

Man hätte auch als Induktionsanfang n=0 wählen können, den dann wäre M leer, und P(M) besäße zumindest 2^0=1 Element, nämlich ebenfalls die Leere Menge.

Der Rest ist aber analog zu oben....

mfg

Niels
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Coldstone2509 (Coldstone2509)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Junior Mitglied
Benutzername: Coldstone2509

Nummer des Beitrags: 16
Registriert: 10-2003
Veröffentlicht am Sonntag, den 16. November, 2003 - 17:22:   Beitrag drucken

nochmal eine intelligente frage:
was bedeutet das n |-> n +1 beim Induktionsschritt??? laso ist die Aufgabe somit komplett.
danke nochmals
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 262
Registriert: 10-2001
Veröffentlicht am Sonntag, den 16. November, 2003 - 18:19:   Beitrag drucken

Niels:
ich habs mir überlegt, habe mir aber auf natürliche Zahlen beschränkt, weil viele Professoren 0 nicht als natürliche Zahl ansehen und Induktion gewöhnlich über natürliche Zahlen gemacht wird

Coldstone: das soll nur heißen, das ich von n Elementen auf n+1 Elemente schließe, schließlich kann man ja auch von n-1 Elementen auf n Elemente schließen.

Tamara
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Niels2 (Niels2)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Niels2

Nummer des Beitrags: 901
Registriert: 06-2001
Veröffentlicht am Sonntag, den 16. November, 2003 - 21:12:   Beitrag drucken

Hi Tamara,

das ist wohl dann eine geschmacksfrage. Allerdings übergeht man dann den Fall n=0 mit der Leeren Menge- so trivial er auch sein mag.
Und die Formel stimmt ja auch dann.

Naja, war ja nur so ein Hinweis.
Ich denke es kommt darauf an ob die Aufgabe auch den Induktionsanfang n=0 zulässt oder nicht- und wenn dies der Fall sein sollte, warum soll man nicht den Fall als Induktionsanfang nehmen?

kommt wohl auf die Einstellung der Profs an....

Gruß

Niels



Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 266
Registriert: 10-2001
Veröffentlicht am Montag, den 17. November, 2003 - 20:37:   Beitrag drucken

Ja, man kann sich auch (mal wieder) auf den Stand stellen: ist die leere Menge überhaupt eine Menge?

Das sie (in Formeln...) unheimlich nützlich ist, ist unbestritten, aber entscheidet ihr Nützlichkeit über ihre Existenz?

Ich persönlich finde den Standpunkt doof, schließlich existieren Zahlen ja auch nicht (es gibt nicht DIE DREI).

Naja, ich finde, du hast schon Recht, man kann es auch für eine leere Menge zeigen, muss es aber nicht. Das nächste Mal werde ich beim Induktionsanfang beides anbieten.

Übrigens, ist 2^0=1 tatsächlich so oder "nur" eine Definition? (schlechte Formulierung!)

Grüße

Tamara

Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Jair_ohmsford (Jair_ohmsford)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Jair_ohmsford

Nummer des Beitrags: 223
Registriert: 10-2003
Veröffentlicht am Dienstag, den 18. November, 2003 - 08:56:   Beitrag drucken

Hi Spezi,
was soll das heißen: "Ist 20 tatsächlich so oder nur eine Definition?"
Ein Term der Form xn mit n Î N\{0} ist doch ursprünglich erklärt als ein Produkt mit n gleichen Faktoren x. (Selbst das ist übrigens eine Definition.) Ist n aus irgendeiner anderen Menge, dann kann diese Erklärung nicht mehr greifen. Daher muss alles andere per Definition erklärt werden. Dass dabei kein Widerspruch zu bestehenden Definitionen erzeugt werden sollte, versteht sich ja von selbst.
20=1 wird zum Beispiel definiert, um keinen Bruch in den Potenzregeln zu Potenzen mit gleicher Basis zu erhalten:
1 = 2n/2n = 2n-n = 20
Mit freundlichen Grüßen
Jair
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin243 (Martin243)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Martin243

Nummer des Beitrags: 874
Registriert: 02-2001
Veröffentlicht am Dienstag, den 18. November, 2003 - 16:40:   Beitrag drucken

Kleine Anmerkung zu Jairs Erklärung:

Hier kann man sich natürlich fragen, was zuerst da war, das Huhn oder das Ei?
Denn wie definieren wir die Potenz xn?
Wir können es es machen wie oben, dass wir für alle nat. Zahlen >0 sagen, dass sie dem n-fachen Produkt von x entspricht, und dann zusätzlich herleiten:
x0 = xn/xn = 1 für x<>0

Andererseits könnten wir aber induktiv vorgehen und sagen:
x0 = 1
und
xn+1 = x * xn


Wie auch immer. Man muss das Eine irgendwann durch das Andere ausdrücken und das Schöne ist, dass man das ohne Widersprüche machen kann. Also ist es in sich konsistent und sinnvoll.

... wie übrigens die leere Menge, die man meiner Meinung nach nie außer Acht lassen sollte!


MfG
Martin
________
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 270
Registriert: 10-2001
Veröffentlicht am Dienstag, den 18. November, 2003 - 19:17:   Beitrag drucken

Hi Jair, hi Martin,

natürlich bezweifle ich nicht, dass 2^0=1 ist, danke übrigens für die Erklärungen.

Martin: "und das Schöne ist..." sagen wir mal so: es wäre eine Katastrophe, wenn es nicht so wäre

Außerdem habe ich die leere Menge in jedem meiner betrachteten Fälle miteinbezogen, sonst wäre ja 2^p - 1. Deshalb ist es wohl wirklich besser, man fängt mit der leeren Menge an. Aber das habe ich ja schon letzes Mal zugegeben.
Aber im Prinzip ist es auch fast egal.

Jair, da du durchzublicken scheinst: Wie in aller definiert man, was 3,46^7,13 ist??

Tamara

Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Jair_ohmsford (Jair_ohmsford)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Jair_ohmsford

Nummer des Beitrags: 225
Registriert: 10-2003
Veröffentlicht am Dienstag, den 18. November, 2003 - 21:27:   Beitrag drucken

Hi Tamara,
solange der Exponent noch eine abbrechende oder wenigstens eine periodische Dezimalzahl (also rational) ist, gibt es noch keine Probleme. Man verwandelt ihn in einen Bruch, und Potenzen mit gebrochenen Exponenten kann man wieder elementar über die Potenzgesetze definieren.
Beginnen wir z.B. mit x1/n, x ³ 0, n Î N.
Damit das 5. Potenzgesetz auch für solche Potenzen erfüllt ist (anm=anm), definiert man
a1/n = nÖa
Dann ist nämlich
(a1/n)n=(nÖa)n = a
Für beliebige Brüche mit m Î Z, n Î N definiert man
am/n = nÖam
in Übereinstimmung mit dem 1.Potenzgesetz.
Dein Beispiel ist somit
3,467,13 =
3,46713/100 =
100Ö3,46713
Mit freundlichen Grüßen
Jair
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin243 (Martin243)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Martin243

Nummer des Beitrags: 877
Registriert: 02-2001
Veröffentlicht am Dienstag, den 18. November, 2003 - 21:43:   Beitrag drucken

Hi!

Man kann die Exponentialfunktion mit reeller Basis und reellem Exponenten auch so einführen:

Zuerst definiert man exp(x) durch die Exponentialreihe:
exp(x) := Soo n=0 xn/n!

Da exp eine bijektive Abbildung ist, findet man dazu die Umkehrabbildung ln.

Dann kann man beliebige Potenzen bx defnieren durch:
bx := exp(x * ln b)

Es lässt sich zeigen, dass sich die Potenzen mit natürlichen Exponenten hier einbetten lassen, dass also z.B. gilt:
mn = exp(n * ln m) für natürliche m, n

Dasselbe geht auch mit rationalen Exponenten, wie Jair sie oben eingeführt hat.


MfG
Martin


P.S.
Nur damit es nicht so abstrakt wirkt: Zwei Beispiele
1)
32 = exp(2 * ln 3)

= Soo n=0 (2*ln 3)n / n!

= (2*ln 3)0 / 0! + (2*ln 3)1 / 1! + (2*ln 3)2 / 2! + (2*ln 3)3 / 3! + (2*ln 3)4 / 4! + (2*ln 3)5 / 5! + (2*ln 3)6 / 6! + ...

= 1 + 2*ln 3 + (2*ln 3)2 / 2 + (2*ln 3)3 / 6 + (2*ln 3)4 / 24 + (2*ln 3)5 / 120 + (2*ln 3)6 / 720 + ...

= 8,93328269 + ...

Ich denke, die Summe 9=32 zeichnet sich bereits nach 7 Gliedern deutlich ab...


2) Hier ziehen wir die Wurzel aus 9:
W(9) = 90.5 = exp(0.5 * ln 9)

= (0.5*ln 9)0 / 0! + (0.5*ln 9)1 / 1! + (0.5*ln 9)2 / 2! + (0.5*ln 9)3 / 3! + (0.5*ln 9)4 / 4! + (0.5*ln 9)5 / 5! + (0.5*ln 9)6 / 6! + ...

= 1 + 0.5*ln 9 + (0.5*ln 9)2 / 2 + (0.5*ln 9)3 / 6 + (0.5*ln 9)4 / 24 + (0.5*ln 9)5 / 120 + (0.5*ln 9)6 / 720 + ...

= 2.9995569

Auch hier ist klar, dass am Ende (wenn man unendlich viele Glieder addiert hat) 3 herauskommt.


(Beitrag nachträglich am 18., November. 2003 von Martin243 editiert)
________
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Niels2 (Niels2)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Niels2

Nummer des Beitrags: 904
Registriert: 06-2001
Veröffentlicht am Dienstag, den 18. November, 2003 - 22:33:   Beitrag drucken

Hi Tamara, Martin und Jair,

meint ihr nicht das die Diskussion etwas über das Ziel hinausschießt und das die von Spezie angezettelte Diskussion man zwar ruhig führen kann aber doch an dieser Stelle etwas deplaziert erscheint, weil sie nichts mit der ursprunglichen Induktionsaufgabe zu tun hat?

Das mit der Leeren Menge, war nur ein Hinweis von mir und Allaussagen über die Leere Menge sind meist eh trivial. Dennoch haben sich die Mathematiker mit der Einführung der Leeren Menge ein tolles Spielzeug geschaffen.

Oder habt ihr euch nicht schon mal gefragt was der Schnitt über die Leere Menge ist?...

mfg

Niels



Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 271
Registriert: 10-2001
Veröffentlicht am Mittwoch, den 19. November, 2003 - 18:21:   Beitrag drucken

Hallo Niels,

ich wusste es wirklich nicht, und da man ja gerade beim Thema war kann man ja fragen, oder nicht?

Übrigens wollte ich keine Diskussion anzetteln, eigentlich wollte ich nur die Frage beantworten und sagen, warum ich mich damals für n=1 entschieden habe.

Deine Formulierung mit Spielzeug hat mir sehr gut gefallen.

Außerdem weiß ich wirklich nicht, das der Schnitt über die leere Menge ist.

Tamara
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Niels2 (Niels2)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Niels2

Nummer des Beitrags: 905
Registriert: 06-2001
Veröffentlicht am Mittwoch, den 19. November, 2003 - 20:48:   Beitrag drucken

Hi Tamara,

natürlich darf man nachfragen, wenn man etwas nicht weiß oder etwas nicht versteht, so war das auch nicht gemeint. Nur ich finde das die auf deiner Nachfrage beruhende Diskussion etwas ausuferte.

Zum Schnitt über die Leere Menge:

Was ist der Schnitt (über die)/der Leere Menge?

bischen nachdenken, morgen Nachmittag kommt die verblüfende Antwort....

mfg

Niels
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Stani
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 13. November, 2012 - 21:50:   Beitrag drucken

DANKE Tamara
Wirklich super erklärt! Einfach und das wichtigste drin !!!!

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page