Кіріспе
Математикада жақсы реттеу принципі оң сандардың бос емес кез келген ішкі жиынында ең кіші элемент болатынын айтады. Басқаша айтқанда, оң бүтін сандар жиыны өзінің "табиғи" немесе "мөлшері" бойынша жақсы реттелген, яғни бір сан екінші саннан кіші немесе тең болады, егер ол сан немесе оң бүтін санның қосындысы болса (басқа реттеулерге ; және) жатады. "Жақсы реттеу принципі" термині кейде "жақсы реттеу теоремасы" терминімен бірдей мағынада қолданылады. Ал кейде бұл принцип бүтін сандар жиынында жақсы реттелген ішкі жиынтық бар екенін, оны табиғи сандар деп атайды, және осы жиынтықтағы кез келген бос емес ішкі жиынтықта ең кіші элемент болатынын білдіреді.
In mathematics, the well ordering principle states that every non empty subset of positive integers contains a least element. In other words, the set of positive integers is well ordered by its "natural" or "magnitude" order in which precedes if and only if is either or the sum of and some positive integer (other orderings include the ordering ; and ). The phrase "well ordering principle" is sometimes taken to be synonymous with the "well ordering theorem". On other occasions it is understood to be the proposition that the set of integers contains a well ordered subset, called the natural numbers, in which every nonempty subset contains a least element.
Қасиеттері
Натурал сандар қалай енгізілгеніне байланысты, табиғи сандар жиынының бұл (екінші реттік) қасиеті аксиома немесе дәлелдеме арқылы көрсетілетін теорема болып табылады. Мысалы: Пеано арифметикасында, екінші реттік арифметикада және оған байланысты жүйелерде, тіпті жақсы реттелу принципінің көптеген (қажетті түрде формалды емес) математикалық қарастырылуларында, принцип математикалық индукция принципінен туындайды, ол өзі негізгі болып есептеледі. Натурал сандарды нақты сандардың ішкі жиыны ретінде қарастырып, нақты сандар толық екенін білеміз деп есептесек (қайтадан, аксиома немесе нақты сандар жүйесі туралы теорема ретінде), яғни, әрбір шектелген (төменнен) жиынның инфимумы болады, онда табиғи сандардың кез келген жиынының да инфимумы болады, мысалы, біз енді жартылай ашық аралықта жатқан бүтін санды таба аламыз, содан кейін екенін көрсетуге болады, және аксиомалық жиын теориясында натурал сандар ең кіші индуктивті жиын ретінде анықталады (яғни, 0-ді қамтитын және кейіннен келетін амал бойынша жабық жиын). Адам (тұрақтылық аксиомасын қолданбастан) барлық натурал сандардың жиыны "жақсы реттелген" индуктивті екенін және демек, барлық натурал сандарды қамтуы керек екенін көрсетуге болады; осы қасиеттен барлық натурал сандар жиыны да жақсы реттелген деген қорытынды жасауға болады. Екінші мағынада, бұл тіркес дәлелдерді негіздеу үшін осы ұсынысқа сүйенген кезде қолданылады: әрбір натурал сан белгілі бір жиынға жататынын дәлелдеу үшін, керісінше деп есептейік, бұл қарсы мысалдар жиыны бос емес және демек, ең кішкентай қарсы мысал бар екенін білдіреді. Содан кейін кез келген қарсы мысалдан одан да кішкентай қарсы мысал табуға болады, бұл қайшылыққа әкеледі. Бұл аргумент толық индукция арқылы дәлелдеудің керісіне сәйкес келеді. Бұл әдіс "ең кішкентай қылмыскер" әдісі деп белгілі және табиғаты бойынша Ферманың "шексіз төмен түсу" әдісіне ұқсас. Гаррет Бирхофф және Сондерс Мак Лейн «Қазіргі алгебраға шолу» еңбегінде бұл қасиет, нақты сандар үшін жоғарғы шек аксиомасы сияқты, алгебралық емес екенін жазды; яғни, оны бүтін сандардың алгебралық қасиеттерінен (реттелген интегралды домен құрайтын) шығаруға болмайды.
In Peano arithmetic, second order arithmetic and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well ordering principle, the principle is derived from the principle of mathematical induction, which is itself taken as basic. Considering the natural numbers as a subset of the real numbers, and assuming that we know already that the real numbers are complete (again, either as an axiom or a theorem about the real number system), i. e., every bounded (from below) set has an infimum, then also every set of natural numbers has an infimum, say We can now find an integer such that lies in the half open interval , and can then show that we must have , and in In axiomatic set theory, the natural numbers are defined as the smallest inductive set (i. e., set containing 0 and closed under the successor operation). One can (even without invoking the regularity axiom) show that the set of all natural numbers such that " is well ordered" is inductive, and must therefore contain all natural numbers; from this property one can conclude that the set of all natural numbers is also well ordered. In the second sense, this phrase is used when that proposition is relied on for the purpose of justifying proofs that take the following form: to prove that every natural number belongs to a specified set , assume the contrary, which implies that the set of counterexamples is non empty and thus contains a smallest counterexample. Then show that for any counterexample there is a still smaller counterexample, producing a contradiction. This mode of argument is the contrapositive of proof by complete induction. It is known light heartedly as the "minimal criminal" method and is similar in its nature to Fermat's method of "infinite descent". Garrett Birkhoff and Saunders Mac Lane wrote in A Survey of Modern Algebra that this property, like the least upper bound axiom for real numbers, is non algebraic; i. e., it cannot be deduced from the algebraic properties of the integers (which form an ordered integral domain).
Қолдану үлгілері
Жақсы реттеу принципі келесі дәлелдемелерде қолданылады.
Басты факторларға бөлу
Теорема: Бірден үлкен кез келген бүтін санды жай сандардың көбейтіндісі түрінде жіктеуге болады. Бұл теорема жай санға жіктеу теоремасының бір бөлігін құрайды. Дәлел (жақсы реттелген принцип бойынша). – бірден үлкен және жай сандардың көбейтіндісі түрінде жіктеуге болмайтын бүтін сандардың жиыны болсын. Біз бос екенін көрсетеміз. Қарама-қайшылыққа қарай, бос емес деп есептейік. Онда, жақсы реттелген принцип бойынша, ең кіші элемент бар; жай сан өзі жай сандардың бірлік ұзындығының көбейтіндісі саналатындықтан, жай сан бола алмайды. Жай сан емес сандардың анықтамасы бойынша, -ның факторлары бар, мұнда бірден үлкен және -дан кіші бүтін сандар. -ның ең кіші элемент екендігіне байланысты, олар жиынында жоқ. Сондықтан, -ны және жай сандардың көбейтіндісі түрінде жіктеуге болады, яғни – жай сандардың көбейтіндісі. Бұл деген болжамға қайшы келеді, сондықтан бос емес деген болжам дұрыс емес.
Бүкіл сандарды қосу
Теорема: Барлық оң бүтін сандар үшін.
Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non empty set of positive integers By the well ordering principle, has a minimum element such that when , the equation is false, but true for all positive integers less than The equation is true for , so ; is a positive integer less than , so the equation holds for as it is not in Therefore,
which shows that the equation holds for , a contradiction. So, the equation must hold for all positive integers.
Дәлелдеу. Қарама-қайшылыққа түсу үшін, жоғарыдағы теорема жалған деп есептейік. Онда, оң бүтін сандардың бос емес жиыны бар. Жақсы реттеу принципі бойынша, жиынның ең кіші элементі бар, мұндағы теңдеу дұрыс емес, бірақ одан кіші барлық оң бүтін сандар үшін дұрыс. Теңдеу 1 үшін дұрыс, яғни ; 1 – 1-ден кіші оң бүтін сан, сондықтан теңдеу 1 үшін де орындалады, себебі ол жиынға жатпайды.
Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non empty set of positive integers By the well ordering principle, has a minimum element such that when , the equation is false, but true for all positive integers less than The equation is true for , so ; is a positive integer less than , so the equation holds for as it is not in Therefore,
which shows that the equation holds for , a contradiction. So, the equation must hold for all positive integers.
Осылайша, теңдеу 1 үшін де орындалады, бұл қарама-қайшылықты көрсетеді. Демек, теңдеу барлық оң бүтін сандар үшін дұрыс болуы керек.
Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non empty set of positive integers By the well ordering principle, has a minimum element such that when , the equation is false, but true for all positive integers less than The equation is true for , so ; is a positive integer less than , so the equation holds for as it is not in Therefore,
which shows that the equation holds for , a contradiction. So, the equation must hold for all positive integers.