Страница:
Ясно, что пересечение этих множеств даст двух студентов, которые одновременно и отличники и спортсмены. Они, скорее всего, девушки, да еще и красавицы, но красота не использовалась здесь в качестве характеристики, по которой выделялись элементы этих множеств…
Когда у математиков появляются в руках об'екты, а у нас здесь раздолье – любые об'екты можно брать, и операции – а мы основную тройку тоже обозначили, то математики начинают говорить об АЛГЕБРЕ.
Алгебра множеств как небо и земля отличается от школьной, хотя есть некоторые аналогии. В алгебре множеств есть те же названия законов: КОММУТАТИВНЫЙ, АССОЦИАТИВНЫЙи ДИСТРИБУТИВНЫЙ(перестановочный, сочетательный и распределительный). Первые два похожи как две капли воды, упавшие с неба на землю. А вот дистрибутивный закон имеет и аналог в школьной алгебре (выражаясь «по-школьному» произведение суммы есть сумма произведений), но имеет и уникальную версию. В теории множеств, если тоже сказать кратко, то пересечение с об'единением равно об'единению пересечений и ( !) об'единение с пересечением равно пересечению об'единений. Второе не имеет аналогии в школьной алгебре:"Сумма с произведением не равна произведению сумм".
Проиллюстрируем сказанное:
Коммутативный закон: Об'единение (пересечение) отличников и спортсменов равно об'единеию (пересечению) спортсменов и отличников.
Ассоциативный закон: От изменения порядка об'единения (пересечения) спортсменов, отличников и красавцев результат не меняется.
Дистрибутивный закон (только экзотическая версия): Об'единение красавцев с пересечением спортсменов и отличников равно множеству, в котором пересекаются об'единения красавцев и спортсменов с об'единеием красавцев с отличниками. (В условных обозначениях это было бы гораздо короче и нагляднее, но мы зареклись насчет формул).
Сложновато воспринимается на слух закон поглощения, который, однако, в ряде случаев позволяет упрощать теоретико-множественные конструкции. Пересечение отличников с об'единением отличников и спортсменов дает множество отличников. Или второй вариант. Об'единение отличников с пересечением отличников и спортсменов дает множество отличников. Тем не мение, если обдумать сказанное, и поразмахивать руками, то справедливость результатов очевидна.
Есть еще закон, название которого почему-то студентов забавляет – он им, видимо, что то-напоминает. А закон этот смело можно отнести к самым важным законам (свойствам). Это закон ИДЕМПОТЕНТНОСТИ. Об'единение (пересечение) множества спортсменов с множеством спортсменов дает множество спортсменов.
Очень по-французски звучит ЗАКОН Де Моргана: Дополнение об'единения отличников со спортсменами равно пересечению дополнения множества спортсменов с дополнением множества отличников. И второй вариант. Дополнение пересечения отличников со спортсменами равно об'единению дополнения множества спортсменов с дополнением множества отличников. За универсум (для дополнения) можно взять множество студентов группы (или университета, или мира – роли не играет). Возьмите реальных спортсменов с отличниками и убедитесь в справедливости закона.
Очень прост закон ДВОЙНОГО ДОПОЛНЕНИЯ. Дополнение дополнения множества спортсменов есть само множество спортсменов. Персонально для тех, кто успешно продирается через всю нашу словесную казуистику, можем сформулировать ближайшее следствие из этого закона. Дополнение дополнения дополнения множества спортсменов есть дополнение множества спортсменов.
Самыми экзотическими являются два закона: ПРОТИВОРЕЧИЯи ИСКЛЮЧЕННОГО ТРЕТЬЕГО.
Противоречия: Пересечение множества спортсменов с дополнением множества спортсменов пусто. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены, то у этого пересечения не может быть общих элементов.
Исключенного третьего: Об'единение множества спортсменов с дополнением множества спортсменов совпадает с рассматриваемым универсумом. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены из универсума, то это об'единение как раз и составляет весь универсум.
Остается только высказать сожаление, что не все математики согласны с этими законами. Еще большее сожаление вызывает то, что у них на это есть весьма веские основания… Не менее веские, чем у сторонников законов.
Несогласные себя называют КОНСТРУКТИВИСТАМИили ИНТУИЦИОНИСТАМИ.
Согласным же ничего не осталось, как назвать самих себя КЛАССИКАМИ… С чем не согласны несогласные.
Лекция 4. СООТВЕТСТВИЯ, ОТОБРАЖЕНИЯ, ОТНОШЕНИЯ
Лекция 5. ОСОБЫЕ ОТНОШЕНИЯ
Лекция 6. МАТЕМАТИЧЕСКАЯ ЛОГИКА (БЕССМЫСЛЕННАЯ ЛОГИКА)
Когда у математиков появляются в руках об'екты, а у нас здесь раздолье – любые об'екты можно брать, и операции – а мы основную тройку тоже обозначили, то математики начинают говорить об АЛГЕБРЕ.
Алгебра множеств как небо и земля отличается от школьной, хотя есть некоторые аналогии. В алгебре множеств есть те же названия законов: КОММУТАТИВНЫЙ, АССОЦИАТИВНЫЙи ДИСТРИБУТИВНЫЙ(перестановочный, сочетательный и распределительный). Первые два похожи как две капли воды, упавшие с неба на землю. А вот дистрибутивный закон имеет и аналог в школьной алгебре (выражаясь «по-школьному» произведение суммы есть сумма произведений), но имеет и уникальную версию. В теории множеств, если тоже сказать кратко, то пересечение с об'единением равно об'единению пересечений и ( !) об'единение с пересечением равно пересечению об'единений. Второе не имеет аналогии в школьной алгебре:"Сумма с произведением не равна произведению сумм".
Проиллюстрируем сказанное:
Коммутативный закон: Об'единение (пересечение) отличников и спортсменов равно об'единеию (пересечению) спортсменов и отличников.
Ассоциативный закон: От изменения порядка об'единения (пересечения) спортсменов, отличников и красавцев результат не меняется.
Дистрибутивный закон (только экзотическая версия): Об'единение красавцев с пересечением спортсменов и отличников равно множеству, в котором пересекаются об'единения красавцев и спортсменов с об'единеием красавцев с отличниками. (В условных обозначениях это было бы гораздо короче и нагляднее, но мы зареклись насчет формул).
Сложновато воспринимается на слух закон поглощения, который, однако, в ряде случаев позволяет упрощать теоретико-множественные конструкции. Пересечение отличников с об'единением отличников и спортсменов дает множество отличников. Или второй вариант. Об'единение отличников с пересечением отличников и спортсменов дает множество отличников. Тем не мение, если обдумать сказанное, и поразмахивать руками, то справедливость результатов очевидна.
Есть еще закон, название которого почему-то студентов забавляет – он им, видимо, что то-напоминает. А закон этот смело можно отнести к самым важным законам (свойствам). Это закон ИДЕМПОТЕНТНОСТИ. Об'единение (пересечение) множества спортсменов с множеством спортсменов дает множество спортсменов.
Очень по-французски звучит ЗАКОН Де Моргана: Дополнение об'единения отличников со спортсменами равно пересечению дополнения множества спортсменов с дополнением множества отличников. И второй вариант. Дополнение пересечения отличников со спортсменами равно об'единению дополнения множества спортсменов с дополнением множества отличников. За универсум (для дополнения) можно взять множество студентов группы (или университета, или мира – роли не играет). Возьмите реальных спортсменов с отличниками и убедитесь в справедливости закона.
Очень прост закон ДВОЙНОГО ДОПОЛНЕНИЯ. Дополнение дополнения множества спортсменов есть само множество спортсменов. Персонально для тех, кто успешно продирается через всю нашу словесную казуистику, можем сформулировать ближайшее следствие из этого закона. Дополнение дополнения дополнения множества спортсменов есть дополнение множества спортсменов.
Самыми экзотическими являются два закона: ПРОТИВОРЕЧИЯи ИСКЛЮЧЕННОГО ТРЕТЬЕГО.
Противоречия: Пересечение множества спортсменов с дополнением множества спортсменов пусто. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены, то у этого пересечения не может быть общих элементов.
Исключенного третьего: Об'единение множества спортсменов с дополнением множества спортсменов совпадает с рассматриваемым универсумом. Действительно, коль скоро в дополнение множества спортсменов входят все остальные студенты неспортсмены из универсума, то это об'единение как раз и составляет весь универсум.
Остается только высказать сожаление, что не все математики согласны с этими законами. Еще большее сожаление вызывает то, что у них на это есть весьма веские основания… Не менее веские, чем у сторонников законов.
Несогласные себя называют КОНСТРУКТИВИСТАМИили ИНТУИЦИОНИСТАМИ.
Согласным же ничего не осталось, как назвать самих себя КЛАССИКАМИ… С чем не согласны несогласные.
Лекция 4. СООТВЕТСТВИЯ, ОТОБРАЖЕНИЯ, ОТНОШЕНИЯ
Алгеброй далеко не исчерпывается все то, что можно сделать с множествами…
В математике, как и в жизни, различные об'екты могут чему-то соответствовать или не соответствовать. Находиться меж собой в определенных отношениях или наоборот – не находится. И основой формализации, если угодно – математизации, здесь также служат множества.
То есть между множествами могут устанавливаться различные СООТВЕТСТВИЯи ОТНОШЕНИЯ. Более того (а серьезные математики может быть даже сказали бы «прежде всего»), множества нередко могут ОТОБРАЖАТЬСЯдруг в друг друга и даже в самих себя…
Человек может соответствовать профессии, зарплата соответствовать должности, наказание – преступлению, оценка – знаниям.
Глядя на многочисленные примеры вокруг мы замечаем, что для определения конкретного соответствия надо определить два множества: множество (область) определения и множество (область) значений. А также определить «пары соответствий». Например, область определения – группа ух-005, сдающая экзамен; область значений – отл, хор, уд, неуд – множество оценок. И множество пар Иванов – отл, Петров – хор, Сидоров – отл. А Хведоров – не явился. Вот вам и готовое соответствие.
Соответствия обладают свойствами.
1. В данном случае соответствие НЕ-ВСЮДУ-ОПРЕДЕЛЕННОЕ, поскольку для Хведорова в этом соответствии нет пары. (Даже если бы мы написали в ведомости Хведоров – н/я, то это все равно бы не попало в соответствие, поскольку «н/я» нет в множестве допустимых значений!). Если бы деканат своевременно исключил из ведомости Хведорова, как отчисленного, то это соответствие стало бы ВСЮДУ-ОПРЕДЕЛЕННЫМ
2. Соответствие ФУНКЦИОНАЛЬНО, поскольку каждому студенту соответствует не более одной оценки. Такое соответствие называют по-простому, ФУНКЦИЕЙ. В данном случае из-за Хведорова это не всюду определенная функция. Никакой разницы со школьной функцией кроме той принципиальной, что здесь аргументами и значениями могут быть не только числа, а любые об'екты. Кстати, не всем математикам нравится такое определение функции, хотя оно абсолютно строгое. Просто сказывается ревность к множествам с позиций некоторых других разделов математики.
Если бы за один экзамен студенты могли получать несколько оценок, то соответствие было бы НЕФУНКЦИОНАЛЬНЫМ. То есть не было бы функцией. (Оно было бы «многозначной [недетерминированной] функцией», но это уже другая математика). Да и в жизни так не бывает.
3. Данное соответствие НЕИН'ЕКТИВНО, поскольку отл получил более, чем один студент. Если бы Сидоров, из-за фатальной предрасположенности к несчастьям, получил не отл, а уд (или неуд), то соответствие было бы ИН'ЕКТИВНЫМ… Получение студентами олимпийских медалей за победу в беге на 100 метров было бы примером ин'ективного соответствия.
4. Данное соответствие НЕСЮР'ЕКТИВНО, поскольку на экзамене были использованы не все возможные оценки. На реальных экзаменах обычно бывает задействован весь возможный спектр оценок, поэтому это соответствие бывает «по жизни» СЮР'ЕКТИВНЫМ. Естественно, сюр'ективно в даный момент приобретение билетов на Витаса.
5. Соответствие, которое одновременно ВСЮДУ-ОПРЕДЕЛЕНО, ФУНКЦИОНАЛЬНО, ИН'ЕКТИВНОи СЮР'ЕКТИВНОназывается БИЕКТИВНЫМ. Еще его называют ВЗАИМНО-ОДНОЗНАЧНЫМ, но так звучит менее красиво. Говорят, что самый убедительный пример биективного соответствия головы на плечах. Возьмите множество голов, множество плеч и убедитесь во всех четырех свойствах. Криминальные варианты не предлагать!
Выделение соответствий в отдельную категорию предложили европейцы, а точнее французы, а еще точнее, Николя Бурбаки (это французский Козьма Прутков, состоявший из математиков интеллектуалов). Американская школа считает соответствия частным случаем отношений. А у нас разговор про отношения отдельный – так легче разложить все по полочкам. Так что пришла пора поговорить об отношениях.
В математике, как и в жизни, различные об'екты могут иметь какое-то отношение к другим об'ектам или не иметь.
Родственные отношения, дружеские отношения, дипломатические отношения, равноправные отношения.
Глядя на многочисленные примеры вокруг, мы замечаем, что отношения отличаются от соответствий тем, что определяются на одном множестве. Бессмысленно бы было говорить об отношениях между студентами и оценками. О дипломатических, родственных или любых других отношениях между должностью и зарплатой. Для определения конкретного отношения надо определить множество, и пары, для которых имеет место данное отношение.
Например, на множестве людей отношения «быть братом», «учиться в одной группе» или «быть выше ростом».
Отношения, в силу специфики, характеризуются иным перечнем свойств, нежели соответствия.
1. РЕФЛЕКСИВНОСТЬ. Это когда отношение обращено на себя. Ранее уже рассматривалось отношение включения. Поскольку любое множество включено само в себя, то отношение включения обладает свойством рефлексивности. Если верить народной мудрости, то и отношение «спасения» на множестве утопающих – рефлексивно.
2. АНИТИРЕФЛЕКСИВНОСТЬ. Это когда отношение к самому об'екту (всегда) неприменимо. Например, «перпендикулярность» на множестве прямых. Прямая не может быть перпендикулярна самой себе.
3. СИММЕТРИЧНОСТЬ. Если Иванов «учится в одной группе» с Петровым, то и обратное справедливо. Если прямая А «перпендикулярна» прямой B, то и обратное справедливо.
4. АНТИСИММЕТРИЧНОСТЬ. Если тысячу рублей можно «разменять» сотнями, то обратное не под силу даже фокуснику. Мрачноватый, но очень точный пример: «носить траур по кому-то»…
5. ПОЛНОТА. Это самое сложное свойство, поскольку, в отличие от всех остальных, оно прежде всего «направлено» на само множество. Полнотой обладает отношение, которое для любой пары разных элементов данного множества выполнимо хотя бы «в одну сторону». Например, полнотой обладает отношение «больше» для множества действительных чисел, ибо для двух разных действительных чисел одно обязательно больше другого. Но если мы к действительным числам добавим комплексные, то свойство полноты исчезнет. Если хотя бы одно из сравниваемых чисел будет комплексным, сравнение на «больше»-"меньше" теряет смысл.
6. ТРАНЗИТИВНОСТЬ. Если Иванов «учится в одной группе» с Петровым, а Петров с Сидоровым, то Иванов «учится в одной группе» с Сидоровым. Отношение включения тоже транзитивно. Если группа «включена» в множество студентов университета, а это множество «включено» в множество студентов страны. То множество студентов группы «включено» в множество студентов страны. Можно продолжить эту цепочку включений, прихватив галактику. И вот тут опять подводный камень казуистики!
Если студенческую группу рассматривать как элемент университета – множества, состоящего из групп, а университет элемент высшей школы – множества, состоящего из университетов, то группа не является элементом высшей школы (там элементы университеты). То есть отношение «принадлежности» нетранзитивно. «Вассал моего вассала -…»
Вернемся к функциональному соответствию (то есть к функции). Если это соответствие к тому же еще и всюду-определено, то оно называется ОТОБРАЖЕНИЕМ.
Если отобразить множество студентов в группе, на множество фамилий в группе, То это скорее всего будет ОТОБРАЖЕНИЕмножества студентов НАмножество фамилий. То есть сюр'ективное соответствие. Если же отобразить множество студентов группы на множество фамилий студентов университета, то говорят, что имеет место ОТОБРАЖЕНИЕмножества студентов В множество фамилий. То есть в области значений будут и «незадействованные фамилии».
Мы подошли к одному из самых фундаментальных, может потому и неблагозвучных, понятий и теории множеств, и математики вообще, мы подошли к ГОМОМОРФИЗМУ.
Пример. Отобразим множество точек участка земной поверхности на множество точек карты. Сейчас оставим в стороне то, что некое множество точек земной поверхности отобразится в одну точку на карте, в таких случаях неин'ективность – обычное дело. Для нас существенно то что, чем выше точки земной поверхности над уровнем моря, тем в более коричневые точки карты они отображаются.
Таким образом, мы рассматриваем не просто множества элементов. В первом случае здесь между элементами множества существует отношение «выше», а во втором – «коричневее». Где выше в первом – там коричневее во втором. «Выше» и «коричневее» – это отношения заданные на своих множествах.
Отображение земной поверхности НАкарту не просто ставит всем элементам одного множества элементы другого. Но, кроме того, если между двумя элементами первого множества существует отношение «выше», то между их образами во втором множестве имеет место отношение «коричневее». Естественно, если точки земной поверхности лежат на одной высоте, то они отобразятся в точки карты с одинаковой коричневостью.
Такое отображение называется ГОМОМОРФНЫМ. Или говорят, что между этими множествами существует ГОМОМОРФИЗМ.
Вернемся к тому, что слово не очень благозвучное, а по американским меркам и громоздкое. Поэтому последнее время все чаше используется более короткий (усеченный) термин – МОРФИЗМ.
Морфизмы играют в математике исключительную роль. Коль скоро математику не без оснований часто отождествляют с математическим моделированием, то приведем афоризм из одной умной философской книжки: ХОРОШАЯ МОДЕЛЬ ВСЕГДА ГОМОМОРФНА.
Афоризм в конце лекции провоцирует размышления. Чего бы и хотелось добиться…
В математике, как и в жизни, различные об'екты могут чему-то соответствовать или не соответствовать. Находиться меж собой в определенных отношениях или наоборот – не находится. И основой формализации, если угодно – математизации, здесь также служат множества.
То есть между множествами могут устанавливаться различные СООТВЕТСТВИЯи ОТНОШЕНИЯ. Более того (а серьезные математики может быть даже сказали бы «прежде всего»), множества нередко могут ОТОБРАЖАТЬСЯдруг в друг друга и даже в самих себя…
Человек может соответствовать профессии, зарплата соответствовать должности, наказание – преступлению, оценка – знаниям.
Глядя на многочисленные примеры вокруг мы замечаем, что для определения конкретного соответствия надо определить два множества: множество (область) определения и множество (область) значений. А также определить «пары соответствий». Например, область определения – группа ух-005, сдающая экзамен; область значений – отл, хор, уд, неуд – множество оценок. И множество пар Иванов – отл, Петров – хор, Сидоров – отл. А Хведоров – не явился. Вот вам и готовое соответствие.
Соответствия обладают свойствами.
1. В данном случае соответствие НЕ-ВСЮДУ-ОПРЕДЕЛЕННОЕ, поскольку для Хведорова в этом соответствии нет пары. (Даже если бы мы написали в ведомости Хведоров – н/я, то это все равно бы не попало в соответствие, поскольку «н/я» нет в множестве допустимых значений!). Если бы деканат своевременно исключил из ведомости Хведорова, как отчисленного, то это соответствие стало бы ВСЮДУ-ОПРЕДЕЛЕННЫМ
2. Соответствие ФУНКЦИОНАЛЬНО, поскольку каждому студенту соответствует не более одной оценки. Такое соответствие называют по-простому, ФУНКЦИЕЙ. В данном случае из-за Хведорова это не всюду определенная функция. Никакой разницы со школьной функцией кроме той принципиальной, что здесь аргументами и значениями могут быть не только числа, а любые об'екты. Кстати, не всем математикам нравится такое определение функции, хотя оно абсолютно строгое. Просто сказывается ревность к множествам с позиций некоторых других разделов математики.
Если бы за один экзамен студенты могли получать несколько оценок, то соответствие было бы НЕФУНКЦИОНАЛЬНЫМ. То есть не было бы функцией. (Оно было бы «многозначной [недетерминированной] функцией», но это уже другая математика). Да и в жизни так не бывает.
3. Данное соответствие НЕИН'ЕКТИВНО, поскольку отл получил более, чем один студент. Если бы Сидоров, из-за фатальной предрасположенности к несчастьям, получил не отл, а уд (или неуд), то соответствие было бы ИН'ЕКТИВНЫМ… Получение студентами олимпийских медалей за победу в беге на 100 метров было бы примером ин'ективного соответствия.
4. Данное соответствие НЕСЮР'ЕКТИВНО, поскольку на экзамене были использованы не все возможные оценки. На реальных экзаменах обычно бывает задействован весь возможный спектр оценок, поэтому это соответствие бывает «по жизни» СЮР'ЕКТИВНЫМ. Естественно, сюр'ективно в даный момент приобретение билетов на Витаса.
5. Соответствие, которое одновременно ВСЮДУ-ОПРЕДЕЛЕНО, ФУНКЦИОНАЛЬНО, ИН'ЕКТИВНОи СЮР'ЕКТИВНОназывается БИЕКТИВНЫМ. Еще его называют ВЗАИМНО-ОДНОЗНАЧНЫМ, но так звучит менее красиво. Говорят, что самый убедительный пример биективного соответствия головы на плечах. Возьмите множество голов, множество плеч и убедитесь во всех четырех свойствах. Криминальные варианты не предлагать!
Выделение соответствий в отдельную категорию предложили европейцы, а точнее французы, а еще точнее, Николя Бурбаки (это французский Козьма Прутков, состоявший из математиков интеллектуалов). Американская школа считает соответствия частным случаем отношений. А у нас разговор про отношения отдельный – так легче разложить все по полочкам. Так что пришла пора поговорить об отношениях.
В математике, как и в жизни, различные об'екты могут иметь какое-то отношение к другим об'ектам или не иметь.
Родственные отношения, дружеские отношения, дипломатические отношения, равноправные отношения.
Глядя на многочисленные примеры вокруг, мы замечаем, что отношения отличаются от соответствий тем, что определяются на одном множестве. Бессмысленно бы было говорить об отношениях между студентами и оценками. О дипломатических, родственных или любых других отношениях между должностью и зарплатой. Для определения конкретного отношения надо определить множество, и пары, для которых имеет место данное отношение.
Например, на множестве людей отношения «быть братом», «учиться в одной группе» или «быть выше ростом».
Отношения, в силу специфики, характеризуются иным перечнем свойств, нежели соответствия.
1. РЕФЛЕКСИВНОСТЬ. Это когда отношение обращено на себя. Ранее уже рассматривалось отношение включения. Поскольку любое множество включено само в себя, то отношение включения обладает свойством рефлексивности. Если верить народной мудрости, то и отношение «спасения» на множестве утопающих – рефлексивно.
2. АНИТИРЕФЛЕКСИВНОСТЬ. Это когда отношение к самому об'екту (всегда) неприменимо. Например, «перпендикулярность» на множестве прямых. Прямая не может быть перпендикулярна самой себе.
3. СИММЕТРИЧНОСТЬ. Если Иванов «учится в одной группе» с Петровым, то и обратное справедливо. Если прямая А «перпендикулярна» прямой B, то и обратное справедливо.
4. АНТИСИММЕТРИЧНОСТЬ. Если тысячу рублей можно «разменять» сотнями, то обратное не под силу даже фокуснику. Мрачноватый, но очень точный пример: «носить траур по кому-то»…
5. ПОЛНОТА. Это самое сложное свойство, поскольку, в отличие от всех остальных, оно прежде всего «направлено» на само множество. Полнотой обладает отношение, которое для любой пары разных элементов данного множества выполнимо хотя бы «в одну сторону». Например, полнотой обладает отношение «больше» для множества действительных чисел, ибо для двух разных действительных чисел одно обязательно больше другого. Но если мы к действительным числам добавим комплексные, то свойство полноты исчезнет. Если хотя бы одно из сравниваемых чисел будет комплексным, сравнение на «больше»-"меньше" теряет смысл.
6. ТРАНЗИТИВНОСТЬ. Если Иванов «учится в одной группе» с Петровым, а Петров с Сидоровым, то Иванов «учится в одной группе» с Сидоровым. Отношение включения тоже транзитивно. Если группа «включена» в множество студентов университета, а это множество «включено» в множество студентов страны. То множество студентов группы «включено» в множество студентов страны. Можно продолжить эту цепочку включений, прихватив галактику. И вот тут опять подводный камень казуистики!
Если студенческую группу рассматривать как элемент университета – множества, состоящего из групп, а университет элемент высшей школы – множества, состоящего из университетов, то группа не является элементом высшей школы (там элементы университеты). То есть отношение «принадлежности» нетранзитивно. «Вассал моего вассала -…»
Вернемся к функциональному соответствию (то есть к функции). Если это соответствие к тому же еще и всюду-определено, то оно называется ОТОБРАЖЕНИЕМ.
Если отобразить множество студентов в группе, на множество фамилий в группе, То это скорее всего будет ОТОБРАЖЕНИЕмножества студентов НАмножество фамилий. То есть сюр'ективное соответствие. Если же отобразить множество студентов группы на множество фамилий студентов университета, то говорят, что имеет место ОТОБРАЖЕНИЕмножества студентов В множество фамилий. То есть в области значений будут и «незадействованные фамилии».
Мы подошли к одному из самых фундаментальных, может потому и неблагозвучных, понятий и теории множеств, и математики вообще, мы подошли к ГОМОМОРФИЗМУ.
Пример. Отобразим множество точек участка земной поверхности на множество точек карты. Сейчас оставим в стороне то, что некое множество точек земной поверхности отобразится в одну точку на карте, в таких случаях неин'ективность – обычное дело. Для нас существенно то что, чем выше точки земной поверхности над уровнем моря, тем в более коричневые точки карты они отображаются.
Таким образом, мы рассматриваем не просто множества элементов. В первом случае здесь между элементами множества существует отношение «выше», а во втором – «коричневее». Где выше в первом – там коричневее во втором. «Выше» и «коричневее» – это отношения заданные на своих множествах.
Отображение земной поверхности НАкарту не просто ставит всем элементам одного множества элементы другого. Но, кроме того, если между двумя элементами первого множества существует отношение «выше», то между их образами во втором множестве имеет место отношение «коричневее». Естественно, если точки земной поверхности лежат на одной высоте, то они отобразятся в точки карты с одинаковой коричневостью.
Такое отображение называется ГОМОМОРФНЫМ. Или говорят, что между этими множествами существует ГОМОМОРФИЗМ.
Вернемся к тому, что слово не очень благозвучное, а по американским меркам и громоздкое. Поэтому последнее время все чаше используется более короткий (усеченный) термин – МОРФИЗМ.
Морфизмы играют в математике исключительную роль. Коль скоро математику не без оснований часто отождествляют с математическим моделированием, то приведем афоризм из одной умной философской книжки: ХОРОШАЯ МОДЕЛЬ ВСЕГДА ГОМОМОРФНА.
Афоризм в конце лекции провоцирует размышления. Чего бы и хотелось добиться…
Лекция 5. ОСОБЫЕ ОТНОШЕНИЯ
Каждое конкретное отношение обладает сразу совокупностью свойств. Полезно исследовать группы отношений, у которых совокупности свойств одинаковые.
Прежде всего к таковым относятся отношения ЭКВИВАЛЕНТНОСТИ. Это отношения, которые одновременно обладают свойствами рефлексивности, симметричности и транзитивности. Отношение «равенства» чисел – самый простой пример эквивалентности. Или «учиться в одной студенческой группе».
Интересно, что каждый об'ект эквивалентен сам себе хотя бы потому, что для самого невероятного об'екта, который ни на что не похож, по отношении к самому себе выполняются рефлексивность, симметричность и транзитивность. Обычно же об'екты не столь уникальны и имеют место множества (любят говорить КЛАССЫ) эквивалентных между собой об'ектов.
Самое важное свойство отношения эквивалентности (то есть свойство отношения, которое само определено с помощью трех вышеупомянутых свойств) покажем на примере. Если взять первозданный хаос, то есть все множество студентов университета, которые болтаются по коридорам, сидят в буфете или в аудиториях, а еще лучше дома или вообще неизвестно где, то отношение «учиться в одной группе» РАЗБИВАЕТэто множество на подмножества-группы. Каждый студент принадлежит какой-то группе и не может принадлежать сразу двум. (В реальной жизни возможны исключения из этих очевидных свойств, но мы по умолчанию рассматриваем лишь нормальных студентов).
В качестве лабораторной работы по разбиению рекомендуется разбить тарелку. Желательно, из китайского фарфора. А потом созерцать осколки, каждый из которых будет для фарфоринок классом эквивалентности применительно к отношению «принадлежать одному и тому же осколку»… Это лучше, чем разбивать группы, тем более, что ортодоксальные алгебраисты под «группой» понимают не кучу студентов, а нечто фундаментальное математическое… Но это уже начало другой романтической истории про молоденького французского гения и (увы) дуэлянта – Эвариста Галуа.
Заметную роль в математике играют и отношения ПОРЯДКА, обладающие свойствами транзитивности и антисимметричности. Нарушение любого из них нарушает порядок не только с точки зрения математики, но и здравого смысла.
Примеры. «Быть больше» на множестве чисел, «быть после» в очереди, «быть старше по званию» в армии.
Дополнительно, если порядки обладают свойством полноты, то их называют СОВЕРШЕННЫМИ. Например, «больше», на множестве действительных чисел.
Если отношение еще и рефлексивно, то порядок называют НЕСТРОГИМ (ЧАСТИЧНЫМ). Например, «выть выше или равного роста». А предыдущие три примера – это отношения СТРОГОГО (ЛИНЕЙНОГО)порядка, поскольку в них имеет место антирефлексивность.
Отрадно то, что теоретико-множественные отношения порядка как правило совпадают с житейским представлением об упорядочении. Но не всегда. Знаменитое отношение «быть братом» с одной стороны очень похоже на отношение порядка. Иван брат Марьи, но Марья не брат Петра – вроде( !) антирефлексивность. Если Иван брат Петра, а Петр брат Марьи, то Иван брат Марьи. Вроде бы( !) транзитивность. Но, если Иван брат Петра, то и Петр брать Ивана – то есть с анитисимметричностью все-таки не получается. Хуже того, если Иван брат Петра, а Петр брать Ивана, то по свойству транзитивности придем к заключению, что Иван брат Ивана. А чтобы не возникал такой абсурдный результат, отношение «быть братом» признается нетранзитивным.
Более интересными являются другие отношения, очень похожие на отношения порядка. Например, «быть немного выше ростом». Это антисимметричное, но нетранзитивное отношение. Иван немного выше ростом Петра, Петро немного выше ростом Егора. Но Иван намного выше ростом Егора. Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ. Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, ящерицы «плавно» превращаются в птиц и т.п.
Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные, на которые накладывают ряд дополнительных свойств, изучаются в рамках раздела математики с экзотическим названием ТЕОРИЯ РЕШЕТОК. Это название пугает, поэтому в нашей стране первоначально слово latticeпереводили как " структура". Но когда в математике все шире стал употребляться термин structure, то пришлось ему отдать русское слово структура, а решетки стали и у нас в стране решетками.
Можно предположить, что название «решетки» возникло в связи с использованием так называемых диаграмм Хассе, которые может и напоминают экстравагантные решетки для окон… Но мы договорились без формул, а тем более без рисунков. Рисунки, в отличие от формул, народ любит. Но рисовать картинки в Ворде еще противнее, чем формулы, поэтому постараемся, насколько, конечно, возможно, компенсировать и их красноречием…
Начнем с примеров решеток.
Возьмем слова: о, ор, вор, ворот, кол, олово, коловорот, и упорядочим их по вхождению одних слов в другие (не забывая, что каждое слово входит в само себя). Это будет наша первая решетка.
Можно убедиться, что здесь выполняются все свойства частичного порядка. А о дополнительных свойствах поговорим позже.
Числа: 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить нацело, так же образуют решетку.
Обычные действительные числа с отношением «больше или равно» дают одну из самых распространенных решеток. Хотя для нас она менее экзотическая. Можно сказать, простая как бревно…
Множество всех подмножеств какого-то множества с отношением включения также дает решетку, причем, с рядом замечательных свойств.
Для определения решетки договоримся называть элемент НАИБОЛЬШИМ (НАИМЕНЬШИМ), если он больше (меньше) любого другого элемента частично-упорядоченного множества– кратко ЧУМ. За математиками иногда можно заметить педантичность до занудства, а иногда непонятную приблизительность. Строже и точнее было бы здесь и далее, вопреки сложившейся традиции, применительно к ЧУМ, обладающим свойством рефлексивности, говорить «больше или равно» " НАИБОЛЬШИЙ ИЛИ РАВНЫЙ" и т.п. Но мы тоже будем говорить кратко «больше», подразумевая эти более длинные и точные словосочетания. Наибольший элемент, если таковой существует – единственный. На то он и наибольший. С наименьшим все аналогично.
МАКСИМАЛЬНЫМ (МИНИМАЛЬНЫМ)называется элемент ЧУМ, больше (меньше) которого в этом множестве нет элементов. На первый взгляд это определение повторяет предыдущее. Но максимальных элементов в ЧУМможет быть и несколько. Если рассматривать современный мир, упорядоченный по этажам власти, то все главы государств «максимальны», но каждый в своей стране, поскольку главнее его нет. Но каждый из них не главнее другого главы. Главы всей планеты не существует и даже Генсек ООН его не заменит. Если бы, следуя фантастическим романам, существовал глава Земли, то он был бы и максимальным и наибольшим элементом.
Если, далее, возьмем множество студентов потока и наведем в нем частичный порядок. Имеется в виду не «всеми доступными средствами», а лишь отношением «учится лучше (или одинаково)», считая, что ради такого дела можно для любых двух студентов решить, который лучше… Из этого множества выделим группу ух-005 и найдем студентов потока, которые учатся лучше всех студентов группы ух-005. То есть найдем на потоке студентов, «наибольших» для этой группы. Таких студентов может оказаться несколько, если только «наибольший» студент группы не является одновременно наибольшим элементом всего потока. Такое множество наибольших элементов называется множеством МАЖОРАНТ. Рассматривая наименьших студентов, получим множество МИНОРАНТ. А теперь в самом множестве мажорант (минорант) найдем наименьший (наибольший) элемент [это не опечатка!]. Для данного примера это будут лучший и худший студенты самой группы ух-005. Такие элементы называются соответственно СУПРЕМУМи ИНФИМУМ. Или кратко, supи inf.
Для множества чисел 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить, возьмем подмножество чисел 3, 6, 9. Для него множество мажорант будет 12, 36. Множество минорант – 3, 1. супремум – 12, инфимум – 3.
РЕШЕТКОЙназывается ЧУМ, в котором для любого непустого подмножества существуют супремум и инфимум.
Решетки, которые получаются как множества подмножеств данного конечного множества, с отношением включения, относятся к БУЛЕВЫМ РЕШЕТКАМ. Для тех, кто знают про булеву алгебру, добавим, что традиционная булева алгебра есть решетка из двух элементов: «истина», «ложь», с отношением порядка «более истинный».
Определить решетку можно и «алгебраически». Если для элементов множества с отношением частичного порядка (частично-упорядоченным множеством) выполняются законы коммутативный, ассоциативный, поглощения и идемпотентности, то такое частично-упорядоченное множество называется решеткой.
Если, кроме того, выполняется дистрибутивный закон – то решетка называется дистрибутивной.
Тут уж поверьте на слово – с помощью решеток решен ряд важных проблем. В том числе и теоретического программирования.
Прежде всего к таковым относятся отношения ЭКВИВАЛЕНТНОСТИ. Это отношения, которые одновременно обладают свойствами рефлексивности, симметричности и транзитивности. Отношение «равенства» чисел – самый простой пример эквивалентности. Или «учиться в одной студенческой группе».
Интересно, что каждый об'ект эквивалентен сам себе хотя бы потому, что для самого невероятного об'екта, который ни на что не похож, по отношении к самому себе выполняются рефлексивность, симметричность и транзитивность. Обычно же об'екты не столь уникальны и имеют место множества (любят говорить КЛАССЫ) эквивалентных между собой об'ектов.
Самое важное свойство отношения эквивалентности (то есть свойство отношения, которое само определено с помощью трех вышеупомянутых свойств) покажем на примере. Если взять первозданный хаос, то есть все множество студентов университета, которые болтаются по коридорам, сидят в буфете или в аудиториях, а еще лучше дома или вообще неизвестно где, то отношение «учиться в одной группе» РАЗБИВАЕТэто множество на подмножества-группы. Каждый студент принадлежит какой-то группе и не может принадлежать сразу двум. (В реальной жизни возможны исключения из этих очевидных свойств, но мы по умолчанию рассматриваем лишь нормальных студентов).
В качестве лабораторной работы по разбиению рекомендуется разбить тарелку. Желательно, из китайского фарфора. А потом созерцать осколки, каждый из которых будет для фарфоринок классом эквивалентности применительно к отношению «принадлежать одному и тому же осколку»… Это лучше, чем разбивать группы, тем более, что ортодоксальные алгебраисты под «группой» понимают не кучу студентов, а нечто фундаментальное математическое… Но это уже начало другой романтической истории про молоденького французского гения и (увы) дуэлянта – Эвариста Галуа.
Заметную роль в математике играют и отношения ПОРЯДКА, обладающие свойствами транзитивности и антисимметричности. Нарушение любого из них нарушает порядок не только с точки зрения математики, но и здравого смысла.
Примеры. «Быть больше» на множестве чисел, «быть после» в очереди, «быть старше по званию» в армии.
Дополнительно, если порядки обладают свойством полноты, то их называют СОВЕРШЕННЫМИ. Например, «больше», на множестве действительных чисел.
Если отношение еще и рефлексивно, то порядок называют НЕСТРОГИМ (ЧАСТИЧНЫМ). Например, «выть выше или равного роста». А предыдущие три примера – это отношения СТРОГОГО (ЛИНЕЙНОГО)порядка, поскольку в них имеет место антирефлексивность.
Отрадно то, что теоретико-множественные отношения порядка как правило совпадают с житейским представлением об упорядочении. Но не всегда. Знаменитое отношение «быть братом» с одной стороны очень похоже на отношение порядка. Иван брат Марьи, но Марья не брат Петра – вроде( !) антирефлексивность. Если Иван брат Петра, а Петр брат Марьи, то Иван брат Марьи. Вроде бы( !) транзитивность. Но, если Иван брат Петра, то и Петр брать Ивана – то есть с анитисимметричностью все-таки не получается. Хуже того, если Иван брат Петра, а Петр брать Ивана, то по свойству транзитивности придем к заключению, что Иван брат Ивана. А чтобы не возникал такой абсурдный результат, отношение «быть братом» признается нетранзитивным.
Более интересными являются другие отношения, очень похожие на отношения порядка. Например, «быть немного выше ростом». Это антисимметричное, но нетранзитивное отношение. Иван немного выше ростом Петра, Петро немного выше ростом Егора. Но Иван намного выше ростом Егора. Отношения, похожие на отношения порядка, но не обладающие свойством транзитивности, называют отношениями ТОЛЕРАНТНОСТИ. Хорошей иллюстрацией этого отношения служат многие известные картинки Эшера, где, например, ящерицы «плавно» превращаются в птиц и т.п.
Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные, на которые накладывают ряд дополнительных свойств, изучаются в рамках раздела математики с экзотическим названием ТЕОРИЯ РЕШЕТОК. Это название пугает, поэтому в нашей стране первоначально слово latticeпереводили как " структура". Но когда в математике все шире стал употребляться термин structure, то пришлось ему отдать русское слово структура, а решетки стали и у нас в стране решетками.
Можно предположить, что название «решетки» возникло в связи с использованием так называемых диаграмм Хассе, которые может и напоминают экстравагантные решетки для окон… Но мы договорились без формул, а тем более без рисунков. Рисунки, в отличие от формул, народ любит. Но рисовать картинки в Ворде еще противнее, чем формулы, поэтому постараемся, насколько, конечно, возможно, компенсировать и их красноречием…
Начнем с примеров решеток.
Возьмем слова: о, ор, вор, ворот, кол, олово, коловорот, и упорядочим их по вхождению одних слов в другие (не забывая, что каждое слово входит в само себя). Это будет наша первая решетка.
Можно убедиться, что здесь выполняются все свойства частичного порядка. А о дополнительных свойствах поговорим позже.
Числа: 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить нацело, так же образуют решетку.
Обычные действительные числа с отношением «больше или равно» дают одну из самых распространенных решеток. Хотя для нас она менее экзотическая. Можно сказать, простая как бревно…
Множество всех подмножеств какого-то множества с отношением включения также дает решетку, причем, с рядом замечательных свойств.
Для определения решетки договоримся называть элемент НАИБОЛЬШИМ (НАИМЕНЬШИМ), если он больше (меньше) любого другого элемента частично-упорядоченного множества– кратко ЧУМ. За математиками иногда можно заметить педантичность до занудства, а иногда непонятную приблизительность. Строже и точнее было бы здесь и далее, вопреки сложившейся традиции, применительно к ЧУМ, обладающим свойством рефлексивности, говорить «больше или равно» " НАИБОЛЬШИЙ ИЛИ РАВНЫЙ" и т.п. Но мы тоже будем говорить кратко «больше», подразумевая эти более длинные и точные словосочетания. Наибольший элемент, если таковой существует – единственный. На то он и наибольший. С наименьшим все аналогично.
МАКСИМАЛЬНЫМ (МИНИМАЛЬНЫМ)называется элемент ЧУМ, больше (меньше) которого в этом множестве нет элементов. На первый взгляд это определение повторяет предыдущее. Но максимальных элементов в ЧУМможет быть и несколько. Если рассматривать современный мир, упорядоченный по этажам власти, то все главы государств «максимальны», но каждый в своей стране, поскольку главнее его нет. Но каждый из них не главнее другого главы. Главы всей планеты не существует и даже Генсек ООН его не заменит. Если бы, следуя фантастическим романам, существовал глава Земли, то он был бы и максимальным и наибольшим элементом.
Если, далее, возьмем множество студентов потока и наведем в нем частичный порядок. Имеется в виду не «всеми доступными средствами», а лишь отношением «учится лучше (или одинаково)», считая, что ради такого дела можно для любых двух студентов решить, который лучше… Из этого множества выделим группу ух-005 и найдем студентов потока, которые учатся лучше всех студентов группы ух-005. То есть найдем на потоке студентов, «наибольших» для этой группы. Таких студентов может оказаться несколько, если только «наибольший» студент группы не является одновременно наибольшим элементом всего потока. Такое множество наибольших элементов называется множеством МАЖОРАНТ. Рассматривая наименьших студентов, получим множество МИНОРАНТ. А теперь в самом множестве мажорант (минорант) найдем наименьший (наибольший) элемент [это не опечатка!]. Для данного примера это будут лучший и худший студенты самой группы ух-005. Такие элементы называются соответственно СУПРЕМУМи ИНФИМУМ. Или кратко, supи inf.
Для множества чисел 1, 2, 3, 4, 6, 9, 12, 18, 36 с отношением делить, возьмем подмножество чисел 3, 6, 9. Для него множество мажорант будет 12, 36. Множество минорант – 3, 1. супремум – 12, инфимум – 3.
РЕШЕТКОЙназывается ЧУМ, в котором для любого непустого подмножества существуют супремум и инфимум.
Решетки, которые получаются как множества подмножеств данного конечного множества, с отношением включения, относятся к БУЛЕВЫМ РЕШЕТКАМ. Для тех, кто знают про булеву алгебру, добавим, что традиционная булева алгебра есть решетка из двух элементов: «истина», «ложь», с отношением порядка «более истинный».
Определить решетку можно и «алгебраически». Если для элементов множества с отношением частичного порядка (частично-упорядоченным множеством) выполняются законы коммутативный, ассоциативный, поглощения и идемпотентности, то такое частично-упорядоченное множество называется решеткой.
Если, кроме того, выполняется дистрибутивный закон – то решетка называется дистрибутивной.
Тут уж поверьте на слово – с помощью решеток решен ряд важных проблем. В том числе и теоретического программирования.
Лекция 6. МАТЕМАТИЧЕСКАЯ ЛОГИКА (БЕССМЫСЛЕННАЯ ЛОГИКА)
Обычно, настоящие математики не приспособлены к жизни. Посмотрите на них, если имеете возможность. Они где-то витают… Казалось бы, следует сделать исключение для логиков. Хотя бы потому, что поступки логиков должны быть наиболее логичны. Как бы не так! Все как раз наоборот! На самом-то деле логика строго оговаривает свои «правила игры» и действует пунктуально до беспощадности, граничащей с идиотизмом, в рамках этих правил. При этом их логика с «логикой жизни» имеет не больше общего, чем вы найдете общего в шахматной и Бородинской битвах… Но все-таки есть что-то похожее… Когда страсти с обеих противоборствующих сторон накаляются и дело доходит до рукопашной!…
Кстати, основной клоунский прием: с фанатичным исступлением совершать некие формально логичные, но с точки зрения жизненной реальности абсурдные до идиотизма, действия. Всем, прежде всего детям, очевиден полный идиотизм происходящего, но клоун продолжает поступать ЛОГИЧНО! И ничто не в силах свернуть его с этого пути.
Вообще-то всяких разных логик много. Выражаясь более конкретно – бесконечно много. Поэтому будем говорить не о логике вообще, как это любят делать в некоторых учебниках для юристов, а о математической логике. Тем более, что логики у юристов часто даже меньше, чем у политиков… А от политики предпочтительно держаться подальше… Математическая логика понятие тоже достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл… Логично?
Кстати, основной клоунский прием: с фанатичным исступлением совершать некие формально логичные, но с точки зрения жизненной реальности абсурдные до идиотизма, действия. Всем, прежде всего детям, очевиден полный идиотизм происходящего, но клоун продолжает поступать ЛОГИЧНО! И ничто не в силах свернуть его с этого пути.
Вообще-то всяких разных логик много. Выражаясь более конкретно – бесконечно много. Поэтому будем говорить не о логике вообще, как это любят делать в некоторых учебниках для юристов, а о математической логике. Тем более, что логики у юристов часто даже меньше, чем у политиков… А от политики предпочтительно держаться подальше… Математическая логика понятие тоже достаточно неконкретное, из-за того, что математических логик также бесконечно много. Здесь будем обсуждать некоторые из них, отдавая больше дань традиции, чем здравому смыслу. Поскольку, весьма возможно, в этом и заключен здравый смысл… Логично?