Лекции Русакова, страница 3

(=,≤,≥,⊆)Определение.Отношение ℜ над М называется антирефлексивным, если xρx невыполняется ни для какого x ∈ X . (≠,<,>,⊂)Определение.Бинарное отношение ℜ над М называется транзитивным, если из(х, y) ∈ ℜ и (y, z) ∈ ℜ ⇒ (x, z) ∈ ℜ или, в инфексной записи:если хρy и yρz, то хρz. (=,≤,≥,⊆,<,>,⊂), не транз. (≠)Определение.Для каждого бинарного отношения ℜ над М определено обращение ℜТ(обратное отношение), а именно:(х, y) ∈ ℜТ ⇔ (y, x) ∈ ℜ.Определение.Бинарное отношение ℜ над М называется симметричным, если ℜТ = ℜ,или, в инфиксной записи: если хρy, то yρx. (=,≠)Определение.17Отношение ℜ над М называется антисимметричным, если для любыхx,y∈X из xρy и yρx ⇒ x=y. (≤,≥,⊆)Определение.Отношение ℜ над М называется строго антисимметричным, если длялюбых x,y∈X из <x,y>∈ρ ⇒ <y,x>∉ρ.

(<,>,⊂)Определение.Бинарное отношение ℜ называется отношением эквивалентности, еслионо:1. рефлексивно;2. транзитивно;3. симметрично.Теорема.Для того, чтобы бинарное отношение ℜ позволяло разбить множествоМ на классы необходимо и достаточно, чтобы ℜ было эквивалентным.Доказательство:Докажем необходимость утверждения.Пусть имеется множество М и его разбиение на классы, то есть пусть аи b находятся в одном классе и связаны отношением ρ.

Легко видеть, что вклассе Ка выполняется:аρа;если аρb и bρc, то аρс;если аρb (а это так), то bρa,то есть отношение ρ является эквивалентным.Докажем достаточность.Пусть1. ρ — отношение эквивалентности между элементами множества М;182. Ка — класс элементов х ∈ М, эквивалентных элементу а, то естьxρa, где ρ – отношение эквивалентности.Так как ρ — отношение эквивалентности, то в силу рефлексивностиа ∈ Ка. Докажем, что два класса Ка и Кb либо совпадают, либо непересекаются. Пусть с ∈ Ка и с ∈ Кb, то естьсρа(3)исρb.(4)В силу симметричности из (3) ⇒аρс(5)и, учитывая (5) и транзитивность ρ , имеем:аρb .(6)Для ∀х ∈ Ка по определению имеемхρа .(7)Учитывая (6): аρb и свойство транзитивности из (6) и (7) имеем хρb, тоестьх ∈ Кb.Аналогичнодоказывается,что∀y ∈ Кbодновременнопринадлежит и Ка.

Таким образом, два класса Ка и Кb, имеющих хотя быодин общий элемент, совпадают между собой. Итак, получено разбиениемножества М на классы по заданному отношению эквивалентности, что итребовалось доказать.Замечание.Понятие разбиения множества на классы тесно связано с понятиемотображения, а именно:Пусть ƒ – отображение множества А в множество В,то естьbƒ: A →B . Множество элементов А, образы которых в В совпадают,образуют класс элементов,то есть возникает некоторое разбиениемножества А.19Пусть В – совокупность тех классов, на которые разбито множество А.Ставя в соответствие каждому элементу а ∈ А тот класс ( то есть элемент изВ), к которому а принадлежит, то есть g: a → Ка, получаем отображение Ана множество В.Примеры.1.

Пусть ƒ – проекция плоскости хy на ось х. Прообразы точек оси х –вертикальные прямые. Следовательно, этому отображению отвечаетразбиение плоскости на параллельные прямые.2. Разобьём все точки трехмерного пространства на классы, объединив водин класс точки, равноудаленные от начала координат. Каждый класспредставляет собой сферу некоторого радиуса. Совокупность всех этихклассов можно отождествить с множеством всех точек, лежащих на луче[0, ∞), то есть разбиению трёхмерного пространства на концентрическиесферы отвечает отображение этого пространства на полупрямуюreiϕ → r (двумерный случай)илиƒ:ƒ: r(i cosα + j cosβ + kcosγ) → r(трёхмерный случай).3. Объединим в один класс все действительные числа с одинаковойдробной частью. Этому разбиению отвечает отображение прямой линии наотрезок [0, 1): ƒ: d.k → 0.k.1.06.

Упорядоченные множества. Изоморфизм теориимножеств.Определение.Пусть М – произвольное множество, ρ – бинарное отношение,определяемоеназываетсянекоторымчастичноймножествомℜ⊂ M ×M .упорядоченностью,условиям:1. рефлексивности: аρа ;20еслиЭтооноотношениеудовлетворяет2. транзитивности: из аρb & bρc ⇒ aρc ;3. антисимметричности: из аρb & bρa ⇒ a = b.Частичную упорядоченность обозначают символом ≤ .Определение.Множество, в котором задана некоторая частичная упорядоченность,называется частично упорядоченным.Примеры.Всякое множество можно тривиальным образом рассматривать какчастично упорядоченное, если положить a ≤ b ⇔ a = b , то есть за частичнуюупорядоченность всегда можно принять отношение тождества ε.Пусть М – множество всех непрерывных функций на отрезке[α , β ]èëè Ñ[α ,β ] .

Положим f ≤ g ⇔ f (t ) ≤ g (t ) äëÿ ∀t ∈ [α , β ]. Это будетчастичная упорядоченность функций из Ñ[α,β ] .Множество всех подмножеств Σ некоторого множества М частичноупорядочено по включению, то есть M 1 ≤ M 2 означает M 1 ⊂ M 2 .Множество всех натуральных чисел частично упорядочено, если a ≤ bозначает “b делится без остатка на а”.Определение.Элемент а называется максимальным, если из a ≤ b следует, что b = a .Определение.Элемент а называется минимальным, если из c ≤ a следует, что c = a .Определение.21Частично упорядоченное множество, для любых двух точек а, bкоторого найдется следующая за ними точка с (a ≤ c, b ≤ c) , называетсянаправленным.Определение.Пусть:1.

М и M ' – частично упорядоченные множества;â2. f : M →M '.â3. Отображение f : M →M ' сохраняет порядок, то есть если из a ≤ b ,где a ∈ M , b ∈ M ' ⇒ f (a ) ≤ f (b ) .Тогда.Отображениеâ→f :M M ' называется изоморфизмом частичноупорядоченных множеств М и M ' , если оно1. биективно(существуетвзаимооднозначноесоответствиемеждуэлементами множеств М и M ' );2. соотношение f (a ) ≤ f (b) ⇔ a ≤ b .Пример.ПустьМ – множество натуральных чисел, частично упорядоченное по“делимости”;M ' — множество натуральных чисел, упорядоченное естественнымобразом,то есть b ≥ a , если b ≥ a – неотрицательноечисло,то естьb − a ≥ 0.íàТогда отображение f : M →M '{n → n}, то есть ставящее ∀ числу nего само:1.

сохраняет порядок;222. не является изоморфизмом.Замечание.Отношениемножествамиизоморфизмапредставляетмеждусобойчастичноупорядоченнымиотношениеэквивалентности(рефлексивность, транзитивность, симметричность). Следовательно, какоелибо множество частично упорядоченных множеств можно разбить наклассы изоморфных между собой подмножеств.Определение.То общее, что присуще любым двум изоморфным между собойчастично упорядоченным множествам, называется порядковым типом.Определение.ПустьМ – частично упорядоченное множество;a ∈ M ,b ∈ M ;не выполняется ни одно из соотношений a ≤ b и b ≤ a .Тогда а и b называются несравнимыми элементами.Определение.Если в частично упорядоченном множестве М несравнимых элементовнет, то множество М называется упорядоченным (линейно упорядоченным,совершенно упорядоченным), то есть если оно:частично упорядочено;для a ∈ M , b ∈ M имеет место a < b либо b < a .23Замечания.Всякое подмножество упорядоченного множества само упорядочено.Таккакупорядоченностьестьчастныйслучайчастичнойупорядоченности, то можно говорить о порядковом типе упорядоченногомножества.Примеры.Пусть= {1,2,3,...} – множество натуральных чисел с естественнымотношением порядка.

Его порядковый тип обозначают ω.Если два частично упорядоченных множества изоморфны междусобой, то они, конечно, имеют одинаковую мощность, так как изоморфизм –это биекция. Следовательно, можно говорить о мощности, отвечающейданному порядковому типу, например, типу ω отвечает мощность ℵ0 .Однако обратное неверно, так как множество данной мощности может бытьупорядочено, вообще говоря, многими разными способами.Порядковый тип линейно упорядоченного конечного множестваоднозначно определяется числом n его элементов и обозначается n.Для счётного множества натуральных чисел возможен такой тип:1,3,5,,2,4,6,, то есть любое чётное число следует за любым нечётным, приэтом чётные и нечётные числа упорядочены по возрастанию.1.07.

Счётные множества. Теорема Кантора.Все множества можно разделить на конечные и бесконечные.В качестве первых можно привести, например, 1) множество всехвершин некоторого многогранника; 2) множество всех простых чисел, не24превосходящих данного числа; 3) множество молекул воды в данный моментна Земле и т.д.В качестве бесконечных множеств можно указать, например,множество всех натуральных чисел;множество всех многочленов с рациональными коэффициентами и т.д.Определение.Множество называется бесконечным, если из него можно извлечь одинэлемент, два элемента и т.д., причём после каждого такого шага в этоммножестве ещё останутся элементы.Определение.Счётное множество – это такое множество, элементы которогобиективно сопоставимы со всеми натуральными числами,то есть это –множество, элементы которого можно занумеровать в бесконечнуюпоследовательность: а1, а2, а3,…, аn,….Примеры счётных множеств.Множество всех целых чисел.Установим биекцию между множествами натуральных и целых чиселследующим образом:0 –1 1 –2 2 …,1 2 3 4 5 …, то естьn ↔ 2n + 1, при n ≥ 0;n ↔ 2|n|, при n < 0.Множество всех чётных положительных чисел, так как n ↔ 2n –биекция.Множество степеней числа 2: 2, 4, 8,…,2n,… при показателе степениn ≥ 1.