Artikel

5: Mengen und Zählen - Mathematik


Lernziele

In diesem Kapitel lernen Sie:

  • Verwenden Sie Mengentheorie und Venn-Diagramme, um Zählprobleme zu lösen.
  • Verwenden Sie das Multiplikationsaxiom, um Zählprobleme zu lösen.
  • Verwenden Sie Permutationen, um Zählprobleme zu lösen.
  • Verwenden Sie Kombinationen, um Zählprobleme zu lösen.
  • Verwenden Sie den Binomialsatz, um ((x+y)^n) zu erweitern

Zählmarken

Zählmarken, auch genannt Rautenzeichen, sind ein unäres Zahlensystem. Sie sind eine Form von Zahlen, die zum Zählen verwendet werden. Sie sind am nützlichsten beim Zählen oder Auszählen von laufenden Ergebnissen, wie z. B. der Punktzahl in einem Spiel oder einer Sportart, da keine Zwischenergebnisse gelöscht oder verworfen werden müssen.

Aufgrund der Länge großer Zahlen werden Tallys jedoch nicht häufig für statischen Text verwendet. Historisch wurden hierfür auch gekerbte Stäbe, sogenannte Tallysticks, verwendet.


5: Mengen und Zählen - Mathematik


Fakultät für Mathematik der Illinois State University

MAT 305: Kombinatorik-Themen für K-8-Lehrer

Grundlegende Zähltechniken

Hier wählen wir einen Artikel aus einer Sammlung von Artikeln aus. Da es unter den beiden Sets, die Blaise Greens und Potatoes genannt hat, keine gemeinsamen Gegenstände gibt, können wir die Gegenstände in einem großen Set zusammenfassen. Wir verwenden Addition, hier 4+5, um die Gesamtzahl der zur Auswahl stehenden Artikel zu bestimmen.

Dies veranschaulicht ein wichtiges Zählprinzip.

Wenn eine Wahl aus Gruppe I auf n Arten und eine Wahl aus Gruppe II auf m Arten getroffen werden kann, dann ist die Anzahl der möglichen Wahlen aus Gruppe I oder Gruppe II n+m.

Notwendige Bedingung: Keine Elemente in Gruppe I sind gleich wie Elemente in Gruppe II.

Dies kann auf eine einzelne Auswahl aus mehr als zwei Gruppen verallgemeinert werden, wiederum unter der Bedingung, dass alle Gruppen oder Mengen disjunkt sind, d. h. nichts gemeinsam haben.

Beispiele zur Veranschaulichung des Additionsprinzips:

Hier sind drei Sätze von Buchstaben, nennen Sie sie Sätze I, II und III:

Wie viele Möglichkeiten gibt es, einen Buchstaben aus den Sets I, II oder III auszuwählen? Beachten Sie, dass die drei Mengen disjunkt sind oder sich gegenseitig ausschließen: Es gibt keine gemeinsamen Elemente zwischen den drei Mengen.

Hier sind zwei Sätze von positiven ganzen Zahlen:

Wie viele Möglichkeiten gibt es, eine ganze Zahl aus den Mengen A oder B auszuwählen? Beachten Sie, dass die beiden Mengen nicht disjunkt sind. Welche Modifikation können wir am Additionsprinzip vornehmen, um diesem Fall Rechnung zu tragen? Versuchen Sie, diese Änderung zu schreiben.

Das Multiplikationsprinzip

Wir können die möglichen Mahlzeiten aufzählen, vorzugsweise in einer organisierten Weise, um sicherzustellen, dass wir alle Möglichkeiten in Betracht gezogen haben. Hier ist eine Skizze einer solchen Aufzählung, in der , , , und repräsentieren die Artikel, die jeweils aus der Suppen-, Fleisch-, Grüngemüse- und Dessertkarte gewählt werden können.

Beachten Sie das in der Tabelle verwendete Aufzählungsverfahren. Wie könnte man es mit Worten beschreiben?

Wie sonst könnten wir die Zählung abschließen, ohne alle möglichen Optionen zu identifizieren? Eine Karte oder ein Baum zur Veranschaulichung des Aufzählungsprozesses bietet eine Brücke zu einem solchen Verfahren.

Wir haben zwei Möglichkeiten, einen Suppenartikel auszuwählen, zwei Möglichkeiten, einen Fleischartikel auszuwählen, vier grüne Gemüsesorten zur Auswahl und vier Desserts zur Auswahl. Die Kombination einer Suppe mit jedem Fleisch, dann jedes dieser Paare mit jedem von vier möglichen grünen Gemüsen und jedes dieser Tripel mit jedem von vier möglichen Desserts führt zur Verwendung der Multiplikation, um alle möglichen Mahlzeiten schnell zu zählen könnte sich bei Blaise versammeln.

Dies legt nahe, dass wir ein anderes Zählprinzip verwenden, um diese Technik zu beschreiben.

Das Multiplikationsprinzip

Wenn eine Aufgabe zwei Schritte umfasst und der erste Schritt auf n Arten und der zweite Schritt auf m Arten abgeschlossen werden kann, dann gibt es n*m Möglichkeiten, die Aufgabe zu erledigen.

Notwendige Bedingung: Die Möglichkeiten, wie jeder Schritt ausgeführt werden kann, sind unabhängig voneinander.

Dies kann so verallgemeinert werden, dass eine Aufgabe in mehr als zwei Schritten abgeschlossen wird, solange die Bedingung erfüllt ist.

Beispiel zur Veranschaulichung des Multiplikationsprinzips:

Erinnern Sie sich an unsere drei Sets I, II und III: , , und . Bestimmen Sie die Anzahl der Drei-Buchstaben-Sets, die erstellt werden können, sodass ein Buchstabe aus Set I, ein Buchstabe aus Set II und ein Buchstabe aus Set III stammt. Beachten Sie, dass unsere Wahl in jedem Satz unabhängig von unserer Wahl in den anderen Sätzen ist. Bei Bedarf könnten wir die möglichen Drei-Buchstaben- oder Drei-Elemente-Mengen aufzählen.

Permutationen
Auf wie viele Arten können die Buchstaben innerhalb eines Satzes aus I, II und III geordnet werden? In Set I haben wir diese Möglichkeiten:

Wir verwenden das Multiplikationsprinzip, um unsere Auswahl zu beschreiben. Wir haben drei Buchstaben zur Auswahl, um die erste Position zu besetzen, zwei Buchstaben bleiben für die zweite Position übrig und nur noch ein Buchstabe für die letzte Position: 3x2x1=6 verschiedene Reihenfolgen sind möglich. Ebenso gibt es für Set II 120 verschiedene Möglichkeiten, die fünf Buchstaben zu bestellen, und es gibt 24 verschiedene Möglichkeiten, die Buchstaben in Set III zu bestellen.

Diese obige Diskussion veranschaulicht das Konzept einer anderen grundlegenden Zählstrategie.

Eine lineare Anordnung von Elementen, bei der die Reihenfolge der Elemente berücksichtigt werden muss.

Wir weisen auch auf die Verfügbarkeit der faktoriellen Notation hin, um die spezifische Multiplikation, die wir gerade durchgeführt haben, kompakt darzustellen: 3x2x1=3!, 5x4x3x2x1=5!, und so weiter. Also n(n-1)(n-2). (2)(1)=n!.

Eine kompakte Darstellung für die Multiplikation von aufeinanderfolgenden ganzen Zahlen. Wir verwenden n! um das Produkt n(n-1)(n-2) erneut darzustellen. (2)(1) , wobei n eine positive ganze Zahl ist.

Beispiel zur Veranschaulichung der Verwendung von Permutationen:

Fast jeden Morgen oder Abend höre ich in den Nachrichten vom DCFS des Staates Illinois, dem Ministerium für Kinder- und Familiendienste. Ich bin verwirrt, weil unsere Fakultät für Mathematik einen Ausschuss namens Department Faculty Status Committee (DFSC) hat. Können Sie sehen, warum ich verwirrt bin? Wie viele verschiedene 4-Buchstaben-geordnete Anordnungen oder Permutationen gibt es für die Buchstabenmenge? ?

Wenn wir an vier Stellen denken, die besetzt werden müssen, __ __ __ __ , haben wir 4 Buchstaben zur Auswahl für die erste Stelle, 3 für die nächste, 2 Buchstaben für die nächste Stelle und 1 Wahl für die letzte Stelle. Nach dem Multiplikationsprinzip gibt es 4x3x2x1=24 verschiedene 4-Buchstaben-geordnete Anordnungen für die Buchstabenmenge .

Wir können diese Anwendung erweitern, um geordnete Anordnungen nur einiger Elemente in einer Menge zu betrachten. Zurück zum Beispiel zur Getränkekarte von Blaise's Bistro. Wenn Blaise nur vier mögliche Limonadenauswahlen posten wird, wie viele verschiedene bestellte Arrangements der vier Limonaden gibt es?

Wenn wir an vier Positionen denken, die besetzt werden müssen, __ __ __ __, haben wir 6 Limonaden zur Auswahl für die erste Position, 5 für die nächste, 4 Limonaden für die nächste und 3 Limonaden für die letzte Position. Nach dem Multiplikationsprinzip gibt es 6x5x4x3=360 verschiedene Möglichkeiten, vier der sechs Limonaden im Menü auszuwählen und zu bestellen.

Im Allgemeinen verwenden wir die Notation P(n,r), um die Anzahl der Möglichkeiten darzustellen, r Objekte aus einer Menge von n Objekten anzuordnen. Im ersten oben genannten Problem haben wir P(4,4)=24 bestimmt und im zweiten haben wir P(6,4)=360 berechnet. Der allgemeine Wert von P(n,r) ist n(n-1)(n-2). ([n-(r-1)] oder P(n,r)=n(n-1)(n-2). (n-r+1). Beachten Sie, dass n eine beliebige nichtnegative ganze Zahl sein kann. Gibt es Einschränkungen für den Wert von r?

Es gibt einen arithmetischen Schritt, den wir auf das allgemeine Muster für P(n,r) anwenden können, um die Permutationsberechnungen zu rationalisieren. In der zweiten Zeile unten haben wir mit multipliziert, was nur der Wert 1 ist, da Zähler und Nenner gleich sind. In der vierten Zeile unten sehen wir, wie der Ausdruck durch die faktorielle Notation vereinfacht werden kann.

Somit haben wir P(6,2)=6!/4! Und P(40,8)=40!/32!.

Was ist mit P(4,4)? Das obige Ergebnis legt P(4,4)=4!/0! nahe. Wir wissen bereits, dass P(4,4)=4x3x2x1=4!, also haben wir 4!=4!/0!. Damit dies zutrifft, muss 0!=1 sein. So seltsam das auch erscheinen mag, wir brauchen 0!=1, um die Konsistenz der Berechnungen zu gewährleisten, die wir durchführen möchten.

Kombinationen
Was ist der Unterschied zwischen diesen beiden Fragen?

(i) Auf wie viele Arten kann eine 5-Karten-Pokerhand ausgeteilt werden?

(ii) Wie viele verschiedene 5-Karten-Pokerhände gibt es?

Die erste Frage befasst sich mit der Reihenfolge oder Anordnung der Karten, wenn sie ausgeteilt werden. In der zweiten Frage ist das Endergebnis, wenn 2H,4D,JC,3S,10D in dieser Reihenfolge ausgeteilt wird, dasselbe wie bei 4D,3S,JC,10D,2H in dieser Reihenfolge. In jedem Fall existiert die gleiche 5-Karten-Pokerhand. Die Fragen helfen, den Unterschied zwischen einer Permutation und einer Kombination zu veranschaulichen.

Eine Sammlung von Elementen, deren Reihenfolge keine Rolle spielt.

Als Lösung des ersten Problems haben wir P(52,5) gefunden. Das heißt, wir haben 5 Objekte angeordnet, die aus 52 Karten ausgewählt wurden. Für die zweite Frage gibt es viele Arrangements, die das gleiche 5-Karten-Blatt ergeben. Dem müssen wir Rechnung tragen. Betrachten wir ein einfacheres Problem.

Wie viele geordnete Anordnungen gibt es für die Buchstaben des Sets ?

Mit Permutationen haben wir P(5,5) = 5! = 120 Möglichkeiten, die fünf Buchstaben anzuordnen.

Wie viele bestellte Arrangements gibt es von 3 Artikeln aus dem 5-Elemente-Set?

Wir haben P(5,3) = 543 = 5!/2! = 60 Anordnungen. Zum Beispiel für die drei Buchstaben wir haben diese Arrangements: ABC, ACB, BAC, BCA, CAB, CBA. Dies stellt 6 der 60 Arrangements dar, jedoch beinhaltet jedes die gleiche Auswahl von drei Buchstaben. Ebenso für die drei Buchstaben : Wir haben ACE, AEC, CAE, CEA, EAC, ECA.

Es scheint, dass für jede 3-Buchstaben-Teilmenge von Es gibt 6 Anordnungen der gleichen drei Buchstaben. Dies ist eine hilfreiche Beobachtung bei der Untersuchung der folgenden Frage:

Eine Möglichkeit besteht darin, die eindeutigen 3-Element-Teilmengen von list aufzulisten : ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Es gibt 10 solcher 3-Element-Teilmengen.

Eine andere Möglichkeit, die Anzahl zu berücksichtigen, besteht darin, die Tatsache zu verwenden, dass:

Im Allgemeinen haben wir eine Möglichkeit, die Anzahl der Kombinationen von n ausgewählten Elementen r gleichzeitig zu bestimmen, wobei die Auswahlreihenfolge oder die Anordnung der r Elemente nicht berücksichtigt wird:

Die Beziehung zwischen Permutationen und Kombinationen

Wenn r Elemente aus einer Menge von n Elementen gesammelt oder angeordnet werden sollen, dann ist die Anzahl der Kombinationen von n Elementen, die r gleichzeitig genommen werden, C(n,r) , bezogen auf die Anzahl der Permutationen von n Elementen, die r bei a at genommen werden Zeit, P(n,r) , gemäß der Gleichung

Kreisförmige Permutationen

Betrachten wir den Fall linear,

wir haben P(5,5) = 5! Anordnungen. Erweitern Sie dies nun zu einem Kreis:

Beachten Sie, dass in jedem dieser Fälle die gleichen Personen nebeneinander sitzen. Obwohl es eine Veränderung – eine Rotation – um den Tisch gegeben hat, befinden sich die fünf Kinder immer noch in der gleichen Position zueinander. Wie viele Möglichkeiten gibt es, die eindeutige lineare Beziehung ABCDE zu drehen? Es gibt fünf solcher Möglichkeiten, die alle in der Zeichnung abgebildet sind.

Somit haben wir 5! einzigartige lineare Anordnungen der Kinder, aber wir können diese gruppieren, sodass jede Gruppe 5 Anordnungen hat, die die Kinder in derselben Position relativ zueinander zeigen. Daher haben wir 5!/5 = 4! zirkuläre Permutationen der fünf Kinder.

Was ist, wenn wir eine r-elementige Teilmenge aus einer n-elementigen Menge in einem Kreis anordnen? Angenommen, wir arrangieren 3 der 5 Kinder. Im linearen Fall gibt es P(5,3) = 60 Anordnungen, aber wir können diese gruppieren, sodass jede Gruppe 3 Anordnungen hat, die die Kinder in derselben Position relativ zueinander zeigen. Daher haben wir P(5,3)/3 = 5!/(2!*3) zirkuläre Permutationen der fünf Kinder in Untermengen von 3 Kindern.

Eine zirkuläre Permutation ist eine zirkuläre Anordnung von Elementen, bei der die Reihenfolge der Elemente berücksichtigt werden muss.


Inhalt

Grundlegende kombinatorische Konzepte und Aufzählungsergebnisse tauchten in der gesamten antiken Welt auf. Im 6. Jahrhundert v. Chr. behauptet der alte indische Arzt Sushruta in Sushruta Samhita, dass 63 Kombinationen aus 6 verschiedenen Geschmacksrichtungen gemacht werden können, einer nach dem anderen, zwei gleichzeitig usw., wodurch alle 2 6 − 1 Möglichkeiten berechnet werden. Der griechische Historiker Plutarch diskutiert ein Argument zwischen Chrysippus (3. Jahrhundert v. Chr.) und Hipparchos (2. Jahrhundert v. Chr.) über ein ziemlich heikles Aufzählungsproblem, von dem später gezeigt wurde, dass es mit Schröder-Hipparchus-Zahlen zusammenhängt. [7] [8] [9] Früher, im Ostomachione, Archimedes (3. Jahrhundert v. Chr.) hat möglicherweise die Anzahl der Konfigurationen eines Kachelpuzzles berücksichtigt, [10] während kombinatorische Interessen möglicherweise in verlorenen Werken von Apollonius vorhanden waren. [11] [12]

Im Mittelalter wurde die Kombinatorik weitgehend außerhalb der europäischen Zivilisation weiter studiert. Der indische Mathematiker Mahāvīra (ca. 850) lieferte Formeln für die Zahl der Permutationen und Kombinationen, [13] [14] und diese Formeln dürften indischen Mathematikern bereits im 6. Jahrhundert n. Chr. geläufig gewesen sein. [15] Der Philosoph und Astronom Rabbi Abraham ibn Ezra (ca. 1140) stellte die Symmetrie der Binomialkoeffizienten auf, während der Talmudist und Mathematiker Levi ben Gerson (besser bekannt als Gersonides) 1321 eine geschlossene Formel erhielt. [16 ] Das arithmetische Dreieck – ein grafisches Diagramm, das die Beziehungen zwischen den Binomialkoeffizienten zeigt – wurde von Mathematikern in Abhandlungen aus dem 10. Jahrhundert vorgestellt und wurde schließlich als Pascal-Dreieck bekannt. Später, im mittelalterlichen England, lieferte die Campanologie Beispiele für das, was heute als Hamiltonsche Zyklen in bestimmten Cayley-Graphen zu Permutationen bekannt ist. [17] [18]

In der Renaissance erlebte die Kombinatorik zusammen mit der übrigen Mathematik und den Naturwissenschaften eine Wiedergeburt. Werke von Pascal, Newton, Jacob Bernoulli und Euler wurden in diesem aufstrebenden Feld grundlegend. In der Neuzeit sind die Werke von J.J. Sylvester (Ende des 19. Jahrhunderts) und Percy MacMahon (Anfang des 20. Jahrhunderts) trugen dazu bei, den Grundstein für die enumerative und algebraische Kombinatorik zu legen. Gleichzeitig erfreute sich auch die Graphentheorie einer Explosion des Interesses, insbesondere im Zusammenhang mit dem Vierfarbenproblem.

In der zweiten Hälfte des 20. Jahrhunderts erlebte die Kombinatorik ein schnelles Wachstum, was zur Gründung Dutzender neuer Zeitschriften und Konferenzen zu diesem Thema führte. [19] Das Wachstum wurde teilweise durch neue Verbindungen und Anwendungen auf andere Gebiete angetrieben, die von der Algebra bis zur Wahrscheinlichkeit, von der Funktionalanalyse bis zur Zahlentheorie usw. reichen. Diese Verbindungen lösten die Grenzen zwischen der Kombinatorik und Teilen der Mathematik und der theoretischen Informatik, führte aber gleichzeitig zu einer teilweisen Zersplitterung des Feldes.

Enumerative Kombinatorik Bearbeiten

Die enumerative Kombinatorik ist der klassischste Bereich der Kombinatorik und konzentriert sich auf das Zählen der Anzahl bestimmter kombinatorischer Objekte. Obwohl das Zählen der Anzahl von Elementen in einer Menge ein ziemlich breites mathematisches Problem ist, haben viele der Probleme, die in Anwendungen auftreten, eine relativ einfache kombinatorische Beschreibung. Fibonacci-Zahlen sind das grundlegende Beispiel für ein Problem in der enumerativen Kombinatorik. Der zwölffache Weg bietet einen einheitlichen Rahmen zum Zählen von Permutationen, Kombinationen und Partitionen.

Analytische Kombinatorik Bearbeiten

Die analytische Kombinatorik befasst sich mit der Aufzählung kombinatorischer Strukturen mit Werkzeugen der komplexen Analysis und der Wahrscheinlichkeitstheorie. Im Gegensatz zur enumerativen Kombinatorik, die explizite kombinatorische Formeln und generierende Funktionen verwendet, um die Ergebnisse zu beschreiben, zielt die analytische Kombinatorik darauf ab, asymptotische Formeln zu erhalten.

Teilungstheorie Bearbeiten

Die Partitionstheorie untersucht verschiedene Aufzählungs- und asymptotische Probleme im Zusammenhang mit ganzzahligen Partitionen und ist eng mit q-Reihen, speziellen Funktionen und orthogonalen Polynomen verbunden. Ursprünglich ein Teil der Zahlentheorie und -analyse, wird sie heute als Teil der Kombinatorik oder als eigenständiges Gebiet betrachtet. Es beinhaltet den bijektiven Ansatz und verschiedene Werkzeuge der Analysis und der analytischen Zahlentheorie und hat Verbindungen zur statistischen Mechanik.

Graphentheorie Bearbeiten

Graphen sind grundlegende Objekte der Kombinatorik. Überlegungen zur Graphentheorie reichen von der Aufzählung (z. B. die Anzahl der Graphen auf nein Scheitel mit k Kanten) auf bestehende Strukturen (z. B. Hamiltonsche Kreise) auf algebraische Darstellungen (z. B. gegebener Graph G und zwei Zahlen x und ja, ist das Tutte-Polynom TG(x,ja) haben eine kombinatorische Interpretation?). Obwohl es sehr starke Verbindungen zwischen Graphentheorie und Kombinatorik gibt, werden sie manchmal als separate Fächer betrachtet. [20] Während kombinatorische Methoden auf viele Probleme der Graphentheorie anwendbar sind, werden die beiden Disziplinen im Allgemeinen verwendet, um Lösungen für verschiedene Arten von Problemen zu suchen.

Designtheorie Bearbeiten

Die Designtheorie ist eine Untersuchung von kombinatorischen Designs, bei denen es sich um Sammlungen von Teilmengen mit bestimmten Schnitteigenschaften handelt. Blockdesigns sind kombinatorische Designs einer besonderen Art. Dieser Bereich ist einer der ältesten Teile der Kombinatorik, wie etwa in Kirkmans 1850 vorgeschlagenem Schulmädchenproblem. Die Lösung des Problems ist ein Spezialfall eines Steiner-Systems, dessen Systeme eine wichtige Rolle bei der Klassifikation endlicher einfacher Gruppen spielen. Das Gebiet hat weitere Verbindungen zur Codierungstheorie und zur geometrischen Kombinatorik.

Endliche Geometrie Bearbeiten

Endliche Geometrie ist die Lehre von geometrischen Systemen, die nur eine endliche Anzahl von Punkten haben. Strukturen, die denen in kontinuierlichen Geometrien (Euklidische Ebene, realer projektiver Raum usw.) analog sind, aber kombinatorisch definiert sind, sind die wichtigsten untersuchten Elemente. Dieser Bereich bietet eine reiche Quelle an Beispielen für die Designtheorie. Sie sollte nicht mit diskreter Geometrie (kombinatorische Geometrie) verwechselt werden.

Ordnungstheorie Bearbeiten

Ordnungstheorie ist das Studium von teilweise geordneten Mengen, sowohl endlichen als auch unendlichen. Verschiedene Beispiele für Teilordnungen erscheinen in Algebra, Geometrie, Zahlentheorie und in der Kombinatorik und Graphentheorie. Bemerkenswerte Klassen und Beispiele für Teilordnungen umfassen Gitter und Boolesche Algebren.

Matroid-Theorie Bearbeiten

Die Matroidtheorie abstrahiert einen Teil der Geometrie. Es untersucht die Eigenschaften von Mengen (normalerweise endlichen Mengen) von Vektoren in einem Vektorraum, die nicht von den jeweiligen Koeffizienten in einer linearen Abhängigkeitsbeziehung abhängen. Zur Matroidtheorie gehören nicht nur die Struktur, sondern auch enumerative Eigenschaften. Die Matroidtheorie wurde von Hassler Whitney eingeführt und als Teil der Ordnungstheorie untersucht. Es ist heute ein eigenständiges Studienfach mit einer Reihe von Verbindungen zu anderen Teilen der Kombinatorik.

Extremale Kombinatorik Bearbeiten

Extremale Kombinatorik untersucht extremale Fragen an Mengensystemen. Die in diesem Fall behandelten Arten von Fragen beziehen sich auf den größtmöglichen Graphen, der bestimmte Eigenschaften erfüllt. Der größte dreiecksfreie Graph auf 2n Ecken ist ein vollständiger zweiteiliger Graph Kn, n. Oft ist es sogar zu schwer, die extreme Antwort zu finden f(nein) genau und man kann nur asymptotisch abschätzen.

Die Ramsey-Theorie ist ein weiterer Teil der extremalen Kombinatorik. Es besagt, dass jede ausreichend große Konfiguration eine Art von Ordnung enthält. Es ist eine fortgeschrittene Verallgemeinerung des Schubladenprinzips.

Probabilistische Kombinatorik Bearbeiten

In der probabilistischen Kombinatorik sind die Fragen der folgenden Art: Wie hoch ist die Wahrscheinlichkeit einer bestimmten Eigenschaft für ein zufälliges diskretes Objekt, beispielsweise einen zufälligen Graphen? Wie groß ist zum Beispiel die durchschnittliche Anzahl von Dreiecken in einem Zufallsgraphen? Probabilistische Methoden werden auch verwendet, um die Existenz kombinatorischer Objekte mit bestimmten vorgeschriebenen Eigenschaften (für die es schwierig sein könnte, explizite Beispiele zu finden) zu bestimmen, indem einfach beobachtet wird, dass die Wahrscheinlichkeit, ein Objekt mit diesen Eigenschaften zufällig auszuwählen, größer als 0 ist. Dieser Ansatz ( oft bezeichnet als das probabilistische Methode) hat sich in Anwendungen der Extremalkombinatorik und der Graphentheorie als sehr effektiv erwiesen. Ein eng verwandtes Gebiet ist das Studium endlicher Markov-Ketten, insbesondere an kombinatorischen Objekten. Auch hier werden probabilistische Werkzeuge verwendet, um die Mischzeit abzuschätzen.

Oft mit Paul Erdős in Verbindung gebracht, der die Pionierarbeit zu diesem Thema leistete, wurde die probabilistische Kombinatorik traditionell als eine Reihe von Werkzeugen angesehen, um Probleme in anderen Teilen der Kombinatorik zu untersuchen. Mit der Zunahme von Anwendungen zur Analyse von Algorithmen in der Informatik sowie der klassischen Wahrscheinlichkeitstheorie, der additiven Zahlentheorie und der probabilistischen Zahlentheorie hat sich das Gebiet jedoch in jüngster Zeit zu einem eigenständigen Gebiet der Kombinatorik entwickelt.

Algebraische Kombinatorik Bearbeiten

Algebraische Kombinatorik ist ein Bereich der Mathematik, der Methoden der abstrakten Algebra, insbesondere Gruppentheorie und Darstellungstheorie, in verschiedenen kombinatorischen Kontexten anwendet und umgekehrt kombinatorische Techniken auf Probleme der Algebra anwendet. Die algebraische Kombinatorik erweitert ihren Umfang sowohl thematisch als auch technisch kontinuierlich und kann als der Bereich der Mathematik angesehen werden, in dem das Zusammenspiel von kombinatorischen und algebraischen Methoden besonders stark und bedeutsam ist.

Kombinatorik an Wörtern Bearbeiten

Kombinatorik auf Wörtern beschäftigt sich mit formalen Sprachen. Es entstand unabhängig in mehreren Zweigen der Mathematik, darunter Zahlentheorie, Gruppentheorie und Wahrscheinlichkeit. Es hat Anwendungen auf enumerative Kombinatorik, Fraktalanalyse, theoretische Informatik, Automatentheorie und Linguistik. Während viele Anwendungen neu sind, ist die klassische Chomsky-Schützenberger-Hierarchie von Klassen formaler Grammatiken vielleicht das bekannteste Ergebnis auf diesem Gebiet.

Geometrische Kombinatorik Bearbeiten

Geometrische Kombinatorik bezieht sich auf konvexe und diskrete Geometrie, insbesondere polyedrische Kombinatorik. Sie fragt beispielsweise, wie viele Seiten jeder Dimension ein konvexes Polytop haben kann. Auch metrische Eigenschaften von Polytopen spielen eine wichtige Rolle, z.B. der Cauchy-Satz über die Starrheit konvexer Polytope. Auch spezielle Polytope kommen in Betracht, wie Permutoheder, Assozieder und Birkhoff-Polytope. Kombinatorische Geometrie ist ein altmodischer Name für diskrete Geometrie.

Topologische Kombinatorik Bearbeiten

Kombinatorische Analoga von Konzepten und Methoden in der Topologie werden verwendet, um Graphfärbung, Fair Division, Partitionen, teilweise geordnete Mengen, Entscheidungsbäume, Halskettenprobleme und diskrete Morsetheorie zu studieren. Es sollte nicht mit kombinatorischer Topologie verwechselt werden, die ein älterer Name für algebraische Topologie ist.

Arithmetische Kombinatorik Bearbeiten

Die arithmetische Kombinatorik entstand aus dem Zusammenspiel von Zahlentheorie, Kombinatorik, Ergodentheorie und harmonischer Analysis. Es handelt sich um kombinatorische Schätzungen im Zusammenhang mit arithmetischen Operationen (Addition, Subtraktion, Multiplikation und Division). Die additive Zahlentheorie (manchmal auch additive Kombinatorik genannt) bezieht sich auf den Sonderfall, bei dem nur die Operationen Addition und Subtraktion beteiligt sind. Eine wichtige Technik in der arithmetischen Kombinatorik ist die ergodische Theorie dynamischer Systeme.

Unendliche Kombinatorik Bearbeiten

Die unendliche Kombinatorik oder kombinatorische Mengenlehre ist eine Erweiterung der Ideen der Kombinatorik auf unendliche Mengen. Es ist ein Teil der Mengenlehre, einem Gebiet der mathematischen Logik, verwendet jedoch Werkzeuge und Ideen sowohl aus der Mengenlehre als auch aus der Extremalkombinatorik.

Gian-Carlo Rota hat den Namen verwendet kontinuierliche Kombinatorik [21] um die geometrische Wahrscheinlichkeit zu beschreiben, da es viele Analogien zwischen Zählen und messen.

Kombinatorische Optimierung Bearbeiten

Kombinatorische Optimierung ist das Studium der Optimierung an diskreten und kombinatorischen Objekten. Es begann als Teil der Kombinatorik und Graphentheorie, wird aber heute als ein Zweig der angewandten Mathematik und Informatik betrachtet, der mit Operations Research, Algorithmustheorie und Computational Complexity Theory verbunden ist.

Codierungstheorie Bearbeiten

Die Codierungstheorie begann als Teil der Designtheorie mit frühen kombinatorischen Konstruktionen von fehlerkorrigierenden Codes. Die Hauptidee des Themas ist es, effiziente und zuverlässige Methoden der Datenübertragung zu entwickeln. Es ist jetzt ein großes Studiengebiet, Teil der Informationstheorie.

Diskrete und rechnerische Geometrie Bearbeiten

Diskrete Geometrie (auch kombinatorische Geometrie genannt) begann ebenfalls als Teil der Kombinatorik mit frühen Ergebnissen zu konvexen Polytopen und Kissing Numbers. Mit dem Aufkommen von Anwendungen der diskreten Geometrie auf die Computergeometrie verschmolzen diese beiden Gebiete teilweise und wurden zu einem separaten Studiengebiet. Es bleiben viele Verbindungen zur geometrischen und topologischen Kombinatorik, die ihrerseits als Auswüchse der frühen diskreten Geometrie betrachtet werden können.

Kombinatorik und dynamische Systeme Bearbeiten

Kombinatorische Aspekte dynamischer Systeme sind ein weiteres aufstrebendes Feld. Hier können dynamische Systeme auf kombinatorischen Objekten definiert werden. Siehe zum Beispiel Graph dynamisches System.

Kombinatorik und Physik Bearbeiten

Es gibt zunehmend Wechselwirkungen zwischen Kombinatorik und Physik, insbesondere der statistischen Physik. Beispiele sind eine exakte Lösung des Ising-Modells und eine Verbindung zwischen dem Potts-Modell einerseits und den chromatischen und Tutte-Polynomen andererseits.


5: Mengen und Zählen - Mathematik

Aber das wiederholte Addieren von 1 ist eine sehr primitive Form der Addition, die auch nicht sehr nützlich ist. Beim Tippen des Zitats verlor ich auch mehrmals die Zählung. Es ist viel einfacher, Objekte zu zählen, indem Sie sie in kleine Gruppen gruppieren und später die zu jeder Gruppe gehörenden Mengen addieren. Wenn alle Gruppen die gleiche Anzahl von Objekten haben, erkennen wir die Relevanz einer anderen arithmetischen Operation - Multiplikation - zum Zählen. Die mathematische Schreibweise für "2 und 2 und 2" ist beispielsweise "3 mal 2" oder symbolisch 3·2. 3·2 ist also dasselbe wie "1 und 1 und 1 und 1 und 1 und 1", was als 6 bezeichnet wird: 3·2 = 6. Manchmal können wir Objekte nicht gleichmäßig in kleinere Gruppen aufteilen. Wenn wir beispielsweise 7 in Gruppen von 3 Objekten aufteilen, erhalten wir 2 Gruppen und 1 übrig gebliebenes Objekt. In diesem Fall verbinden sich Addition und Multiplikation in der mathematischen Schreibweise: 2·3 + 1 = 7. So führt das Zählen auf die Idee von Einteilung und sogar von Division mit Rest. 3·2 = 6 bedeutet nicht nur, dass drei Gruppen zu je 2 Elementen zusammen 6 Elemente ergeben, sondern auch, dass eine Gruppe von 6 Elementen sein kann geteilt in 3 Gruppen zu je 2 Elementen. Der zweite Teil ist eine bloße Paraphrase des ersten Teils der vorherigen Aussage. Wenn wir versuchen, 7 in zwei Gruppen aufzuteilen, erhalten wir zwei Gruppen von drei Objekten und 1 zusätzliches Element. 7 wird nicht gleichmäßig durch 2 geteilt.

Im Folgenden finden Sie ein Applet, das beim Erkunden dieser Konzepte hilft. Sehen Sie, dass dies tatsächlich möglich ist, Objekte auf viele verschiedene Arten zu zählen und zu gruppieren, die immer zum gleichen Ergebnis führen. Beachten Sie die mathematischen Notationen, die verwendet werden, um verschiedene Gruppierungen von Objekten zu beschreiben. Zähle Objekte, indem du sie nacheinander anklickst.

Wenn Sie dies lesen, ist Ihr Browser nicht auf die Ausführung von Java-Applets eingestellt. Probieren Sie IE11 oder Safari aus und deklarieren Sie die Site https://www.cut-the-knot.org als vertrauenswürdig im Java-Setup.

Das nächste Applet ist etwas abstrakter. Zählen ist ein nützliches Handwerk, aber wir wissen bereits, dass Addition und Multiplikation es oft erheblich beschleunigen können. In diesem Applet können Sie auf jede der drei Zahlen klicken. Wenn Sie etwas rechts von der Mittellinie klicken, wird die Zahl um eins erhöht. Ein kleiner Klick links neben der Zahl verringert die Zahl um 1. Das mathematische Symbol ">" steht für mehr als, "

Wenn Sie dies lesen, ist Ihr Browser nicht auf die Ausführung von Java-Applets eingestellt. Probieren Sie IE11 oder Safari aus und deklarieren Sie die Site https://www.cut-the-knot.org als vertrauenswürdig im Java-Setup.

Schließlich ist hier ein Applet, das eine Variation eines Problems mit zwei Gruppen darstellt. Sagen Sie, Sie haben Äpfel und Pfirsiche. Insgesamt sind es 12 Früchte. Es gibt zwei Äpfel mehr als Pfirsiche. Wie viele von jeder Frucht gibt es? Beachten Sie, dass das Problem nicht immer eine Lösung hat. Versuchen Sie, daran zu denken, wann dies der Fall ist.

Wenn Sie dies lesen, ist Ihr Browser nicht auf die Ausführung von Java-Applets eingestellt. Probieren Sie IE11 oder Safari aus und deklarieren Sie die Site https://www.cut-the-knot.org als vertrauenswürdig im Java-Setup.

Prof. W. McWorter war so freundlich, seine Erfahrungen im Unterrichten des Zählens an junge Studenten zu teilen.

In seinem Buch Die automatische Ameise verfolgen (Springer, 1998) erzählt David Gale die folgende Geschichte:

Es war einmal ein kleines Mädchen namens Clara, die war kaum drei Jahre alt und hatte gerade das Zählen gelernt. Sie konnte erkennen, wie viele Stühle im Wohnzimmer standen und wie viele Stufen von der Veranda entfernt waren. Eines Tages beschloss ihr Vater, sie zu testen. „Schau“, sagte er, „ich habe dir diese vier Lutscher mitgebracht“, aber er gab ihr nur drei. Clara nahm die Lutscher und zählte pflichtbewusst: "Eins, zwei, vier." Dann sah sie ein wenig verwirrt auf und fragte: "Wo ist der dritte?"


Zähle und vergleiche

Zähle zwei Sätze von Objekten und zeichne mehr, um sie gleich zu machen.

Ein Schläger nützt nicht viel, wenn Sie keinen Ball haben. Es gibt viele Möglichkeiten, Objektgruppen im ganzen Haus zu kombinieren, aber es ist auch nützlich, sich hinzusetzen und es auf Papier zu versuchen. Hier ist ein großartiger Satz von vier Seiten, auf dem Kinder aufgefordert werden, zwei Sätze Schläger und Bälle zu zählen und dann mehr zu zeichnen, um sie gleich zu machen.

Gehen deine Socken beim Waschen verloren? Es gibt viele Möglichkeiten, Objektgruppen im ganzen Haus zu kombinieren, aber es ist auch nützlich, sich hinzusetzen und es auf Papier zu versuchen. Hier ist ein großartiger Satz von vier Seiten, auf dem Kinder aufgefordert werden, zwei Sätze Schuhe und Socken zu zählen und dann mehr zu zeichnen, um sie gleich zu machen.

Zählen und Zuordnen kleiner Mengen von Honiggläsern und Löffeln.

Zählen und Zuordnen einer kleinen Anzahl von Spinnen und Netzen.

Haben Sie die richtige Anzahl an Löffeln für all die leckeren Eiscremes? Es gibt viele Möglichkeiten, Objektgruppen im ganzen Haus zu kombinieren, aber es ist auch nützlich, sich hinzusetzen und es auf Papier zu versuchen. Hier ist ein schönes Set von vier Seiten, auf dem die Kinder zwei Sätze zählen und dann mehr zeichnen, um sie gleich zu machen.


Inhalt

Die folgenden Abschnitte führen bestimmte Konstruktionen in den beiden Theorien ZFC und NFU durch und vergleichen die resultierenden Implementierungen bestimmter mathematischer Strukturen (zB der natürlichen Zahlen).

Mathematische Theorien beweisen Theoreme (und sonst nichts). Zu sagen, dass eine Theorie die Konstruktion eines bestimmten Objekts erlaubt, bedeutet, dass es ein Theorem dieser Theorie ist, dass dieses Objekt existiert. Dies ist eine Aussage über eine Definition der Form "das x so dass ϕ existiert", wobei ϕ eine Formel unserer Sprache ist: die Theorie beweist die Existenz von "the x such dass ϕ ", nur für den Fall, dass es ein Theorem ist, dass "es ein und nur ein x mit ϕ " gibt. (Siehe Bertrand Russells Theorie der Beschreibungen.) In diesem Fall "definiert" oder "konstruiert" die Theorie dieses Objekt. Wenn die Aussage kein Theorem ist, kann die Theorie nicht zeigen, dass das Objekt existiert, wenn die Aussage in der Theorie beweisbar falsch ist, sie beweist, dass das Objekt nicht lose existieren kann, das Objekt kann nicht konstruiert werden.

Ausdrücke, die in der Set-Builder-Notation definierbar sind, sind sowohl in ZFC als auch in NFU sinnvoll: Es kann sein, dass beide Theorien beweisen, dass eine gegebene Definition erfolgreich ist oder dass keine der beiden Theorien erfolgreich ist (der Ausdruck < x ∣ x ∉ x >> verweist auf nichts in irgendein Mengenlehre mit klassischer Logik in Klassentheorien wie NBG bezieht sich diese Notation auf eine Klasse, aber sie ist anders definiert) oder dass die eine dies tut und die andere nicht. Außerdem kann sich herausstellen, dass ein in ZFC und NFU auf dieselbe Weise definiertes Objekt in den beiden Theorien unterschiedliche Eigenschaften hat (oder es kann einen Unterschied geben, was bewiesen werden kann, wenn es keinen beweisbaren Unterschied zwischen ihren Eigenschaften gibt).

Darüber hinaus importiert die Mengenlehre Konzepte aus anderen Zweigen der Mathematik (in Absicht, alle Zweige der Mathematik). In einigen Fällen gibt es verschiedene Möglichkeiten, die Konzepte in ZFC und NFU zu importieren. For example, the usual definition of the first infinite ordinal ω in ZFC is not suitable for NFU because the object (defined in purely set theoretical language as the set of all finite von Neumann ordinals) cannot be shown to exist in NFU. The usual definition of ω in NFU is (in purely set theoretical language) the set of all infinite well-orderings all of whose proper initial segments are finite, an object which can be shown not to exist in ZFC. In the case of such imported objects, there may be different definitions, one for use in ZFC and related theories, and one for use in NFU and related theories. For such "implementations" of imported mathematical concepts to make sense, it is necessary to be able to show that the two parallel interpretations have the expected properties: for example, the implementations of the natural numbers in ZFC and NFU are different, but both are implementations of the same mathematical structure, because both include definitions for all the primitives of Peano arithmetic and satisfy (the translations of) the Peano axioms. It is then possible to compare what happens in the two theories as when only set theoretical language is in use, as long as the definitions appropriate to ZFC are understood to be used in the ZFC context and the definitions appropriate to NFU are understood to be used in the NFU context.

Whatever is proven to exist in a theory clearly provably exists in any extension of that theory moreover, analysis of the proof that an object exists in a given theory may show that it exists in weaker versions of that theory (one may consider Zermelo set theory instead of ZFC for much of what is done in this article, for example).

These constructions appear first because they are the simplest constructions in set theory, not because they are the first constructions that come to mind in mathematics (though the notion of finite set is certainly fundamental). Even though NFU also allows the construction of set ur-elements yet to become members of a set, the empty set is the unique set with no members:

The union of two sets is defined in the usual way:

In NFU, all the set definitions given work by stratified comprehension in ZFC, the existence of the unordered pair is given by the Axiom of Pairing, the existence of the empty set follows by Separation from the existence of any set, and the binary union of two sets exists by the axioms of Pairing and Union ( x ∪ y = ⋃ < x , y >> ).

First, consider the ordered pair. The reason that this comes first is technical: ordered pairs are needed to implement relations and functions, which are needed to implement other concepts which may seem to be prior. The first definition of the ordered pair was the definition ( x , y ) = d e f < < < x >, ∅ > , < < y >> > ><=>><<,emptyset >,<>>> proposed by Norbert Wiener in 1914 in the context of the type theory of Principia Mathematica. Wiener observed that this allowed the elimination of types of nein-ary relations for nein > 1 from the system of that work. It is more usual now to use the definition ( x , y ) = d e f . < < x >, < x , y >> ><=>><,>> , due to Kuratowski. Either of these definitions works in either ZFC or NFU. In NFU, these two definitions have a technical disadvantage: the Kuratowski ordered pair is two types higher than its projections, while the Wiener ordered pair is three types higher. It is common to postulate the existence of a type-level ordered pair (a pair ( x , y ) which is the same type as its projections) in NFU. It is convenient to use the Kuratowski pair in both systems until the use of type-level pairs can be formally justified. The internal details of these definitions have nothing to do with their actual mathematical function. For any notion ( x , y ) of ordered pair, the thing that matters is that it satisfies the defining condition

( x , y ) = ( z , w ) ≡ x = z ∧ y = w

…and that it be reasonably easy to collect ordered pairs into sets.

In ZFC, some relations (such as the general equality relation or subset relation on sets) are 'too large' to be sets (but may be harmlessly reified as proper classes). In NFU, some relations (such as the membership relation) are not sets because their definitions are not stratified: in < ( x , y ) ∣ x ∈ y >> x and y would need to have the same type (because they appear as projections of the same pair), but also successive types (because x is considered as an element of y ).

Related definitions Edit

Das field of R is the union of the domain and range of R .

Notice that with our formal definition of a binary relation, the range and codomain of a relation are not distinguished. This could be done by representing a relation R with codomain B as ( R , B ) , but our development will not require this.

Properties and kinds of relations Edit

  • Reflexive if x R x for every x in the field of R .
  • Symmetric if ∀ x , y ( x R y → y R x ) .
  • Transitive if ∀ x , y , z ( x R y ∧ y R z → x R z ) .
  • Antisymmetric if ∀ x , y ( x R y ∧ y R x → x = y ) .
  • Well-founded if for every set S which meets the field of R , ∃ x ∈ S whose preimage under R does not meet S .
  • Extensional if for every x , y in the field of R , x = y if and only if x and y have the same preimage under R .

Relations having certain combinations of the above properties have standard names. A binary relation R is:

Operations on functions Edit

Special kinds of function Edit

A function is an injective (also called one-to-one) if it has an inverse function.

It can be shown that | A | ≤ | B | is a linear order on abstract cardinals, but not on sets. Reflexivity is obvious and transitivity is proven just as for equinumerousness. The Schröder–Bernstein theorem, provable in ZFC and NFU in an entirely standard way, establishes that

    | A | ≤ | B | ∧ | B | ≤ | A | → | A | = | B |

(this establishes antisymmetry on cardinals), and

follows in a standard way in either theory from the axiom of choice.

Natural numbers can be considered either as finite ordinals or finite cardinals. Here consider them as finite cardinal numbers. This is the first place where a major difference between the implementations in ZFC and NFU becomes evident.

which is the intersection of all sets which contain the empty set and are closed under the "successor" operation y ↦ y ∪ < y >> .

The usual operations of arithmetic can be defined recursively and in a style very similar to that in which the set of natural numbers itself is defined. For example, + (the addition operation on natural numbers) can be defined as the smallest set which contains ( ( x , ∅ ) , x ) for each natural number x and contains ( ( x , y ∪ < y >) , z ∪ < z >) ),zcup )> whenever it contains ( ( x , y ) , z ) .

The standard definition of the natural numbers, which is actually the oldest set-theoretic definition of natural numbers, is as equivalence classes of finite sets under equinumerousness. Essentially the same definition is appropriate to NFU (this is not the usual definition, but the results are the same): define Fin, the set of finite sets, as

The operations of arithmetic can be defined in a style similar to the style given above (using the definition of successor just given). They can also be defined in a natural set theoretical way: if A and B are disjoint finite sets, define |A|+|B| as | A ∪ B | . More formally, define m+n for m und nein im Nein as

(But note that this style of definition is feasible for the ZFC numerals as well, but more circuitous: the form of the NFU definition facilitates set manipulations while the form of the ZFC definition facilitates recursive definitions, but either theory supports either style of definition).

The two implementations are quite different. In ZFC, choose a representative of each finite cardinality (the equivalence classes themselves are too large to be sets) in NFU the equivalence classes themselves are sets, and are thus an obvious choice for objects to stand in for the cardinalities. However, the arithmetic of the two theories is identical: the same abstraction is implemented by these two superficially different approaches.

A general technique for implementing abstractions in set theory is the use of equivalence classes. If an equivalence relation R tells us that elements of its field EIN are alike in some particular respect, then for any set x, regard the set [ x ] R = < y ∈ A ∣ x R y >=> as representing an abstraction from the set x respecting just those features (identify elements of EIN up to R).

Similarity is shown to be an equivalence relation in much the same way that equinumerousness was shown to be an equivalence relation above.

In New Foundations (NFU), the order type of a well-ordering W is the set of all well-orderings which are similar to W. The set of ordinal numbers is the set of all order types of well-orderings.

This does not work in ZFC, because the equivalence classes are too large. It would be formally possible to use Scott's trick to define the ordinals in essentially the same way, but a device of von Neumann is more commonly used.

In ZFC, the order type of a well-ordering W is then defined as the unique von Neumann ordinal which is equinumerous with the field of W and membership on which is isomorphic to the strict well-ordering associated with W. (the equinumerousness condition distinguishes between well-orderings with fields of size 0 and 1, whose associated strict well-orderings are indistinguishable).

In ZFC there cannot be a set of all ordinals. In fact, the von Neumann ordinals are an inconsistent totality in any set theory: it can be shown with modest set theoretical assumptions that every element of a von Neumann ordinal is a von Neumann ordinal and the von Neumann ordinals are strictly well-ordered by membership. It follows that the class of von Neumann ordinals would be a von Neumann ordinal if it were a set: but it would then be an element of itself, which contradicts the fact that membership is a strict well-ordering of the von Neumann ordinals.

The existence of order types for all well-orderings is not a theorem of Zermelo set theory: it requires the Axiom of replacement. Even Scott's trick cannot be used in Zermelo set theory without an additional assumption (such as the assumption that every set belongs to a rank which is a set, which does not essentially strengthen Zermelo set theory but is not a theorem of that theory).

Ordinals fixed by T are called Cantorian ordinals, and ordinals which dominate only cantorian ordinals (which are easily shown to be cantorian themselves) are said to be strongly cantorian. There can be no set of cantorian ordinals or set of strongly cantorian ordinals.

Digression: von Neumann ordinals in NFU Edit

The only von Neumann ordinals which can be shown to exist in NFU without additional assumptions are the concrete finite ones. However, the application of a permutation method can convert any model of NFU to a model in which every strongly cantorian ordinal is the order type of a von Neumann ordinal. This suggests that the concept "strongly cantorian ordinal of NFU" might be a better analogue to "ordinal of ZFC" than is the apparent analogue "ordinal of NFU".

Cardinal numbers are defined in NFU in a way which generalizes the definition of natural number: for any set EIN, | A | = d e f < B ∣ B ∼ A > ><=>>left> .

The natural order on cardinal numbers is seen to be a well-ordering: that it is reflexive, antisymmetric (on abstract cardinals, which are now available) and transitive has been shown above. That it is a linear order follows from the Axiom of Choice: well-order two sets and an initial segment of one well-ordering will be isomorphic to the other, so one set will have cardinality smaller than that of the other. That it is a well-ordering follows from the Axiom of Choice in a similar way.

With each infinite cardinal, many order types are associated for the usual reasons (in either set theory).

The exponential operation is total and behaves exactly as expected on cantorian cardinals, since T fixes such cardinals and it is easy to show that a function space between cantorian sets is cantorian (as are power sets, cartesian products, and other usual type constructors). This offers further encouragement to the view that the "standard" cardinalities in NFU are the cantorian (indeed, the strongly cantorian) cardinalities, just as the "standard" ordinals seem to be the strongly cantorian ordinals.

So there are two different implementations of the natural numbers in NFU (though they are the same in ZFC): finite ordinals and finite cardinals. Each of these supports a T operation in NFU (basically the same operation). It is easy to prove that T ( n ) is a natural number if n is a natural number in NFU + Infinity + Choice (and so | N | and the first infinite ordinal ω are cantorian) but it is not possible to prove in this theory that T ( n ) = n . However, common sense indicates that this should be true, and so it can be adopted as an axiom:

One natural consequence of this axiom (and indeed its original formulation) is

All that can be proved in NFU without Counting is | < 1 , … , n >| = T 2 ( n ) |=T^<2>(n)> .

A consequence of Counting is that Nein is a strongly cantorian set (again, this is an equivalent assertion).

Properties of strongly cantorian sets Edit

Any subset of a strongly cantorian set is strongly cantorian. The power set of a strongly cantorian set is strongly cantorian. The cartesian product of two strongly cantorian sets is strongly cantorian.

Introducing the Axiom of Counting means that types need not be assigned to variables restricted to Nein or to P(Nein), R (the set of reals) or indeed any set ever considered in classical mathematics outside of set theory.

There are no analogous phenomena in ZFC. See the main New Foundations article for stronger axioms that can be adjoined to NFU to enforce "standard" behavior of familiar mathematical objects.

Represent magnitudes (positive reals) as nonempty proper initial segments of the positive rationals with no largest element. The operations of addition and multiplication on magnitudes are implemented by elementwise addition of the positive rational elements of the magnitudes. Order is implemented as set inclusion.

This is the briefest sketch of the constructions. Note that the constructions are exactly the same in ZFC and in NFU, except for the difference in the constructions of the natural numbers: since all variables are restricted to strongly cantorian sets, there is no need to worry about stratification restrictions. Without the Axiom of Counting, it might be necessary to introduce some applications of T in a full discussion of these constructions.

In this class of constructions it appears that ZFC has an advantage over NFU: though the constructions are clearly feasible in NFU, they are more complicated than in ZFC for reasons having to do with stratification.

The definitions are the same in ZFC but without any worries about stratification (the grouping given here is opposite to that more usually used, but this is easily corrected for).

It is possible to extend these definitions to handle index sets which are not sets of singletons, but this introduces an additional type level and is not needed for most purposes.

Permutation methods can be used to show relative consistency with NFU of the assertion that for every strongly cantorian set A there is a set I of the same size whose elements are self-singletons: i = < i >> for each ich im I.

This construction cannot be carried out in NFU because the power set operation is not a set function in NFU ( P ( A ) is one type higher than A for purposes of stratification).

In particular, there will be an isomorphism type [v] whose preimage under E is the collection of all T[x]'s (including T[v]). Schon seit T[v] E v and E is well-founded, T [ v ] ≠ v . This resembles the resolution of the Burali–Forti paradox discussed above and in the New Foundations article, and is in fact the local resolution of Mirimanoff's paradox of the set of all well-founded sets.

There are ranks of isomorphism classes of set pictures just as there are ranks of sets in the usual set theory. For any collection of set pictures EIN, define S(EIN) as the set of all isomorphism classes of set pictures whose preimage under E is a subset of A call A a "complete" set if every subset of EIN is a preimage under E. The collection of "ranks" is the smallest collection containing the empty set and closed under the S operation (which is a kind of power set construction) and under unions of its subcollections. It is straightforward to prove (much as in the usual set theory) that the ranks are well-ordered by inclusion, and so the ranks have an index in this well-order: refer to the rank with index α as R α > . It is provable that | R α | = ℶ α |=eth _> for complete ranks R α > . The union of the complete ranks (which will be the first incomplete rank) with the relation E looks like an initial segment of the universe of Zermelo-style set theory (not necessarily like the full universe of ZFC because it may not be large enough). It is provable that if R α > is the first incomplete rank, then R T ( α ) > is a complete rank and thus T ( α ) < α . So there is a "rank of the cumulative hierarchy" with an "external automorphism" T moving the rank downward, exactly the condition on a nonstandard model of a rank in the cumulative hierarchy under which a model of NFU is constructed in the New Foundations article. There are technical details to verify, but there is an interpretation not only of a fragment of ZFC but of NFU itself in this structure, with [ x ] ∈ N F U [ y ] [y]> defined as T ( [ x ] ) E [ y ] ∧ [ y ] ∈ R T ( α ) + 1 > : this "relation" E N F U > is not a set relation but has the same type displacement between its arguments as the usual membership relation ∈ .

So there is a natural construction inside NFU of the cumulative hierarchy of sets which internalizes the natural construction of a model of NFU in Zermelo-style set theory.

Under the Axiom of Cantorian Sets described in the New Foundations article, the strongly cantorian part of the set of isomorphism classes of set pictures with the E relation as membership becomes a (proper class) model of ZFC (in which there are nein-Mahlo cardinals for each nein this extension of NFU is strictly stronger than ZFC). This is a proper class model because the strongly cantorian isomorphism classes do not make up a set.

Permutation methods can be used to create from any model of NFU a model in which every strongly cantorian isomorphism type of set pictures is actually realized as the restriction of the true membership relation to the transitive closure of a set.


5: Sets and Counting - Mathematics

Counting and Comparing Difficulties

Subitizing is the ability to recognize a number of briefly presented items without actually counting.

A common response to students who are having counting problems is to simply have them do daily counting practice however, students with counting and comparing difficulties also benefit from practice that utilizes patterns and relationships. These strategies improve their ability to conceptualize and compare numbers without counting. Data in a study of dyslexic students who had difficulty with basic arithmetic skills (Fischer B., Kongeter A., Hartnegg K., 2008) showed that dyslexic children could also improve subitizing and visual counting through daily practice. It is important to distinguish the whole-to part process involved with this training. Not all daily counting practice is created equal. These dyslexic students did not achieve their gains in arithmetic merely through the process of counting. They were taught counting strategies for many years to add and subtract numbers with little benefit to their overall concept of number. Students made their gains because they were supplied with a whole- or gestalt then they combined subordinate parts to reconstruct the image. Over time they improved their ability to match quantity with successively larger patterns.

(See the example strategy below.)

Example Strategy: Using Icons of Quantity To Teach Whole-to-Part Relationships

Woodin: The ability to identify a subordinate quantity in relation to a whole enables these quantities to be seen in a relational context that fosters comparison without employing the inefficient and often inaccurate process of counting. The following exercise explains a whole-to-part procedure that is driven by a concrete visual model. Using a whole-to-part model, place five pieces of cereal on a table in a canonical “: • :” pattern. Model a subtraction event by removing pieces. Label the process by making a subtraction sentence, then let the student replace the pieces, and label this action with a related addition fact:

Teacher: “How many are you starting with?”

-The teacher removes the center piece of cereal to leave a square arrangement.

(: • : – • = : :).

Teacher: “Tell me what happened.”

Student: “We had five, you took away one and four are left.”

Teacher: “Say the same thing with a number sentence.”

-The teacher hands the piece of cereal to the student.

Teacher: “Put this back and make a number sentence.” (: : + • = : • :).

Example Strategy: Using Patterns To Support Number Comparisons

Woodin has seen impressive results from instruction that incorporates visual patterning. Consistent graphic organizers that relate quantities to both five and ten provide the structure necessary to develop cardinality with numbers one through ten, and then extend this knowledge to the base-ten system. Consider the following patterns that relate to the gestalts of five and ten.

Each of these icons of quantity is subordinate to the gestalt of the Ten Icon (Woodin, 1995). Using the Ten Icon as a reference, the other icons represent a quantity of items that are visible, as well as an identifiable void that is the missing addend to make 10. Additional shading allows comparison to 5. For example, the Six Icon is made with a blue component of 5 and one red block: (6 = 5 + 1). In reference to the Ten Icon, the 6 is missing a square arrangement of 4 red blocks: (10 = 6 + 4). All of the missing addends to 10 may be driven by flashing an Icon card, asking the name of the card and the missing shape or number needed to make ten. See an example of this technique by viewing the video below.

Strategy Demonstration: Prompt the Missing Addends to 10

Quantities that are presented in concrete form, or represented by a diagram, are not subject to reversals. With the circles/dots at the left, there’s no change of misreading the quantity they represent. Consider an Arabic “4,” which can be incorrectly written in its mirrored form, versus a square pattern with an identical mirror image. These patterns can be used to diagram addition or subtraction problems. An “X” is used as an efficient way of producing a group of five in the following to make icons of 6 and 7. When addition problems are diagramed with Icon patterns, the sum emerges from the two addends. The following video clip illustrates the Icon addition process:

Patterning Should Be Extended to the Multiplication Process

Generate the 2x facts by stamping finger patterns on a template like the one pictured above. The teacher should write the number of fingers to be stamped in the top circle. The student then holds out that number of fingers, dips them in paint, and stamps this quantity onto the template “two times.” The student should first stamp his fingers at the top of the template, then duplicate the same pattern again below it. From this student-centered location the student produces a concrete diagram of multiplication from his primary frame of reference. The process of stamping the quantity “two times” provides the student with a concrete definition of the “times: X” multiplication operation and sign.

Example Strategies: Finger Stamping the 2x Facts

Strategy I: Stamp 3 two times

Use the student’s right hand to produce patterns of two times: one, two, three, or four fingers. Have the student dip his right-hand fingers in red paint, then “stamp” the pattern twice on the red portion of the template. The example shown above depicts stamping 2 x 3 = 6. Dip three fingers on the right hand in red paint and stamp them twice.

The six red dots can be smeared into an Arabic “6” when done.

To stamp numbers 5 and larger “two times,” the left-hand fingers will be needed. Dip the left-hand fingers in blue paint, then extend additional right (red) fingers necessary to match the number. The stamped quantities of fingerprints display a chunked depiction of the product that aligns with base ten place value. A blue pattern of ten will be produced on the left in the ten’s place. Additional red prints will be produced on the right.

Strategy II: Stamp 8 Two Times

Extend all left-hand fingers and dip them in blue finger paint. Extend three right-hand fingers and dip them in red paint. Stamp both hands (two times) on the paper. By stamping all eight fingers two times, the student will create the product: 1 group of ten blue fingerprints on the left–in the ten’s place, and six red prints on the right–in the ones place: “2 x 8 = 16.” The following movie demonstrates the process of creating the 2x products with the finger-stamping technique.

Using a Clock Face To Chunk and Organize Information

Download the Graphic Organizer for this Exercise. Click here.
Chris Woodin has graciously allowed us to offer PDFs of some of the graphic organizers he uses in his classroom. To see more organizers and information, click here.

The 12 clock positions of the analog clock may be used to learn and compare the 5x facts. This is accomplished through a series of gross motor kinesthetic activities that initially place the student at the center of a large clock dial, facing the 12 position. From this student-centered location the student internalizes the relative number locations from his primary reference frame. Minute values are then associated with these positions. Clock positions are merged with minute values to create 5x multiplication facts in a relational context. As the student points to the 3 position of the clock, both the number 3 and minute value of 15 may be simultaneously held in memory. The internalized structure of the clock also provides a student with the ability to simultaneously access several facts so they may be compared. This ability is particularly useful when dividing. For instance, if a student were able to visualize 37 between the benchmark minute values of 35 and 40, he would be able to determine that 37 cents would be made with 7, not 8, nickels.

In the following video, students will use the familiar structure of the clock to learn about the 5x fact family within a relational context. Students learn to interact with the analog clock dial from within their primary reference frame, and then externalize this structure to a paper-and-pencil task. Ultimately, they are empowered to create and compare 5x facts.

Tell us if you have your own strategies for your students. Click here.

One educator in Connecticut suggested this for learning the 9 facts: When multiplying the numbers 2 – 9 by 9, the two digits in the resulting answer will add up to nine. So, for instance, 5 x 9 = 45 (4 plus 5 adds up to 9). It’s a good way to check your answers.

About Chris Woodin:

Christopher Woodin is a specialist in the field of mathematics and learning disabilities. A graduate of Middlebury College and Harvard Graduate School of Education, he has taught extensively at Landmark School in Massachusetts. At Landmark School’s Elementary/Middle School Campus, he holds the Ammerman Chair of Mathematics. Christopher served on the Massachusetts Department of Education’s Mathematics 2011 Curriculum Framework Panel, and teaches graduate-level professional development courses during the summer through Landmark’s Outreach Program. Chris was the 1997 Massachusetts Learning Disabilities Association (LDA) Samuel Kirk Educator of the Year. He has presented at numerous international LDA and International Dyslexia Association (IDA) conferences, and has led math workshops to audiences across the country.

Christopher has published The Landmark Method of Teaching Arithmetic ©1995 and several journal articles. His latest project, Multiplication and Division Facts for the Whole-to-Part, Visual Learner: An Activity-Based Guide to Developing Fluency with Math Facts, is currently in press and due to be released in 2012. This comprehensive text features the methodologies and many of the activities that are described on The Yale Center for Dyslexia & Creativity’s website. To learn more about Mr. Woodin and his work, please visit his page on the Landmark School website and his own website.


Fingers instead of dots!

These finger games address the same math concepts as the dot card games. Children can have fun practicing their math skills in a new format. All that’s needed are fingers!

Finger Games

Focus on subitizing and on composition and decomposition of numbers.

Game 1: Fingers, Fingers

  1. Say, “Hold your hands behind your back.”
  2. Together, chant, “Fingers, fingers, 1, 2, 3. How many fingers do you see?”
  3. Using two hands, hold up three fingers. (Start with the typical ways of showing 1–5 on your fingers.)
  4. Children can say three or show three with their fingers.
  5. Keep playing with different numbers of fingers, focusing on 1–5 and slowly moving up to 10.
  6. Vary how you show each number on your fingers.

Game 2: Show Me . . .

  1. Hold up any number of fingers.
  2. Ask children to show you the same number on their fingers but in a different way.

Game 3: One More, One Less

  1. Hold up any number of fingers on your hands.
  2. Ask children to show you one more than you’re showing or one less.

Game 4: How Old Are You?

  1. Ask a 4-year-old, “How old are you? Are you this age?” Hold up four fingers on one hand.
  2. Then ask, “How old are you? Are you this age?” Hold up two fingers on one hand and two fingers on your other hand. (Children usually answer, “No!”)
  3. Try this with other ages, too!

Things to notice as children play

The critical learning in this game is that numbers can be composed (or made) in different ways. You can make 5 with five fingers on one hand and zero on the other, or with four and one, or with three and two. These different combinations all make five. This helps children recognize that smaller numbers are part of larger numbers (e.g., 3 and 1 are two parts of 4).

ENGAGE FAMILIES IN MATH!

Make copies of the finger game instructions to send home with families. Print and send home math mini-books—find them at NAEYC.org/math-at-home.


Finding More

Counting and drawing more to match the number of objects.

Count and write down how many burgers there are. Count and write down how many cartons of chips there are. Draw more burgers to match the number of cartons of chips.

Count and write down how many bats there are. Count and write down how many balls there are. Draw more balls to match the number of bats.

Count and write down how many drinks there are. Count and write down how many boys there are. Draw more drinks to match the number of boys.


Schau das Video: Mathe von NULL an: Teil 5 - Zahlen und Mengen (Oktober 2021).