И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 5

Ч.1. ТЕОРИЯ МНОЖЕСТВ Рассмотреть случай, когда А — линейно упорядоченное множество. 39. Доказать, что любое частично упорядоченное множество А изоморфно некоторой системе подмножеств множества А, упорядоченной включением ы. 40. Пусть В и Я вЂ” линейные порядки на множестве А. Когда 1 2 В .)г — линейный порядок? 1 2 41. (а) Доказать, что любое непустое конечное частично упорядоченное множество А содержит минимальный и максимальный элементы.

(б) Пусть частично упорядоченное множество А конечно. Доказать, что для любого элемента аЕА существуют элементы Ь и с из А такие, что аиЬ и Ь есть максимальный элемент в А; сяа и с есть минимальный элемент в А. 42. Построить линейный порядок на множестве: (а),Х; (б) М() 4' ()йг' ()...(.) 4'пО..:, (в) Вг комплексных чисел. 43, Доказать, что любое конечное множество можно линейно упорядочить.

44. Доказать, что всякий частичный порядок В на конечном множестве А может быль продолжен до линейного порядка Л й Я на множестве А (см. также задачу 69 из $5). 45. Пусп А — частично упорядоченное множество, в котором каждая цепь имеет не более т элементов, а любое подмножество попарно несравнимых элементов состоит ие более чем из и элементов. Показать, что А имеет не более т п элементов.

46. Пуси < есть частичный порядок иа множестве А, и — час- А ' — в тичный порядок на множестве В. Назовем прямым произведением част ичко упорядоченных множеств А и В миожесгво А х В с заданным на нем отношением я: (а1, Ь1)я(а2, Ь ) а(яла2«Ь(~ВЬ2. Доказать, что я есть частичный порядок наАЯВ. 47. Пусть А — частично упорядоченное множество, а, ЬЕА и аяЬ. Назовем сегментом множество (а, Ь) (х~аяхиЬ). Показать, что множество всех сегментов множества А, частично упорядоченное по включению, иэоморфно некоторому подмножеству прямого произведении А и двойственного к нему частично упорядоченного множества. $ 3. СПЕПИАЛЪНЫЕ БИНАРНЫР ОТНОШЕНИЯ 29 48. Назовем частично упорядоченное множество А самодвойственным, если оно изоморфно двойственному к нему частично упорядоченному множеству.

Доказать, что: (а) имеются в точности два неизоморфных частично упорядоченных двухэлементных множества, каждое из которых самодвойственно; (б) имеется пять попарно неизоморфных частично упорядоченных множеств, имеющих три элемента, и три из ннх самодвойственны. 49*. Будем говорить, что частично упорядоченное множество А удовлетворяет: (1) условию минимальности, если всякое нспусгое подмножество М множества А обладает по крайней мере одним минималъным элементом; (2) условию обрыва убывающих пеней, если всякая строго убывающая цепь в А конечна; (3) условию индуктивности, если для любого свойства Т выполнено следующее: пусть для любого элемента аЕА из справедливости свойства Т для всех элементов, строго меньших а, вытекает справедливость Т для а; тогда свойспюм Т обладают все элементы множества А.

Доказать эквивалентность всех этих условий. 50. Доказать, что частично упорядоченное множество удовлетворяет условию минимальности тогда н толъко тогда, когда все его цепи вполне упорядочены, 51'. Описать все линейно упорядоченные множества А, обладающие таким свойством, что для любых а ~ Ь существует только конечное число с таких, что а(с~Ь. 52. Найти все множества М такие, что существует полный порядок -! Я такой, что Я также является полным порядком на М. 53. Пусть(в: АхА~А и для всех х, у, зЕА (г(х, у) = р(у, х), Р(Х, (9(У, з)) = зг((Г(Х, У), х), р(х х)=х. Определим хиу съ у(х, у) = х.

Доказать, что: (а) я есть частичный порядок на А," (б) (в(х, у) есть точная нижняя грань относителъно порядка ч. 54. Доказать, что любое подмножество множества Р(А), частично упорядоченное по вхлючеиию, имеет точную верхнюю грань и точную нижнюю грань. 55. Доказать, что: (а) любое линейно упорядоченное множеспю есть решетка; (б) семейство всех эквивалентностей на множестве А есть решетка. 30 Ч.1. ТЕОРИЯ МНОЖЕСТВ 56.

Доказать, что в решетке любой максимальный элемент является наибольшим, а любой минимальный элемент является наименьшим. 57, Доказать, что в любой конечной решетке существуют наибольший и наименьший элементы. 58. Привести примеры решеток: (а) без наибольшего элемента, но с наименьшим элементом; (б) без наименьшего элемента, но с наибольшим элементом; (в) без наибольшею и без наименьшего элементов. 59. Доказать, что в любой решетке выполнены тождества: (1,) хну = уОх, (12) х()у = уйх, ((з) х()(У(-)г) = (х()У)Ох, (14) х()(у(!г) = (хг)У)!)х, (1 ) (хщу) (~у = у, (1 ) х! ) (х(.)у) — у.

60. Пусть на множестве М заданы двуместные функции () и ( !, удовлетворяющие тождествам (1, ) — (! ) из предыдущей задачи. (а) Доказать, что для любых х, уЕМ хс)у = у тогда и только тогда, когда х()у = х. (б) Определим х<у «ь х()у = х. Доказать, что М есть решетка от- носительно н, причем точная нижняя и точная верхняя грани элемен- тов х и у совпадают с х()у и хну соответственно. 61. Доказать, что во всякой булевой алгебре М: (а) существует наименьший элемент О и наибольший элемент 1; (б) для всякого аЕМ дополнение (-а) единственно; (в) Ь = -а «ь а(!Ь = Она()Ь = 1; (г) -(а()Ь) = (-а)(1(-Ь); (д) -(а(.)Ь) = (-а)й(-Ь); (е) аЕЬ «ь а()(-Ь) = О. 62. Доказать, что алгебра подмножеств, упорядоченная включением, есть булева алгебра.

63. Доказать, что 1ЕР и ОЮР для любого фильтра .Р. 64. Пусть М вЂ” булева алгебра, А~М. Доказать, что если а ()...г)а мО для любого п>О и любых элементов а,, ..., а ЕА, то л 1'"' и множество Р = (х!хЕМ, а !)...(!а Нхдлянекоторыха, ..., а ЕА) ! ''' в 1' ' в есть фильтр на М. 65. Пусть Р— фильтр на булевой алгебре М и (х( )у) Е Р. Доказать, чтосуществуетфильтрР мРтакой, чтохЕР илиуЕР . 1 1 1' $4.

КАРДИНАЛЬНЫР ЧИСЛА 66. Доказать, что для любого фильтра В следующие условия эквивалентны: (а) 1) есть максимальный фильтр; (б) 2) есть простой фильтр; (в) В есть ультрафильтр. 67'. Доказать, что любой фильтр на булевой алгебре М содержится в некотором максимальном фильтре на М.

бй. Доказать, что для любых элементов а, Ь булевой алгебры М, если неверно, что а~Ь, то существует простой фильтр Р такой, что аЕ1) и Ж.О. 69. Пусть М вЂ” булева алгебра, У вЂ” множество всех простых фильтров на М. Положим для аЕМ й(а) = (1)~ аЕВЕУ).

Доказать, что множество В = (Ь(.Н. есть алгебра подмножеств множества .У. 70. Доказать, что любая булева алгебра изоморфна некоторой алгебре подмножеств подходящего множества (теорема Стоуна) . 71. Доказать, что любой фильтр на конечной булевой алгебре имеет наименьший элемент. 72. Доказать, что любая конечная булеза алгебра изоморфна алгебре всех подмножеств некоторого множества. 1 4. КАРДИНАЛЪНЫЕ ЧИСЛА Множество А называется эквивалентным множеству В (символически А — В), если между А и В можно установить взаимно однозначное соответствие. мощностью множества А называется класс всех множеств, эквивалентных множеству А, и обозначается через А.

Эквивалентные множества называются также равномощными. Обозначимчерезнмощностьмножества Х = 10, 1, ..., н-1), где нЕ Х. Каждое множество А, эквивалентное Х для некоторого и, в называется конечным, а н — числом элементов множества А. Множество, не являющееся конечным, называется бесконечным. Каждое множествоА, эквивалентное множеству,Х = 10, 1, 2, ...), называется счетным и его мощность обозначается через )х . Каждое множество А, эквивалентное множеству действительных чисел и), называется континуальным и его мощность обозначается через с.

зз 3(опнпктп произвольных множеств пазывавггсв кардинальными числами. Елрдпназыпее числа коночных множеств иззывакпсн конечными, длн бесконечных множеств — (>еекоиечными. )(зрдинзльное число с пазмвзегсн мон(нОснгьго конвпенуума. Будем говорить, что Яз и, если А эквшщлеитно некоторому подьоивкеству множества В. Если ЛнЗ, а Я и В ие эквивалентны, то скажем, что А<3. 1. Доказать, что: (а) А — А (рефлексищижть); (б) если А — В, то  — Я (симметричность>; (в) если А — В я  — С, то Я - С (транзптнвность) .

2. Доказать, что: (а)А -В «ь Л=З; А — з (в> если существует функции нз А на В, тоЗВХ 8'. ПустьЯзСЯ>ЙЯ нА — Я .Доказать, чтоА — А . 4. Доказать, что если ЯаВ и ВнЯ, то Я=В (теорема Кантора — Бернюиимйна) . 5. Доказать, по: (а> венное подмножество конечного множества конечно; (б) объединение конечжно числа конечных множеств конечно; (в) примое произведение конечного числа конечных множеств конечно. 6. (а) Доказать, что конечное множество не эквивалентно никакому своему собственному подмножеству н никакому собственному нади ножеству. (б> Доказать, что два конечных множества эквивалентны тогда н только тогда, когда онн содержат одинаковое число элементов.

(в) Доказать, что кардинальных чисел бесконечна много. 7. Доказать, что из всякого бесконечного множества можно выделить счетное подмножество. 8. Доказать, что множество тот «а н только тогда бесконечно, когда оно эквивалентно некоторому собс1 венноыу подмножеству. 9. Показать, что всккое подмножество счетного множества счетно илн конечно. 19. (а) Пусть область определенна функции счетна.