SHARE
TWEET

Untitled

a guest Feb 19th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass{beamer}
  2. \usetheme{Madrid}
  3. \usepackage[english,russian]{babel}
  4. \usepackage{csquotes}
  5. \usepackage{amsmath,amssymb,lmodern}
  6. \usepackage{soul}
  7. \usepackage{soulutf8}
  8. \mathbb {N}
  9.  
  10. \title{Математическая индукция и метод бесконечного спуска}
  11. \author{}
  12. \centering
  13. \date{20.02.20}
  14. \begin{document}
  15. \maketitle
  16. %\\
  17. %\quad
  18.  
  19. \begin{frame}{Вполне упорядоченное множество}
  20. \begin{block}{Вполне упорядоченное множество}
  21. - множество Р с заданным на нем бинарным отношением ≤, удовлетворяющим условиям:\\
  22. 1) для любых х, у ∈ Р либо х <= y, либо y <= x;\\
  23. 2) если х <= y и у <= x, то х = у;\\
  24. 3) если х <= у и у <= z, то x <= z;\\
  25. 4) в любом непустом подмножестве X множества Р существует такой элемент а, что а <= х для всех х \in X
  26. \end{block}
  27. \end{frame}
  28.  
  29. \begin{frame}{Примеры вполне упорядоченных множеств}
  30.  
  31. \begin{itemize}
  32. \item
  33. {
  34. Простейший пример бесконечного вполне упорядоченного множества — множество натуральных чисел с естественным упорядочением.
  35. }
  36. \item
  37. {
  38. Пустое множество является вполне упорядоченным.
  39. }
  40. \item
  41. {
  42. Множество целых чисел не является вполне упорядоченным, так как, например, среди отрицательных чисел нет наименьшего. Однако его можно сделать вполне упорядоченным, если переопределить отношение <= следующим образом:\\
  43. a \preccurlyeq b \text{, если:}
  44.   \begin{itemize}
  45.   \item\text{либо a = b}
  46.    \item\text{либо |a| = |b|}
  47.     \item\text{либо |a| = |b| и a<0<b}
  48.   \end{itemize}
  49. }  
  50. \end{itemize}
  51. \end{frame}
  52.  
  53. \begin{frame}{Вполне упорядоченность множества \mathbb N }
  54. \begin{block}{Принцип математической индукции}
  55. \text{Если подмножество Е множества натуральных чисел таково, что}\\
  56. 1 \in \text{E и вместе с некоторым числом x} \in \text{E множеству E}\\ \text{ принадлежит и число (x+1), то E - множество натуральных чисел}
  57. То есть:\\
  58. (\text{E }\in \mathbb N)\wedge(1 \in \text{E})\wedge(\forall x \in \text{E : }(x \in \text{E} \Rightarrow (x+1) \in \text{E})) \Rightarrow (\text{E} = \mathbb N)
  59. \end{block}
  60. \begin{block}{Покажем, что (n \in \mathbb N)\wedge(n \neq 1)\Rightarrow((n-1) \in \mathbb N)}
  61. Рассмотрим множество E натуральных чисел вида (n-1) для \forall \text{n} \in \mathbb N\\
  62. Поскольку 1 \in\mathbb N, \text{то } 2:=(1+1) \in \mathbb N,\text{ а значит } 1 := (2-1) \in \text{E.}\\
  63. \forall \text{m} \in \text{E , m = n - 1}, \text{где n}  \in \mathbb N;\\ \text{Тогда m+1 = (n+1)-1 и, поскольку (n+1)} \in \mathbb N, \text{ имеем, что }\\ \text{(m+1)} \in \text{E.} \\ \text{Итак, 1}\in \text{E, и } \forall \text{m} \in \text{E : (m+1)}\in \text{E}.\\ \text{Из этого, по принципу индукции} \Rightarrow \text{ E = }\mathbb N
  64. \end{block}
  65. \end{frame}
  66.  
  67. \begin{frame}{Вполне упорядоченность множества \mathbb N}
  68. \begin{block}{Принцип наименьшего числа - в любом непустом подмножестве натуральных чисел есть минимальный элемент}
  69. \text{Пусть M }\subset \mathbb N. \\
  70. \text{Если 1} \in \text{M},\text{то minM = 1, поскольку }\forall n\in \mathbb N  \text{ (1 }\leq \text{n)}\\
  71. \text{Если 1} \notin \text{M}, \text{ т.е.  1} \in \text{E} = \mathbb N   \setminus \text{M, то в множестве Е должно}\\ \text{ найтись такое натуральное число n} \in \text{E, что}\\ \text{все натуральные числа, не превосходящие n, лежат в Е, }\\
  72. \text{а (n+1)}\in\text{M}.\text{ Если бы такого n не было, то множество }\\ E \subset \mathbb N\text{ , содержащее 1, вместе с n}\in \text{Е, содержало бы и (n+1)} \\\text{и по принципу индукции совпадало бы} с \mathbb N
  73. \text{Последнее невозможно, т.к}
  74. \mathbb N\setminus \text{E = M} \neq \varnothing\\
  75. \text{Найденное число (n+1)} \in\text{M}\text{ и будет минимальным в M,}\\ \text{поскольку между n и (n+1) нет натуральных чисел.}
  76. \end{block}
  77. \end{frame}
  78.  
  79. \begin{frame}{}
  80. \begin{block}{Вторая формулировка принципа наименьшего числа:}
  81. не сущeствует бесконечно убывающей последовательности натуральных чисел.
  82. \end{block}
  83. \begin{block}{Доказать, что среди всех равных друг другу дробей
  84. непременно найдётся несократимая дробь:}
  85. Предположим, что в нашем множестве дробей нет несократимой. Возьмём произвольную дробь
  86. из этого множества и сократим её. Полученную дробь также сократим, и так далее.
  87. Знаменатели этих дробей будут всё меньшими и меньшими, и возникнет бесконечная убывающая последовательность натуральных
  88. чисел, что невозможно.
  89. \end{block}
  90. \end{frame}
  91.  
  92. \begin{frame}{Метод бесконечного спуска}
  93. \begin{block}{Метод бесконечного спуска}
  94. Метод бесконечного спуска - метод доказательства от противного, основанный на том, что множество натуральных чисел вполне упорядочено.
  95. Из предположения, что решение существует, вытекает существование другого решения, которое в некотором смысле меньше. Тогда можно построить бесконечную цепочку решений, каждое из которых меньше предыдущего. Это вызывает противоречие с тем, что в любом подмножестве множества натуральных чисел существует минимальный элемент, значит предположение о существовании начального решения неверно.
  96. \end{block}
  97. \end{frame}
  98.  
  99. \begin{frame}{x^2+y^2 = 3z^2}
  100. \begin{block}{x^2+y^2 = 3z^2}
  101. Доказать, что это уравнение не имеет решений в целых числах при условии, что z \neq 0 \\
  102. Пусть (x,y,z): z \neq 0 \text{ - некоторое решение}\\
  103. Из уравнения видно, что x^2+y^2 \equiv\text{ 0 mod 3}\\
  104. (x^2+y^2 \equiv\text{ 0 mod 3}) \Rightarrow (x^2 \equiv y^2 \equiv\text{ 0 mod 3}) \Rightarrow (x \equiv y \equiv \text{ 0 mod 3} )\\
  105. Обозначив x и y как x=3a и y=3b, получаем:
  106. 9a^2+9b^2 = 3z^2 \\
  107. 9a^2+9b^2 = 3z^2 \Rightarrow (z \equiv \text{ 0 mod 3} )\\
  108. Обозначив z как z=3c получаем: a^2+b^2 = 3c^2\\
  109. Таким образом, (a,b,c) = (x/3, y/3, z/3) - еще одно решение изначального уравнения.\\
  110. a^2+b^2=3c^2 .\\ \text{ повторяя вышеописанное, строим бесконечную} \\ \text{ цепочку решений, каждое из которых меньше предыдущего}\\
  111. \Rightarrow \text{ Получаем противоречие в связи с п-ом наименьшего числа в } \mathbb N
  112.  
  113. \end{block}
  114. \end{frame}
  115. %\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\%\\
  116. \begin{frame}{8x^4+4y^4+2z^4=t^4}
  117. \begin{block}{8x^4+4y^4+2z^4=t^4}
  118. Доказать, что это уравнение не имеет решений в целых числах при условии, что t \neq 0 \\
  119. Пусть (x,y,z,t): t \neq 0 \text{ - некоторое  целочисленное решение}\\
  120. Из уравнения видно, что t^4 \equiv\text{ 0 mod 2}\\
  121. (t^4 \equiv\text{ 0 mod 2}) \Rightarrow (t \equiv\text{ 0 mod 2}) \\
  122. Пусть t=2t_1, \text{получаем:}\\
  123. 8x^4+4y^4+2z^4 = t^4 \Rightarrow 8x^4+4y^4+2z^4 = 16t_1^4 \\
  124. 8x^4+4y^4+2z^4 = 16t_1^4 \Rightarrow 4x^4+2y^4+z^4 = 8t_1^4 \Rightarrow z=2z_1:\\
  125. 4x^4+2y^4+16z_1^4 = 8t_1^4\Rightarrow 2x^4+y^4+8z_1^4 = 4t_1^4 \Rightarrow y=2y_1:\\
  126. 2x^4+16y_1^4+8z_1^4 = 4t_1^4\Rightarrow x^4+8y_1^4+4z_1^4 = 2t_1^4 \Rightarrow x=2x_1\\
  127. 16x_1^4+8y_1^4+4z_1^4 = 2t_1^4\Rightarrow 8x_1^4+4y_1^4+2z_1^4 = t_1^4\\
  128. Получаем (x_1,y_1,z_1,t_1) = (x/2, y/2, z/2, t/2) \text{ -новое решение} \\
  129. Таким же образом из решения (x_1, y_1, z_1, t_1)\text{ можно получить}  \\
  130. Решение (x_2, y_2, z_2, t_2) = (x_1/2, y_1/2, z_1/2, t_1/2) \quad...
  131. \end{block}
  132. \end{frame}
  133.  
  134. \begin{frame}{8x^4+4y^4+2z^4=t^4}
  135. \begin{block}{}
  136. (x_2, y_2, z_2, t_2) = (x_1/2, y_1/2, z_1/2, t_1/2) = (x/4, y/4, z/4, t/4)\\
  137. \text{И так далее}\\
  138. \text{Таким образом, для }\forall n \in \mathbb N \text{ можно получить решение}\\ (x_n, y_n, z_n, t_n) =(x_{n-1}/2, y_{n-1}/2, z_{n_1}/2, t_{n-1})/2) = (x_{n-2}/4, y_{n-2}/4, z_{n-2}/4, t_{n-2}/4) = ... = (x/2^n, y/2^n, z/2^n, t/2^n) \\
  139. \Rightarrow \text{Откуда возникает противоречие в связи принципом}\\ \text{наименьшего числа во множестве натуральных чисел} \mathbb N\\
  140. Таким образом, уравнение 8x^4+4y^4+2z^4=t^4 \text{ не имеет решений в целых числах при t} \neq 0
  141. \end{block}
  142. \end{frame}
  143.  
  144. \begin{frame}{Иррациональность \sqrt2}
  145. \begin{block}{}
  146. Предположим, что \sqrt2 \text{ рационален и выражается некоторой несократимой дробью m/n}\\
  147. Следовательно, (m/n)^2 =2 \\
  148. Или: m^2 = 2n^2\\
  149. m^2 = 2n^2 \Rightarrow (m^2 \equiv \text{0 mod 2}) \Rightarrow (m \equiv \text{0 mod 2})\\
  150. Значит m=2k при некотором целом k:\\
  151. m^2 = 2n^2 \Rightarrow (2k)^2 = 2n^2 \Rightarrow 4k^2 = 2n^2 \Rightarrow 2k^2 = n^2 \\
  152. или n^2 = 2k^2 \\
  153. Теперь аналогичным образом можно убедиться в том, что
  154. n^2 = 2k^2 \Rightarrow (n^2 \equiv \text{0 mod 2}) \Rightarrow (n \equiv \text{0 mod 2})\\
  155. То есть n также чётное.
  156. Следовательно, дробь m/n можно сократить на два \Rightarrow \text{получаем противоречие в связи с тем},\\ \text{ что дробь  m/n изначально выбрана несократимой }\Rightarrow \sqrt2 \text{ - иррациональное число}
  157.  
  158. \end{block}
  159. \end{frame}
  160.  
  161.  
  162. \begin{frame}{x^4+y^4 = z^4}
  163. \begin{block}{Пифагорова тройка}
  164. комбинация из трёх целых чисел (x,y,z), удовлетворяющих уравнению Пифагора: x^2+y^2=z^2.
  165. \end{block}
  166. \begin{block}{}
  167. Уравнение x^2+y^2=z^2 \text{ однородно, тогда при домножении}\\
  168. \text{чисел x,y,z на
  169. одно и то же число p можно получить другую}\\
  170. \text{ пифагорову тройку : (xp)^2+(\text{yp})^2+(\text{zp})^2
  171. \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad}
  172. \end{block}
  173. \begin{block}{Примитивная пифагорова тройка}
  174. Если некоторая пифагорова тройка не может быть получена подобным образом, то она называется примитивной. То есть x,y,z - взаимно простые числа, НОД(x,y,z)=1
  175. \end{block}
  176. \end{frame}
  177.  
  178. \begin{frame}{x^4+y^4 = z^4}
  179. \begin{block}{Пифагорова тройка}
  180. В примитивной тройке (x,y,z) числа x и y имеют разную чётность, причём чётное делится на 4, а z — всегда нечётно\\
  181. Любая примитивная пифагорова тройка (x,y,z), где x — нечётно,\\
  182. а y — чётно, однозначно представляется в виде  
  183. ^.(m^2-n^2, 2mn, m^2+n^2)\\
  184. \text{для некоторых натуральных взаимно простых чисел m>n разной} чётности.
  185. \end{block}
  186. \end{frame}
  187.  
  188. \begin{frame}{x^4+y^4 = z^4}
  189. \begin{block}{x^4+y^4 = z^4}
  190. Докажем, что у этого уравнения нет решения в целых числах.
  191. Начнем с аналогичного доказательства для уравнения x^4+y^4=z^2\\
  192. Пусть (x,y,z) - наименьшее решение уравнения.\\
  193. У этого наименьшего решения числа x,y,z взаимно простые:\\
  194. Докажем это:\\
  195. Очевидно, что если какие-то два числа из (x,y,z) делятся на некоторое простое число p, то третье число также делится на p.
  196. Тогда^.\quad x=px_1,\quad y=py_1,\quad z=pz_1\\
  197. ^.p^4x_1^4+p^4y_1^4 = p^2z_1^2 \Rightarrow p^2x_1^4+p^2y_1^4 = z_1^2
  198.  \Rightarrow x_1^4+y_1^4 = z_2^2\\
  199.  x_1^4+y_1^4 = z_2^2 \\
  200. \end{block}
  201. \end{frame}
  202.  
  203. \end{document}
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top