Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Ian Stewart, Does God play dice? В этом параграфе мы анализируем основные понятия, связанные с отоб- ражениями множеств. Как уже упоминалось во введении, в силу скупости чистой теории множеств в использовании выразительных средств — эв- фемически называемой минимализмом — все в ней выражается в тер- минах отображений 179 . В различных контекстах отображения истол- ковываются как функции, преобразования, движения, действия, операции, 179 Конечно, признавая ограниченность ресурсов чистой теории множеств, мы ни в малейшей степени не хотим поставить под сомнение ее огромную выразительную силу 400 списки, наборы, перестановки, симметрии, функционалы, операторы, фор- мы, семейства, последовательности, слова, векторы, матрицы, etc. — все на свете является функцией. 1. Функции. Понятие отображения или, как принято говорить в школьной математи- ке, функции, является одним из основных в математике. Отображение f : X −→ Y сопоставляет каждому элементу x множества X единственный элемент y множества Y , обозначаемый обычно f (x) и называемый обра- зом элемента x под действием f . Равенство y = f (x) записывается также в виде f : x 7→ y и читается, например, так: x отображает x в y или f переводит x в y. Множество X называется областью определения отображения f : X −→ Y и обозначается D(f), от английского domain, а множество Y называется областью значений отображения f и обозначается R(f ), от английского range. Область определения и область значений часто назы- ваются просто областью и кообластью. Говорят также, что f действует из X в Y . Напомним, что D(f ) и R(f ) входят в определение отображения f . Иными словами, два отображения f и g называются равными, если и только если • их области совпадают, D(f) = D(g) = X, • их кообласти совпадают, R(f) = R(g) = Y , • для любого x ∈ X выполнено равенство f(x) = g(x). Однако, основным в определении отображения является сам способ , ко- торым элементам X сопоставляются элементы Y . С чисто экстенсиональ- ной точки зрения этот способ тоже должен задаваться некоторым мно- жеством, ведь в ортодоксальной теории множеств вообще не существует ничего, кроме множеств! Подмножество Γ(f ) = {(x, f(x)), | x ∈ X} ⊆ X × Y, состоящее из всех пар (x, f (x)), называется графиком отображения f : X −→ Y . В [VH2] мы подробно обсуждаем отличия этого обычного в математике экстенсионального определения функции от понятия функции, принятого в компьютерной алгебре. Пусть X = {x 1 , . . . , x m } и Y = {y 1 , . . . , y n } два конечных множества. Данными какой структуры удобнее всего задавать отображение f : X −→ Y ? Ответ на этот вопрос зависит от контекста, решаемых задач и исполь- зуемых алгоритмов. Пусть f (x i ) = z i ∈ Y . При этом мы считаем сами множества X и Y фиксированными. Разумеется, в учебных целях мы мог- ли бы задавать отображение как тройки, состоящие из области, кообласти и какой-то дополнительной структуры данных. Однако, в реальных вычис- лениях никто не будет включать область и кообласть в задание функции, так что и мы не будем заниматься подобными глупостями. Вот несколько обычных способов задавать отображения. 401 • Задать график отображения, {{x1,z1},...,{xm,zm}}, в программиро- вании такой способ задания функции называется табличным. • Перечислить элементы множества X в каком-то порядке, а потом их образы, в том же порядке {{x1,...,xm},{z1,...,zm}}, такой способ зада- ния отображения называется полным. • Задать образы {z1,...,zm}, элементов x i , в том порядке, как x i идут в списке, представляющем X — этот способ называется сокращенным. В параграфе, посвященном перестановкам, мы подробнейшим образом ана- лизируем все эти способы для частного случая X = Y и методы перехода от одной формы записи к другой. Ограничимся поэтому несколькими за- дачами общего характера. 1.1. Задайте функцию, выясняющую, является ли набор пар графиком отображения f : X −→ Y . 1.2. Напишите программу, генерирующую все отображения X −→ Y . 1.3. Напишите программу, генерирующую случайное отображение f : X −→ Y . Указание. Проще всего породить m случайных элементов множества Y . Пусть f : X −→ Y и A ⊆ X. Тогда f (A) = {f(x) | x ∈ A} называется образом множества A относительно (или под действием) отоб- ражения f . Образ f (X) области X = D(f ) под действием f обозначается обычно Im(f ), от английского image, и называется образом отображения f . Иными словами, Im(f ) — это множество таких y ∈ Y , для которых существует такое x ∈ X, что f(x) = y. Вообще говоря, для y ∈ Im(f) может существовать много x со свойством f (x) = y. Любой x ∈ X такой, что f(x) = y называется прообразом y Множество всех прообразов некоторого y ∈ Y обозначается f −1 (y) и на- зывается полным прообразом элемента Y . Разумеется, если y / ∈ Im(f), то f −1 (y) = ∅. Вообще, для любого подмножества B ⊆ Y его полный прообраз f −1 (B) определяется как f −1 (B) = {x ∈ X | f(x) ∈ B} = [ y ∈B f −1 (y). 1.4. Задайте функцию, вычисляющую для подмножества A ⊆ X его образ относительно отображения f : X −→ Y . 1.5. Задайте функцию, вычисляющую для подмножества B ⊆ Y его про- образ относительно отображения f : X −→ Y . 402 2. Предметы и ящики. Математик (вынимая из головы шар) Я вынул из головы шар. Я вынул из головы шар. Я вынул из головы шар. Я вынул из головы шар. Андрей Семенович Положь его обратно. Положь его обратно. Положь его обратно. Положь его обратно. Даниил Хармс, Математик и Андрей Семенович Традиционная комбинаторика говорит о задачах размещения, в ко- торых требуется разместить n предметов по m ящикам: • рассадить n кроликов по m клеткам, • раскрасить n стран в m цветов, • разложить n писем по m конвертам, • опустить n шаров по m урнам, • распределить n частиц по m энергетическим уровням, С нашей точки зрения всюду здесь речь идет об отображениях n-элемент- ного множества X в m-элементное множество Y , удовлетворяющих опре- деленным ограничениям. При этом элементы множества X соответствуют предметам, элементы множества Y — ящикам, а отображение f : X −→ Y сопоставляет каждому предмету его ящик. Множество всех отображений из X в Y обозначается обычно одним из следующих трех образов: Map(X, Y ), от английского map или mapping, Mor(X, Y ), от английского morphism, либо, наконец, просто Y X . Обратите внимание, что именно Y X , а не X Y На отображение f : X −→ Y могут накладываться те или иные условия. Простейшие условия на отображения — инъективность, сюръективность и биективность — обычно формулируются в терминах того, сколько предме- тов — ни одного, один или несколько — попадают в каждый ящик. • Отображение называется инъективным, если в каждый ящик попа- дает не более одного объекта. Иными словами, если f (x 1 ) = f (x 2 ) для некоторых x 1 , x 2 ∈ X, то x 1 = x 2 . Про такое отображение можно сказать, что оно удовлетворяет принципу запрета Паули: два фермиона не могут иметь один и тот же набор квантовых чисел. Множество инъективных отображений из X в Y обозначается через Inj(X, Y ). • Отображение называется сюръективным, если в каждый ящик попа- дает хотя бы один объект. Иными словами, для каждого y ∈ Y существу- ет такое x ∈ X, что f(x) = y. Множество сюръективных отображений из X в Y обозначается через Sur(X, Y ). • Отображение называется биективным, если в каждый ящик попада- ет ровно один объект, иначе говоря, если оно одновременно инъективно и 403 сюръективно. Таким образом, для каждого y ∈ Y существует единствен- ное такое x ∈ X, что f(x) = y. Множество биективных отображений из X в Y обозначается через Bij(X, Y ). С точки зрения теории перечисления, т.е. подсчета отображений дан- ного типа, как предметы, так и ящики могут быть • различимыми, • неразличимыми • или частично различимыми. Это значит, что мы можем подсчитывать либо число самих отображений X −→ Y с какими-то ограничениями, либо число орбит таких отображе- ний под действием симметрических групп S X и/или S Y или каких-либо их подгрупп. При этом мы будем получать существенно различные ответы. Например, существует m различных способов положить один предмет в m различимых ящиков и единственный способ положить этот же предмет в m неразличимых ящиков. С точки зрения индивидуального студента совершенно не все равно, какую оценку он получил на экзамене, но с точки зрения статистики успеваемости важно лишь сколько студентов получило на экзамене оценку почти удовлетворительно или весьма хорошо. В некоторых разделах комбинаторики, например, в теории графов в этом контексте обычно говорят о помеченных и непомеченных предметах и ящиках. Одной из наших первых целей в этом параграфе является получение формул для числа инъективных и сюръективных отображений. Уже про- стейшая из этих формул, которая утверждает, что | Inj(X, Y )| = 0 при |X| > |Y |, и, двойственным образом, | Sur(X, Y )| = 0 при |X| < |Y |, оказы- вается настолько полезной, что мы посвятим ей отдельный пункт. 3. Принцип Дирихле. 180 В наиболее простой форме принцип Дирихле утверждает, что если |X| > |Y |, то не существует инъективных отображений f : X −→ Y . Иными словами, если нам даны n шаров, которые мы хотим распределить по m ящикам, причем n > m, то хотя бы в одном ящике окажется по крайней мере два шара. В русской учебной литературе этот принцип часто называется также принципом клеток и кроликов: если нам дано n кроликов, которых мы хотим рассадить по m клеткам, причем n > m, то хотя бы в одной клетке окажется по крайней мере два кролика. В англоязычной литерату- ре этот же принцип обычно называется pigeonhole principle = принцип ящика для писем: если имеются n писем, которые нужно распихать по m отделениям ящика для писем, причем n > m, то хотя бы в одном отделении окажется по крайней мере два письма. 180 Everybody who reasons carefully about anything is making a contribution to mathe- matics. c Richard Feynman, The Character of Physical Law 404 Представляется совершенно невероятным, чтобы столь тривиальное на- блюдение приводило к нетривиальным результатам, — но, как замечает по этому поводу Олег Александрович Иванов, 181 откуда и следующие задачи: “однако, . . . ” 3.1. Легко видеть, что шахматную доску размера 8 × 8 можно покрыть костяшками домино 2 ×1 так, чтобы каждая костяшка покрывала две сосед- ние клетки. Можно ли сделать то же самое с доской, из которой вырезаны две клетки на противоположных концах диагонали? Решение. Нет, потому что костяшка домино покрывает одну белую и одну черную клетку, а обе вырезанные клетки одного цвета, при этом неважно даже, что вырезаны клетки на одной из главных диагоналей. 3.2. Покажите, что для любого покрытия шахматной доски ×6 костяш- ками домино 2 × 1 существует такое разрезание доски вертикальной или горизонтальной линией, которое не разрезает ни одной костяшки. Верно ли то же самое для доски 8 × 8? Указание. Сколько костяшек может разрезать такая линия? 3.3. На белую плоскость брызнули черной краской. Докажите, что най- дутся две точки одного цвета на расстоянии 1 метр друг от друга. Указание. Таких пар точек очень много. Воспользуйтесь принципом Лагранжа и считайте, что 2 — переменная величина, например, что 2 = 3. Тогда на белое пространство брызнули красками двух цветов, скажем черной и красной. Вам будет много легче увидеть решение. Сформулируем теперь принцип Дирихле в чуть большей общности, как утверждение о ядре любого отображения m-элементного множества в n-элементное. 3.4. Пусть m = m 1 + . . . + m n − n + 1 кроликов рассажены по n клеткам. Тогда найдется такой номер i, что в i-й клетке окажется по крайней мере m i кроликов. Указание. +1. 3.5. В классе 30 учеников. Андрюша Крылов сделал в диктанте 13 ошибок, а остальные меньше. Докажите, что найдутся три ученика, сделавшие одинаковое количество ошибок — или не сделавшие ни одной. 3.6. Докажите, что у некоторой натуральной степени числа 17 семь по- следних цифр равны 0000001. 3.7. Группа из 21 студента успешно сдала сессию из трех экзаменов. До- кажите, что по крайней мере 3 студента сдали сессию с одинаковыми оцен- ками. 4. Инъективные отображения. Здесь мы вычислим количество инъективных отображений n-элементно- го множества в m-элементное. 181 Иванов О.А. Избранные главы элементарной математики.— СПб.: Изд-во СПбГУ, 1995, pp. 1-223., Гл. 7 405 4.1. Пусть |X| = m, |Y | = n. Докажите, что | Inj(X, Y )| = [n] m Решение. Пусть X = {x 1 , . . . , x m }. Образом x 1 при инъективном отоб- ражении f : X −→ Y может быть любой из n элементов Y . После того как f (x 1 ) зафиксирован, образом x 2 может быть любой из оставшихся n − 1 элемента Y . После того как f (x 1 ) и f (x 2 ) зафиксированы, образом x 3 мо- жет быть любой из оставшихся m −2 элементов Y . Продолжая действовать таким образом, на последнем шаге мы заифксировали f (x 1 ), . . . , f (x m −1 ), после чего образом x m может быть любой из оставшихся n − (m − 1) эле- ментов Y . Остается применить правило произведения. 4.2. Докажите, что | Bij(X, Y )| = |X|! в случае |X| = |Y | и 0 в противном случае. Напомним, что, кроме того, в § 1 настоящей главы мы вводили понятие возрастающего факториала. Она становится интересным, в случае, когда инъективность не имеет места. 4.3. Докажите, что число упорядоченных размещений n предметов по m ящикам равно [n] m Указание. Для доказательства нужно лишь заметить, сколькими спосо- бами можно разместить i-й объект, если i − 1 объект уже размещены и применить правило произведения. 4.4. Перечислите все упорядоченные размещения трех поросят в трех до- миках. С точки зрения волка отнюдь не все равно не только то, в каком именно домике (соломенном, деревянном или каменном) находятся порося- та, но и то, в каком порядке съедать поросят, оказавшихся в одном домике. Он может начать с самого жирного или, наоборот, оставить самого жирного на десерт. Задача о трех поросятах во всевозможных вариантах — неразличимые и различимые поросята и домики, инъективность и неинъективность, сюръ- ективность и несюръективность, случай, когда поросята построили пять домиков, etc. — обсуждается в замечательной книге Мацумаса Анно Три поросенка. Вернемся теперь к инъективным отображениям. 4.5. Напишите программу, генерирующую все инъективные отображения f : X −→ Y . 4.6. Напишите программу, генерирующую случайное инъективное отобра- жение f : X −→ Y . Указание. Ничем не отличается от задачи генерации произвольного слу- чайного отображения, за исключением того, что на каждом шаге вытяну- тый элемент выьрасывается. 4.7. Докажите, что инъективность отображения f : X −→ Y эквивалентна тому, что для любого подмножества A ⊆ X выполняется равенство A = f −1 (f (A)). |