Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

5.4. ФУНКЦИИ

111

ми

. Классы не могут быть элементами других классов, и тем более

множеств. Таким образом, классы рассматриваются скорее как сокра-

щения, а не как объекты. Доказано, что добавление классов к обычной

теории множеств ничего существенно не меняет.

Есть интересный критерий, позволяющий свести вопрос, является

ли данная совокупность множеством, к этому же вопросу для уже из-

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

множестве, сама является множеством. Если избавиться от функции, то

критерий примет следующий вид:

Аксиома подстановки.

Если X — множество, и ∀x(x ∈ X ⇒

∃1y A(x, y), то

{y | ∃x(x ∈ X & A(x, y))}

также множество.

Контрапозицией аксиомы подстановки получаем, что, если

X — класс,

ϕ — инъективное отображение X в Y , то Y — также класс.

Данный критерий называется аксиомой по той причине, что,отчаяв-

шись найти внешние критерии того, какие формулы могут определять

множество, математики начала XX века решили просто постулировать

возможность построения тех множеств, которые широко вошли в мате-

матическую практику и не приводят к известным парадоксам. Так воз-

никла аксиоматическая теория множеств. В настоящее время абсолют-

ным большинством математиков принята формальная система теории

множеств ZF (Цермело-Френкеля). В ней постулируются следующие

аксиомы (помимо аксиомы подстановки)

Пустое множество:

∃X ∀x x /∈ X

Двухэлементное множество:

∀x, y ∃X ∀z(z ∈ X ⇔ z = x ∨ z = y)

В традиционной логике понятие класса означало совокупность объектов, удовлетво-

ряющих данному свойству. Г. Кантор, создатель теории множеств, ввел новое понятие

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

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

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

112

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Объединение множества множеств:

∀X ∃Y ∀y(y ∈ Y ⇔ ∃x(x ∈ X & y ∈ x))

(это множество обозначается просто

)

Множество всех подмножеств:

∀X ∃Y ∀Z(Z ∈ Y ⇔ ∀x(x ∈ Z ⇒ x ∈ X))

Аксиома бесконечности:

Существует множество, у которого есть инъекция самого в себя.

∃X ∃f





f : X → X &

∀x, y(x ∈ X & y ∈ X & f(x) = f(y) ⇒ x = y) &

∃y(y ∈ X & ∀x(x ∈ X ⇒ f (x) 6= y))





Аксиома выбора:

∀X



∀Y (Y ∈ X ⇒ ∃y y ∈ Y ) ⇒

∃f(f : X →

X & ∀Y (Y ∈ X ⇒ f(Y ) ∈ Y )



Аксиома объемности:

∀X, Y (∀z(z ∈ X ⇔ z ∈ Y ) ⇒ X = Y )

Если множества имеют одни и те же элементы, они равны.

Аксиома регулярности:

∀X ∃x (x ∈ X &

∃y(y ∈ x & y ∈ X))

Суть ее в том, чтобы запретить ситуации вида x ∈ x. Эта аксио-

ма служит примером технических улучшений, необходимых в ка-

ждой новой теории для ее логического замыкания.

Аксиомы теории множеств,как выяснилось, не слишком удобны для

представления некоторых структур, возникающих в современных обла-

стях математики, в частности, в теории категорий. Но они по крайней

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

5.4. ФУНКЦИИ

113

что означает то или иное утверждение классической математики

. И,

что еще важнее, они дали возможность строго поставить вопрос о не-

разрешимости некоторых проблем традиционной математики.

Функции, аргументом которых служат натуральные числа, обычно

называют последовательностями и обозначают несколько по-другому:

саму функцию

)

n∈N

, конкретное значение a

. В данной книге мы,

следуя логической традиции, несколько расширяем понятие последова-

тельности.

Определение 5.4.7. Конечной последовательностью

называется отобра-

жение множества

{i | i ∈ N & i > 1 & i 6 k}

— ее длина.

Бесконечной последовательностью

называется отображение множества

либо

N \ 0

Конечная последовательность

b : {i | i ∈ N & i > 1 & i 6 k} → X

явля-

ется началом конечной последовательности

a : {i | i ∈ N & i > 1 & i 6 l} → X,

если

l > k

∀i(1 6 i & i 6 k ⇒ a(i) = b(i))

Конечная последовательность

b : {i | i ∈ N & i > 1 & i 6 k} → X

явля-

ется началом бесконечной последовательности

a : N \ 0 → X

, если

∀i(1 6 i & i 6 k ⇒ a(i) = b(i))

Последовательность

— это конечная либо бесконечная последователь-

ность.

Отношение вхождения для кортежей обобщается на последователь-

ности следующим образом:

Определение 5.4.8.

Последовательность

содержит конечную после-

довательность

длины

, если существует такое

, что

∀i(1 6 i & i 6 k ⇒ α(i + n) = β(i)).

И, наконец, обратим внимание на иное обозначение функций, по-

явившееся по аналогии с последовательностями и употребляемое в том

случае, если область определения фиксирована и нас интересуют в пер-

вую очередь значения функции, а не взаимосвязь между аргументами и

Как Вы чувствуете из этой оговорки, появилась и неклассическая математика, но

объем произведенного в классической настолько больше, что многие и не подозревают о

существовании существенно других интерпретаций. Примерно так же сейчас в России

многие, говоря ‘компьютер’, понимают IBM PC.

114

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

значениями. Это — запись функции как семейства значений:

)

i∈I

Аргумент называется в данном случае индексом,результат — i-тым чле-

ном семейства.Чаще всего как семейства представляют функции,значе-

ниями которых служат объекты высших типов: множества либо другие

функции.

Семейства, в частности, полезны для обобщения операций на беско-

нечное число аргументов, если это возможно. Например, в теории мно-

жеств обобщаются на любое семейство аргументов операции объедине-

ния, пересечения, прямой суммы, прямого произведения.

Определение 5.4.9.

i∈I

= {x | ∃i(i ∈ I & x ∈ X

)}

i∈I

= {x | ∀i(i ∈ I ⇒ x ∈ X

)}

i∈I

= {(i, x) | i ∈ I & x ∈ X

}

i∈I

= {f | f : I →

i ∈ X

& ∀i(i ∈ I ⇒ f(i) ∈ X

)}

Будьте осторожнее с обобщением операций на бесконечное семей-

ство операндов! Часто они просто не обобщаются, как, например, алге-

браические операции над действительными числами, либо теряют при

обобщении полезные свойства.

5.4. ФУНКЦИИ

115

Упражнения к § 5.4

5.4.1. Когда тройка

X♣Y

= hX, Y, X × Y i является функцией? Когда

данная функция является инъекцией? Сюръекцией? Биекцией?

5.4.2. Имеются ли функции из

∅ в непустые множества? Какие? А нао-

борот?

5.4.3. Почему доказательство теоремы Кантора-Шредера-Бернштейна

не может быть использовано для составления программы, пре-

образующей две инъекции в биекцию, даже для счетных множеств?

5.4.4. Дайте доказательство теоремы Кантора-Шредера-Бернштейна для

конечных множеств, подходящее для построения с его помощью

преобразователя программ: процедуры, трансформирующей две

данные функции-инъекции в одну — биекцию

5.4.5. Какое из равенств выполнено?Для невыполненного укажите,есть

ли вложение в одну из сторон.

f hXi ∪ f hY i = f hX ∪ Y i, f hXi ∩ f hY i = f hX ∩ Y i.

5.4.6. Является ли любая ретракция сюръекцией? А накрытие — инъ-

екцией?

5.4.7. Верно ли, что

X < Y и Y < X влечет, что X и Y равномощны?

5.4.8. Каковы взаимоотношения между

X 6 Y и Y < X?

5.4.9. Докажите, что если

X — счетно, то и множество всех кортежей

∞

также счетно.

5.4.10. Студент Гениалькис предложил определить конечное множество

как множество, представимое в виде

, . . . , x

}. Что Вы ска-

жете по этому поводу?

5.4.11. При обсуждении предыдущего определения студент Интеллек-

туалов выдвинул свое:

Будьте внимательнее! Разве вы еще не поняли, что автор — ехидна?

116

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Класс конечных множеств — транзитивное замыкание

класса, содержащего ∅и все множества вида {x}(чтобы

снять все замечания, он определил их как множества,

удовлетворяющие следующему условию:

∃x(x ∈ X & ∀y(y ∈ X ⇒ x = y)) )

относительно операции объединения двух множеств.

Что Вы скажете по поводу этого определения?

5.4.12. Студент Рессель заявил, что на самом деле лучшее определение

конечных множеств следующее:

Конечное множество — множество

X, неравномощное

никакому

Y ⊂ X & Y 6= X.

А Вы что здесь скажете?

5.4.13. Студентка Программистская заявила, что все предыдущие опре-

деления никуда не годятся, поскольку ссылаются на множество

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

ные множества так, как делают все нормальные программисты —

по индукции.

∅ — конечное множество.

2. Если

a — объект, то {a} — конечное множество.

3. Если

X и Y — конечные множества, то X ∪ Y — конечное

множество.

А что Вы здесь скажете?

5.4.14. Определите верхнюю и нижнюю границы мощности множества

всех последовательностей действительных чисел

5.4.15. Покажите, что нет сюръекции

X на

5.4.16. Определите,а что же такое подпоследовательность бесконечной

последовательности?

5.5. ФАКТОР-МНОЖЕСТВА

117

§ 5.5. ФАКТОР-МНОЖЕСТВА

В предыдущем параграфе у нас частенько фигурировало слово ‘мощ-

ность’. Но мы стыдливо умалчивали, что это такое. На самом деле хо-

рошего математического определения мощности множества просто нет,

наиболее прозрачной была попытка Кантора определить мощность как

множество всех равномощных друг другу множеств, но из-за парадокса

Кантора и несуществования универса таких множеств просто не суще-

ствует (за исключением мощности пустого множества). Кантор в своем

определении следовал сложившейся к концу XIX века математической

традиции, когда уже был хорошо разработан способ перевода отноше-

ний эквивалентности в отношения равенства через посредство фактор-

множества.

Условия, накладываемые на отношение эквивалентности, на самом

деле минимальный вариант выразимых на логическом языке свойств ра-

венства. А именно:

Определение 5.5.1. Отношением эквивалентности

называется рефлек-

сивное, транзитивное и симметричное отношение

Таким образом, класс эквивалентности элемента x есть R hxi. Отно-

шение эквивалентности R обладает, в частности, следующими важны-

ми свойствами:

Предложение 5.5.1. 1.

∀x ∀y(R hxi = R hyi ∨ R hxi ∩ R hyi = ∅).

∀x(x ∈ Dom R ⇒ x ∈ R hxi).

∀x ∀y(x ∈ Dom R & y ∈ Dom R ⇒ (R hxi = R hyi ⇔ (x, y) ∈

R)).

Доказательство. Пункт 3. Если образы равны, то, по рефлексивности,

y ∈ R hyi, но R hxi = R hyi, значит, (x, y) ∈ R. Если, наоборот, (x, y) ∈

R, то из (y, z) ∈ R по транзитивности следует (x, z) ∈ R, а из (x, z) ∈ R

по симметричности и транзитивности следует (y, z) ∈ R.

Пункт 1. Пусть имеется такое

z, что (x, z) ∈ R & (y, z) ∈ R. То-

гда, по симметричности, (x, z) ∈ R & (z, y) ∈ R. По транзитивности

Поскольку все эти понятия применяются у нас лишь к отношениям на некотором

множестве

X, отсюда следует, что отношение эквивалентности является подмноже-

ством некоторого

118

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

(x, y) ∈ R, и по пункту 3 образы равны. Значит, если они пересекаются,

то они совпадают

Последний пункт очевиден.

Итак, отношение эквивалентности разбивает свою область опреде-

ления на непересекающиеся классы эквивалентности.

Определение 5.5.2.

Класс эквивалентности

элемента

— его образ

R hxi

, то есть

{y | (x, y) ∈ R}.

Фактор-множество

— множество классов эквивалентности всех

элементов множества

по отношению эквивалентности

≡

3. Если

— функция из множества

с заданным на нем отноше-

нием эквивалентности

в множество

с заданным на нем от-

ношением эквивалентности

, то

называется

согласованной с

эквивалентностью

, если

∀x ∀y(x ∈ X & y ∈ X & (x, y) ∈ R

⇒ (f (x), f(y)) ∈ R

Таким образом, функция согласована с эквивалентностью, если

она по эквивалентным аргументам выдает эквивалентные значе-

ния.

4. Отношение эквивалентности

на множестве

X сильнее

отноше-

ния эквивалентности

на том же множестве, если

⊂ R

Класс эквивалентности x относительно R обозначается ˆx

и еще

чаще просто ˆx, поскольку обычно одновременно рассматривается лишь

одно отношение эквивалентности.

Предложение 5.5.2. 1. Отношение равенства — сильнейшее из от-

ношений эквивалентности.

То, что последующий пункт доказан раньше предыдущего и использован в дока-

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

порядок пунктов в теореме не играет с логической точки зрения никакой роли, посколь-

ку конъюнкция коммутативна. Зато в доказательстве порядок играет важнейшую роль,

поскольку не допускается ссылка на то, что еще не обосновано.

5.5. ФАКТОР-МНОЖЕСТВА

119

2. Отношение R = X

— слабейшее из отношений эквивалентно-

сти.

3. Предикат

P (x) согласован с эквивалентностью ттт

∀x ∀y((x, y) ∈ R ⇒ (P (x) ⇔ P (y))).

Очевидно.

Отношение эквивалентности часто записывают как бинарную опе-

рацию, похожую по внешнему виду на равенство, пользуясь для этого

значками типа ∼, ',

∼

, ≡, . Полного единообразия здесь быть и не

должно, поскольку на одной и той же структуре часто рассматриваются

несколько отношений эквивалентности. Если отношение эквивалентно-

сти обозначается бинарной операцией

, то фактор-множество X по от-

ношению

обозначается X/

=. Класс эквивалентности элемента a по

рассматриваемому в данный момент отношению эквивалентности часто

обозначается ˆa.

Если функция согласована с отношением эквивалентности R (

), то

можно определить функцию из фактор-множества с теми же значения-

ми:

=(ˆx)

= f(x). (5.16)

Обратим Ваше внимание на одну тонкость.Мы определили фактор-фун-

кцию, не прибегая к несколько неаккуратной конструкции, часто ис-

пользуемой в данном случае: не выбирая произвольного элемента из

ˆx, так что ее определение ни от каких сомнительных принципов тео-

рии множеств не зависит. Но, конечно же, отношение, заданное в (5.16),

является функциональным лишь тогда, когда f согласована с эквива-

лентностью.

Пример 5.5.1.

Фактор-множество

по отношению равенства — мно-

жество всех

{{x} | x ∈ X}

. Таким образом, здесь мы просто рассажи-

ваем все элементы по отдельным клеткам, превращая множество в зоо-

парк.

Пример 5.5.2.

Фактор-множество

по отношению

состоит из од-

ного всеобъемлющего класса эквивалентности

{X}

. Здесь вместо зоо-

парка получается загон для всего стада элементов

Пример 5.5.3.

Кольцо вычетов по модулю

может быть представлено

как фактор-множество множества целых чисел по отношению

∃z |x − y| = n ∗ z.

120

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Все арифметические операции на кольце получаются при этом из ариф-

метических операций на целых числах простой факторизацией.

Если X — алгебра с какими-то операциями, то переходить к фак-

тор-алгебре можно лишь тогда, когда операции по всем аргументам со-

гласованы с эквивалентностью.

Фактор-множества тесно связаны с функциями. А именно, любая

функция задает отношение эквивалентности:

{(x, y) | x ∈ Dom f & y ∈ Dom f & f(x) = f(y)}.

С другой стороны, λx. ˆx является функцией, определяющей данное от-

ношение эквивалентности. Множества, на которых функция сохраняет

одно и то же значение, часто называются множествами уровня данной

функции. Таким образом, любое отношение эквивалентности предста-

вляется как совокупность множеств уровня некоторой функции. Отно-

шение эквивалентности, генерируемое функцией

f, обозначается

=, а

фактор-множество по

= — просто X/f.

Пользуясь отношениями эквивалентности, легко установить следу-

ющий фундаментальный результат:

Предложение 5.5.3. Любая функция может быть представлена как

композиция сюръекции и инъекции.

Доказательство. Возьмем

Dom f/f. λx. ˆx является сюръекцией на это

множество, а

= — инъекцией из этого множества в Val f.

Еще одно фундаментальное представление фактор-множеств и от-

ношений эквивалентности основывается на понятии разбиения множе-

ства.

Определение 5.5.3.

Семейство множеств

)

i∈I

называют

разбиением

множества

, если:

i∈I

= X

∀i ∀j (i ∈ I & j ∈ I & i 6= j ⇒ X

∩ X

= ∅)

3. Ни одно из

не пусто.

Итак, в совокупности множества из разбиения покрывают все X и

между собой они попарно не пересекаются.