Artikel

5: Set dan Pengiraan - Matematik


Objektif Pembelajaran

Dalam bab ini, anda akan belajar untuk:

  • Gunakan teori set dan gambarajah Venn untuk menyelesaikan masalah pengiraan.
  • Gunakan Paksi Pendaraban untuk menyelesaikan masalah mengira.
  • Gunakan Permutasi untuk menyelesaikan masalah pengiraan.
  • Gunakan Gabungan untuk menyelesaikan masalah mengira.
  • Gunakan Teorem Binomial untuk mengembangkan ((x + y) ^ n )

Tally markah

Tally markah, juga dipanggil tanda hash, adalah sistem angka yang tidak sekata. Mereka adalah bentuk angka yang digunakan untuk mengira. Mereka sangat berguna dalam menghitung atau menghitung hasil yang sedang berjalan, seperti skor dalam permainan atau sukan, kerana tidak ada hasil perantaraan yang harus dihapus atau dibuang.

Namun, kerana panjangnya jumlah yang besar, penghitung biasanya tidak digunakan untuk teks statik. Tongkat berlekuk, yang dikenali sebagai tongkat tally, juga digunakan secara historis untuk tujuan ini.


5: Set dan Pengiraan - Matematik


Jabatan Matematik Universiti Negeri Illinois

MAT 305: Topik Gabungan untuk Guru K-8

Teknik Mengira Asas

Di sini kami memilih satu item dari koleksi item. Kerana tidak ada barang yang sama di antara dua set yang disebut Blaise sebagai Hijau dan Kentang, kami dapat mengumpulkan item tersebut menjadi satu set besar. Kami menggunakan tambahan, di sini 4 + 5, untuk menentukan jumlah item yang boleh dipilih.

Ini menggambarkan prinsip pengiraan yang penting.

Sekiranya pilihan dari Kumpulan I dapat dibuat dengan cara n dan pilihan dari Kumpulan II dapat dibuat dengan cara m, maka jumlah pilihan yang mungkin dari Kumpulan I atau Kumpulan II adalah n + m.

Keadaan yang Perlu: Tidak ada unsur dalam Kumpulan I yang sama dengan unsur dalam Kumpulan II.

Ini dapat digeneralisasikan menjadi satu pilihan dari lebih dari dua kumpulan, sekali lagi dengan syarat bahawa semua kumpulan, atau kumpulan, tidak terpisah, iaitu, tidak mempunyai persamaan.

Contoh untuk menggambarkan Prinsip Penambahan:

Berikut adalah tiga set huruf, panggil mereka set I, II, dan III:

Berapa banyak kaedah yang ada untuk memilih satu huruf di antara set I, II, atau III? Perhatikan bahawa ketiga-tiga set itu terpisah, atau saling eksklusif: tidak ada unsur yang sama di antara ketiga set tersebut.

Berikut adalah dua set bilangan bulat positif:

Berapa banyak kaedah untuk memilih satu bilangan bulat dari antara set A atau B? Perhatikan bahawa kedua-dua set tidak terpisah. Pengubahsuaian apa yang dapat kita buat pada Prinsip Penambahan untuk menampung kes ini? Cuba tulis pengubahsuaian itu.

Prinsip Pendaraban

Kita boleh menghitung makanan yang mungkin, lebih baik dengan cara yang teratur untuk memastikan bahawa kita telah mempertimbangkan semua kemungkinan. Berikut adalah lakaran satu penghitungan seperti itu, di mana , , , dan mewakili item yang akan dipilih masing-masing dari menu sup, daging, sayur hijau, dan pencuci mulut.

Perhatikan proses penghitungan yang digunakan dalam jadual. Bagaimana anda boleh menerangkannya dengan kata-kata?

Bagaimana lagi kita dapat menyelesaikan kiraan tanpa mengenal pasti semua kemungkinan pilihan? Peta atau pokok untuk menggambarkan proses penghitungan menyediakan jambatan untuk kaedah sedemikian.

Kami mempunyai dua cara untuk memilih item sup, dua cara untuk memilih item daging, empat sayur hijau untuk dipilih, dan empat pencuci mulut untuk dipilih. Pemadanan satu sup dengan setiap daging, kemudian masing-masing pasangan dengan masing-masing dari empat kemungkinan sayur hijau, dan masing-masing tiga kali ganda dengan masing-masing empat kemungkinan pencuci mulut membawa kepada penggunaan penggandaan sebagai cara cepat untuk mengira semua kemungkinan makanan yang kita boleh berkumpul di Blaise's.

Ini menunjukkan bahawa kita menggunakan prinsip penghitungan lain untuk menerangkan teknik ini.

Prinsip Pendaraban

Sekiranya tugas melibatkan dua langkah dan langkah pertama dapat diselesaikan dengan cara n dan langkah kedua dengan cara m, maka ada cara n * m untuk menyelesaikan tugas.

Keadaan yang Diperlukan: Cara setiap langkah dapat diselesaikan saling bergantung antara satu sama lain.

Ini dapat digeneralisasikan untuk menyelesaikan tugas dalam lebih dari dua langkah, asalkan syaratnya berlaku.

Contoh untuk menggambarkan Prinsip Pendaraban:

Ingat tiga set I, II, dan III kami: , , dan . Tentukan jumlah set tiga huruf yang dapat dibuat sedemikian rupa sehingga satu huruf berasal dari set I, satu huruf dari set II, dan satu huruf dari set III. Perhatikan bahawa pilihan kami di setiap set adalah bebas daripada pilihan kami di set yang lain. Sekiranya perlu, kita dapat menghitung kemungkinan set tiga huruf, atau tiga elemen.

Permutasi
Dengan berapa cara surat-surat dalam satu set, dari antara I, II, dan III dapat disusun? Dalam set I, kami mempunyai kemungkinan berikut:

Kami menggunakan Prinsip Pendaraban untuk menerangkan pemilihan kami. Kami mempunyai tiga huruf untuk dipilih untuk mengisi posisi pertama, dua huruf lagi untuk mengisi posisi kedua, dan hanya tinggal satu huruf untuk posisi terakhir: 3x2x1 = 6 pesanan yang berbeza mungkin. Begitu juga, untuk set II terdapat 120 cara yang berbeza untuk memerintahkan lima huruf dan terdapat 24 cara yang berbeza untuk memesan huruf dalam set III.

Perbincangan di atas menunjukkan contoh strategi pengiraan asas yang lain.

Susunan unsur elemen yang mana susunan elemen mesti diambil kira.

Kami juga menunjukkan ketersediaan notasi faktorial untuk merepresentasikan pendaraban spesifik yang baru kami jalankan: 3x2x1 = 3 !, 5x4x3x2x1 = 5 !, dan seterusnya. Jadi n (n-1) (n-2). (2) (1) = n !.

Perwakilan padat untuk pendaraban bilangan bulat berturut-turut. Kami menggunakan n! untuk menyerahkan semula produk n (n-1) (n-2). (2) (1), di mana n adalah bilangan bulat positif.

Contoh untuk menggambarkan penggunaan Permutasi:

Hampir setiap pagi atau petang mengenai berita yang saya dengar mengenai State of Illinois DCFS, Jabatan Perkhidmatan Kanak-kanak dan Keluarga. Saya menjadi keliru, kerana jabatan matematik kita mempunyai jawatankuasa yang disebut Jawatankuasa Status Fakulti Jabatan, atau DFSC. Bolehkah anda melihat mengapa saya keliru? Berapa banyak susunan yang diperintahkan 4 huruf, atau permutasi, ada untuk set huruf ?

Memikirkan empat kedudukan yang harus diisi, __ __ __ __, kita mempunyai 4 huruf untuk dipilih untuk kedudukan pertama, 3 untuk yang berikutnya, 2 huruf untuk posisi berikutnya, dan 1 pilihan untuk posisi terakhir. Dengan menggunakan prinsip pendaraban, terdapat 4x3x2x1 = 24 susunan pesanan 4 huruf yang berbeza untuk set huruf .

Kami dapat memperluas aplikasi ini untuk mempertimbangkan susunan teratur hanya beberapa elemen dalam satu set. Contohnya, kembali ke menu minuman Blaise's Bistro. Sekiranya Blaise akan menghantar hanya empat kemungkinan soda chocies, berapa banyak susunan tersusun dari empat soda yang ada?

Memikirkan empat kedudukan yang perlu diisi, __ __ __ __, kita mempunyai 6 soda untuk dipilih untuk kedudukan pertama, 5 untuk yang berikutnya, 4 soda untuk yang berikutnya, dan 3 soda untuk kedudukan terakhir. Dengan menggunakan prinsip pendaraban, terdapat 6x5x4x3 = 360 cara yang berbeza untuk memilih dan memesan empat dari enam soda pada menu.

Secara umum, kami menggunakan notasi P (n, r) untuk mewakili jumlah cara untuk mengatur objek r dari sekumpulan objek n. Dalam masalah pertama di atas, kami menentukan bahawa P (4,4) = 24, dan pada yang kedua kami mengira P (6,4) = 360. Nilai umum P (n, r) adalah n (n-1) (n-2). (& # 91n- (r-1) & # 93 atau P (n, r) = n (n-1) (n-2). (N-r + 1). Perhatikan bahawa n boleh menjadi bilangan bulat bukan negatif. Adakah terdapat sekatan pada nilai r?

Terdapat langkah aritmetik yang dapat kita terapkan pada pola umum untuk P (n, r) untuk membantu melancarkan pengiraan permutasi. Pada baris kedua di bawah, kita telah didarabkan dengan, yang hanya nilai 1 kerana pengangka dan penyebutnya sama. Pada baris keempat di bawah ini kita melihat bagaimana ungkapan dapat dipermudahkan dengan menggunakan notasi faktorial.

Oleh itu, kita mempunyai P (6,2) = 6! / 4! Dan P (40,8) = 40! / 32 !.

Bagaimana dengan P (4,4)? Hasil di atas menunjukkan P (4,4) = 4! / 0 !. Kita sudah tahu bahawa P (4,4) = 4x3x2x1 = 4 !, Oleh itu, kita mempunyai 4! = 4! / 0 !. Agar ini benar, mestilah 0! = 1. Seperti peliknya, kita memerlukan 0! = 1 untuk mengekalkan konsistensi dalam pengiraan yang ingin kita laksanakan.

Gabungan
Apakah perbezaan antara bertanya dua soalan ini?

(i) Dalam berapa banyak cara tangan poker 5 kad dapat ditangani?

(ii) Berapa banyak tangan poker 5 kad yang berbeza?

Soalan pertama mempertimbangkan urutan atau susunan kad semasa ia dibagikan. Dalam soalan kedua, hasil akhir apabila dibagikan 2H, 4D, JC, 3S, 10D dalam urutan itu sama seperti yang dibahaskan 4D, 3S, JC, 10D, 2H dalam urutan itu. Dalam setiap kes, tangan poker 5 kad yang sama ada. Soalan-soalan membantu menggambarkan perbezaan antara permutasi dan kombinasi.

Kumpulan elemen yang susunannya tidak menjadi masalah.

Kami mendapati P (52,5) sebagai penyelesaian untuk masalah pertama. Maksudnya, kami menyusun 5 objek yang dipilih dari 52 kad. Untuk soalan kedua, terdapat banyak susunan yang menghasilkan tangan 5 kad yang sama. Kita perlu mengambil kira perkara ini. Mari kita fikirkan masalah yang lebih mudah.

Berapa banyak susunan yang diperintahkan untuk huruf set itu ?

Dengan menggunakan permutasi, kita mempunyai P (5,5) = 5! = 120 cara menyusun lima huruf.

Berapa banyak susunan yang dipesan ada 3 item dari set 5 elemen?

Kami mempunyai P (5,3) = 543 = 5! / 2! = 60 susunan. Contohnya, untuk tiga huruf kami mempunyai pengaturan berikut: ABC, ACB, BAC, BCA, CAB, CBA. Ini mewakili 6 dari 60 susunan, namun masing-masing melibatkan pemilihan tiga huruf yang sama. Begitu juga untuk ketiga-tiga huruf itu : Kami mempunyai ACE, AEC, CAE, CEA, EAC, ECA.

Nampaknya bagi setiap subset 3 huruf dari terdapat 6 susunan tiga huruf yang sama. Ini adalah pemerhatian yang berguna dalam meneroka soalan berikut:

Salah satu cara adalah dengan menyenaraikan subset 3 elemen unik : ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Terdapat 10 subset 3 elemen tersebut.

Cara lain untuk mempertimbangkan kiraan adalah dengan menggunakan fakta bahawa:

Secara umum, kami mempunyai cara untuk menentukan jumlah kombinasi item n yang dipilih r pada satu waktu, di mana urutan pemilihan atau susunan item r tidak dipertimbangkan:

Hubungan Antara Permutasi dan Gabungan

Sekiranya unsur r dikumpulkan atau disusun dari sekumpulan unsur n, maka jumlah kombinasi unsur n diambil r pada satu masa, C (n, r), berkaitan dengan jumlah permutasi unsur n yang diambil r pada masa, P (n, r), mengikut persamaan

Permutasi Pekeliling

Sekiranya kita mempertimbangkan kes itu secara linear,

kita mempunyai P (5,5) = 5! susunan. Sekarang panjangkan ini ke bulatan:

Perhatikan bahawa dalam setiap kes ini, orang yang sama duduk bersebelahan. Walaupun terdapat perubahan - putaran - mengenai meja, lima kanak-kanak itu masih dalam kedudukan yang sama antara satu sama lain. Berapa banyak kaedah untuk memutarkan hubungan linear ABCDE yang unik? Terdapat lima cara seperti itu, semuanya digambarkan dalam lukisan.

Oleh itu, kita mempunyai 5! susunan linear kanak-kanak yang unik, tetapi kita dapat mengelompokkannya sehingga setiap kumpulan mempunyai 5 susunan yang menunjukkan anak-anak berada dalam kedudukan yang sama berbanding satu sama lain. Oleh itu, kita mempunyai 5! / 5 = 4! permutasi bulat kelima-lima anak.

Bagaimana jika kita mengatur dalam bulatan subset elemen r dari set unsur-n? Anggaplah kami mengatur 3 dari 5 kanak-kanak. Dalam kes linear, terdapat susunan P (5,3) = 60, tetapi kita dapat mengelompokkannya sehingga setiap kumpulan mempunyai 3 susunan yang menunjukkan anak-anak berada dalam kedudukan yang sama berbanding satu sama lain. Oleh itu, kami mempunyai permutasi bulat P (5,3) / 3 = 5! / (2! * 3) ke dalam subset 3-anak.

Permutasi bulat adalah susunan elemen yang melingkar yang mana susunan elemen mesti diambil kira.


Kandungan

Konsep penggabungan asas dan hasil penghitungan muncul di seluruh dunia kuno. Pada abad ke-6 SM, doktor India kuno Sushruta menegaskan di Sushruta Samhita bahawa 63 kombinasi dapat dibuat dari 6 rasa yang berbeza, diambil satu per satu, dua pada satu masa, dan lain-lain, sehingga menghitung semua kemungkinan 2 6 - 1. Sejarawan Yunani Plutarch membincangkan pertikaian antara Chrysippus (abad ke-3 SM) dan Hipparchus (abad ke-2 SM) mengenai masalah pembilang yang agak rumit, yang kemudiannya ditunjukkan berkaitan dengan angka Schröder – Hipparchus. [7] [8] [9] Sebelumnya, di Ostomachion, Archimedes (abad ke-3 SM) mungkin telah mempertimbangkan jumlah konfigurasi teka-teki berjubin, [10] sementara minat kombinatori mungkin ada dalam karya-karya yang hilang oleh Apollonius. [11] [12]

Pada Zaman Pertengahan, kombinatorik terus dipelajari, sebahagian besarnya di luar tamadun Eropah. Ahli matematik India Mahāvīra (sekitar 850) menyediakan formula untuk bilangan permutasi dan kombinasi, [13] [14] dan formula ini mungkin sudah biasa dilakukan oleh ahli matematik India seawal abad ke-6 Masehi. [15] Ahli falsafah dan ahli astronomi Rabbi Abraham ibn Ezra (sekitar 1140) menetapkan simetri pekali binomial, sementara formula tertutup diperoleh kemudian oleh talmudis dan ahli matematik Levi ben Gerson (lebih dikenali sebagai Gersonides), pada tahun 1321. [16 Segitiga aritmetik - rajah grafik yang menunjukkan hubungan antara pekali binomial - disampaikan oleh ahli matematik dalam risalah yang berasal dari abad ke-10, dan akhirnya akan dikenali sebagai segitiga Pascal. Kemudian, di Zaman Pertengahan England, campanologi memberikan contoh apa yang sekarang dikenali sebagai kitaran Hamilton dalam grafik Cayley tertentu mengenai permutasi. [17] [18]

Semasa Renaissance, bersama dengan matematik dan sains yang lain, kombinatorik menikmati kelahiran semula. Karya Pascal, Newton, Jacob Bernoulli dan Euler menjadi asas dalam bidang yang baru muncul. Pada zaman moden ini, karya J.J. Sylvester (akhir abad ke-19) dan Percy MacMahon (awal abad ke-20) membantu meletakkan asas bagi penggabungan dan penghitungan algebra. Teori grafik juga menikmati ledakan minat pada masa yang sama, terutama berkaitan dengan masalah empat warna.

Pada separuh kedua abad ke-20, kombinatorik menikmati pertumbuhan pesat, yang membawa kepada penubuhan puluhan jurnal dan persidangan baru dalam subjek ini. [19] Sebahagiannya, pertumbuhan didorong oleh sambungan dan aplikasi baru ke bidang lain, mulai dari aljabar hingga kebarangkalian, dari analisis fungsional hingga teori nombor, dan lain-lain. Sambungan ini melepaskan batas antara kombinatorik dan bahagian matematik dan sains komputer teori, tetapi pada masa yang sama menyebabkan sebahagian pecahan ladang.

Penggabungan numerik Edit

Kombinatorik berangka adalah kawasan kombinatorik yang paling klasik dan menumpukan perhatian untuk mengira bilangan objek kombinatori tertentu. Walaupun menghitung jumlah elemen dalam satu set adalah masalah matematik yang agak luas, banyak masalah yang timbul dalam aplikasi mempunyai keterangan gabungan yang agak sederhana. Nombor Fibonacci adalah contoh asas masalah dalam kombinatorik enumeratif. Cara dua belas kali lipat menyediakan kerangka yang bersatu untuk menghitung permutasi, kombinasi dan partisi.

Penggabungjalinan analitik

Combinatorics analitik menyangkut penghitungan struktur kombinatorial menggunakan alat dari analisis kompleks dan teori kebarangkalian. Berbeza dengan kombinatorik berangka, yang menggunakan formula kombinatorial eksplisit dan menghasilkan fungsi untuk menerangkan hasilnya, kombinatorik analitik bertujuan untuk mendapatkan formula asimtotik.

Teori partition Edit

Teori partition mengkaji pelbagai masalah penghitungan dan asimtotik yang berkaitan dengan partisi integer, dan berkait rapat dengan siri-q, fungsi khas dan polinomial ortogonal. Pada asalnya merupakan bahagian teori dan analisis nombor, ia kini dianggap sebagai bahagian gabungan atau bidang bebas. Ia menggabungkan pendekatan bijektif dan pelbagai alat dalam analisis nombor analisis dan teori dan mempunyai hubungan dengan mekanik statistik.

Teori grafik Edit

Grafik adalah objek asas dalam kombinatorik. Pertimbangan teori grafik berkisar dari penghitungan (mis., Jumlah graf di n bucu dengan k tepi) ke struktur yang ada (mis., kitaran Hamiltonian) ke perwakilan algebra (mis., diberi grafik G dan dua nombor x dan y, adakah polinomial Tutte TG(x,y) mempunyai tafsiran gabungan?). Walaupun terdapat hubungan yang sangat kuat antara teori grafik dan kombinatorik, mereka kadang-kadang dianggap sebagai subjek yang terpisah. [20] Walaupun kaedah kombinatori berlaku untuk banyak masalah teori grafik, kedua disiplin tersebut umumnya digunakan untuk mencari jalan keluar untuk berbagai jenis masalah.

Teori reka bentuk Edit

Teori reka bentuk adalah kajian reka bentuk gabungan, yang merupakan kumpulan subset dengan sifat persimpangan tertentu. Reka bentuk blok adalah reka bentuk gabungan dari jenis khas. Kawasan ini adalah salah satu bahagian kombinatorik tertua, seperti masalah murid sekolah Kirkman yang dicadangkan pada tahun 1850. Penyelesaian masalah ini adalah kes khas sistem Steiner, yang mana sistem memainkan peranan penting dalam klasifikasi kumpulan sederhana terhingga. Kawasan ini mempunyai hubungan lebih jauh dengan teori pengekodan dan penggabungan geometri.

Edit geometri terhingga

Geometri terhingga adalah kajian sistem geometri yang hanya mempunyai bilangan titik terhingga. Struktur yang serupa dengan yang terdapat dalam geometri berterusan (satah Euclidean, ruang unjuran sebenar, dll.) Tetapi ditakrifkan secara kombinatori adalah item utama yang dikaji. Kawasan ini memberikan banyak sumber contoh teori reka bentuk. Ia tidak boleh dikelirukan dengan geometri diskrit (geometri gabungan).

Teori pesanan Edit

Teori pesanan adalah kajian set yang disusun separa, baik yang terhingga dan tidak terbatas. Pelbagai contoh pesanan separa muncul dalam algebra, geometri, teori nombor dan keseluruhan teori kombinasi dan grafik. Kelas yang terkenal dan contoh pesanan separa termasuk kisi dan algebra Boolean.

Teori Matroid Edit

Teori Matroid mengaburkan sebahagian daripada geometri. Ia mengkaji sifat set (biasanya, set terhingga) vektor dalam ruang vektor yang tidak bergantung pada pekali tertentu dalam hubungan ketergantungan linear. Bukan hanya struktur tetapi juga sifat numerik tergolong dalam teori matroid. Teori Matroid diperkenalkan oleh Hassler Whitney dan dikaji sebagai bahagian teori pesanan. Ia kini menjadi bidang kajian yang bebas dengan sejumlah hubungan dengan bahagian-bahagian kombinatorik yang lain.

Penggabungan ekstrem

Combinatorics ekstremal mengkaji soalan ekstrem pada sistem set. Jenis soalan yang dikemukakan dalam kes ini adalah mengenai graf terbesar yang memenuhi sifat tertentu. Contohnya, grafik bebas segitiga terbesar dihidupkan 2n bucu adalah graf dua bahagian yang lengkap Kn, n. Selalunya terlalu sukar untuk mencari jawapan yang melampau f(n) tepat dan seseorang hanya dapat memberikan anggaran asimtotik.

Teori Ramsey adalah bahagian lain dari penggabungan ekstrem. Ia menyatakan bahawa konfigurasi yang cukup besar akan mengandungi beberapa jenis pesanan. Ini adalah generalisasi lanjutan dari prinsip merpati.

Penggabungan probabilistik

Dalam kombinatorik probabilistik, soalan adalah dari jenis berikut: apakah kebarangkalian sifat tertentu untuk objek diskrit rawak, seperti grafik rawak? Contohnya, berapakah bilangan segitiga rata-rata dalam graf rawak? Kaedah probabilistik juga digunakan untuk menentukan keberadaan objek kombinatori dengan sifat tertentu yang ditentukan (yang contohnya sukar dijumpai), hanya dengan memerhatikan bahawa kebarangkalian memilih objek secara rawak dengan sifat tersebut lebih besar daripada 0. Pendekatan ini ( sering disebut sebagai yang kaedah probabilistik) terbukti sangat berkesan dalam aplikasi untuk penggabungan ekstrem dan teori grafik. Kawasan yang berkait rapat adalah kajian mengenai rantai Markov yang terbatas, terutama pada objek kombinatorial. Di sini sekali lagi alat probabilistik digunakan untuk menganggarkan masa pencampuran.

Seringkali dikaitkan dengan Paul Erdős, yang melakukan kerja perintis mengenai perkara ini, kombinatorik probabilistik secara tradisional dipandang sebagai satu set alat untuk mengkaji masalah di bahagian lain dari kombinatorik. Namun, dengan pertumbuhan aplikasi untuk menganalisis algoritma dalam sains komputer, serta kebarangkalian klasik, teori nombor aditif, dan teori nombor probabilistik, wilayah ini baru-baru ini berkembang menjadi bidang gabungan yang bebas.

Penggabungan algebra

Algebraic combinatorics adalah bidang matematik yang menggunakan kaedah algebra abstrak, terutamanya teori kumpulan dan teori representasi, dalam pelbagai konteks kombinasi dan, sebaliknya, menerapkan teknik kombinatori untuk masalah dalam aljabar. Penggabungjalinan algebra terus mengembangkan skopnya, baik dalam topik dan teknik, dan dapat dilihat sebagai bidang matematik di mana interaksi kaedah kombinatorial dan algebra sangat kuat dan signifikan.

Gabungan pada kata-kata Edit

Kombinasi kata berkaitan dengan bahasa formal. Ia timbul secara bebas dalam beberapa cabang matematik, termasuk teori nombor, teori kumpulan dan kebarangkalian. Ini mempunyai aplikasi untuk kombinatorik enumeratif, analisis fraktal, sains komputer teoritis, teori automata, dan linguistik. Walaupun banyak aplikasi baru, hierarki klasik Chomsky – Schützenberger kelas tatabahasa formal mungkin merupakan hasil yang paling terkenal di lapangan.

Gabungan geometri Edit

Combinatorics geometri berkaitan dengan geometri cembung dan diskrit, khususnya kombinatorik polyhedral. Ini bertanya, sebagai contoh, berapa banyak wajah setiap dimensi yang dapat dimiliki oleh polytop cembung. Sifat metrik polytop juga memainkan peranan penting, mis. teorema Cauchy mengenai ketegaran politop cembung. Polytop khas juga dipertimbangkan, seperti polutop permutohedra, associahedra dan Birkhoff. Geometri gabungan adalah nama kuno untuk geometri diskrit.

Penggabungan topologi Edit

Analog gabungan konsep dan kaedah dalam topologi digunakan untuk mengkaji pewarnaan grafik, pembahagian adil, pembahagian, set yang disusun separa, pohon keputusan, masalah kalung dan teori Morse diskrit. Ia tidak boleh dikelirukan dengan topologi gabungan yang merupakan nama yang lebih tua untuk topologi algebra.

Penggabungan aritmetik

Kombinatorik aritmetik timbul daripada interaksi antara teori nombor, kombinatorik, teori ergodik, dan analisis harmonik. Ini mengenai anggaran gabungan yang berkaitan dengan operasi aritmetik (penambahan, pengurangan, pendaraban, dan pembahagian). Teori nombor tambah (kadang kala disebut juga kombinatorik aditif) merujuk kepada kes khas apabila hanya operasi penambahan dan pengurangan yang terlibat. Salah satu teknik penting dalam kombinatorik aritmetik adalah teori ergodik sistem dinamik.

Penggabungan infinitari

Infinitary combinatorics, atau combinatorial set theory, adalah perluasan idea dalam combinatorics kepada set tak terhingga. Ia adalah bahagian teori set, bidang logik matematik, tetapi menggunakan alat dan idea dari kedua teori set dan gabungan ekstrem.

Gian-Carlo Rota menggunakan nama tersebut penggabungan berterusan [21] untuk menggambarkan kebarangkalian geometri, kerana terdapat banyak analogi antara mengira dan mengukur.

Pengoptimuman Gabungan Edit

Pengoptimuman gabungan adalah kajian pengoptimuman pada objek diskrit dan gabungan. Ia bermula sebagai bahagian teori kombinatorik dan grafik, tetapi kini dipandang sebagai cabang ilmu matematik dan sains komputer, yang berkaitan dengan penyelidikan operasi, teori algoritma dan teori kerumitan komputasi.

Teori pengekodan Edit

Teori pengekodan dimulakan sebagai sebahagian daripada teori reka bentuk dengan pembinaan awal kod pembetulan kesalahan. Idea utama subjek adalah merancang kaedah penghantaran data yang cekap dan boleh dipercayai. Sekarang bidang pengajian besar, sebahagian daripada teori maklumat.

Edit geometri diskrit dan komputasi

Geometri diskrit (juga disebut geometri kombinatorial) juga dimulakan sebagai bahagian kombinatorik, dengan hasil awal pada politop cembung dan angka ciuman. Dengan munculnya aplikasi geometri diskrit untuk geometri komputasi, kedua bidang ini bergabung dan menjadi bidang pengajian yang terpisah. Masih terdapat banyak hubungan dengan kombinatorik geometri dan topologi, yang dapat dilihat sebagai hasil daripada geometri diskrit awal.

Gabungan dan sistem dinamik Edit

Aspek gabungan sistem dinamik adalah satu lagi bidang yang baru muncul. Di sini sistem dinamik dapat didefinisikan pada objek gabungan. Lihat contoh sistem dinamik grafik.

Gabungan dan fizik Edit

Terdapat peningkatan interaksi antara kombinatorik dan fizik, terutamanya fizik statistik. Contohnya termasuk penyelesaian tepat model Ising, dan hubungan antara model Potts di satu pihak, dan polinomial kromatik dan Tutte di sisi lain.


5: Set dan Pengiraan - Matematik

Tetapi menambahkan berulang 1 adalah bentuk penambahan yang sangat primitif yang juga tidak begitu berguna. Semasa menaip petikan, saya juga kehilangan kiraan beberapa kali. Jauh lebih mudah untuk mengira objek dengan mengelompokkannya ke dalam kumpulan kecil dan kemudian menambahkan jumlah yang berkaitan dengan setiap kumpulan. Sekiranya semua kumpulan mempunyai jumlah objek yang sama, kami akan mengetahui kaitan operasi aritmetik lain - pendaraban - untuk mengira. Contohnya, notasi matematik untuk "2 dan 2 dan 2" adalah "3 kali 2" atau, secara simbolik, 3 & middot2. 3 & middot2 demikian sama dengan "1 dan 1 dan 1 dan 1 dan 1 dan 1" yang dilambangkan sebagai 6: 3 & middot2 = 6. Kadang-kadang, kita tidak dapat memisahkan objek secara merata ke dalam kumpulan yang lebih kecil. Sebagai contoh, membahagi 7 menjadi kumpulan 3 objek, kita mendapat 2 kumpulan dan 1 objek yang tersisa. Dalam kes ini, penambahan dan pendaraban bergabung dalam notasi matematik: 2 & middot3 + 1 = 7. Ini adalah bagaimana pengiraan membawa kepada idea pembahagian dan bahkan dari pembahagian dengan baki. 3 & middot2 = 6 bermaksud bukan sahaja tiga kumpulan 2 elemen masing-masing merangkumi 6 elemen, tetapi juga sekumpulan 6 elemen dapat dibahagikan menjadi 3 kumpulan yang terdiri daripada 2 elemen masing-masing. Bahagian kedua menjadi frasa belaka dari bahagian pertama penyataan sebelumnya. Apabila kita cuba membahagikan 7 kepada dua kumpulan kita mendapat dua kumpulan tiga objek dan 1 elemen tambahan. 7 tidak dibahagi sama rata dengan 2.

Berikut adalah applet yang membantu meneroka konsep ini. Lihat bahawa memang mustahil untuk menghitung dan mengelompokkan objek dengan pelbagai cara yang selalu membawa kepada hasil yang sama. Perhatikan notasi matematik yang digunakan untuk menerangkan pelbagai pengelompokan objek. Kira objek dengan mengklik pada gilirannya.

Sekiranya anda membaca ini, penyemak imbas anda tidak ditetapkan untuk menjalankan applet Java. Cuba IE11 atau Safari dan nyatakan laman web https://www.cut-the-knot.org sebagai dipercayai dalam penyediaan Java.

Applet seterusnya sedikit lebih abstrak. Menghitung adalah cara yang berguna tetapi kita sudah tahu bahawa penambahan dan pendaraban dapat mempercepatnya, sering kali. Dalam applet ini, anda boleh mengklik setiap tiga nombor tersebut. Mengklik sedikit di sebelah kanan garis pusatnya akan menambah bilangannya satu persatu. Mengklik sedikit di sebelah kiri nombor mengurangkan nombor dengan 1. Simbol matematik ">" bermaksud lebih daripada, "

Sekiranya anda membaca ini, penyemak imbas anda tidak ditetapkan untuk menjalankan applet Java. Cuba IE11 atau Safari dan nyatakan laman web https://www.cut-the-knot.org sebagai dipercayai dalam penyediaan Java.

Akhirnya, berikut adalah applet yang merupakan variasi pada masalah dengan dua kumpulan. Katakanlah, anda mempunyai epal dan pic. Bersama-sama ada 12 buah. Terdapat dua lagi epal daripada buah persik. Berapakah bilangan buah yang ada? Perhatikan bahawa masalahnya tidak selalu ada jalan penyelesaian. Cuba fikirkan bila berlaku.

Sekiranya anda membaca ini, penyemak imbas anda tidak ditetapkan untuk menjalankan applet Java. Cuba IE11 atau Safari dan nyatakan laman web https://www.cut-the-knot.org sebagai dipercayai dalam penyediaan Java.

W. W. McWorter cukup baik untuk berkongsi pengalamannya mengajar mengira kepada pelajar muda.

Dalam bukunya Mengesan Semut Automatik (Springer, 1998), David Gale menceritakan kisah berikut:

Suatu ketika dahulu ada seorang gadis kecil bernama Clara yang baru berusia tiga tahun dan baru belajar bagaimana mengira. Dia dapat mengetahui berapa banyak kerusi yang ada di ruang tamu dan berapa langkah dari beranda depan. Suatu hari ayahnya memutuskan untuk mengujinya. "Lihat," katanya, "Aku telah membawakan keempat-empat lolipop ini kepadamu," tetapi dia hanya memberikannya tiga. Clara mengambil lolipop dan menghitung dengan hormat, "Satu, dua, empat." Kemudian dia melihat sedikit bingung dan bertanya, "Di mana yang ketiga?"


Kira dan padan

Hitung dua set objek dan lukis lebih banyak untuk menjadikannya sama.

Kelawar tidak banyak digunakan jika anda tidak mendapat bola. Ada banyak peluang untuk mencocokkan set objek di sekitar rumah, tetapi juga berguna untuk duduk dan bersantai di atas kertas. Berikut adalah sekumpulan empat halaman yang bagus yang meminta kanak-kanak mengira dua set kelawar dan bola dan kemudian melukis lebih banyak untuk menjadikannya sama.

Adakah stokin anda hilang semasa mencuci? Ada banyak peluang untuk mencocokkan set objek di sekitar rumah, tetapi juga berguna untuk duduk dan bersantai di atas kertas. Berikut adalah sekumpulan empat halaman yang bagus yang meminta kanak-kanak mengira dua set kasut dan stoking dan kemudian melukis lebih banyak untuk menjadikannya sama.

Membilang dan memadankan sebilangan kecil balang madu dan sudu.

Membilang dan memadankan sebilangan kecil labah-labah dan jaring.

Adakah anda mendapat bilangan sudu yang tepat untuk semua ais krim yang lazat itu? Ada banyak peluang untuk mencocokkan set objek di sekitar rumah, tetapi juga berguna untuk duduk dan bersantai di atas kertas. Berikut adalah sekumpulan empat halaman yang indah yang meminta kanak-kanak mengira dua set dan kemudian melukis lebih banyak untuk menjadikannya sama.


Kandungan

Bahagian berikut menjalankan konstruksi tertentu dalam dua teori ZFC dan NFU dan membandingkan pelaksanaan struktur matematik tertentu yang dihasilkan (seperti nombor semula jadi).

Teori matematik membuktikan teorema (dan tidak ada yang lain). Oleh itu mengatakan bahawa teori membenarkan pembinaan objek tertentu bermaksud bahawa teori adalah bahawa teori itu wujud. Ini adalah pernyataan mengenai definisi bentuk "the x sedemikian yang ϕ < displaystyle phi> ada", di mana ϕ < displaystyle phi> adalah formula bahasa kita: teori membuktikan adanya "x x seperti itu" bahawa ϕ < displaystyle phi> "sekiranya berlaku teorema bahawa" ada satu dan hanya satu x sehingga ϕ < displaystyle phi> ". (Lihat teori penerangan Bertrand Russell.) Secara longgar, teori "mendefinisikan" atau "membina" objek ini dalam kes ini. Sekiranya pernyataan itu bukan teorema, teori tidak dapat menunjukkan bahawa objek itu ada jika pernyataan itu terbukti salah dalam teori, ini membuktikan bahawa objek itu tidak boleh wujud secara longgar, objek tersebut tidak dapat dibina.

Ungkapan yang dapat ditentukan dalam notasi pembangun set masuk akal dalam ZFC dan NFU: mungkin kedua-dua teori membuktikan bahawa definisi yang diberikan berjaya, atau yang tidak berlaku (ungkapan < displaystyle > gagal merujuk kepada apa sahaja di ada menetapkan teori dengan logik klasik dalam teori kelas seperti NBG notasi ini merujuk kepada kelas, tetapi didefinisikan secara berbeza), atau yang satu itu dan yang lain tidak. Selanjutnya, objek yang didefinisikan dengan cara yang sama dalam ZFC dan NFU mungkin ternyata mempunyai sifat yang berbeza dalam kedua teori (atau mungkin ada perbezaan dalam apa yang dapat dibuktikan di mana tidak ada perbezaan yang dapat dibuktikan antara sifatnya).

Selanjutnya, teori set mengimport konsep dari cabang matematik lain (dengan niat, semua cabang matematik). Dalam beberapa kes, terdapat cara yang berbeza untuk mengimport konsep ke ZFC dan NFU. Sebagai contoh, definisi biasa ordinal tak terbatas pertama ω < displaystyle omega> dalam ZFC tidak sesuai untuk NFU kerana objek tersebut (didefinisikan dalam bahasa teori yang ditetapkan sebagai himpunan semua ordinal von Neumann terhingga) tidak dapat dilihat wujud di 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 n-ary relations for n > 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

The 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 suntikan (juga dipanggil 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 untuk m dan n dalam N sebagai

(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 A 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 A 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 A, | 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 N 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 N or to P(N), 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 Saya of the same size whose elements are self-singletons: i = < i >> for each i dalam Saya.

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 semua T[x]'s (including T[v]). Sejak 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 A, define S(A) 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 A 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 n-Mahlo cardinals for each n 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.


Tonton videonya: Cara-cara nk pandai matematik (Disember 2021).