Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Упорядоченные множества

Содержание

ВВЕДЕНИЕ…………………………………………………………………………………….……..3

1. Понятие множества……………………………………………………………………………......4

2. Упорядоченные множества………………………………………………………………………..5

3. Вполне упорядоченные множества ……………………………………………………………..10

ЗАКЛЮЧЕНИЕ…………………………………………………………………………………........11

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ…..………………………………………………...12

Введение

В настоящее время алгебра понимается в основном как общая теория алгебраических операций и отношений. Ее характеризует большая внутренняя естественность исходных идей и задач, единство методов, далеко идущая широта основных понятий. Ее область очерчена четко и ясно. И все же существующие границы теории нельзя признать установленными прочно и окончательно. Все чаще начинает выявляться стремление выйти за ее пределы. Ощущается потребность рассматривать операции не только полные, но и частичные.

Теорию упорядоченных множеств создал Г. Кантор.. В 1883 он ввёл понятие вполне упорядоченного множества и порядкового числа, а в 1895 - понятие упорядоченного множества и порядкового типа. В 1906-07 С. О. Шатуновский сформулировал определения направленного множества (у Шатуновского - расположенный комплекс) и предела по направленному множеству (амер. математиками Э. Г. Муром и Г. Л. Смитом эти же понятия были рассмотрены независимо от Шатуновского, но значительно позднее - в 1922). Общее понятие частично упорядоченного множества принадлежит Ф. Хаусдорфу (1914).

Таким образом, теория частичных алгебраических действий, будучи продолжением теории полных действий, пользуясь ее достижениями, связанная с ней идеями и опытом приложений за пределами алгебры, все же должна оформиться как самостоятельное направление в обширной области современной алгебры.

К настоящему времени опубликованы сотни работ, специально посвященных изучению частичных действий. Что касается работ, в которых те или иные частичные действия встречаются по ходу исследования, то число их не поддается оценке. О частичных действиях говорится и в некоторых общих алгебраических трудах, но всегда очень кратко.

Понятие множества

Множество - это любая определенная совокупность объектов. Объекты, из которых составлено множество, называются его элементами.

Элементы множества различны и отличны друг от друга. Ели объект Х является элементом множества М, то говорят, что х ϵ М. В противном случае, говорят, что х не принадлежит множеству М.

Множество, не содержащее элементов, называется пустым. Совокупность объектов, которые не являются множеством, называются классом. Некоторое, достаточно широкое множество, будем называть универсальным.

Множество - это совокупность определенных различаемых объектов таких, что для любого объекта можно установить, принадлежит этот объект данному множеству или нет.

Множество, которое подчиняется лишь такому ограничению, может содержать объекты почти любой природы. Например:

множество всех подземных станций Лондона;
множество левых ботинок;
множество натуральных чисел: 1, 2, 3, 4 и т.д.
множество символов, доступных специальному печатающему устройству;
множество кодов операций конкретного компьютера;

множество зарезервированных слов языка паскаль.

В конечном счете, нас будут интересовать следующие множества:

множество идентификаторов, встречающихся в определенной программе;
множество операций в той же самой программе;
множество операций, которые могут быть выполнены после данной инструкции в той ж программе.

Однако эти множества также являются достаточно сложными для исследования. Поэтому для большинства примеров лучше использовать некоторые абстрактные множества, такие как множества чисел.

Множества обычно обозначают прописными буквами, например А, и специфицируют одним из двух путей. Если множество содержит несколько элементов, то мы просто записываем все его элементы. Например, если мы определим А как множество всех целых чисел строго между 6 и 10, то это можно записать следующим образом:

А={7, 8, 9} и прочитать так «А- множество, содержащее 7, 8, 9» . Здесь, символ «=» используется в определенном смысле: А равно множеству..

Упорядоченные множества

Упорядоченные и частично упорядоченные множества (математические) множества, в которых каким-либо способом установлен порядок следования их элементов или, соответственно, частичный порядок. Понятия порядка и частичного порядка следования элементов определяются следующим образом. Говорят, что для пары элементов х, у множества М установлен порядок, если указано, который из этих элементов следует за другим (если у следует за х или, что то же самое, х предшествует у, то пишут х π у, у ). Говорят, что в множестве М установлен частичный порядок следования элементов, если для некоторых пар его элементов установлен порядок, причём выполнены следующие условия:

1) никакой элемент не следует сам за собой;

2) если х π у и у π z, то х π z (транзитивность отношения порядка).

Может случиться, что в частично упорядоченном множестве М порядок не установлен ни для какой пары элементов М. С др. стороны, может случиться, что порядок установлен для всех пар различных элементов М, в этом случае частичный порядок следования элементов, установленный в множестве М, называют просто порядком следования элементов, или линейным порядком (упорядоченные множества, таким образом, являются видом частично упорядоченных множеств). Например, будем считать, что комплексное число a’ + b’i следует за комплексным числом и а + bi, если a’ > a и b’ > b.

Любое множество комплексных чисел становится тогда частично упорядоченным. В частности, частично упорядоченным становится любое множество действительных чисел (рассматриваемых как специальный случай комплексных).

Т. к. при этом порядок следования таков, что действительное число a’ следует за действительным числом, а тогда и только тогда, когда a’ больше а, то всякое множество действительных чисел оказывается даже просто упорядоченным. Понятия частично упорядоченного (иначе – полуупорядоченного) и упорядоченного множества принадлежат к числу основных общих понятий.

Множество M называется упорядоченным, если между его элементами установлено некоторое отношение a < b("a предшествует b"), обладающее следующими свойствами:

1) между любыми двумя элементами a и b существует одно и только одно из трех соотношений: a = b, a < b, b < a;

2) для любых трех элементов a, b и c из a < b, b < c следует a < c. Пустое множество считается упорядоченным.

Замечание. Знак = мы всегда понимаем в смысле тождества, совпадения элементов. Запись a = b просто означает, что буквами a и bобозначен один и тот же элемент множества M. Поэтому из свойства 1 следует, что между двумя различными элементами выполняется одно и только одно из двух соотношений a < b или b < a. Если a предшествует b, то говорят, что b следует за a и пишут: b > a. Отношение a > b обладает, как легко проверить, свойствами, аналогичными 1 и 2. Его можно принять за основное, определив тогда через него отношение a < b. Если в упорядоченном множестве M поменять ролями отношения < и >, т. е. вместо a < b писать a > b, и наоборот, то получится новое упорядоченное множество M', порядок которого называется обратным относительно порядка M. Например, для приведенного выше порядка во множестве натуральных чисел обратным будет порядок:

..., 3, 2, 1.

Два упорядоченные множества, составленные из одних и тех же элементов, но расположенные в разном порядке, считаются различными. Поэтому при задании упорядоченного множества через его элементы необходимо указать их порядок. Будем считать, что запись слева направо соответствует порядку элементов, и сохраним прежнее обозначение фигурными скобками. Одно и то же множество можно упорядочить различным образом (если оно содержит не менее двух элементов). Так, множество натуральных чисел можно упорядочить обычным образом или в обратном порядке, можно нечетные числа поставить впереди четных или наоборот, располагая те и другие в возрастающем или убывающем порядке. Получим упорядоченные множества

{1, 2, 3, ...}, (1)

{..., 3, 2, 1}, (2)

{1, 3, 5, ..., 2, 4, 6, ...}, (3)

{1, 3, 5, ..., 6, 4, 2}, (4)

{..., 5, 3, 1, 2, 4, 6, ...}, (5)

{..., 5, 3, 1, ..., 6, 4, 2}. (6)

Элемент, не имеющий предшествующего, называется первым, а элемент, не имеющий следующего, - последним. Элементы a и bназываются соседними, если не существует c, для которого a < c < b или b < c < a. Если a и b - соседние и a < b, то говорят, что aнепосредственно предшествует b, а b непосредственно следует за a. Упорядоченное множество (1) имеет первый элемен и не имеет последнего, множество (2), наоборот, имеет последний элемент, но не имеет первого, множество (4) имеет как первый элемент, так и последний, а множество (5) - ни первого элемента, ни последнего, множество (3) содержит два элемента, не имеющих непосредственно предшествующего, множество (6) - два элемента, не имеющих непосредственно следующего. Во всех этих множествах каждый элемент имеет соседний. Множество рациональных чисел, расположенных по возрастанию, не имеет соседних элементов, так как между любыми числами a и b лежит число

Если a = b или a < b, то пишут: a ≥ b; если a = b или a > b, то пишут: a ≥ b. Из определения 1 легко вытекает справедливость следующих двух теорем:

Теорема 1. Если a≤ b и b≤a, то a = b.

Теорема 2. Если a≤ b и b≤c, то a≤ c. Если a≥b и b≥c, то a≥c . При этом, если хотя бы в одном из данных неравенств имеется строгое неравенство, то и в полученном неравенстве будет строгое неравенство.

Определение 2. Два упорядоченных множества A и B называются подобными, если между ними можно установить взаимно однозначное соответствие, сохраняющее порядок элементов, т. е. такое, что из

a₁→b₁, a₂→b₂и a₁< a₂

следует b₁< b₂.

Из определения 2 следует, что все множества, содержащие лишь один элемент, подобны и пустое множество подобно лишь самому себе. О подобных множествах говорят, что они имеют один и тот же тип. Отношение подобия обозначается так:A ͌ B.

Отношение подобия обладает следующими тремя свойствами:

1) Рефлексивность:A ͌ A
     2) Симметрия: если A ͌ B , то B ͌ A.
     3) Транзитивность: если  и B ͌ C, то A ͌ C.

Сравнивая определение подобия с определением равномощности, убеждаемся, что первое включает второе, т. е. верна следующая: A ͌ B

Теорема 3. Подобные множества равномощны; из A ͌ B следует A ~ B.

Обратное утверждение не верно. Так, множества (1) и (2) равномощны (даже просто равны как неупорядоченные множества), но не подобны, так как множество (1) имеет первый элемент, а множество (2) - не имеет тогда, как при соответствии подобия первому элементу одного множества должен соответствовать первый элемент другого. Тем не менее, для конечных множеств теорема, обратная теореме 3, также верна. А именно:

Теорема 4. Если конечные, упорядоченные множества равномощны, то они подобны.

Эта теорема ввиду свойств 1) - 3) подобия является непосредственным следствием приведенной ниже теоремы 7. Для любых множеств в известной мере обратной теореме 3 является следующая теорема:

Теорема 5. Любое множество A, равномощное упорядоченному множеству B, само можно упорядочить, т. е. определить для его элементов отношение порядка, обладающее свойствами 1) и 2), и притом так, что полученное упорядоченное множество подобно B.

Доказательство. Если a₁и a₂- любые элементы множества A, b₁и b₂- соответствующие им, при взаимно однозначном отображении A и B, элементы B, и b₁< b₂, то положим a₁< a₂. Легко проверить, что определенное как отношение порядка в A обладает свойствами 1) и 2) и, очевидно, A подобно B.

Теорема 6. Любое конечное упорядоченное множество A содержит первый и последний элемент (если только A не пусто).

Доказательство. Пусть A не имеет последнего элемента. Берем любой элемент a₁ϵ A.

Так как он не последний, то существует a₂ϵ A такой, что a₁< a₂; так как a₂- не последний, то существует a₃ϵ A такой, что a₂< a₃. Если элемент a_nпостроен, то существует a_n+1ϵ A такой, что a_n< a_n+1. По индукции элемент a_nпостроен для любого n.

Пусть

N' = {a₁, a₂, a₃, ...}

Пусть

N' = {a₁, a₂, a₃, ...}

- множество всех построенных элементов. Очевидно, что из i < k следует по свойству 2) a_i< a_k, откуда по свойству 1)a_i≠a_k. Значит, N' равномощно множеству натуральных чисел. Поэтому множество A бесконечно (см. теорему 5), что невозможно. Существование первого элемента доказывается аналогично.

Теорема 7. Любое конечное множество можно упорядочить. Все конечные упорядоченные множества с одним и тем же числом элементов n > 0 подобны отрезку |1, n| натурального ряда и, значит, подобны между собой.

Доказательство. Пустое множество упорядочено по определению. Если A≠0 - конечное множество, то A ~ |1, n|. Отрезок |1, n|, очевидно, есть упорядоченное множество. По теореме 5 множество A можно упорядочить. Пусть теперь A - любое конечное упорядоченное множество с числом элементов n > 0. По теореме 6 множество A содержит первый элемент a₁. Если n > 1, то множество

и снова содержит первый элемент a₂, причем a₁< a₂. Пусть уже построен элемент a_i. Если i < n, то

и по теореме 6 оно содержит первый элемент a_i+1, причем a_i< a_i+1. Так мы построим элементы a_iдля всех . Множество

A_n= {a₁, a₂, ..., a_n} ~ |1, n| ~ A.

Множество A не равномощно собственному подмножеству (см. теорему 1). Значит,

A = A_n= {a₁, a₂, ..., a_n}.

Очевидно, что из i < k следует a_i< a_k, т. е. A подобно отрезку |1, n|.

Из этой теоремы следует, что все n! возможных перестановок множества с n элементами имеют один и тот же тип.

Вполне упорядоченные множества

Упорядоченное множество называется вполне упорядоченным, если каждое его подмножество обладает первым элементом (т. е. элементом, за которым следуют все остальные). Все конечные упорядоченные множества вполне упорядочены. Натуральный ряд, упорядоченный по возрастанию (а также некоторыми др. способами), образует вполне упорядоченное множество. Важность вполне упорядоченных множеств определяется главным образом тем, что для них справедлив принцип трансфинитной индукции.

Упорядоченные множества, имеющие одинаковый порядковый тип, обладают и одинаковой мощностью, так что можно говорить о мощности данного порядкового типа. С др. стороны, конечные упорядоченные множества одинаковой мощности имеют один и тот же порядковый тип, так что каждой конечной мощности соответствует определённый конечный порядковый тип. Положение меняется при переходе к бесконечным множествам. Два бесконечных упорядоченных множества могут иметь одну и ту же мощность, но разные порядковые типы.

Частично упорядоченное множество называется направленным, если для всяких его элементов х и у существует такой элемент z, что z ϕ̲ х и z ϕ̲ у (a ϕ̲ b означает, что либо a ϕ̲ b, либо а = b). Понятие направленного множества позволяет дать весьма общее определение предела. Пусть f (p) - числовая (для простоты) функция, заданная на направленном множестве М; число с называется пределом f (p) по направленному множеству М, если для всякого ε > 0 найдётся такой элемент ̅pϵ M, что для всех p из М таких, что р ≥ р выполняется неравенство|f(p)-c|<ɛ Предела и охватывает весьма широкий класс частных случаев.

Заключение

В заключении можно отметить, что теорию упорядоченных множеств создал Г. Кантор. В 1883 он ввёл понятие вполне упорядоченного множества и порядкового числа, а в 1895 – понятие упорядоченного множества и порядкового типа. В 1906–07 С. О. Шатуновский сформулировал определения направленного множества (у Шатуновского – расположенный комплекс) и предела по направленному множеству (амер. математиками Э. Г. Муром и Г. Л. Смитом эти же понятия были рассмотрены независимо от Шатуновского, но значительно позднее – в 1922). Общее понятие частично упорядоченного множества принадлежит Ф. Хаусдорфу (1914).

Список используемой литературы

Александров П. С., Введение в общую теорию множеств и функций, М. – Л., 2003;
А.К. Клифорд, Г. Престон. Алгебраическая теория полугрупп, 2005;
Кожевников О.Б. Частично упорядоченные множества, Москва, 2001;
Ляпин Е.С. Алгебра и теория чисел. Москва, 2000;
Д.Кук, Г.Бейз «Компьютерная математика», 2003;
Хаусдорф Ф., Теория множеств, пер. с нем., М. – Л., 1997;
Куратовский К., Мостовскиq А., Теория множеств, пер. с англ., М., 1980;
Бурбаки Н., Теория множеств, пер. с франц., М., 1995.

Упорядоченные множества 📙 Реферат → 🆔 286121