FN_Alg14 (Лекции 2009), страница 2
Описание файла
Файл "FN_Alg14" внутри архива находится в папке "Избранные лекции по алгебре 2-3 семестр для ФН". PDF-файл из архива "Лекции 2009", который расположен в категории "". Всё это находится в предмете "линейная алгебра и аналитическая геометрия" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Но есть классы, не являющиеся множествами (например, класс Рассела). Собственноклассы отличаются от множество только в одном: они не могут рассматриваться в качествеэлементов других классов или множеств. Такое разделение позволяет снять парадоксы теориимножеств.ÌÃÒÓ1) существует пустое множество;2) из любой конечной совокупности множеств M1 , M2 , .
. . , Mk можно образовать конечноемножество {M1 , M2 , . . . , Mk };3) объединение, пересечение, разность двух множеств есть множество;4) существует множества N натуральных чисел, Z целых чисел, Q рациональных чисел, Rдействительных чисел, C комплексных чисел* ;5) для всякого множества M существует множество всех его подмножеств 2M — булеан;6) для любого множества M и любого условия ϕ(x) существует множество {x ∈ M : ϕ(x)}.ÔÍ-12Замечание 14.1. В качестве парадокса иногда приводят следующее. Деревенский парикмахер бреет тех и только тех в своей деревне, кто сам не бреется.
Бреет ли этот парикмахерсебя? Конструкция очень похожа на парадокс Рассела, но на самом деле от него отличается.Здесь нет ссылки на себя самого: все объекты, рассматриваемые в качестве элементов множества (жители деревни) определены, и их конечное число. Здесь не может возникнуть нарушенияпричинно-следственной связи, как в парадоксе Рассела, приводящей к незамкнутости определения. Можно проверить всех жителей деревни на соответствие условию и убедиться в том, чтомножество описанных парикмахеров пусто. Коллективизирующее свойство содержит противоречие и определяет пустое множество.
Увязать рассмотренный пример с парадоксом Расселаможно только в аллегорическом плане.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓОпределение множества свертыванием не связано какими-либо ограничениями. Например,можно попытаться определить множество всех множеств, не принадлежащих самому себе“,”что записывается следующим образом: {x: x ∈/ x}. Формальная сторона определения соблюдена: любое множество, как элемент, может находиться слева от знака принадлежности, и втоже время оно может находиться справа от этого знака. Однако определение A = {x: x ∈/ x}внутренне противоречиво.
Действительно, что верно A ∈ A или A ∈/ A? Если предположить,что A ∈ A, то по своему определению заключаем: A ∈/ A. А если предположить, что A ∈/ A, тозаключаем, что A ∈ A. В результате в любом случае имеем два взаимоисключающих утверждения.Полученное противоречие называют парадоксом Рассела. Это не единственное противоречие в теории множеств, использующей неограниченное свертывание — наивной теориимножеств. Такие противоречия часто называют антиномиями или парадоксами теориимножеств.Причины возникновения парадоксов в теории множеств можно понять на содержательномуровне: объект определяется через другие еще не определенные объекты (в данном случаечерез себя). Налицо нарушение причинно-следственной связи. Это противоречие проявляетсяи в таком определении: множество всех множеств“. Если это множество, то оно должно”принадлежать самому себе.
Но если мы допускаем такое свойство, то мы можем рассмотретьчасть этого множества, а именно множество всех множеств, не принадлежащих самому себе!Так что и здесь есть противоречие.ÌÃÒÓÔÍ-12ÌÃÒÓ29ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓÌÃÒÓÔÍ-12Отметим, что в подавляющем числе предметных областей универсум оказывается множеством. В этом случае все рассматриваемые множества получаются выделением, и противоречийне возникает.Рассмотрим еще один способ определения множеств.
Напомним, что из двух объектов a иb можно образовать упорядоченную пару — новый объект (a, b). Термин упорядоченный“”указывает на то, что объекты (a, b) и (b, a) при различных a и b различаются. Формальноупорядоченную пару можно определить как множество {{a}, {a, b}}. С помощью объектов a1 ,a2 , .
. . , an можно определить упорядоченную n-ку, или кортеж (a1 , a2 , . . . , an ). Объекты a1 ,a2 , . . . , an называются компонентами этого кортежа.Для любого конечного набора множеств A1 , A2 , . . . , An определено множествоA1 × A2 × . . . × An = {(a1 , a2 , . . . , an ): a1 ∈ A1 , a2 ∈ A2 , . . . , an ∈ An }всех кортежей длины n. Это множество называется декартовым произведением множествA1 , A2 , . . . , An .
Множество A × A × . . . × A называют n-й декартовой степенью множества A иобозначают An . В частности, A2 — декартов квадрат A, A3 — декартов куб A.Замечание 14.2. Обратим внимание на то, что, например, A1 × A2 × A3 и (A1 × A2 ) × A3 —разные множества. Первое состоит из кортежей длины 3, а второе из кортежей длины 2, перваякомпонента которых есть кортеж длины 2. Элементы первого множества имеют вид (a1 , a2 , a3 ),а элементы второго — вид ((a1 , a2 ), a3 ).
Однако указанное различие формально, на практикетакие конструкции не различают.14.2. Отображения и соответствияОпределение. Обозначения. Виды отображений (сюръекция, инъекция и биекция). Композиция.Обратное отображение. Соответствия. Композиция соответствий и обратное соответствие.ÌÃÒÓD(F ) = {x ∈ X: ∃y ∈ Y : (x, y) ∈ F }ÔÍ-12Пусть даны множества X и Y . Любое подмножество F ⊂ X × Y называется соответствием. Выделим два тривиальных соответствия: пустое соответствие ∅ ⊂ X × Y иуниверсальное соответствие F = X × Y .Соответствия обозначаются так же, как и отображения: F : X → Y .
Это становится понятным, если заметить, что отображения — фактически частный случай соответствия.Напомним, что отображением F множества X в множество Y называют закон или правило, которое с каждым элементом x ∈ X сопоставляет единственный элемент y ∈ Y . В этомопределении есть неопределенный термин закон или правило“. Но в действительности такой”неопределенный термин в определении отображения не нужен. Этот закон или правило“ —”всего лишь способ определения множества F упорядоченных пар (x, y), удовлетворяющих двумусловиям:• ∀x ∈ X ∃y: (x, y) ∈ F ;• (x, y1 ) ∈ F , (x, y2 ) ∈ F , ⇒ y1 = y2 .Каждому соответствию F : X → Y отвечают область определения соответствияÌÃÒÓÌÃÒÓÌÃÒÓ30ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯR(F ) = {y ∈ Y : ∃x ∈ X : (x, y) ∈ F } .Соответствие F : X → Y всюду определено, если D(F ) = X.
Соответствие F : X → Yфункционально по второй (первой) компоненте, если для любых упорядоченных пар (x, y1 ) ∈F и (x, y2 ) ∈ F выполняется условие y1 = y2 . Всюду определенное функциональное по второйкомпоненте соответствие называется отображением.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12и область значений соответствияÌÃÒÓ{(x, z) ∈ X × Z: ∃y ∈ Y (x, y) ∈ F, (y, z) ∈ G} .Легко увидеть, что в частном случае отображений композиция соответствий совпадает с композицией отображений.Замечание 14.4. Установилась традиция, когда отображения, участвующие в композиции,записываются справа налево.
Это связано с равенством g ◦ f (x) = g(f (x)). Для композициисоответствий принято то же соглашение, однако это не является обязательным* .Для соответствия F : X → Y множество{(y, x) ∈ Y × X: (x, y) ∈ F }idX = (x, y) ∈ X 2 : x = y .i∈Ii∈I*В книге Дискретная математика“ А.И. Белоусова, С.Б. Ткачева (вып. XIX серии Математика в техниче””ском университете“) как раз использовано прямое обозначение композиции.**Это не совсем точно: область определения F −1 ◦ F может не совпадать с множеством X.ÔÍ-12Индексация семейства множеств нужна лишь из соображений удобства.
Например, можнобыло бы рассмотреть множество A, элементами которого являются множества и ввести операцию ∪A = {z: ∃u ∈ A, z ∈ u}, которая представляет собой объединение всех элементов множества A.ÌÃÒÓПусть I, U — некоторые множества. Отображение F : I → 2U можно интепретироватькак индексированное семейство множеств {Ai , i ∈ I}. Например, когда мы пишемA1 , A2 , . . . , Am , то тем самым каждому значению индекса в соответствие ставим множествосемейства.
С помощью индексированных семейств можно ввести объединение и пересечениебесконечного числа множеств. Пусть задано семейство {Ai , i ∈ I}. Тогда определены множества[\Ai = {x: ∃i ∈ I, x ∈ Ai } ,Ai = {x: ∀i ∈ I, x ∈ Ai } ,ÔÍ-12определяет обратное соответствие F −1 . Композиция F −1 ◦ F есть тождественноеотображение** idX : X → X, определяяемое как диагональ декартова квадратаÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Хотя соответствие определено нейтрально — как определенного вида множество, его обозначение указывает, с какой точки зрения рассматривается этот объект.
Можно сказать, чтосоответствие — это многозначное отображение, при которого одному значению x может соответствовать несколько (или ни одного) значений y. Нетрудно сформулировать эквивалентноеопределение соответствия F : X → Y как отображения F : X → 2Y , при котором каждому элементу x ∈ X в соответствие ставится некоторое подмножество y ∈ 2Y (иначе y ⊂ Y ).Основная операция над отображениями — композиция отображений. Она без измененийпереносится на соответствия. Композицией G ◦ F соответствий F : X → Y и G: Y → Zназывается множествоÌÃÒÓÌÃÒÓЗамечание 14.3. Данное определение соответствия (отображения) приводит к тому, чтос этим понятием сливается другое понятие — график соответствия (отображения).Это понятие появляется как прямое обобщение понятия графика функции действительного переменного.
Но если график функции действительного переменного — ее удобное графическоепредставление, то абстрактное понятие графика соответствия ничего не добавляет к самомупонятию соответствия.ÌÃÒÓÔÍ-12ÌÃÒÓ31ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ14. МНОЖЕСТВА ÔÍ-12И ОТНОШЕНИЯÌÃÒÓ• рефлексивные x ρ x (т.е. ∀x(x, x) ∈ ρ) и иррефлексивные x ρ y ⇒ x 6= y (т.е.∀x(x, x) ∈/ ρ);• симметричные x ρ y ⇒ y ρ x и антисимметричные x ρ y, y ρ x ⇒ x = y;• транзитивные x ρ y, y ρ z ⇒ x ρ z.Рефлексивное, антисимметричное, транзитивное отношение называется порядком (отношением порядка). Пример — отношение неравенства a 6 b на множестве действительных чисел(естественный порядок на множестве действительных чисел).Иррефлексивное, антисимметричное, транзитивное отношение называется строгим порядком.
Пример — отношение строго неравенства a < b на множестве действительных чисел.ÔÍ-12• рефлесивное idA ⊂ ρ, иррефлексивное idA ∩ρ = ∅;• симметричное ρ−1 = ρ, антисимметричное ρ−1 ∩ ρ ⊂ idA ;• транзитивное ρ2 ⊂ ρ (здесь ρ2 = ρ ◦ ρ).ÌÃÒÓМожно также выделить нерефлексивные отношения, которые не относятся ни к рефлексивным, ни к иррефлексивным, и несимметричные отношения, которые не относятсяни к симметричным, ни к антисимметричным отношениям.Указанные виды отношений можно определить, используя операции композиции и обратногоотношения (в этих операциях отношение интерпретируется как соответствие):ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓБинарное отношение арности n на множестве A — это любое подмножество n-й декартовой степени An множества A.Отношения служат для описания связей между группами объектов.