Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық жиын, шекті сандағы элементтерді қамтитын.
Mathematical set containing a finite number of elements
Математикада, әсіресе жиын теориясында, шекті жиын – элементтерінің саны шекті жиын. Дәл айтқанда, шекті жиынды принцип бойынша санап, санауды аяқтауға болады. Мысалы,
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
бес элементі бар шекті жиын. Шекті жиынның элементтерінің саны – табиғи сан (мүмкін, нөл) және бұл жиынның кардиналдығы (немесе кардинал саны) деп аталады. Егер жиын шекті болмаса, онда ол шексіз жиын деп аталады. Мысалы, барлық оң бүтін сандар жиыны шексіз:
is a finite set with five elements. The number of elements of a finite set is a natural number (possibly zero) and is called the cardinality (or the cardinal number) of the set. A set that is not a finite set is called an infinite set. For example, the set of all positive integers is infinite:
Шекті жиындар комбинаторикада, яғни сандық есептеудің математикалық зерттеуінде ерекше маңызға ие. Шекті жиындарға қатысты көптеген дәлелдер «көгершін ұясы» принципіне негізделген, ол үлкен шекті жиыннан кіші шекті жиынға инъекциялық функцияның болуы мүмкін емес екенін көрсетеді.
Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.
Негізгі мәселелер
Георг Кантор шексіз жиындарды математикалық тұрғыдан қарастыру үшін жиындар теориясын қалыптастырды. Осылайша, шекті және шексіз арасындағы ерекшелік жиындар теориясының негізгі мәселесі болып табылады. Кейбір негізшілер, қатаң финитистер шексіз жиындардың бар екенін жоққа шығарады және тек шекті жиындарға негізделген математиканы ұсынады. Бағытталған математиктер қатаң финитизмді тым шектеулі деп есептейді, бірақ оның салыстырмалы тұрақтылығын мойындайды: тұқым қуалайтын шекті жиындардың әлемі, шексіздік аксиомасы теріспен ауыстырылған Зермело-Франкель жиындар теориясының моделін құрайды. Шексіз жиындарды қабылдайтын көптеген математиктер үшін де, кейбір маңызды контекстерде шекті мен шексіз арасындағы формалды ерекшелік күрделі мәселе болып қалуы мүмкін. Бұл қиындық Гёдельдің толық еместік теоремаларынан туындайды. Тұқым қуалайтын шекті жиындар теориясын Пеано арифметикасының ішінде (және әрине, керісінше) түсіндіруге болады, сондықтан Пеано арифметикасының толық еместігі тұқым қуалайтын шекті жиындар теориясының толық еместігін білдіреді. Әсіресе, екі теорияның да стандартты емес модельдері бар. Көрінетін парадокс – шексіз жиындарды қамтитын тұқым қуалайтын шекті жиындар теориясының стандартты емес модельдері бар, бірақ бұл шексіз жиындар модельдің ішінде шекті болып көрінеді. (Бұл модельде осы жиындардың шексіздігіне куәлік ететін жиындар немесе функциялар болмаған жағдайда мүмкін болады.) Толық еместік теоремаларының салдарынан, ешбір бірінші реттік предикат, тіпті бірінші реттік предикаттардың рекурсивті схемасы да, мұндай модельдердің барлық стандартты бөлігін сипаттауға қабілетті емес. Демек, кемінде бірінші реттік логика тұрғысынан, шектілікті шамамен ғана сипаттауға үміттене аламыз. Жалпы алғанда, жиын және әсіресе шекті жиын сияқты формалды емес ұғымдар, әртүрлі формальды жүйелерде, олардың аксиоматикасы мен логикалық құралдарына сәйкес интерпретацияларға ие болуы мүмкін. Ең белгілі аксиоматикалық жиындар теорияларына Зермело-Франкель жиындар теориясы (ZF), таңдау аксиомасымен Зермело-Франкель жиындар теориясы (ZFC), фон Нейман-Бернайс-Гёдель жиындар теориясы (NBG), жақсы негізделмеген жиындар теориясы, Бертран Расселдің типтер теориясы және олардың әртүрлі модельдерінің барлық теориялары кіреді. Классикалық бірінші реттік логика, әртүрлі жоғары реттік логикалар және интуиционистік логика арасынан да таңдау жасауға болады. Формалист жиынның мағынасын жүйеден жүйеге қарай өзгеретіндей деп қарастыруы мүмкін. Платонистердің кейбір түрлері нақты формальды жүйелерді жатқан шындыққа жақындау деп қарауы мүмкін.
Georg Cantor initiated his theory of sets in order to provide a mathematical treatment of infinite sets. Thus the distinction between the finite and the infinite lies at the core of set theory. Certain foundationalists, the strict finitists, reject the existence of infinite sets and thus recommend a mathematics based solely on finite sets. Mainstream mathematicians consider strict finitism too confining, but acknowledge its relative consistency: the universe of hereditarily finite sets constitutes a model of Zermelo–Fraenkel set theory with the axiom of infinity replaced by its negation. Even for the majority of mathematicians that embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so called non standard models of both theories. A seeming paradox is that there are non standard models of the theory of hereditarily finite sets which contain infinite sets, but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first order predicate, nor even any recursive scheme of first order predicates, can characterize the standard part of all such models. So, at least from the point of view of first order logic, one can only hope to describe finiteness approximately. More generally, informal notions like set, and particularly finite set, may receive interpretations across a range of formal systems varying in their axiomatics and logical apparatus. The best known axiomatic set theories include Zermelo Fraenkel set theory (ZF), Zermelo Fraenkel set theory with the Axiom of Choice (ZFC), Von Neumann–Bernays–Gödel set theory (NBG), Non well founded set theory, Bertrand Russell's Type theory and all the theories of their various models. One may also choose among classical first order logic, various higher order logics and intuitionistic logic. A formalist might see the meaning of set varying from system to system. Some kinds of Platonists might view particular formal systems as approximating an underlying reality.
Шектіліктің басқа ұғымдары
ZF жинақ теориясында таңдау аксиомасысыз, S жиыны үшін шектіліктің келесі түсініктері ерекшеленеді. Олар қатаң түрде төмендеу ретімен орналастырылған, яғни егер S жиыны тізімдегі бір критерийге жауап берсе, онда ол одан кейінгі барлық критерийлерге де жауап береді. Таңдау аксиомасы болмаған жағдайда кері тұжырымдардың ешқайсысы да дәлелденбейді, бірақ егер таңдау аксиомасы қабылданса, онда бұл түсініктердің барлығы эквивалентті болады. (Ешқайсысы да бұл анықтамаларға шекті реттік сандар жиыны алдын ала анықталғаннан кейін қажет емес; олардың барлығы теңдік және кіріктіру қатынастары тұрғысынан таза «жинақ теориялық» анықтамалар болып табылады, ω қатыспайды.) I шекті. S жиынының бос емес әрбір кіші жиынында максималды элемент болады. (Бұл минималды элементтің болуын талап етуге тең. Бұл стандартты сандық шектілік түсінігіне де тең.) Ia шекті. S жиынының кез келген екі жиынға бөлінуі үшін, кем дегенде біреуі I шекті болады. (Бұл қасиетке ие, бірақ I шекті емес жиын аморфты жиын деп аталады.) II шекті. S жиынының бос емес әрбір монотонды кіші жиынында максималды элемент болады. III шекті. P(S) қуат жиыны Дедекинд шекті. IV шекті. S жиыны Дедекинд шекті. V шекті. |S| = 0 немесе 2 ⋅ |S| > |S|. VI шекті. |S| = 0 немесе |S| = 1 немесе |S|² > |S|. VII шекті. S жиыны I шекті немесе жақсы реттелмейді. Алға бағытталған тұжырымдар (күштіден әлсізге дейін) ZF ішінде теоремалар болып табылады. ZF-те урелементтермен кері тұжырымдарға (әлсізден күштіге) қарсы мысалдар модельдік теорияны қолдану арқылы табылды. Бұл шектілік анықтамаларының көпшілігі және олардың атаулары авторға жатқызылады. Дегенмен, I, II, III, IV және V анықтамалары алға бағытталған тұжырымдар үшін дәлелдермен (немесе дәлелдерге сілтемелермен) бірге ұсынылды. Сол кезде модельдік теория қарсы мысалдарды табу үшін жеткілікті дамымаған еді. I шектіден IV шектіге дейінгі әрбір қасиет осындай қасиетке ие жиынның кез келген кіші жиыны да осы қасиетке ие болатыны мағынасында кішілік түсінігі болып табылады. Бұл V шектіден VII шектіге дейін дұрыс емес, өйткені олардың саналатын шексіз кіші жиындары болуы мүмкін.
In ZF set theory without the axiom of choice, the following concepts of finiteness for a set S are distinct. They are arranged in strictly decreasing order of strength, i. e. if a set S meets a criterion in the list then it meets all of the following criteria. In the absence of the axiom of choice the reverse implications are all unprovable, but if the axiom of choice is assumed then all of these concepts are equivalent. (Note that none of these definitions need the set of finite ordinal numbers to be defined first; they are all pure "set theoretic" definitions in terms of the equality and membership relations, not involving ω.) I finite. Every non empty set of subsets of S has a ⊆ maximal element. (This is equivalent to requiring the existence of a ⊆ minimal element. It is also equivalent to the standard numerical concept of finiteness.) Ia finite. For every partition of S into two sets, at least one of the two sets is I finite. (A set with this property which is not I finite is called an amorphous set.) II finite. Every non empty ⊆ monotone set of subsets of S has a ⊆ maximal element. III finite. The power set P(S) is Dedekind finite. IV finite. S is Dedekind finite. V finite. ∣S∣ = 0 or 2 ⋅ ∣S∣ > ∣S|. VI finite. ∣S∣ = 0 or ∣S∣ = 1 or ∣S∣2 > ∣S∣. VII finite. S is I finite or not well orderable. The forward implications (from strong to weak) are theorems within ZF. Counter examples to the reverse implications (from weak to strong) in ZF with urelements are found using model theory. Most of these finiteness definitions and their names are attributed to by However, definitions I, II, III, IV and V were presented in , together with proofs (or references to proofs) for the forward implications. At that time, model theory was not sufficiently advanced to find the counter examples. Each of the properties I finite thru IV finite is a notion of smallness in the sense that any subset of a set with such a property will also have the property. This is not true for V finite thru VII finite because they may have countably infinite subsets.