Редактирование: Натуральные числа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
==Определение натуральных чисел==
 
 
===Неформальное определение===
 
 
{{Определение
 
|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>разность множеств. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.
 
 
 
==Деление чисел с остатком==
 
==Деление чисел с остатком==
 
   
 
   
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Если [[Классы чисел#Определение натуральных чисел | натуральное число]] <tex>n\,</tex> не делится на натуральное число <tex>m</tex>, т.е. не существует такого натурального числа <tex>k</tex> , что <tex>n = m \cdot k</tex>, то деление называется '''делением с остатком''' (англ. ''modulo operation'').
+
Если натуральное число <tex>n\,</tex> не делится на натуральное число <tex>m</tex>, т.е. не существует такого натурального числа <tex>k</tex> , что <tex>n = m \cdot k</tex>, то деление называется '''делением с остатком''' (англ. ''modulo operation'').
 
}}
 
}}
  
'''Формула деления с остатком''': <tex>n = m \cdot k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex>
+
'''Формула деления с остатком''': <tex>n = m\,k + r,</tex> где <tex>n\,</tex> — делимое, <tex>m\,</tex> — делитель, <tex>k\,</tex> — частное, <tex>r\,</tex> — остаток, причем <tex>0\leqslant r < b </tex>
  
 
:Любое число можно представить в виде: <tex>n = 2 \cdot k + r</tex>, где остаток <tex>r\, = 0\,</tex> или <tex>r\, = 1\,</tex>
 
:Любое число можно представить в виде: <tex>n = 2 \cdot k + r</tex>, где остаток <tex>r\, = 0\,</tex> или <tex>r\, = 1\,</tex>
Строка 92: Строка 20:
 
|id=th1
 
|id=th1
 
|statement=
 
|statement=
Если простое число <tex>p</tex> делит без остатка произведение двух [[Классы чисел#Определение целых, рациональных, вещественных и комплексных чисел | целых чисел]] <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.
+
Если простое число <tex>p</tex> делит без остатка произведение двух целых чисел <tex>x\cdot y</tex>, то <tex>p</tex> делит <tex>x</tex> или <tex>y</tex>.
 
|proof=
 
|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 y</tex> делится на <tex>p</tex>, но <tex>x</tex> не делится на <tex>p</tex>. Тогда <tex>x</tex> и <tex>p</tex> — взаимно простые, следовательно, найдутся такие целые числа <tex>u</tex> и <tex>v</tex>, что
Строка 110: Строка 38:
 
'''Существование'''. Пусть <tex>n</tex> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <tex>n</tex> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <tex>n</tex> тоже является произведением простых чисел. Противоречие.
 
'''Существование'''. Пусть <tex>n</tex> — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <tex>n</tex> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, <tex>n</tex> тоже является произведением простых чисел. Противоречие.
  
'''Единственность'''. Пусть <tex>n</tex> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <tex>p</tex> — любой из сомножителей в любом из двух разложений. Если <tex>p</tex> входит и в другое разложение, мы можем сократить оба разложения на <tex>p</tex> и получить два разных разложения числа <tex>\dfrac{n}{p}</tex>, что невозможно. А если <tex>p</tex> не входит в другое разложение, то одно из произведений делится на <tex>p</tex>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.
+
'''Единственность'''. Пусть <tex>n</tex> — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть <tex>p</tex> — любой из сомножителей в любом из двух разложений. Если <tex>p</tex> входит и в другое разложение, мы можем сократить оба разложения на <tex>p</tex> и получить два разных разложения числа <tex>n/p</tex>, что невозможно. А если <tex>p</tex> не входит в другое разложение, то одно из произведений делится на <tex>p</tex>, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.
 
}}
 
}}
 
[[Категория: Теория чисел]]
 
  
 
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==
 
==Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел==
Строка 139: Строка 65:
 
Для любого подмножества натурального ряда всегда существует минимум.
 
Для любого подмножества натурального ряда всегда существует минимум.
 
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A, x \leqslant y</tex>
 
Т. е. <tex>\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A, x \leqslant y</tex>
}}
+
|proof=
Из этой теоремы вытекает следующее утверждение, эквивалентное аксиоме математической индукции, но иногда более удобное при проведении доказательств.
+
Если <tex>1 \in A</tex>, то <tex>1</tex> и есть '''min'''. Иначе <tex>1 \notin A</tex>
{{Утверждение
+
Если <tex>2 \in A</tex>, то <tex>2</tex> и есть '''min'''. Иначе <tex>2 \notin A</tex>
|id=utv1
+
<tex>P(n)</tex> — все элементы <tex>\leqslant n</tex> не лежат в <tex>A</tex> <tex>\Rightarrow</tex> <tex>P(1) \ldots P(n)</tex> — верно и <tex>P(n+1)</tex> — верно (т.к. он был бы '''min''') <tex>\Rightarrow</tex> в <tex>A</tex> ничего не лежит. Противоречие.
|author=
 
|about=
 
|statement= Если <tex>T(n)</tex> истинно при <tex>n = 1,</tex> а из того, что оно истинно при всех <tex>n < k,</tex> следует, что оно истинно и при <tex>n = k,</tex> то <tex>T(n)</tex> истинно для всех натуральных значений <tex>n</tex>.
 
|proof=Обозначим через <tex>A</tex> подмножество натуральных чисел, для которых <tex>T(n)</tex> ложно. Если это подмножество непусто, то оно содержит наименьшее число k. Этим числом не может быть <tex>1</tex>, так как по условию <tex>T(1)</tex> истинно. Значит, <tex>k > 1</tex>. Но поскольку <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>.
 
 
}}
 
}}
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)