![](/user_photo/_userpic.png)
Непейвода. Прикладная логика
.PDF![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM141x1.jpg)
5.4. ФУНКЦИИ |
|
|
111 |
||
|
|
Аксиома подстановки. Если X — |
множество, и x(x |
||
|
|
X 1y A(x, y), то |
|
|
|
|
|
{y | x(x X & A(x, y))} |
|
||
|
|
также множество. |
|
|
|
Контрапозицией аксиомы подстановки получаем, что, если X — |
класс, |
||||
ϕ — |
|
инъективное отображение X в Y , то Y — |
также класс. |
|
|
|
Данный критерий называется аксиомой по той причине, что, отчаяв- |
||||
шись найти внешние критерии того, какие формулы могут определять |
|||||
множество, математики начала XX века решили просто постулировать |
|||||
возможность построения тех множеств, которые широко вошли в мате- |
|||||
матическую практику и не приводят к известным парадоксам. |
Так воз- |
||||
никла аксиоматическая теория множеств. |
В том ее варианте, |
который |
|||
принимается абсолютным большинством математиков, постулируются |
|||||
следующие аксиомы (помимо аксиомы подстановки)37: |
|
||||
|
1. |
Пустое множество: |
|
|
|
|
|
X x x / X |
|
|
|
|
2. |
Двухэлементное множество: |
|
|
|
x, y X z(z X z = x z = y)
3. Объединение множества множеств:
X Y y(y Y x(x X & y x))
(это множество обозначается просто S X.) 4. Множество всех подмножеств:
X Y Z(Z Y x(x Z x X))
37 В данных аксиомах мы для ясности формулировок свободно пользуемся перемен ными для функций, поскольку уже знаем, как определять функции через множества. -
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM142x1.jpg)
112 |
|
|
|
|
|
|
ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ |
|||||||||||||
5. |
Аксиома бесконечности: |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
Существует множество, у которого есть инъекция самого в себя. |
|||||||||||||||||||
|
|
|
|
|
|
f : X → X |
|
|
|
|
|
|
|
|
|
& |
|
|||
|
|
X |
|
f |
x, y(x X & y X & f(x) = f(y) x = y) & |
|||||||||||||||
|
|
|
|
y(y X & x(x X f(x) 6= y)) |
|
|
|
|
||||||||||||
6. |
Аксиома выбора: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
Y Y |
X |
|
y y |
Y |
|
X |
|
f(Y ) |
|
Y ) |
|
|||
|
|
X f((f : X |
|
X & |
|
Y)(Y |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
→ S |
|
|
|
|
|
|
|
|||||
7. |
Аксиома объемности: |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
X, Y ( z(z X z Y ) X = Y ) |
|
|
|
|||||||||||
|
Если множества имеют одни и те же элементы, они равны. |
|
||||||||||||||||||
8. |
Аксиома регулярности: |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
X x (x X & |
¬ y(y x & y X)) |
|
|
|
||||||||||
|
Суть ее в том, |
чтобы запретить ситуации вида x x. Эта аксио- |
||||||||||||||||||
|
ма служит примером технических улучшений, необходимых в ка- |
|||||||||||||||||||
|
ждой новой теории для ее логического замыкания. |
|
|
|
||||||||||||||||
Аксиомы теории множеств, |
как выяснилось, не слишком удобны для |
|||||||||||||||||||
представления некоторых структур, |
возникающих в современных обла- |
|||||||||||||||||||
стях математики, в частности, |
в теории категорий. Но они по крайней |
|||||||||||||||||||
мере дают некоторый общий фундамент, позволяющий точно понимать, |
||||||||||||||||||||
что означает то или иное утверждение классической математики38. |
И, |
|||||||||||||||||||
что еще важнее, |
они дали возможность строго поставить вопрос о не- |
|||||||||||||||||||
разрешимости некоторых проблем традиционной математики. |
|
|
||||||||||||||||||
Функции, аргументом которых служат натуральные числа, обычно |
||||||||||||||||||||
называют |
последовательностями и обозначают несколько по-другому: |
|||||||||||||||||||
саму функцию (an)n N, |
конкретное значение ai. |
В данной книге мы, |
следуя логической традиции несколько расширяем понятие последова тельности. , -
38 Как Вы чувствуете из этой оговорки появилась и неклассическая математика но объем произведенного в классической настолько, больше что многие и не подозревают, о существовании существенно других интерпретаций Примерно, так же сейчас в России многие, говоря ‘компьютер’, понимают IBM PC. .
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM143x1.jpg)
5.4. ФУНКЦИИ |
113 |
Определение 5.4.7. Конечной последовательностью называется ото- |
|
бражение множества {i | i N & i > 1 & i 6 k}. k — |
ее длина. |
Бесконечной последовательностью называется отображение множества
N либо N
Конечная последовательность\ 0. N > 6 явля ется началом конечной последовательностиb : {i | i & i 1 & i k} → X -
a : {i | i N & i > 1 & i 6 l} → X,
если > и 6 6
Конечнаяl kпоследовательностьi(1 i & i k a(i) = b(Ni)). > 6 явля ется началом бесконечной последовательностиb : {i | i & i 1 &Ni k} → X если-
a : \ 0 → X,
Последовательностьi(1 6 i & i 6 k a(—i) =этоb(конечнаяi)). либо бесконечная последователь-
ность.
Отношение вхождения для кортежей обобщается на последователь ности следующим образом: -
Определение Последовательность содержит конечную после довательность5.4длины.8. если существуетαтакое что -
β k, n,
i(1 6 i & i 6 k α(i + n) = β(i)).
И, наконец, обратим внимание на несколько другое обозначение функ- |
|
ций, появившееся по аналогии с последовательностями и употребляе- |
|
мое в том случае, если область определения фиксирована и нас инте- |
|
ресуют в первую очередь значения функции, а не взаимосвязь между |
|
аргументами и значениями. Это — |
запись функции как семейства зна- |
чений: |
|
|
|
|
(ai)i I . |
Аргумент называется в данном случае индексом, результат — i-тым чле- |
|||
ном семейства. Чаще всего как семейства представляют функции, значе- |
|||
ниями которых служат объекты высших типов: множества либо другие |
|||
функции. |
|
|
|
Семейства, в частности, полезны для обобщения операций на беско- |
|||
нечное число аргументов, |
если это возможно. Например, в теории мно- |
||
жеств обобщаются на любое семейство аргументов операции объедине- |
|||
ния, пересечения, прямой суммы, прямого произведения. |
|||
Определение 5.4.9. |
1. |
S |
Xi = {x | i(i I & x Xi)}. |
|
|
|
4 |
i I
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM144x1.jpg)
114 |
ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ |
T4
2.Xi = {x | i(i I x Xi)}.
i I
L4
3.Xi = {(i, x) | i I & x Xi}.
i I
Q |
4 |
S |
4. |
Xi = {f | f : I → i Xi & i(i I f(i) Xi)}. |
Будьтеi I осторожнее с обобщением операций на бесконечное семей-
ство операндов Часто они просто не обобщаются как например алге браические операции! над действительными числами, ,либо теряют, при- обобщении полезные свойства. ,
Упражнения к § 5.4
5.4.1. Когда тройка X♣Y = hX, Y, X × Y i является функцией? Когда |
|||
|
4 |
|
|
|
данная функция является инъекцией? Сюръекцией? Биекцией? |
||
5.4.2. |
Имеются ли функции из в непустые множества? Какие? А нао- |
||
|
борот? |
|
|
5.4.3. |
Почему доказательство теоремы Кантора-Шредера-Бернштейна |
||
|
не может быть использовано для составления программы, пре- |
||
|
образующей две инъекции в биекцию, даже для счетных множеств? |
||
5.4.4. |
Дайте доказательство теоремы Кантора-Шредера-Бернштейна для |
||
|
конечных множеств, подходящее для построения с его помощью |
||
|
преобразователя программ: процедуры, трансформирующей две |
||
|
данные функции-инъекции в одну — |
биекцию39. |
|
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 равномощны?
39 Будьте внимательнее! Разве вы еще не поняли, что автор — ехидна?
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM145x1.jpg)
5.4. ФУНКЦИИ |
|
|
|
115 |
|
5.4.8. Каковы взаимоотношения между X 6 Y и Y < X? |
|||||
5.4.9. |
Докажите, что если X — |
счетно, то и множество всех кортежей |
|||
X∞ также счетно. |
|
|
|
|
|
5.4.10. |
Студент Гениалькис предложил определить конечное множество |
||||
как множество, представимое в виде {x1, . . . , |
xn}. Что Вы ска- |
||||
жете по этому поводу? |
|
|
|
|
|
5.4.11. |
При обсуждении предыдущего определения студент Интеллек- |
||||
туалов выдвинул свое: |
|
|
транзитивное замыкание |
||
|
Класс конечных множеств — |
||||
|
класса, содержащего и все множества вида {x} (чтобы |
||||
|
снять все замечания, он определил их как множества, |
||||
|
удовлетворяющие следующему условию: |
|
|||
|
x(x X & y(y X x = y)) ) |
||||
|
относительно операции объединения двух множеств. |
||||
Что Вы скажете по поводу этого определения? |
|
||||
5.4.12. |
Студент Рессель заявил, что на самом деле лучшее определение |
||||
конечных множеств следующее: |
|
|
|||
|
Конечное множество — |
множество X, неравномощное |
|||
|
никакому |
|
|
|
|
|
Y X & Y 6= X. |
|
А Вы что здесь скажете? |
|
|
||||
5.4.13. Студентка Программистская заявила, что все предыдущие опре- |
||||||
деления никуда не годятся, поскольку ссылаются на множество |
||||||
всех множеств, которого нет. Она предложила определить конеч- |
||||||
ные множества так, как делают все нормальные программисты — |
||||||
по индукции. |
|
|
|
|
||
1. |
— |
конечное множество. |
конечное множество. |
|
||
2. |
Если a — |
объект, то {a} — |
конечное |
|||
3. |
Если X |
и Y — |
конечные множества, то X Y — |
|||
|
множество. |
|
|
|
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM146x1.jpg)
116 |
ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ |
А что Вы здесь скажете?
Определите верхнюю и нижнюю границы мощности множества 5.4.14всех. последовательностей действительных чисел Rn.
5.4.15. Покажите, что нет сюръекции X на P X.
Определите а что же такое подпоследовательность бесконечной 5.4.16последовательности. , ?
§ 5.5. |
ФАКТОР-МНОЖЕСТВА |
|
В предыдущем параграфе у нас частенько фигурировало слово ‘мощ- |
||
ность’. Но мы стыдливо умалчивали, что это такое. На самом деле хо- |
||
рошего математического определения мощности множества просто нет, |
||
наиболее прозрачной была попытка Кантора определить мощность как |
||
множество всех равномощных друг другу множеств, но из-за парадокса |
||
Кантора и несуществования универса таких множеств просто не суще- |
||
ствует (за исключением мощности пустого множества). Кантор в своем |
||
определении следовал сложившейся к концу XIX века математической |
||
традиции, когда уже был хорошо разработан способ перевода отноше- |
||
ний эквивалентности в отношения равенства через посредство фактор- |
||
множества. |
|
|
Условия, накладываемые на отношение эквивалентности, на самом |
||
деле минимальный вариант выразимых на логическом языке свойств ра- |
||
венства. А именно: |
Отношением эквивалентности называется рефлек- |
|
Определение 5.5.1. |
||
сивное, транзитивное и симметричное отношение40. |
||
Таким образом, класс эквивалентности элемента x есть R hxi. Отно- |
||
шение эквивалентности R обладает, в частности, следующими важны- |
||
ми свойствами: |
|
|
Предложение 5.5.1. |
1. x y(R hxi = R hyi R hxi ∩ R hyi = ). |
|
2. |
x(x Dom R x R hxi). |
40 Поскольку все эти понятия применяются у нас лишь к отношениям на некотором множестве отсюда следует что отношение эквивалентности является подмноже ством некоторогоX, X2. , -
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM147x1.jpg)
5.5. ФАКТОР-МНОЖЕСТВА |
117 |
|
||||||||
3. |
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, y) |
|
R, |
и по |
пункту 3 образы равны. Значит, если они пересекаются, |
||||||
|
|
|
|
41 |
. |
|
|
|
||
то они совпадают |
|
|
|
|
||||||
Последний пункт очевиден. |
|
|
||||||||
Итак, отношение эквивалентности разбивает свою область опреде- |
||||||||||
ления на непересекающиеся классы эквивалентности. |
|
|
||||||||
Определение 5.5.2. |
1. Класс эквивалентности элемента x — его образ |
|||||||||
|
R hxi, то есть |
|
{y | (x, y) R}. |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
2. |
Фактор-множество — множество классов эквивалентности всех |
|||||||||
|
элементов множества X по отношению эквивалентности ≡. |
|||||||||
3. |
Если f — |
функция из множества X с заданным на нем отноше- |
||||||||
|
нием эквивалентности R1 в множество Y с заданным на нем от- |
|||||||||
|
ношением эквивалентности R2, то f называется |
согласованной с |
||||||||
|
эквивалентностью, если |
|
|
|||||||
|
|
x y(x X & y X & (x, y) R1 (f(x), f(y)) R2). |
||||||||
|
Таким образом, функция согласована с эквивалентностью, если |
|||||||||
|
она по эквивалентным аргументам выдает эквивалентные значе- |
|||||||||
|
ния. |
|
|
|
|
|
|
сильнее отноше- |
||
4. |
Отношение эквивалентности R1 на множестве X |
|||||||||
|
ния эквивалентности R2 на том же множестве, если R1 R2. |
41 То что последующий пункт доказан раньше предыдущего и использован в дока зательстве, предыдущего сознательная небрежность Важно накрепко запомнить что- порядок пунктов в теореме, не играет с логической“ точки”. зрения никакой роли посколь, ку конъюнкция коммутативна Зато в доказательстве порядок играет важнейшую, роль-
поскольку не допускается ссылка. на то, что еще не обосновано. ,
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM148x1.jpg)
118 |
|
ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ |
||
Класс эквивалентности x относительно R обозначается xˆR и еще |
||||
чаще просто xˆ, поскольку обычно одновременно рассматривается лишь |
||||
одно отношение эквивалентности. |
сильнейшее из от- |
|||
Предложение 5.5.2. |
1. Отношение равенства — |
|||
|
ношений эквивалентности. |
|
||
2. |
Отношение R = X2 — |
слабейшее из отношений эквивалентно- |
||
|
сти. |
|
|
|
3. |
Предикат P (x) согласован с эквивалентностью ттт |
|||
|
x y((x, y) R (P (x) P (y))). |
Очевидно. |
|
|
|
|
Отношение эквивалентности часто записывают как бинарную опе- |
||||
рацию, похожую по внешнему виду на равенство, пользуясь для этого |
||||
значками типа ' |
|
≡ |
Полного единообразия здесь быть и не |
|
должно, поскольку на одной и той же структуре часто рассматриваются |
||||
|
, |
, =, |
, . |
|
несколько отношений эквивалентности.. Если отношение эквивалентно- |
|||
сти обозначается бинарной операцией =, то фактор-множество X по от- |
|||
. |
. |
|
|
ношению = |
обозначается X/=. Класс эквивалентности элемента a по |
||
рассматриваемому в данный момент отношению эквивалентности часто |
|||
обозначается aˆ. |
|
. |
|
Если функция согласована с отношением эквивалентности R |
(=), то |
||
можно определить функцию из фактор-множества с теми же значения- |
|||
ми: |
. |
4 |
(5.16) |
|
f/=(ˆx) = f(x). |
||
Обратим Ваше внимание на одну тонкость. Мы определили фактор-фун- |
|||
кцию, не прибегая к несколько неаккуратной конструкции, часто ис- |
|||
пользуемой в данном случае: не выбирая произвольного элемента из |
|||
xˆ, так что ее определение ни от каких сомнительных принципов тео- |
|||
рии множеств не зависит. Но, конечно же, отношение, заданное в (5.16), |
|||
является функциональным лишь тогда, когда f согласована с эквива- |
|||
лентностью. |
|
|
мно- |
Пример 5.5.1. Фактор-множество X по отношению равенства — |
|||
жество всех |
{{x} | x X}. Таким образом, здесь мы просто рассажи- |
ваем все элементы по отдельным клеткам превращая множество в зоо парк. , -
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM149x1.jpg)
5.5. ФАКТОР-МНОЖЕСТВА |
119 |
Пример 5.5.2. Фактор-множество X по отношению X2 |
состоит из од- |
ного всеобъемлющего класса эквивалентности {X}. Здесь вместо зоо- |
|
парка получается загон для всего стада элементов X. |
|
Пример 5.5.3. Кольцо вычетов по модулю n может быть представлено |
|
как фактор-множество множества целых чисел по отношению |
z |x − y| = n z.
Все арифметические операции на кольце получаются при этом из ариф- |
|
метических операций на целых числах простой факторизацией. |
|
Если X — |
алгебра с какими-то операциями, то переходить к фак- |
тор-алгебре можно лишь тогда, когда операции по всем аргументам со- |
|
гласованы с эквивалентностью. |
|
Фактор-множества теснейшим образом связаны с функциями. А имен- |
|
но, любая функция задает отношение эквивалентности: |
{(x, y) | x Dom f & y Dom f & f(x) = f(y)} .
С другой стороны, λx. xˆ является функцией, определяющей данное от- |
|
ношение эквивалентности. Множества, на которых функция сохраняет |
|
одно и то же значение, часто называются множествами уровня данной |
|
функции. Таким образом, любое отношение эквивалентности предста- |
|
вляется как совокупность множеств уровня некоторой функции. Отно- |
|
шение эквивалентности, |
генерируемое функцией f, обозначается =, а |
фактор-множество по = — |
f |
просто X/f. |
|
f |
|
Пользуясь отношениями эквивалентности, легко установить следу- |
|
ющий фундаментальный результат: |
Предложение Любая функция может быть представлена как композиция сюръекции5.5.3. и инъекции.
Доказательство. Возьмем Dom f/f. λx. xˆ является сюръекцией на это |
|
множество, а f/= — |
инъекцией из этого множества в Val f. |
f |
|
Еще одно фундаментальное представление фактор множеств и от ношений эквивалентности основывается на понятии разбиения- множе- ства. -
Определение Семейство множеств называют разбиением множества X, 5если.5.3.: (Xi)i I
![](/html/611/317/html_pF0Rtq2hPk.Dc3i/htmlconvd-_j_zwM150x1.jpg)
120 |
ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ |
S
1.Xi = X.
i I
2. i j (i I & j I & i 6= j Xi ∩ Xj = ). 3. Ни одно из Xi не пусто.
Итак в совокупности множества из разбиения покрывают все и между собой, они попарно не пересекаются. X
Предложение Любое разбиение задает отношение эквивалент ности и наоборот5.5.4. -
.
Упражнения к § 5.5 |
||
5.5.1. |
Являются ли отношениями эквивалентности объединение и пе- |
|
|
ресечение двух отношений эквивалентности? |
|
5.5.2. |
Постройте фактор-множество R по отношению эквивалентности, |
|
|
задаваемому функцией, находящей дробную часть числа. |
|
5.5.3. Являются ли отношениями эквивалентности отношения: |
||
|
1. |
Иметь одну и ту же мать. |
|
2. |
Иметь одну и ту же сестру. |
|
3. |
Различаться на рациональное число (на множестве действи- |
|
|
тельных чисел). |
|
4. |
Различаться по модулю не более чем на 1. |
|
5. |
Быть равномощными (для множеств). |
|
6. |
Существует изоморфизм G1 на G2 (для групп). |
|
7. |
Существует гомоморфизм G1 в G2 (для групп). |
5.5.4. Какое из отношений эквивалентности более сильное? |
||
|
1. |
Получить одинаковые оценки на вступительном экзамене по |
|
|
математике. |
|
2. |
Иметь одну и ту же сумму баллов на вступительных экзаме- |
|
|
нах. |
|
3. |
Решить одни и те же задачи на вступительном экзамене по |
|
|
математике. |