отношения порядка

Наибольший размер антицепи в порядке равен наименьшему количеству цепей в разбиениях порядка на непересекающиеся цепи. Доказательство. В одну сторону очевидно: если порядок разбит на k непересекающихся цепей, то любая антицепь пересекается с каждой из цепей не более, чем по одному элементу и в антицепи не больше k элементов. Иначе6 и сложнее в другую сторону. Индукция по числу элементов в порядке. База — порядок из одного элемента — очевидно выполнена. Пусть теорема справедлива для порядков с количеством элементов не больше n. Рассмотрим порядок P, в котором n + 1 элемент. В любом конечном порядке есть минимальные элементы. Пусть m — минимальный элемент в порядке P. Отбросив этот элемент, получаем порядок Q, для которого утверждение теоремы выполнено. Обозначим наибольший размер антицепи в Q через s. По предположению индукции порядок Q разбивается на s непересекающихся цепей. Наибольший размер антицепи в P либо равен s, либо равен s + 1. В последнем случае m содержится в антицепи размера s+1 и порядок P разбивается на s+1 цепь: одна состоит только из элемента m, а остальные разбивают Q на s непересекающихся цепей. Случай, когда наибольший размер антицепи в P равен s. Элемент m тогда сравним с какими-либо элементами порядка Q, а так как он минимальный, то он меньше каких-то элементов. Возьмём такой элемент q ∈ Q, что m < q, а все элементы, меньшие q в цепи C разбиения Q на s непересекающихся цепей, не входят в антицепи размера s. Отметим цепь, которая состоит из m и всех элементов цепи C, начиная с q и больше. Порядок на остальных элементах не содержит антицепей размера s (любая такая антицепь должна пересекать остаток от цепи C) и в нём не больше n элементов. Следовательно, для этого порядка утверждение теоремы справедливо и порядок можно разбить на s − 1 непересекающуюся цепь. Добавляя выделенную цепь, получаем разбиение исходного порядка P на s цепей. В итоге, утверждение теоремы справедливо и для порядка P. Из принципа математической индукции теорема справедлива для всех конечных порядков.  Отношения и их типыОпределение 1. Между элементами множеств A и B дано соотношение, если для каждой пары элементов (a, b), где aA, bÂвыполняется это соотношение или нет. Отношение- это соотношение между элементами одного и того же множества AНоситель отношения – это множество А. Соотношение- это некоторое множество пар элементов. Те пары, для которых оно выполнимо, входят в соотношение, а остальные – нет (равенство чисел, отношение родства, отношение подчинённый – начальник, соотношение стимул – реакция и т.п.).Обозначается соотношение специальным символом: < = > ~ ||, или описывается словами,буквойили символом(a = b, 1 < 2, Сидоров ученик Петрова). Определение не требует осмысленности. Любой набор пар (a, b) будет соотношением. Если множества A и B конечны, соотношение можно задать с помощью таблицы.Для отношений используется другой наглядный способ описания: с использованием графов (от латинского grapheo – пишу). Обычно применяется к конечным множествам. Элементы множества отображаются в виде точек плоскости (вершин графа). Дуга графа – направленный отрезок, связывающий пары в данном отношении. Он не обязан быть прямолинейным.К примеру, отношение “” для чисел 0, 1, 3, 4, 7 представимо графом: Петли -это дуги, начало которых совпадает с концом. Может случиться, что некоторые вершины не связаны ни одной дугой, а другие – одной или даже двумя, ориентированными в разные стороны. Можно представить в видже таблицы, или квадратной матрицей.Такая матрица называется матрицей смежности графа. Использованием графа можно изобразить соотношение между двумя разными множествами. Такой граф является двудольным, поскольку все его вершины разбиваются на две группы: слева – вершины, соответствующие элементам множества A, а справа – элементам B. Стрелки будут следовать только слева направо. К отношениям, которые заданы на одном и том же носителе A можно применять обычные операции объединения, пересечения и дополнения и проверять, входит ли одно отношение в другое.Самое простое отношение, которое присуще каждому множеству – это отношение равенства. Граф отношения равенства состоит из одних петель, а матрица является диагональной (т.е. на диагонали стоят единицы, а по сторонам от неё – нули). Следующее отношение, носителем которого является множество чисел, – отношение “меньше”. Его матрица является треугольной, так как единицы стоят только выше диагонали, а на ней и ниже – нули. Матрица отношения “” соединяет две предыдущие: у неё единицы стоят и на диагонали, и выше неё. У первой и третьей таблиц есть общее свойство: все диагональные элементы равны 1, каждый элемент находится в отношении к самому себе. С иной стороны, первая таблица симметрична: выше и ниже диагонали её структура отношения одинакова. Эти простые свойства имеют свои названия.Пусть во множестве М определено бинарное отношение ρ. Определение 1. Отношение ρ на множестве М называется отношением нестрого порядка, если оно рефлексивно, антисимметрично и транзитивно. Определение 2. Отношение ρ на множестве М называется отношением строго порядка, если оно антирефлексивно, асимметрично и транзитивно. Определение 3. Отношение ρ на множестве М называется отношением линейного порядка, если оно связно. Определение 4. Множество с заданным на нём отношением порядка называется упорядоченным множеством. Примеры: N – множество натуральных чисел. х ρ у ⇔ х ∈ N, у ∈ N и х у. Отношение ρ - рефлексивно, антисимметрично, транзитивно. Поэтому, ρ - отношение нестрогого порядка во множестве N. Отношение ρ не является связным. Следовательно, ρ не является линейным порядком. Z – множество целых чисел. х ρ у ⇔ х ∈ Z, у ∈ Z и х < у.Отношение ρ - антирефлексивно, асимметрично, транзитивно. Следовательно, ρ - отношение строгого порядка во множестве Z. Отношение ρ связно. Следовательно, отношение ρ является строгим линейным порядком. 3. R – множество действительных чисел. х ρ у ⇔ х ∈R , у ∈ R и х ≥ у. Отношение ρ рефлексивно, антисимметрично, транзитивно. Следовательно, ρ - отношение нестрогого порядка во множестве R. Отношение ρ связно. Следовательно, ρ - отношение нестрогого линейного порядка в множестве R.Максимальные и наибольшие элементыМаксимальное (наибольшее) число можно определить, как такое, которое больше всех остальных, или такое, что больше него чисел нет. Для частичного порядка эти два свойства не совпадают. Определение. Пусть в множестве A задано отношение порядка (строгого или нестрогого). Элемент a будем называть максимальным относительно этого порядка, если нет элемента, более предпочтительного, чем он. Наибольшим называется элемент, который более предпочтителен, чем другие элементы множества. В качестве примера приведём выборы кандидатов в депутаты Думы по всем районам. По итогам голосования между ними возникает отношение предпочтения со стороны избирателей. Сравнивать при помощи этого отношения можно только кандидатов из единого списка. У кандидатов из разных списков разные избиратели, и не известно их мнение по отношению к “другому” кандидату. Также если включить таких кандидатов в единый список, число полученных ими голосов изменится. Для кандидатов a и b выполняется a b, если они включены в один список и a набрал меньше голосов, чем b. Для определенного таким образом порядка максимальным элементом будет любой кандидат, прошедший в Думу. В множестве может быть несколькомаксимальных элементов. Наибольший элемент может быть только один. Среди депутатов нет “наибольшего”, они все равноправны по отношению к избирателям. Наибольший элемент существует в иерархии исполнительной власти (премьер–министр). В множестве не может существовать наибольшего элемента. Для конечного множества существует максимальный элемент.Можно построить максимальный элемент, начиная с любого элемента множества и двигаясь слева направо по диаграмме Хассе. В множестве натуральных чисел не существует максимального. Понятия минимального и наименьшего элементов определяются по аналогии.В множестве может существовать один наибольший элемент и несколько минимальных, или один наименьший и один наибольший и т.д. Важным случаем частичного порядка является включение множеств, обозначаемое . Наибольшим в смысле этого отношения будет множество, которое включает в себя все остальные, а максимальным – любое подмножество, которое нельзя включить в большее. Различные отношениятакже рассматривают как множества. Например, как множество пар (a, b) или как множество дуг (ребер) графа. В этом смысле отношения можно сравнивать, проверять, входит ли одно в другое. Можно также искать максимальное (наибольшее, минимальное, наименьшее) отношение того или иного типа, которое существует в данном. Общее понятие максимальности для вложенных эквивалентностей можно сформулировать иначе. Определение. Эквивалентность, вложенная в некоторое отношение, является максимальной, если никакие два её класса нельзя объединить в один.Примеры отношения порядкаПример 1. Возьмём отношение "старше" на множестве людей. Очевидно, что оно транзитивно и антисимметрично, и, поэтому, является отношением порядка.Пример 2. Лексикографический порядок слов в словаре является линейным порядком.Пример 3. Отношение "старше" на множестве людей является линейным порядком.Пример 4. Рассмотрим множество людей. Их можно упорядочить различным образом, например, по росту, цвету кожи, возрасту.Пример 5. Отношение делимости во множестве целых чисел не является порядком. Однако оно рефлексивно и транзитивно, значит является предпорядком.Пример 6.Отношение логического следования является предпорядком на множестве формул логики высказываний.Пример 7. Отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков, отношение «выше» на множестве людей, сравниваемых по росту.Пример 8. Отношение подчиненности в учреждении является нестрогим порядком на множестве сотрудников учреждения. Пример 9.Тождественное отношение является как отношением эквивалентности, так и отношением нестрогого порядка.Пример 10. Алфавитный порядок является отношением строгого порядка на множестве букв.ЗаключениеПо формулировке Н. Бурбаки определение «множество», видно, что отношения между элементами множеств имеют фундаментальное значение в теории множеств. Для усиления описательных возможностей теоретико-множественного языка многие математики используют алгебру отношений. Алгебра отношений позволяет решать задачи формализации не только хорошо структурированных – математических задач, используя при этом строгие отношения, такие как равно (=), больше (>), меньше (<), включение и др., но и слабоструктурированные, которые связаны со сложными межличностными отношениями.Понятие «отношение» относится к философской категории и объединяет такие понятия как «соответствие»,«функция», «отображение».Подмножество – это соответствие между множествами А и В, записываемое в виде, что обозначает подмножество пар. Такие отношения называются бинарными. В литературе бывает другая запись бинарных отношений: элемент «а» является первой координатой, а элемент «b» - второй координатой упорядоченной пары.Элементарным примером бинарных отношений служит отношение обучающихся к знаниям по определённой учебной дисциплине, выраженное в оценках, полученных ими в течение семестра.Список литературыКонспект лекций по математическому анализу. А. Н. Шерстнёв д-р физ. мат. наук, проф. В. А. Зорич (Московский государственный университет), кафедра математического анализа Уральского государственного университета (зав. кафедрой д-р физ. мат. наук, проф. В. В. Арестов).Веретенников Б. М. Дискретная математика. Учебное пособие. Б. М. Веретенников, В. И. Белоусова. -Екатеринбург. Издательство Урал. Ун-та, 2014. - Ч 1.- 132 с.Вадим Дунаев. Занимательная математика множества и отношения. - Санкт-Петербург. БХВ-Петербург- 2010.