Читатель measure_0 порекомендовал мне в прошлой заметке пройти тесты GRE subject tests. Какие именно он не уточнил, но я так решил, что видимо по моему направлению это должны быть mathematics и computer science. Скачал примеры тестов по обоим дисциплинам. Тест по математике оказался вроде простым (если не брать в расчет, что там на каждую задачу по 2 минуты, а задачи бывают и не только элементарные). А вот тест по Computer Science оказался для меня каким-то запредельно сложным и у 50% вопросов я даже толком не понимаю о чем там спрашивают. Проблемы у меня вызывают в основном вопросы, связанные с компьютерным железом и архитектурой операционных систем, хотя и в теоретических вопросах бывают какие-то загвоздки.

В общем оказалось, что Computer Scientist из меня дерьмовый, хотя сам тест наверняка простой (если предположить, что его уровень примерно такой же как и по математике, то он вообще должен быть элементарным; об этом так же свидетельствует уровень вопросов по алгоритмам или конкретному кодингу, в чем я худо-бедно разбираюсь).

Посмотрев тест у меня возникло желание как-то подтянуть свои знания в этой области, но возник обычный вопрос: что читать? Нужен список литературы, желательно составленный адекватными людьми. В Интернете я не смог найти чего-то подобного, обычно ограничивается все рекомендацией учебников по алгоритмам, но этого явно недостаточно.

В этой записи я предлагаю коллективными усилиями набросать список литературы по темам Computer Science с прицелом на GRE. Не потому что это какой-то супер-важный экзамен, а просто судя по всему он покрывает на мой взгляд довольно широкий и довольно правильный спектр тем, которыми хорошо бы овладеть быдлокодеру, который ожидает какого-то профессионального роста. Поэтому ниже я привожу темы, заявленные как необходимые для сдачи GRE, а комментаторам я предлагаю предлагать источники, по которым это можно изучать (книги, видеолекции, и подобное — главное чтобы это было возможно достать рядовому пользователю сети Интернет). В комментариях предлагаю указывать собственно источник, темы, которые он покрывает, и уровень — вводный/GRE/продвинутый. Заметку я буду обновлять по мере поступления новых ссылок на материалы.

Пока я просто выложил голый список, свои собственные соображения я тоже чуть позже выложу, а заодно сделаю перевод названий тем для тех, кто не знаком с английским (хотя по-хорошему английский должен идти в списке в любом случае первым). Просьба предлагать лишь те источники, которые вы сами хоть как-то просматривали, а не выдавать случайный набор книг из Гугла.

Собственно темы (извиняюсь за дебильную верстку — это почти копипаста, видимо позже поправлю):

SOFTWARE SYSTEMS AND METHODOLOGY
A. Data organization
• Data types
• Data structures and implementation techniques

B. Program control and structure
• Iteration and recursion
• Procedures, functions, methods and exception handlers
• Concurrency, communication and
synchronization

C. Programming languages and notation
• Constructs for data organization and program control
• Scope, binding and parameter passing
• Expression evaluation

D. Software engineering
• Formal specifications and assertions
• Verification techniques
• Software development models, patterns and tools

E. Systems
• Compilers, interpreters and run-time systems
• Operating systems, including resource management and protection/security
• Networking, Internet and distributed systems
• Databases
• System analysis and development tools

II. COMPUTER ORGANIZATION AND ARCHITECTURE
A. Digital logic design
• Implementation of combinational and sequential circuits
• Optimization and analysis

B. Processors and control units
• Instruction sets
• Computer arithmetic and number representation
• Register and ALU organization
• Data paths and control sequencing

C. Memories and their hierarchies
• Performance, implementation and management
• Cache, main and secondary storage
• Virtual memory, paging and segmentation

D. Networking and communications
• Interconnect structures (e.g., buses, switches, routers)
• I/O systems and protocols
• Synchronization

E. High-performance architectures
• Pipelining superscalar and out-of-order execution processors
• Parallel and distributed architectures

III. THEORY AND MATHEMATICAL BACKGROUND
A. Algorithms and complexity
• Exact and asymptotic analysis of specific algorithms
• Algorithmic design techniques (e.g., greedy, dynamic programming, divide and conquer)
• Upper and lower bounds on the complexity of specific problems
• Computational complexity, including NPcompleteness

B. Automata and language theory
• Models of computation (finite automata, Turing machines)
• Formal languages and grammars (regular and context-free)
• Decidability

C. Discrete structures
• Mathematical logic
• Elementary combinatorics and graph theory
• Discrete probability, recurrence relations and number theory

IV. OTHER TOPICS

• Numerical analysis
• Artificial Intelligence
• Computer graphics
• Cryptography
• Security
• Social issues

UPD: Эту заметку я все-таки не буду корректировать видимо. Лучше когда сам примерно буду иметь представление как правильно готовиться, сделаю отдельный удобный и адекватный обзор. Но пока все равно есть смысл дискутировать в комментариях.

Во время холивора в офисе, вспомнил интересную теорему. Но для начала нам понадобятся некоторые предварительные сведения. (Изложение в этой заметке довольно неформальное, но большего и не требуется для столь простого, но на первый взгляд удивительного результата).

Определение.  Счетное множество это такое множество, элементы которого можно расположить в последовательность.

Теорема. Множество вещественных чисел несчетно.

Вообще сказанное только что мной — не особо строго математически, но для нужд заметки строгая формальность нам и не потребуется. Гораздо более содержательно о множествах и в том числе о свойствах счетности я уже писал. По ссылке вы можете изучить это в деталях, включая доказательства.

Определение. Вычислимое число это такое, которое может быть вычислено на компьютере с любой степенью точности.

Поясню на пальцах (само определение тоже не формально, но, повторюсь, большего нам и не потребуется). Вот есть, например, наделавшее шума число «пи». Оно иррациональное и вообще. Но мы его можем вычислить по известным формулам с любой сколь угодно огромной степенью точности. Ну то есть понятно, что с ограниченной точностью, так как у нас есть ограничение хотя бы на количество компьютерной памяти, но это техническое ограничение, а не теоретическое. Поэтому число «пи» относится к вычислимым.

Может показаться, особенно программистам, что компьютер (или даже какой-нибудь супер-мега-компьютер которого не придумали еще) может вычислить любое число с любой точностью. А вот оказывается, что это не так.

Теорема. Существуют невычислимые числа, то есть такие числа, для которых невозможно написать программу, которая бы их вычисляла с любой степенью точности.

Доказательство. Каждому вычислимому числу соответствует какая-то программа, или даже не одна. Но множество всех программ — счетное (программы можно например перечислить хотя бы лексикографически, располагая их так же с учетом длины). То есть и вычислимых чисел существует лишь счетное множество. Однако само множество вещественных чисел — несчетное. Стало быть существуют невычислимые числа. Что и требовалось доказать.

(Обратите внимание, что это доказательство практически дублирует доказательство существования трансцендентных чисел).

Про невычислимые числа довольно легко можно доказать разные интересные штуковины. Например, любое алгебраическое число — вычислимое, однако вычислимыми являются так же и некоторые трансцендентные (то же «пи»), стало быть невычислимых чисел  меньше, чем трансцендентных.

Самым известным невычислимым числом является константа Хайтина: это вероятность того, что случайно выбранная программа (из множества всех вообще возможных программ) зависнет. Логично, что это число существует и вполне себе определено (хотя и зависит от конкретного языка программирования), но вот вычислить его невозможно. Сейчас я уже не буду приводить доказательство этого факта, так как там потребуется несколько более глубокое копание в теории, но постараюсь через какое-то время вернуться к теме и в том числе доказать данное утверждение (а заодно и парочку других интересных).

По наводке читателя.

В ряд стоит счётное число гномиков и смотрит в затылок друг другу (при этом есть последний гномик, за спиной которого уже никто не стоит, а он видит всех, кроме себя). На каждом гномике надета шапка, синяя или красная, и гномик видит цвета шапок всех впереди стоящих (но не своей собственной).

По сигналу гномики одновременно выкрикивают цвета (синий или красный), пытаясь угадать цвет своей шапки.

Существует ли стратегия (т.е. функция , определяющая цвет, который гномик должен выкрикнуть исходя из того, какую раскраску он видит впереди) придерживаясь которой ошибется лишь конечное число гномиков (для каждой раскраски гномиков из условия задачи)?

Вначале мне показалось, что задача некорректно сформулирована. Если гномики выкрикивают свои цвета одновременно, то у них пропадает какая-либо возможность обмениваться информацией, что меня и смутило. Я предположил, что вероятно кричат свои номера они все же не одновременно, а по порядку, и в этом случае задачу я почти решил: количество ошибок гномиков довольно простым способом возможно сильно сократить (сколь угодно сильно), хотя все равно ошибшихся гномиков будет бесконечное множество (если предположить, что они называют только цвет и не могут передать дополнительной информации). Вы можете попытаться решить задачу в таком варианте сами — это не сложно. Ну либо почитайте мой комментарий к прошлой заметке.

Однако оказалось, что при использовании аксиомы выбора задача все же решается. Сам я ее решить не смог, потребовав решения от задавшего задачу, и вот собственно это решение я теперь и привожу (сама задача изначально читателем как я понимаю была обнаружена в блоге «The everything seminar», перевод на русский здесь).

Фактически, когда на гномиков надеваются шапки, реализуется некоторая последовательность цветов. На множестве всех таких последовательностей введем отношение эквивалентности следующим образом: две последовательности будем считать эквивалентными, если они отличаются лишь конечным числом цветов. Далее в каждом классе эквивалентности выберем по одному представителю (то есть это должны сделать гномики). Мы имеем на это право именно по аксиоме выбора.

Теперь, когда на всех гномиков наденут шапки, каждый гномик может точно определить к какому классу эквивалентности принадлежит та последовательность шапок, которую он видит. Ну действительно же: гномики не видят лишь начало последовательности, а это всегда конечное число шапок, которое на принадлежность к классу эквивалентности повлиять не может, с учетом того, как мы их формировали. Тогда каждый гномик вспоминает, кого они выбрали представителем данного класса эквивалентности, и называет свой цвет исходя из того каким бы он был у представителя класса.

Очевидно, что представитель класса отличается от любой другой раскраски данного класса лишь конечным количеством цветов. Так что ошибку допустит лишь конечное число гномиков. Что и требовалось.

Аксиома выбора вообще замечательная, но эта головоломка с гномиками до сих пор на мой взгляд самый яркий пример ее применения (абсурдный конечно, как может показаться, но вполне себе занятный). Здесь был бы уместен рассказ и о других применениях аксиомы выбора, но его не будет, так как одного только подготовительного текста о лемме Цорна и базисе Гамеля будет довольно много, и он будет не слишком тривиален. Поэтому всех интересующихся отправляю за книжкой Верещагина и Шеня «Начала теории множеств». Она как раз во многом об этом, и понять ее сможет почти каждый, что важно.

Вот вам загадка: как можно разместить шар большего радиуса  в шаре меньшего радиуса?

Понятно, что в евклидовом пространстве этого сделать не получится — речь идет о том, чтобы построить такое метрическое пространство, в котором такое вложение возможно, ну и соответственно привести пример таких шаров.

Эту задачку выискал в «Элементарной топологии» Виро, Нецветаева, Иванова и Харламова. Задачка совершенно бесхитростная, но позабавила. Книжку кстати тоже рекомендую — она оказалась совсем для начинающих, но изложение хорошее, интересующимся математикой будет полезно почитать. Что примечательно — вполне подойдет даже для людей с минимальной подготовкой, хотя для них я бы начинал с «Наглядной топологии» Болтянского. А потом уже к этой переходил.

Подсмотрел у Вербицкого ссылку на чудесную статью: «Down with determinants!». Ну вряд ли для кого-то станет новостью, так как скорее всего мои читатели математической части сильно пересекаются с читателями Миши, но не продублировать ссылку не могу. Потому что поистине прекрасное.

Человек утверждает, что определители в курсе линейной алгебры должны вводиться в самый последний момент, и все изложение должно строиться без них. Что самое удивительное, читая статью понимаешь, что он на самом деле на 100% прав.

Я в принципе не являюсь ярым противником определителей: единственным объективным их недостатком является то, что они вычисляются плохо, но применять их в теоретических выкладках вроде никто не мешает. Да и наглядность вполне себе нормальная, если мыслить о них как о направленных объемах, вопреки тому, что обычно говорят. Однако из статьи удивительным образом действительно выясняется, что без определителей линейная алгебра и вправду оказывается гораздо проще.

Если кратко, то в принципе там все сводится к тому, что автор показывает каким образом любое комплексное векторное пространство разлагается в прямую сумму корневых подпространств, а оттуда уже начинает совсем элементарно выводить все остальное. Опираясь на алгебраическую и геометрическую кратность собственных значений, он вводит понятия минимального и характеристического многочленов соответственно, откуда самоочевидной становится теорема Гамильтона-Кэли.

Про нормальные операторы рассказывается довольно близко к стандартному изложению (как у Кострикина, например), вещественные пространства рассматриваются через комплексификацию вещественного оператора и применении там теорем для комплексных пространств.

Сам определитель в конце вводится как произведение собственных значений. Единственное, что не понравилось, так это вывод формулы определителя матрицы. Чрезвычайно сложно, правильнее все же выводить ее через кососимметрические формы, ну а там показывать, что это то же, что и произведение собственных значений. Ну сугубо мое ИМХО.

А в остальном считаю, что именно так и надо читать курс линейной алгебры, ту часть, где про линейные операторы. Удивлен, но даже в НМУ пока не взяли на вооружение. А при таком подходе самое необходимое о линейных операторах можно за одну лекцию рассказать даже самому тупому кретину в общем-то. Совершенно замечательный подход.

Еще кстати со временем убеждаюсь, что правильность методического подхода и красота доказательства главным образом определяется краткостью.  Чем короче изложение — тем лучше. Это чаще всего значит гораздо более высокий уровень абстракции, но оно себя каждый раз явно окупает. То есть в общем-то начинаю во многом принимать взгляды замечательного measure_01. Взрослею, видать. Хорошо.

UPD: Хотя если подумать по-лучше, то крутость подхода в общем-то не в отсутствии определителя, а в том, что на начальном этапе пространство раскладывается на корневые подпространства.

Не так давно встречались с товарищем (Илья, привет!), обсуждали разное, и в том числе зашел разговор о теории множеств. Говорили мы об аксиоме выбора и парадоксе Банаха-Тарского (тот что о разрезании шара и склеивания из его кусков двух таких же; об этом напишу как-нибудь потом, если эта заметка покажется интересной читателю). Плюс еще на фоне недавнего обзора popmath.ru подумалось мне, что для многих могут быть интересны разные и гораздо более простые утверждения теории множеств о равномощности и счетности, которые не изучаются ни в школе ни в институте на инженерных специальностях, но тем не менее вполне просты и занятны. Вот их-то я и изложу в надежде, что кто-то из нематематиков вникнет и заинтересуется наукой (математикам как обычно читать нет смысла).

Теорема. В единичном отрезке столько же точек, сколько и в единичном квадрате.

Доказательство. Точка единичного отрезка может быть представлена числом от нуля до единицы (). Точка единичного квадрата может быть представлена двумя числами от нуля до единицы, то есть своими координатами. Если представлять эти числа в десятичной записи, то каждой точке отрезка можно однозначно сопоставить точку квадрата, составив ее координаты из четных и нечетных цифр координат точки на отрезке.

В качестве примера, чтобы было понятнее, пусть мы взяли точку на отрезке с координатой . Тогда ей в соответствие мы поставим точку квадрата с координатами Понятно, что таким образом между точками отрезка и точками квадрата устанавливается взаимооднозначное соответствие.

А это и есть, что и требовалось доказать.

На самом деле в этой теореме есть еще что обсудить. Во-первых, не смотря на то, что во всех книгах по теории множеств говорят об отрезке и квадрате, воспринимать это буквально не стоит. Отрезок и квадрат — это понятия в первую очередь геометрические, они имеют длину, площадь, углы, расположение в пространстве. Мы же в этой теореме оперируем лишь с отдельными точками, совершенно игнорируя пространственные свойства этих фигур. Если же смотреть на них геометрически, то можно сказать, что квадрат состоит вообще-то из бесконечного числа единичных отрезков (можно например каждой точке сопоставить вертикальный единичный отрезок и мы получим тот же единичный квадрат), и таким образом получается, что хоть квадрат и имеет ровно то же количество точек, что и один единственный отрезок, но состоит он сам из бесконечного числа отрезков.

Кажущееся на первый взгляд парадоксом на самом деле является лишь следствием того, что в теории множеств мы игнорируем любые геометрические характеристики. Если бы например мы рассматривали квадрат не как множество отдельных точек с нулевыми размерами, а как объединение маленьких областей с ненулевой площадью (пусть даже очень маленьких), никаких парадоксов бы не случилось.

Можно посмотреть на это еще и с такой стороны. Рассмотрим функцию , которая действует на отрезке . Она делает ни что иное, как растягивает наш отрезок в два раза до отрезка , увеличивая его длину, но при этом легко заметить, что взаимнооднозначное поточечное соответствие между и сохраняется, стало быть точек там одинаковое количество.

Аналогичные рассуждения можно провести и для квадрата. Растянув или сжав квадрат в какое-то количество раз, мы получаем фигуру уже другого размера, но состоящую из того же самого количества точек. Причем не стоит думать, что это растяжение похоже на растяжение в физике, когда между «точками»-молекулами при растяжении увеличивается расстояние (в теории множеств понятие расстояния игнорируется). Если вспомнить нашу функцию, производящую растяжение в два раза, то можно сказать, что , и первоначальный отрезок остается совершенно равноценным подмножеством второго. То есть если более строго и менее интуитивно, то нельзя найти такое , чтобы .

Теперь давайте рассмотрим просто произвольную фигуру на плоскости (обозначим ее как ), и пусть эта фигура имеет для простоты ограниченные размеры, то есть она целиком заключена в некотором квадрате (обозначим ), может быть очень большом. Выберем теперь внутри фигуры еще какой-то квадрат , вероятно очень маленький. У нас получается такая цепочка вложений множеств: , причем и имеют одинаковое количество точек. Интуитивно ясно, что в не может быть больше точек, чем в , и не может быть меньше, чем в , а раз так, то с учетом того, что и имеют одинаковое количество точек, то и имеет то же самое количество точек.

На самом деле с учетом всего вышеозначенного, это не столь тривиальное утверждение, так как мы опять ссылаемся на «интуитивно ясно», что как мы уже видели далеко не всегда правомерно.  На самом же деле это утверждение в более общем виде составляет знаменитую теорему Кантора-Бернштейна, которую я тут не привожу и не доказываю, но вы можете найти ее где угодно.

Таким образом мы получили, что все ограниченные фигуры на плоскости имеют одинаковое количество точек (здесь есть тонкости, если мы будем выбирать фигуры, состоящие из отдельных точек, например, но для простоты мы не обращаем на это внимания — считаем только те фигуры, где можно выбрать хотя бы какой-то «сплошной» кусок, и разместить в нем маленький квадратик). Не сложно так же доказать (в качестве упражнения), что на самом деле не только все квадраты имеют одинаковое количество точек, но и вся плоскость (или вещественная ось) так же имеет ровно то же самое количество точек, так что мы можем распространить наше утверждение не только на ограниченные фигуры, но и вообще на произвольные.

Так же можно заметить, что точно так же, как мы строили соответствие между точками квадрата и отрезка, мы могли бы построить соответствие между точками отрезка и куба, либо даже -мерного куба (точки которого отличаются лишь тем, что имеют координат), и рассуждая аналогично, мы пришли бы к тому, что все -мерные фигуры (с той же оговоркой) имеют одинаковое количество точек. Возникает резонный вопрос, а существуют ли вообще множества, которые имеют число точек, отличное от количества точек в отрезке ? Мы на него ответим чуть ниже, а пока сделаю второе важное замечание по всему сказанному.

На протяжении всей заметки я усердно использовал формулировку «одинаковое количество точек». На самом деле формулировка такая не имеет права на существование. «Количество» — это некоторое число, а когда речь идет о бесконечности, то тут привычных нам чисел как таковых уже нет (есть трансфинитные числа, но это выходит за рамки заметки), и соответственно бесконечные величины сравнивать на равенство нельзя, хотя часто люди пытаются это делать во всяких книжках. Во многом из-за того, что в таком виде утверждения звучат более парадоксально, наверное (я использовал этот термин умышленно именно поэтому).

Чтобы проиллюстрировать это, рассмотрим известный «парадокс Галилея». Выделим в натуральном ряду подмножество точных квадратов (это не принципиально — можно рассматривать любое бесконечное подмножество, но по традиции принято говорить о квадратах), то есть чисел, из которых вычисляется квадратный корень (). С одной стороны очевидно, что , и понятно, что точных квадратов намного меньше, чем натуральных чисел. С другой стороны каждому натуральному числу мы можем сопоставить квадрат, и каждому квадрату натуральное число (), и таким образом получается однозначное соответствие между множествами натуральных чисел и рассуждая таким образом выходит, что натуральных чисел столько же, сколько и квадратов.

Это выглядит как парадокс лишь по той причине, что мы интуитивно пытаемся оценить количество элементов в бесконечных множествах, но подобное сравнение не имеет смысла.  Наличие взаимооднозначного соответствия между множествами, и то, что одно является подмножеством другого на самом деле никак не связаны друг с другом. Когда говорят о том, что во множествах «одинаковое количество элементов», подразумевается именно существование взаимнооднозначного соответствия между элементами, что научно называется «равномощностью».

Если множество равномощно натуральному ряду (другими словами возможно построить последовательность, которая будет содержать все элементы множества), то такое множество называют счетным. В качестве упражнения можно доказать, что объединение конечного или счетного числа конечных и счетных множеств будет конечно или счетно. Например множество целых чисел, которое может быть представлено как объединение так же является счетным. В частности, для любого счетного счетным будет являться так же и . Как частный случай этого очевидно, что так же счетные. Если выкинуть из часть элементов, то мы получим множество рациональных дробей . Это тоже счетное множество.

Теорема Кантора. Пусть дано произвольное множество . Множество всех его подмножеств более мощно, чем оно само.

Доказательство. Предположим обратное. Тогда существует взаимооднозначное отображение . Рассмотрим множество . Это множество само является подмножеством , а стало быть так как — отображение однозначное, найдется такой , что . Предположим, что . Тогда , что противоречит . Если предположить, что , то — опять противоречие. Стало быть исходное предположение о существовании взаимооднозначного отображения было неверным. Что и требовалось доказать.

Эта теорема имеет сразу множество следствий. Во-первых, сейчас очевидно, что множества могут быть сколь угодно «мощными». Хоть выше мы и показали, что любая геометрическая фигура в пространстве любой размерности имеет самое большее мощность отрезка , однако если мы возьмем множество всех подмножеств этого отрезка (то есть ), то это будет уже нечто более мощное.

Так же отсюда следует, что не существует «Множества всех множеств». Действительно, если бы оно существовало, то оно имело бы наибольшую мощность изо всех (обоснуйте). Но тогда взяв множество всех его подмножеств, мы получили бы еще более мощное множество, что противоречит тому, что мы имели «множество всех множеств» (я здесь неявно опираюсь на утверждение о том, что любые два множества сравнимы по мощности, то есть что из двух произвольных множеств хотя бы одно равномощно некоторому подмножеству другого — это тоже не тривиальное утверждение, которое нужно доказывать, но мы опустим этот момент, так как утверждение и так выглядит довольно правдоподобно, согласитесь).

Возникает еще вопрос: а является ли множество счетным? (Я выкинул граничные точки, но это не влияет на мощность — это так же не сложно доказать самостоятельно).  Чтобы понять это, вспомним, что числа из единичного интервала могут быть записаны как бесконечная дробь, причем нам будет удобнее рассматривать двоичные дроби. Например:

Рассматривая бесконечные двоичные дроби мы можем записать любое вещественное число. В такой записи любому числу нашего интервала соответствует набор позиций записи, в которых стоят единицы, то есть фактически некоторое подмножество натурального ряда. Отсюда сразу же следует, что чисел в интервале ровно столько же, сколько и подмножеств множества натуральных чисел, и это значит, что мощность выше, и это множество не является счетным.

Кстати, про множества той же мощности, что и принято говорить, что они имеют мощность континуума. Это так, к слову.

Собственно это все, что я хотел сегодня написать. Закончу небольшим количеством совсем стандартных примеров, дабы хоть как-то увязать все сказанное с реальным миром.

Определение. Алгебраическое число — это такое, которое является корнем некоторого многочлена с целыми коэффициентами. Тренсцендентное — это такое, которое не является корнем некоторого многочлена с целыми коэффициентами.

Например, число является корнем многочлена , и стало быть является алгебраическим числом. Вообще легко увидеть, что любые корни любых степеней будут алгебраическими числами, да и вообще если вдуматься, то алгебраических чисел оказывается очень до хрена. Возникает вопрос: а не являются ли алгебраическими вообще все числа, то есть существуют ли трансцендентные в принципе?

Теорема. Трансцендентные числа существуют.

Доказательство. Множество всех многочленов с целыми коэффициентами — счетное (так как коэффициентов счетное число — строгие выкладки вам будет не сложно провести самостоятельно, надеюсь). У каждого многочлена может быть лишь конечное количество корней, откуда видно, что и общее количетсво корней многочленов (то есть алгебраических чисел) — не более чем счетное множество. Однако множество вещественных чисел — несчетное, стало быть всего чисел сильно больше, чем алгебраических. Стало быть, трансцендентные числа существуют.

Ну и еще пара простых примеров.

Теорема. На вещественной оси можно выбрать не более чем счетное число непересекающихся интервалов.

Доказательство. В каждом интервале можно выбрать рациональную точку, а рациональных точек всего счетное множество.

Теорема. Вещественнозначная функция может иметь не более чем счетное множество строгих локальных экстремумов.

Доказательство. Каждый экстремум — это максимум или минимум на каком-то интервале. Поскольку интервалов не более чем счетное число, то и экстремумов не более чем счетное число.

Теорема. Монотонная функция имеет не более чем счетное число разрывов.

Доказательство. Почти полностью аналогично прошлому случаю. Монотонность здесь важна, так как без нее разрывы могут быть и такие, когда с одной или с двух сторон от разрыва, функция стремится к бесконечности. В случае же монотонности, в точке разрыва с обоих сторон должен существовать конечный предел, а стало быть и некоторый интервал, на котором функция непрерывна.

Отсюда на самом деле можно получить десятки всяких почти практичных следствий, вроде того, что ограниченная монотонная функция всегда интегрируема по Риману (в силу счетности числа разрывов), но подобные штуки мне мало интересны. Скучные потому что. А в следующий раз на эту же тему чего-нибудь интересного изложу, если не забуду, и если мозги не отобьют.

В комментариях попросили попиарить блог popmath.ru, ну а мне и не сложно.

Хотя честно сказать, ощущения у меня от блога смешанные. Мне сложно оценить его адекватно, так как все, что там пишут, для меня уже давно пройденный этап, но многие вещи кажутся странными. Например, я совершенно не понимаю зачем вводить на том уровне, что пишется блог, аксиоматизацию теории множеств. Это скучно и не нужно, если только они не планируют лезть в дебри вроде континуум-гипотезы. А они я так понял еще собираются строго строить теорию натуральных чисел.

На мой взгляд на начальном уровне абсолютно все, включая всякие интересные и знаменитые парадоксы, можно объяснить и без этого. Однако авторы почему-то упорно наводят формальщину с кванторами. Лучше бы вместо этого рассказали о теореме Кантора и почему не существует «Множества всех множеств», упомянув заодно про категории, если уж рассказываете о множествах.

Или цикл статей про алгебраические структуры. Во-первых, куча ненужной совершенно информации. Чего только стоит фраза: «Как класс, группа содержит такие виды структур (элементы), как группоид, квазигруппа, лупа, моноид и т.п.». Ну и зачем это? Причем я сомневаюсь, что многие из этих определений сходу вспомнят даже профессиональные математики.

Во-вторых, нет никакого практического выхлопа. Куча слов о том, что «математика — красиво и просто»,  но из статей я этого совершенно не вижу. Рассказали про изоморфизмы, но нафиг они нужны — нет. Есть два банальных примера, но они совершенно не мотивируют. Понятно, что изоморфизмы интересны с точки зрения разных там геометрий, например, но только прежде чем об этом говорить, нужно чтобы читатель уже владел значительным количеством содержательных примеров.  На начальном же уровне я бы рассказывал скорее про гомоморфизмы и факторизацию — отсюда сразу можно вывести всякие интересные и неочевидные свойства, заодно рассказав про нормальные подгруппы и идеалы. А изоморфизм был бы частным случаем.

В-третьих, при явном уклоне в формализм, сами определения вводятся не особо-то строго и не самым явным образом. Например:

Главное требование изоморфизма это существование биективного отображения (биекции) одного множества на другое такого, что сохраняются отношения между элементами. Т.е. отношение между прообразами такое же, как и между образами.

Лично мне такие формулировки взывают мозг, а там такого через слово, и это не  самый страшный пример (двумя абзацами выше все намного хуже, но с формулами). И это на фоне слов о том, что «Математика — просто!». При этом блог уже пишется какое-то время, а никакого содержательного результата еще не изложено — только определения. Это не правильно. Блог продолжает классическую традицию принятую в России: «Сиди зубри, пидор, а зачем это надо потом поймешь». Это не верно и убивает мозг. Математику имеет смысл изучать только для того, чтобы открыть для себя что-то содержательно новое, а не напичкать мозг определениями.

Пишу об этом я в общем-то не для того, чтобы обосрать, а для того, чтобы указать авторам на слабые места и сделать лучше. В комментариях там вообще есть благодарные отзывы, так что вероятно новичкам блог и будет полезен.

Хотя конечно комментарии они по большому счету ничего не значат — в моем блоге тоже до хера благодарных отзывов, но очень сомнительно, что это что-то означает. В личной-то жизни все равно говно.

Как-то раз сидели мы в вегетарианском кафе с одним молодым (на порядок моложе меня) и талантливым математиком. Обсуждали конечно же математику и секс (кстати, на написание статьи «Как пойти к простиутке» во многом сподвиг меня именно он в тот вечер). Один из вопросов, который обсуждался — это список тем и книг, с которыми должен быть знаком начинающий математик на базовом уровне. Под базовым уровнем считается четвертый курс математической специальности.

Поскольку я сам изучаю математику на 90% самостоятельно, я обратился к моему товарищу за советом: что изучать? что читать?  И он накидал мне список. Он попросил меня не упоминять его имени и фамилии в блоге, но список позволил опубликвать. По этому списку хочется заметить, что он ценен тем, что составлен действительно разбирающимся человеком, который понимает то что в этих книгах написано (часто списки составляются людьми невменяемыми). Так же очень ценно, что это довольно свежий взгяд молодого человека, а не старика-профессора, который математику воспринимает уже не так, как обычный студент. Так же нет ретроградства в виде рекомендаций учебников алгебры Гельфанда и Ван дер Вардена, которые может быть и хорошие книги, но уже давно появились гораздо более удачные учебники, о которых старшее поколение может просто не знать.

Ну и от себя я добавлю, что сам список на мой взгляд не полный. Не хватает теории графов, комбинаторики, теории вероятностей и прочих вещей, с которыми математик все же должен быть знаком по моему убеждению — список в этом плане сильно отражает научные интересы моего товарища. Я его публикую в том виде, в каком он его составил без каких-либо правок.

Алгебра

Базовый уровень:

Теория представлений:

Коммутативная алгебра:

Гомологическая алгебра:

Анализ

Базовый уровень:

Линейный Функциональный Анализ:

Более продвинутый анализ (эллиптические и дифференциальные операторы, расслоения и т.д., переход к языку пучков, C*-алгебры, KK-теория):

Алгебраический анализ:

Топология

Базовый уровень:

Алгебраическая топология:

K-теория:

Теория узлов:

Геометрия

Базовый уровень:

Комплексная геометрия:

Введение алгебраическую геомтерию:

Абелевы многообразия и теория тэта-функций

Дифференциальная геометрия

Симплектическая и пуассонова геометрии

Теория деформаций

Теория графов

Я потихоньку читаю (проглядываю) списки книг, которые вывесили в ЛЖР-сообществе НМУ, в том числе дабы ничего не упустить смотрю и в книги для совсем начинающих.

Ну там много таких книг, но особенно мне понравилась книга Алексеева «Теорема Абеля в задачах и решениях». Книга на мой взгляд просто изумительная. Излагаемый в книге материал я изучал по разным взрослым учебникам в течении долгого времени и давалось мне это честно сказать не особо просто. Главным образом из-за того, что я к теореме Абеля шел не напрямую и в гораздо более абстрактных терминах. А тут вдруг оказалось, что теорему Абеля вполне может осилить любой даже средний школьник. Книга действительно написана очень просто и понятно.

Сейчас очень жалею, что не прочитал этой книги еще очень давно. В идеале она должна была бы быть вообще первой, прежде чем начинать заниматься чем-либо. Жаль, что не сложилось, а вместо этого я пару лет читал дерьмище от Ильина и Позняка, не зная о существовании альтернатив. Просто безумно жалко. Мог бы ведь стать математиком, а теперь хер — старый уже.

Я уже приводил доказательство того, что простых чисел бесконечно много. Тогда я использовал основные алгебраические структуры, а сегодня проделаю то же самое, но на языке топологии.

Для тех, кто не в теме, я сформулирую аксиомы тополгического пространства:

Топологическим пространством называется множество , с выделенной системой подмножеств , называемых открытыми множествами, которые удовлетворяют следующим свойствам:

1. Пустое множество и множество являются открытыми (, ).

2. Объединение любого числа открытых множеств — открыто.

3. Пересечение конечного числа открытых множеств — открыто.

Подмножество топологического пространства называется замкнутым, если дополнение к нему — открыто. Для замкнутых множеств справедливы следующие очевидные аналоги свойств открытых множеств:

1. Пустое множество и множество являются замкнутыми.

2. Объединение конечного числа замкнутых множеств —  замкнуто.

3. Пересечение любого числа замкнутых множеств — замкнуто.

Я частично объяснял эти определения в заметке про непрерывность, приводя мотивировку почему здесь фигурируют слова «конечного» и «любого» и почему они важны. Это конечно не особо полноценный обзор, но для наших целей ничего другого кроме аксиом и определений и не понадобится.

Итак, будем рассматривать множество целых чисел , с заданной на нем топологией следующим образом: подмножество считается открытым, если оно пусто, либо если вместе с любым элементом оно содержит подмножество для некоторого .

Легко проверить, что заданные таким образом открытые подмножества действительно удовлетворяют всем аксиомам топологического пространства. Так же полезно отметить тот факт, что все открытые множества, кроме пустого, содержат бесконечное число элементов, и что любое множество является замкнутым, поскольку оно является дополнением к открытому множеству

Множество простых чисел мы будем обозначать через . Поскольку любое число, содержащее в качестве множителя простое число содержится в , то множество всех целых чисел можно представить следующим образом:

Множество не входит в объединение множеств справа, так как единица не имеет простых множителей.

Теперь если предположить, что множество простых чисел конечно, то объединение справа получается замкнутым множеством, и тогда множество оказывается открытым как дополнение. Но это противоречит тому, что как мы выяснили любое непустое открытое множество в данной топологии бесконечно.

Отсюда следует, что множество простых чисел бесконечно.

К топологии конечно все изложенное никакого отношения не имеет, но забавно. Если не иметь достаточной сноровки (как было со мной года два назад, когда я натолкнулся на это доказательство), то это сносит крышу.