26032001 (Курс лекций)

26 марта 2001 г.

Закончим доказательство утверждения.

. Предположим, что , причем . Покажем, что не представляется в виде полинома. Допустим, что она представима полиномом: . Поскольку , то . Но тогда, т.к. , имеем , что противоречит необратимости по модулю (например, мы можем домножить все равенство на и получить неверное ). Доказательство закончено.

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

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

Утверждение. Если , то в существует замкнутый класс, не имеющий свободного порождающего семейства (базиса).

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

Приведем пример класса, имеющего счетный базис.

Пусть , , и - искомый класс.

Утверждение. Для любого функция не выразима формулой над .

Доказательство. От противного.

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

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

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

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

Утверждение. В ( ) континуум замкнутых классов.

Напомним, что предполных классов всего лишь конечное число при любом .

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

Подграф данного графа – это такой граф , что , и ( - это ограничение на , т.е. для любого ). При этом необходимо .

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

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

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

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

Утверждение. В (трехмерном евклидовом пространстве) для любого графа имеется правильная геометрическая реализация.

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

Определение. Разбиение ребра – это переход от графа , , , , к графу , , , где при , .

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

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

Приведем несколько примеров графов.

Полный граф порядка 5 – это граф, состоящий из пяти вершин, каждые две из которых соединены ровно одним ребром (всего 10). Его обозначают .

Граф – это .

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

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

Утверждение. В каждом конечном связном графе можно выделить подграф, который содержит все вершины и является деревом.

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

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

Лемма. В любом конечном ориентированном графе без ориентированных циклов есть вершина, из которой не выходит ребро.

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