Изменения

==Определение натуральных чисел== ===Неформальное определение=== {{Определение|definition='''Натура́льные чи́сла''' (англ. ''natural numbers'', естественные числа) — числа, возникающие естественным образом при счёте (как в смысле перечисления, так и в смысле исчисления).}} Существуют два подхода к определению натуральных чисел — числа, используемые при:* '''перечислении (нумеровании) предметов''' (''первый'', ''второй'', ''третий''…) — подход, общепринятый в большинстве стран мира (в том числе и в России);* '''обозначении количества предметов''' (''нет предметов'', ''один предмет'', ''два предмета''…). Принят в трудах Николя Бурбаки, где натуральные числа определяются как мощность конечных множеств. Отрицательные и нецелые числа натуральными числами не являются. Множество всех натуральных чисел принято обозначать знаком <tex>\mathbb{N}</tex>. Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся большее его натуральное число. ===Формальное определение===Определить множество натуральных чисел позволяют '''аксиомы Пеано''' (англ. ''Peano axioms''):{{Определение|definition=Множество <tex>\mathbb N</tex> будем называть '''множеством натуральных чисел''', если зафиксирован некоторый элемент <tex> 1\in\mathbb N</tex> (единица) и функция <tex>S\colon\mathbb N\to\mathbb N</tex> (функция следования) так, что выполнены следующие условия# <tex>1\in\mathbb{N}</tex> (<tex>1</tex> является натуральным числом);# Если <tex>x\in\mathbb{N}</tex>, то <tex>S(x)\in\mathbb{N}</tex> (Число, следующее за натуральным, также является натуральным);# <tex>\nexists x\in\mathbb{N}\ (S(x) = 1)</tex> (<tex>1</tex> не следует ни за каким натуральным числом);# Если <tex>S(b)=a</tex> и <tex>S(c)=a</tex>, тогда <tex>b=c</tex> (если натуральное число <tex>a</tex> непосредственно следует как за числом <tex>b</tex>, так и за числом <tex>c</tex>, то <tex>b=c</tex>);# '''Аксиома индукции'''. Пусть <tex>P(n)</tex> — некоторый одноместный предикат, зависящий от параметра — натурального числа <tex>n</tex>. Тогда::: если <tex>P(1)</tex> и <tex>\forall n\;(P(n)\Rightarrow P(S(n)))</tex>, то <tex>\forall n\;P(n)</tex>:: ('''Если''' некоторое высказывание <tex>P</tex> верно для <tex>n=1</tex> (''база индукции'') и для любого <tex>n</tex> при допущении, что верно <tex>P(n)</tex>, верно и <tex>P(n+1)</tex> ''(индукционное предположение)'', '''то''' <tex>P(n)</tex> верно для любых натуральных <tex>n</tex>).}} ===Теоретико-множественное определение=== Согласно теории множеств, единственным объектом конструирования любых математических систем является множество. Таким образом, и натуральные числа вводятся, исходя из понятия множества, по двум правилам:* <tex>0=\varnothing</tex>* <tex>S(n)=n\cup\left\{n\right\}</tex>Числа, заданные таким образом, называются ординальными. Первые несколько ординальных чисел и соответствующие им натуральные числа:* <tex>0=\varnothing</tex>* <tex>1=\left\{\varnothing\right\}</tex>* <tex>2=\big\{\varnothing,\;\left\{\varnothing\right\}\big\}</tex>* <tex>3=\Big\{\varnothing,\;\left\{\varnothing\right\},\;\big\{\varnothing,\;\left\{\varnothing\right\}\big\}\Big\}</tex> Классы эквивалентности этих множеств относительно биекций также обозначают <tex>0, 1, 2, \dots.</tex> Перечисленные аксиомы отражают наше интуитивные представления о «натуральном ряде». ==Операции над натуральными числами=====Сложение===Есть два способа определения суммы двух натуральных чисел <tex>a\ и\ b</tex>. Если натуральные числа определяют через мощность множества с конечным числом элементов (мощность множества — это количество элементов в нём), тогда целесообразно дать следующее определение суммы: Пусть <tex>N(S)\ — </tex> мощность множества <tex>S</tex>. Возьмём два не пересекающихся множества <tex>A\</tex> и <tex>B,\</tex> причём <tex>N(A) = a</tex> и <tex>N(B) = b</tex>.Тогда <tex>a + b</tex> можно определить как: <tex>N ( A ∪ B )</tex>. Здесь, <tex>A ∪ B\ — </tex> это объединение множеств <tex>A\ и B\</tex>. В разработкеальтернативной версии этого определения множества <tex>A\ и\ B</tex> перекрываются и тогда в качестве суммы берётся их дизъюнктное объединение, механизм, который позволяет отделять общие элементы, вследствие чего эти элементы учитываются дважды. Другое известное определение рекурсивно:Пусть <tex>n+\ — </tex> следующее за <tex>n</tex> натуральное число, например <tex>0+ = 1, 1+ = 2.</tex> Пусть <tex>a + 0 = a</tex>. Тогда общая сумма определяется рекурсивно: <tex>a + (b+) = (a + b)+</tex>. Отсюда <tex>1 + 1 = 1 + 0+ = (1 + 0)+ = 1+ = 2</tex>. ===Умножение===Воспользуемся определением натуральных чисел <tex>\mathbb{N}</tex> как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств <tex>C,\A,\B\</tex> порождённых биекциями, с помощью скобок: <tex>[C], [A], [B].</tex> Тогда арифметическая операция '''умножение''' определяется следующим образом:<tex>[C] = [A] \cdot [B] = [A \times B];\</tex>где: <tex>A \times B={(a,\ b) \mid a \in A,\ b \in B}\</tex> прямое произведение множеств — множество <tex>C,</tex> элементами которого являются упорядоченные пары <tex>(a,\ b)</tex> для всевозможных  <tex>a \in A,\ b \in B</tex>. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением. ===Вычитание===Воспользуемся определением натуральных чисел <tex>\mathbb{N}</tex> как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств <tex>C , A , B</tex> порождённых биекциями, с помощью скобок: <tex>[C],\ [A],\ [B].</tex> Тогда арифметическая операция '''вычитание''' определяется следующим образом:<tex>[C] = [A] − [B] = [A \backslash B];\</tex>где <tex>A \backslash B = \{ C \in A \mid C \notin B \mid B \subset A \} —\ </tex>разность множеств. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.

Если натуральное число '''Формула деления с остатком''': <tex>n = m \cdot k + r,<math/tex> где <tex>n\,</mathtex> не делится на натуральное число — делимое, <mathtex>m\,</mathtex>— делитель, т.е. не существует такого натурального числа <mathtex>k\,</mathtex> — частное, что <mathtex>n = mr\,k</tex> — остаток,причем <tex>0\leqslant r < b </mathtex> то деление называется '''делением с остатком'''.

'''Формула деления с остатком''':Любое число можно представить в виде: <mathtex>n = m2 \,cdot k + r,</mathtex> , где остаток <mathtex>nr\,</math> - делимое, <math>m= 0\,</mathtex> - делитель, или <mathtex>kr\,</math> - частное, <math>r= 1\,</math> - остаток, причем <math>0\leqslant r < b </mathtex>

:Любое число можно представить в виде: <mathtex>n = 24 \,cdot k + r,</mathtex> , где остаток <mathtex>r\ = 0\,</mathtex> = или <mathtex>0r\, = 1\,</mathtex> или <mathtex>r\, = 2\,</mathtex> = или <mathtex>1r\, = 3\,</mathtex>

:Любое число можно представить в виде: <mathtex>n = 4m \,cdot k + r,</mathtex> , где остаток <mathtex>r\,</mathtex> = принимает значения от <mathtex>0\,</math> или <math>r\,</mathtex> = до <mathtex>(m-1)\,</math> или <math>r\,</math> = <math>2\,</math> или <math>r\,</math> = <math>3\,</mathtex>

==Основная теорема арифметики=====Лемма Евклида=== {{Лемма|id=th1|statement=Если простое число <tex>p</tex> делит без остатка произведение двух [[Классы чисел#Определение целых, рациональных, вещественных и комплексных чисел | целых чисел]] <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.|proof=Пусть <tex>x\cdot y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что:Любое <tex>x\cdot u+p\cdot v=1</tex> ([[Наибольший общий делитель|соотношение Безу]]).Умножая обе части на <tex>y</tex>, получаем: <tex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</tex>Оба слагаемых левой части делятся на <tex>p</tex>, значит, и правая часть делится на <tex>p</tex>.}} ===Основная теорема арифметики=== {{Теорема|id=th666|statement=Каждое натуральное число можно представить <tex>n>1</tex> представляется в виде: <mathtex>n = mp_1\cdots p_k</tex>,k + rгде <tex>p_1,\ldots ,p_k</tex> — [[простые числа]], причём такое представление единственно с точностью до порядка следования сомножителей.|proof='''Существование'''. Пусть <tex>n</tex> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым,потому что любое простое число является произведением одного простого числа — себя. Если <tex>n</mathtex> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, где остаток значит, <tex>n</tex> тоже является произведением простых чисел. Противоречие. '''Единственность'''. Пусть <mathtex>r\n</tex> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае,пусть <tex>p</mathtex> принимает значения от — любой из сомножителей в любом из двух разложений. Если <mathtex>0\p</tex> входит и в другое разложение,мы можем сократить оба разложения на <tex>p</mathtex> до и получить два разных разложения числа <mathtex>(m-1)\dfrac{n}{p}</tex>, что невозможно. А если <tex>p</tex> не входит в другое разложение,то одно из произведений делится на <tex>p</mathtex>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.}} [[Категория: Теория чисел]]

Формулировка '''Формулировка принципа математической индукции''':

:Пусть имеется последовательность утверждений <mathtex>Y_1A_1, Y_2A_2, Y_3A_3, \ldots</mathtex> И пусть первое утверждение <mathtex>Y_1A_1</mathtex> верно и мы умеем доказать, что из верности утверждения <mathtex>Y_kA_k</mathtex> следует верность <mathtex>Y_A_{k + 1}</mathtex>. Тогда все утверждения в этой последовательности верны.

Верность этого метода доказательства вытекает из так называемой '''аксиомы индукции''', пятой из [[m:ru:аксиомы Пеано|аксиом Пеано]], которые определяют [[m:ru:Натуральное число|натуральные числа]]. Рассмотрение аксиом Пеано выходит за рамки этой статьи.

Заметим, что аксиому Также существует '''принцип полной математической индукции можно заменить на [[m:ru'''. Вот его строгая формулировка:Аксиома существования минимума|аксиому существования минимума]], и доказать аксиому индукции как теорему.

:Пусть имеется последовательность утверждений {{Теорема|id=th1|about=О существовании минимума|statement=Для любого подмножества натурального ряда всегда существует минимум.Т. е. <mathtex>Y_1\forall A \subset \mathbb N, Y_2A \ne \varnothing, Y_3\exists x \in A: \forall y \in A, x \ldotsleqslant y</mathtex>}}Из этой теоремы вытекает следующее утверждение, эквивалентное аксиоме математической индукции, но иногда более удобное при проведении доказательств. И пусть мы умеем доказать{{Утверждение|id=utv1|author=|about=|statement= Если <tex>T(n)</tex> истинно при <tex>n = 1,</tex> а из того, что оно истинно при всех <tex>n < k,</tex> следует, что из верности утверждения оно истинно и при <mathtex>Y_1n = k, Y_2</tex> то <tex>T(n)</tex> истинно для всех натуральных значений <tex>n</tex>.|proof=Обозначим через <tex>A</tex> подмножество натуральных чисел, Y_3для которых <tex>T(n)</tex> ложно. Если это подмножество непусто, \ldotsто оно содержит наименьшее число k. Этим числом не может быть <tex>1</tex>, Y_kтак как по условию <tex>T(1)</mathtex> следует верность истинно. Значит, <mathtex>Y_{k + > 1}</mathtex>. Но поскольку <tex>k</tex> — наименьшее число, для которого <tex>T(n)</tex> ложно, то для всех <tex>n < k</tex> <tex>T(n)</tex> истинно, а тогда по условию теорем оно должно быть истинно и при <tex>n = k</tex>. Мы пришли к противоречию — одновременно оказалось, что <tex>T(k)</tex> истинно и ложно. Следовательно, предположение о том, что <tex>A</tex> не пустое множество, ложно. Значит, <tex>A</tex> — пустое множество, т.е. нет натуральных чисел, для которых <tex>T(n)</tex>ложно. Тогда все утверждения в этой последовательности верныЧто означает, что <tex>T(n)</tex> истинно для всех натуральных значений <tex>n</tex>.}}

 ===Существование наименьшего элемента=Источники информации ==* ”Математика: Справ, материалы: Кн. для учащих­ся.— М.: Просвещение, 1988.” Авторы: Гусев В. А., Мордкович А. Г. с. 12—13.* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%BD%D0%B4%D1%83%D0%BA%D1%86%D0%B8%D1%8F Математическая индукция]