Введение
Замечательный американский математик Пол Халмош сказал: “Лучший (и единственный) способ изучать математику — это ее создавать”. Он, конечно, не имел в виду, что школьники и студенты должны доказывать неизвестные науке теоремы. Идея в другом: чтобы научиться доказывать новые для человека утверждения, намного эффективнее пытаться различные утверждения доказывать, чем читать, слушать и выучивать чужие доказательства. Замечательно, что человек, научившийся решать новые математические задачи, которые «непонятно-как-решать», потом сможет использовать это умение и в жизни, если он не станет математиком-исследователем, а будет программистом, или даже займется делом, далеким от математики.
В России такой подход использовался в работе математических кружков — и студенческих, и аспирантских кружков, таких как «Школа Лузина» — «Лузитания», и кружков для школьников.
В эффективность такого подхода верил Николай Николаевич Константинов, создавший в нашей стране систему математических школ и классов, в которой выросли десятки тысяч и математиков, и не математиков.
Мне представляется особенно важным продолжить данную традицию вместе со студентами мехмата. Это — очень существенно для нашей работы в курсе «Введение в математическую логику и теорию алгоритмов». На лекциях мы будем обсуждать условия задач и подходы к их решению. Необходимые определения и условия задач Вы можете найти на сайте в интернете, адрес мы вам предоставим. Там же есть и подсказки и решения задач, но как вы уже поняли, намного лучше пытаться решать задачи самим. Получив очередную задачу, вы пытаетесь ее решить, видите, в чем (для вас) трудность. Пытаетесь преодолеть эту трудность, если не получаетесь, читаете подсказку и пробуете ее применить. Если опять не получается, читаете и пытаетесь понять решение. И в последнем случае ваше решение будет иметь для вас большей смысл, поскольку будет, очень вероятно, включать ответы на вопросы, которые у вас уже возникли.
Еще несколько общих замечаний, относящихся к изложению в курсе. Использование специальных математических символов в математических текстах является одним из великих достижений (изобретений) математики, в частности, это существенная часть алгебры. Естественно, мы эти символы используем автоматически, например, когда говорим «из всякого действительного числа можно извлечь квадратный корень» (ложное высказывание), то немедленно появляется желание сказать «из всякого действительного числа x можно извлечь квадратный корень». В курсе сделана попытка вводить те или иные символы, только если они нужны и действительно приводят к прояснению или упрощению текста. Неожиданным для авторов образом оказалось, что количество употреблений символов при таком подходе оказалось очень небольшим, а тексты упростились и сократились. При этом мы понимаем, что для чтения и понимания текста читатель (студент) может привлекать символы, чтобы обозначать встречающиеся объекты и операции. Разумеется, у преподавателей против этого нет никаких возражений и мы будем рады обсуждать решения задач, где используется произвольная понятная автору решения и объясняемая им символика. Мы используем символ ■ для обозначения конца доказательства, определения и решения задачи, там, где нам такое обозначение кажется полезным.
Символ ⇌ означает «есть по определению» или что-то аналогичное.
Еще одно замечание, относящееся к русскому математическому языку, используемому в курсе. Оно относится к слову «если». Когда мы говорим «если натуральное число делится на 6, то оно делится на 2», то это утверждение верно для любого натурального числа, например, для числа 5. Когда мы говорим «назовем натуральное число простым, если оно делится только на единицу и на само себя», то «если» мы понимаем, как «тогда и только тогда» «если и только если»: число 5 мы «простым» называем, а число 6 «простым» не называем, и такое словоупотребление мы считаем вытекающим из данного определения.
В курсе есть понятия (центральное из них, конечно, это истинность высказывания в структуре), которые используются по ходу дела много раз. Нам кажется полезным напоминать определения по ходу дела, поэтому не удивляйтесь, если определения будут повторяться.
У вас будет возможность рассказывать свои решения преподавателям курса. Детали процесса вы обсудите на ближайшем занятии. Среди задач есть совсем простые – «на понимание», они выделены значком У – упражнение. Значком Д выделены дополнительные задачи. Мы не ожидаем, что вы их решите, но попытки решения и обсуждение этих попыток могут оказаться полезными, иногда – стать темой вашей дальнейшей научной работы.
1. Наивная теория множеств
Основными видами математической деятельности являются: вычисление, доказательство, определение. Математическая логика изучает математическую деятельность математическими средствами. Основными понятиями будем считать множество и одноместное отношение «быть элементом множества». Наше изложение будет использовать то, что используется в большинстве математических курсов — “Наивную теорию множеств”. Мы обсудим вопрос о формализации теории множеств (и тем самым — большей части математики) в одной из последующих лекций. Там будет определена Аксиоматическая теория множеств. Следующие определения и термины, в основном, известны вам из других курсов.
В следующих задачах считается, что найдется человек, который одновременно и математик и шахматист.