Wyliczenie

W matematyce , liczenie jest określenie liczby elementów w zestawie . Zwykle uzyskuje się ją przez liczenie lub obliczanie jego liczności przy użyciu technik kombinatorycznych .

Natychmiastowa percepcja

W obliczu zbioru co najwyżej czterech obiektów, istota ludzka, jeszcze przed opanowaniem języka, i niektóre zwierzęta wydają się mieć natychmiastowe pojęcie o ilości prezentowanej bez wyliczania. Zjawisko to nazywa się subitizing (in) .

W pewnych konfiguracjach, takich jak punkty na ścianach kości, można go rozszerzyć poza cztery . Dzięki temu można łatwiej zlokalizować przedstawione liczby .

Symbolizacja tą samą ilością

Pierwsze oszacowania ilości niekoniecznie były wyrażane za pomocą liczby lub notacji numerycznej . Jednak takie oceny mogłyby być przydatne do śledzenia ewolucji stada, produkcji przemysłowej, zbiorów lub populacji ludzkiej, w szczególności w korpusie wojskowym. W przypadku braku systemu numeracji możliwe jest przedstawienie każdego elementu kolekcji, na przykład za pomocą wycięcia na kawałku drewna lub kości. Innym przykładem jest to widoczne na filmie Ivan Groźny z Sergei Eisenstein , w którym przed walce żołnierze każdy rzut z kolei przedmiotu w torbie.

Rachunkowość

Ocena ilości obiektów przy użyciu określonego terminu wymaga ustalenia listy terminów, których można się nauczyć i przekazać dalej. W ten sposób niektóre ludy Oceanii pokrywają około dwudziestu części ciała w ustalonej kolejności (ale w zależności od lokalizacji ludzi). Każdy język opracował system oznaczania pierwszych liczb całkowitych, prawdopodobnie powiązany z określonym systemem numeracji .

Wyliczenie polega wówczas na jednoczesnym przejściu łańcucha cyfrowego i kolekcji obiektów, tak aby każdy obiekt był brany pod uwagę tylko raz. Zrozumienie tej techniki liczenia dzieli się na pięć zasad:

unikalna zasada adekwatności: każde słowo jest powiązane tylko z jednym i tylko jednym elementem zbioru;
zasada stabilnej kolejności: słowa liczbowe są zawsze recytowane w tej samej kolejności;
podstawowa zasada: aby określić wielkość zbioru, wystarczy podać ostatnie użyte słowo-numer;
zasada abstrakcji: przedmioty mogą mieć różną naturę;
zasada nieistotności kolejności: obiekty można przeglądać w dowolnej kolejności.

Obliczenie

W przypadku dużych ilości lub zbiorów abstrakcyjnych, aw szczególności zbiorów matematycznych, wyliczenie odbywa się za pomocą operacji arytmetycznych lub rozważań kombinatorycznych .

Podstawowe właściwości

Zasada szuflad : jeśli mamy m zbiorów i przechowujemy w nich n obiektów z n> m , to przynajmniej jeden z tych zbiorów będzie zawierał kilka obiektów.
Przykład : w klasie 20 uczniów, jeśli wszyscy urodzili się w tym samym roku, to kilku z nich musiało urodzić się w tym samym miesiącu.
Kardynał z iloczyn kartezjański : jeśli drzewo ma n gałęzi (S) i jest on (a) każdy ma (a) P sub-ramię (y), to drzewa ma N x p sub rozgałęzienia (S).
Przykład elementarnego prawdopodobieństwa : załóżmy, że losujemy kartę z talii 52 kart . Jeśli spróbujemy odgadnąć kolor (trefl, karo, kier lub pik), mamy szansę 1 do 4 na trafienie. Co więcej, jeśli spróbujemy odgadnąć jego wartość (as, król, dama, walet itp. ), Mamy szansę 1 do 13 na poprawne ustawienie. Wreszcie, jeśli spróbujemy odgadnąć jego kolor i wartość, mamy szansę na trafienie równą 52 (4 × 13).

Wyliczenie w zbiorach skończonych

Podstawowe twierdzenia

W tej sekcji, jeśli jest to skończony zbiór , oznaczamy (czytaj „ kardynała z A ”) liczba jej elementów. Na przykład . ${\ mathrm {card}} (A)$ ${\ mathrm {karta}} (\ {e, f, g \}) = 3$

Twierdzenie 1 - Niech będzie częścią skończonego zbioru . Wtedy A jest samo skończone i ≤ . Jeśli dalej , to . $W$ $mi$
${\ mathrm {card}} (A)$ ${\ mathrm {card}} (E)$
${\ mathrm {karta}} (A) = {\ mathrm {karta}} (E)$ $A = E$

Charakterystyka map iniekcyjnych - Niech będzie zbiorem skończonym, zbiorem i mapą w . Mamy : $mi$ $fa$ $fa$ $mi$ $fa$

${\ mathrm {karta}} (f (E))$ ≤ ${\ mathrm {card}} (E)$
$fa$ jest iniekcyjny $\ Leftrightarrow$ ${\ mathrm {karta}} (f (E)) = {\ mathrm {karta}} (E)$

Demonstracja

Aby udowodnić punkt 1, możemy skupić się na zbiorze elementów, które mają obraz wg . Jeśli to oznaczymy , to mapa indukowana przez de in jest bijection. Ponieważ jest podzbiorem , jest skończona i ≤ . Pkt 2 wynika z faktu, że gdy jest injective, wszystkie elementy mają unikalną poprzednik, więc indukowana zastosowanie w to bijection. A więc . I odwrotnie, jeśli , to tak się stanie . $mi$ $fa$ $W$ $fa$ $W$ $f (E)$ $W$ $mi$ ${\ mathrm {karta}} (f (E)) = {\ mathrm {karta}} (A)$ ${\ mathrm {card}} (E)$
$fa$ $f (E)$ $mi$ $f (E)$ ${\ mathrm {karta}} (f (E)) = {\ mathrm {karta}} (E)$ ${\ mathrm {karta}} (f (E)) = {\ mathrm {karta}} (E)$ ${\ mathrm {karta}} (A) = {\ mathrm {karta}} (E)$ $A = E$

Wniosek - Niech będzie iniekcyjną mapą zbioru do zbioru . jeśli jest skończony, to jest skończony i . $fa$ $mi$ $fa$
$f (E)$ $mi$ ${\ mathrm {karta}} (E) = {\ mathrm {karta}} (f (E))$

Konsekwencją tego jest w istocie jedynie zastosowanie charakterystyki zastosowań iniekcyjnych w szczególnym przypadku, gdy jest to zbiór docelowy . $fa$ $f (E)$

Twierdzenie - Niech E i F będą dwoma takimi zbiorami skończonymi . Jeśli jest mapą w mamy: to jest iniekcyjne jest suriektywne jest bijektywne. ${\ mathrm {karta}} (E) = {\ mathrm {karta}} (F)$ $fa$ $mi$ $fa$
$fa$ $\ Leftrightarrow$ $fa$ $\ Leftrightarrow$ $fa$

Nieruchomości

Kardynał związku dwóch rozłącznych zbiorów skończonych - Niech i będą dwoma rozłącznymi zbiorami skończonymi z i . Więc mamy . $mi$ $fa$ ${\ mathrm {karta}} (E) = k$ ${\ mathrm {karta}} (F) = n$
${\ mathrm {karta}} (E \ cup F) = {\ mathrm {karta}} (E) + {\ mathrm {karta}} (F) = n + k$

Demonstracja

Rzeczywiście, niech będzie bijection z in i bijection z in , wtedy możemy skonstruować mapę tego, w czyim ograniczeniu jest i to jest . Podobnie jak bijekcja, jest to zastrzyk, co wynika z następstw charakterystyki . $fa$ $mi$ $[\! [1, k] \!]$ $sol$ $fa$ $[\! [1 + k, n + k] \!]$ $godz$ $E \ miseczka F.$ $[\! [1, n + k] \!]$ $mi$ $fa$ $fa$ $sol$ $godz$ ${\ mathrm {karta}} (h (E \ cup F)) = {\ mathrm {karta}} ([\! [1, n + k] \!]) = n + k$

Przez indukcję uogólniamy tę właściwość na rodzinę rozłącznych zbiorów skończonych dwa na dwa:

Kardynał unii skończonych ustawia dwa do dwóch rozłącznych $nie$ - Niech będzie rodziną skończonych zbiorów od dwóch do dwóch rozłącznych. Więc mamy . $(E_ {i}) _ {{i = 1}} ^ {n}$ $nie$
${\ mathrm {card}} (\ bigcup _ {{i = 1}} ^ {n} E_ {i}) = \ sum _ {{i = 1}} ^ {n} ({\ mathrm {karta}} (E_ {i}))$

Kardynał dopełnienia - Niech będzie zbiorem skończonym, a jego dopełnieniem w . Więc mamy . $mi$ $A \ podzbiór E.$ $\ overline A$ $mi$
${\ mathrm {card}} (A) + {\ mathrm {card (\ overline A)}} = {\ mathrm {card}} (E)$

Demonstracja

Dowód: i są dwoma skończonymi zestawami pustego przecięcia i . Pierwsza właściwość pozwala nam podsumować. $W$ $\ overline A$ $A \ cup \ overline A = E$

Kardynał związku dwóch zbiorów skończonych - Niech i będą dwoma zbiorami skończonymi. Więc mamy . $mi$ $fa$
${\ mathrm {card}} (E \ cup F) = {\ mathrm {card}} (E) + {\ mathrm {card}} (F) - {\ mathrm {card}} (E \ cap F)$

Demonstracja

Dowód: tak jak i uzupełniają się w , poprzednia właściwość ma zastosowanie i mamy + . To samo dotyczy i . Zauważ, że w końcu , i utworzyć partycję . Tożsamość jest wywnioskowana na podstawie trzech poprzednich wyników. $A \ cap B$ $AB$ $W$ ${\ mathrm {karta}} (A \ cap B)$ ${\ mathrm {karta}} (AB) = {\ mathrm {karta}} (A)$ $BA$ $A \ cap B$ $AB$ $A \ cap B$ $BA$ $A \ miseczka B$

Kardynał rozłącznego związku dwóch skończonych zbiorów - Niech i będą dwoma skończonymi zbiorami odpowiednich kardynałów i . Wtedy kardynał jest skończony . $mi$ $fa$ $nie$ $k$
$E \ sqcup F$ ${\ mathrm {karta}} (E \ sqcup F) = {\ mathrm {karta}} (E) + {\ mathrm {karta}} (F) = n + k$

Ten wynik można uogólnić na więcej niż dwa zestawy.

Kardynał rozłącznego związku zbiorów skończonych $nie$ - Niech będzie rodziną zbiorów skończonych. $E_i$
${\ mathrm {card}} (E_ {1} \ sqcup E_ {2} \ sqcup E_ {3} \, \ dots \, \ sqcup E_ {n}) = \ sum _ {{i = 1}} ^ { n} {\ mathrm {karta}} (E_ {i}).$

Kardynał iloczynu kartezjańskiego dwóch skończonych zbiorów - Niech i będą dwoma skończonymi zbiorami odpowiednich kardynałów i . Wtedy kardynał jest skończony . $mi$ $fa$ $nie$ $k$
$E \ razy F$ ${\ mathrm {karta}} (E \ times F) = {\ mathrm {karta}} (E) \ times {\ mathrm {karta}} (F) = nk$

Bardziej ogólnie, dla sekwencji zbiorów skończonych:

Kardynał iloczynu kartezjańskiego ciągu zbiorów skończonych - Niech będzie rodziną zbiorów skończonych. Więc $E_i$
${\ mathrm {card}} (E_ {1} \ times E_ {2} \ times E_ {3} \, \ dots \, \ times E_ {n}) = \ prod _ {{i = 1}} ^ { n} {\ mathrm {karta}} (E_ {i}).$

Kardynał zbioru części zbioru skończonego - Niech będzie zbiorem skończonym kardynała . Ponieważ jest w zgodności jeden do jednego ze zbiorem map w , to jest zbiorem skończonym i mamy . $mi$ $k$
${\ mathcal P} (E)$ $mi$ $\ left \ {0,1 \ right \}$ ${\ mathcal P} (E)$ ${\ mathrm {karta}} ({\ mathcal P} (E)) = 2 ^ {{{{\ mathrm {karta}} (E)}} = 2 ^ {k}$

Kardynał zbioru korespondencji z w $mi$ $fa$ - Niech i być dwóch zbiorów skończonych. Zbiór odpowiedników w , zwykle odnotowywany , jest utożsamiany z tym, że jest skończony lub kardynalny . $mi$ $fa$
$mi$ $fa$ ${\ mathrm {Corr}} (E, F)$ ${\ mathcal P} (E \ razy F)$ $\ {\ mathrm {karta}} ({\ mathrm {Corr}} (E, F)) = 2 ^ {{{\ mathrm {karta}} (E) \ times {\ mathrm {karta}} (F)} } = 2 ^ {{nk}}$

Kardynał zbioru map z w $mi$ $fa$ - Niech i być dwa skończone zestawy odpowiednich kardynałów i . Zbiór odwzorowań in , często odnotowywany , jest kardynalny skończony z konwencją 0 0 = 1, jeśli i oba są puste. $mi$ $fa$ $k$ $nie$
$mi$ $fa$ ${\ mathcal F} (E, F)$ $\ {\ mathrm {karta}} ({\ mathcal F} (E, F)) = {\ mathrm {karta}} (F) ^ {{{\ mathrm {karta}} (E)}} = n ^ {k}$ $mi$ $fa$

Ta właściwość uzasadnia bardziej powszechną notację . $F ^ {E}$

Kardynał zbioru surjections z w $mi$ $fa$ - Niech i być dwa skończone zestawy odpowiednich kardynałów i . Wszystkie surjections w , zwykle zauważyć , ma Kardynała następujące kwoty: . Suma ta wynosi zero, jeśli . $mi$ $fa$ $k$ $nie$
$mi$ $fa$ ${\ mathrm {Surj}} (E, F)$
$\ {\ mathrm {card}} ({\ mathrm {Surj}} (E, F)) = \ sum _ {{i = 0}} ^ {{n}} (- 1) ^ {{i}} { \ frac {n!} {i! (ni)!}} (ni) ^ {{k}}$
${\ mathrm {karta}} (E) <{\ mathrm {karta}} (F)$

Zastosowania iniekcyjne, które odgrywają ważną rolę w kombinatoryce, są omówione bardziej szczegółowo w kolejnych akapitach.

Uwagi i odniesienia

Niektóre obserwacje są powiązane w pierwszym rozdziale Universal History of Figures autorstwa Georgesa Ifraha, strona 22, Éditions Robert Laffont, Paryż 1981.
(w) Usha Goswami , Cognitive Development: The Learning Brain , Nowy Jork, Psychology Press,2008.
Georges Ifrah, Universal History of Figures , strona 46, Editions Robert Laffont, Paryż 1981.
Zgodnie z pracą R. Gellmana i CR Gallistela, cytowaną w artykule Rogera Bastiena „Nabywanie liczb u dzieci” .

Zobacz też