Какими свойствами обладает отношение меньше на множестве натуральных чисел
Свойства отношений:
1) рефлексивность;
2)симметричность;
3)транзитивность.
4)связанность.
Отношение R на множестве Х называется рефлексивным, если о каждом элементе множества Х можно сказать, что он находится в отношении R с самим собой: хRх. Если отношение рефлексивно, то в каждой вершине графа имеется петля. И обратно, граф, каждая вершина которого содержит петлю, представляет собой граф рефлексивного отношения.
Примерами рефлексивных отношений являются и отношение «кратно» на множестве натуральных чисел (каждое число кратно самому себе), и отношение подобия треугольников (каждый треугольник подобен самому себе), и отношение «равенства» (каждое число равно самому себе) и др.
Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.
Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.
Отношение R на множестве Х называется антирефлексивным, если для любого элемента из множества Х всегда ложно хRх: .
Существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Примером такого отношения может служить отношение «точка х симметрична точке у относительно прямой l», заданное на множестве точек плоскости. Действительно, все точки прямой l симметричны сами себе, а точки, не лежащие на прямой l, себе не симметричны.
Отношение R на множестве Х называется симметричным, если выполняется условие: из того, что элемент х находится в отношении с элементом y, следует, что и элемент y находится в отношении R с элементом х: xRyyRx .
Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y, граф содержит стрелку, идущую от y к х (рис. 35).
Примерами симметричных отношений могут быть следующие: отношение «параллельности» отрезков, отношение «перпендикулярности» отрезков, отношение «равенства» отрезков, отношение подобия треугольников, отношение «равенства» дробей и др.
Существуют отношения, которые не обладают свойством симметричности.
Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.
Отношение R называют антисимметричным, если для любых элементов х и y из истинности xRy следует ложностьyRx: : xRyyRx.
Кроме отношения «длиннее» на множестве отрезков существуют и другие антисимметричные отношения. Например, отношение «больше» для чисел (если х больше у, то у не может быть больше х), отношение «больше на» и др.
Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.
Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z: xRy и yRzxRz.
Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z, содержит стрелку, идущую от х к z.
Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b, отрезок b длиннее отрезка с, то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).
Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b, а отрезок b перпендикулярен отрезку с, то отрезки а и с не перпендикулярны!
Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.
Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y, либо элемент y находится в отношении R с элементом х. С помощью символов это определение можно записать так: xy xRy или yRx.
Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y, либо y>x.
На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.
Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y, что ни число х не является делителем числа y, ни число y не является делителем числа х (числа 17 и 11, 3 и 10 и т.д.).
Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y». Построим граф данного отношения и сформулируем его свойства.
Про отношение равенства дробей говорят, оно является отношением эквивалентности.
Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.
Примерами отношений эквивалентности могут служить: отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными).
В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {;}, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества на классы.
Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.
Так, мы установили, что отношению равенства на множестве
Х={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.
Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?
Во-первых, эквивалентный – это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.
Во-вторых, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. свойства, присущие некоторому классу, рассматриваются на одном его представителе.
В-третьих, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные прямые между собой.
Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х={3, 4, 5, 6, 7, 8, 9, 10} задано отношение «иметь один и тот же остаток при делении на 3». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке (это числа 3, 6, 9). Во второй – числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве Х, является отношением эквивалентности.
Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».
Отношение R на множестве Х называется отношением строгого порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х<y».
Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка. Например, отношение «хy».
Примерами отношения порядка могут служить: отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков. Если отношение порядка обладает еще и свойством связанности, то говорят, что оно является отношением линейного порядка. Например, отношение «меньше» на множестве натуральных чисел.
Множество Х называется упорядоченным, если на нем задано отношение порядка.
Например, множество Х={2, 8, 12, 32} можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х, а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.
Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
Введем отношение «меньше» для натуральных чисел, используя сложение.
2.4.6. Определение. Будем говорить, что натуральное число а меньше натурального числа b и писать а если существует натуральное число к такое, что Ь = а + к.
В нашем представлении натуральные числа можно «выстроить в линейку», используя отношение а и b можно однозначно сказать: либо а либо а = Ь, либо b . Это свойство называется свойством трихотомии, что в переводе означает «одно из ipex». Важным свойством отношения «меньше» является также возможность сравнить числа а и с «транзитом» через «посредника» b: если а и Ь то а Это так называемое свойство транзитивности. Уточним эти наши интуитивные представления в виде строгих определений.
- 2.4.7. Определение. Система (А, с основным множеством А и бинарным отношением линейно упорядоченным множеством, если выполнены следующие два условия.
- 1) (Свойство трихотомии). Для любых ауЬеА имеет место одно и только одно из соотношений: а , а = Ь, Ь
- 2) (Свойство транзитивности). Для любых а,Ьус е Л, если а Ь, то а
При этом отношение отношением линейного порядка.
2.4.8. Теорема. Система (Ny
Доказательство. Свойство трихотомии отношения aybyCGN имеют место соотношения а и Ь По 2.4.6, это означает, что b = a + k и с = Ь + т при некоторых kpneN. Отсюда c = (a + k) + m = a + (k + т), что означает а с. ?
Введем отношения >, > в наиболее обшей ситуации.
- 2.4.9. Определение. Пусть дано линейно упорядоченное множество {А, а,Ь е А положим:
- 1) а > b (а больше b) тогда и только тогда, когда b а;
- 2) а (а меньше или равно Ь) тогда и только тогда, когда аили а = b;
- 3) а>Ь (а больше или равно Ь) тогда и только тогда, когда а> b или а = b.
- 2.4.10. Предложение. Отношение
следующими свойствами:
- 1) рефлексивности: а
- 2) антисимметричности: для любых ауЬ е А если а
- 3) транзитивности: для любых ауЬус е А есчи а
- 4) линейности: для любых а,Ь е А а.
Доказательство. Рефлексивность следует из того, что а = а.
Докажем антисимметричность. Предположим, что а Тогда получаем а и Ьу что противоречит свойству трихотомии. Транзитивность отношения
Заметим, что иногда линейно упорядоченное множество определяют как систему (А, где бинарное отношение а строго меньше Ь)у если а и а фЬ. Легко доказать, что так определенное отношение строгого порядка
Основные свойства линейно упорядоченного множества натуральных чисел
Дадим одно общее определение.
- 2.4.11. Определение. Пусть дано линейно упорядоченное множество (А,иМсА. Элемент т&М (hgM) называется наименьшим (соответственно, наибольшим) в М, если т (соответственно, х для любого хеМ.
- 2.4.12. Предложение. Единица 1 — наименьший элемент в N.
Доказательство. Установим, что 1 п для любого п g N.
Если л = 1, то утверждение очевидно. Если же п* 1, то по 2.4.1 существует натуральное число т такое, что п = т’ = т + 1, откуда 1 п, а значит, 1 п. ?
2.4.13. Предложение. (Свойство дискретности). Для любого ogN не существует xgN такого, что а 1, то есть между а и а + = а нет натурального числа.
Доказательство. Предположим противное, пусть для некоторого a gN существует xgN такой, что а Из аполучаем х = а + к для некоторого к g N. Если к = 1, то х = а +1, что противоречит предположению. Если же к Ф1, то, по 2.4.1, существует т g N такое, что к = т = т +1, откуда х = а + т + , то есть а +1 х, что снова противоречит предположению. ?
2.4.14. Следствие. Для любых a,bGN если а 1, то а
Доказательство. Предположение противного ведет к противоречию с 2.4.13. ?
- 2.4.15. Определение. Пусть дано линейно упорядоченное множество (Ау Непустое подмножество MczA называется ограниченным сверху (снизу), если существует элемент 6g А (cgA) такой, что для любого xgM хЬ называется верхней границей (ас- нижней границей) подмножества М .
- 2.4.16. Теорема. В линейно упорядоченном множестве натуральных чисел всякое непустое ограниченное сверху подмножество имеет наибольший элемент.
Доказательство. Индукцией по b докажем, что если натуральное число b есть верхняя граница некоторого непустого подмножества натуральных чисел, то это подмножество имеет наибольший элемент. При b = 1 утверждение тривиально. Пусть утверждение верно для натурального числа b и У — верхняя граница непустого подмножества М ciV. Если У е М, то У и является наибольшим элементом в М. Если же У g А/, то для любого х g М имеем х, откуда по 2.4.14 х Следовательно, b есть верхняя граница подмножества М, и по индуктивному предположению в М сеть наибольший элемент. ?
Теорема 2.4.16 в 3.3.19 будет распространена на целые числа, при этом мы установим одновременно и симметричное утверждение относительно существования наименьшего элемента для всякого непустого ограниченного снизу подмножества целых чисел. Докажем, что для натуральных чисел симметричное утверждение также верно, причем в этом случае условие ограниченности снизу выполняется автоматически, т.к. одной из нижних 1раниц любого подмножества натуральных чисел будет 1. Предварительно введем соответствующее понятие.
- 2.4.17. Определение. Линейно упорядоченное множество называется вполне упорядоченным, если всякое его непустое подмножество имеет наименьший элемент.
- 2.4.18. Теорема. Линейно упорядоченное множество натуральных чисел вполне упорядочено.
Доказательство. Пусть 0 * А с N. Обозначим через М множество всех натуральных чисел, не превосходящих всякого а е А: М = {х е N | х для любого а е А } (рис. 9).
Так как 1 е М, то М — непустое подмножество, ограниченное сверху всяким элементом из А.
Рис. 9 Согласно 2.4.16, в М есть
наибольший элемент,
который обозначим через т. Тогда т для любого аеА, и нам остается лишь установить, что т е А. Предположим, что это не так. Тогда для любого аеА имеем т и по 2.4.14 т’, откуда т € М. Но т пришли в противоречие
с предположением о том, что т — наибольший элемент в М . Остается принять, что т и является там наименьшим элементом. ?
Упражнения
- 1. Пусть отношение «меньше» N на подмножествах четных и нечетных чисел совпадает с отношением ?
- 2. Определим на N отношение «меньше» о следующим образом. На множестве четных чисел оно совпадает с отношением >, а на множестве нечетных чисел ? с отношением является линейно упорядоченным множеством. Сравните его свойства со свойствами (N, .
- 3. Приведите примеры линейно упорядоченных множеств, имеющих наименьший (наибольший) элемент и не имеющих такового, вполне упорядоченных и не вполне упорядоченных.
- 4. Пусть А = {«1, «2,…, а„} и «| а„ . Будет ли отношение А ?
- 5. Сколько существует отношений линейного порядка на множестве из п элементов?
- 6. Выясните, являются ли линейно упорядоченными множествами следующие системы.
- 1) (Р(А), с), где Р{А) — множество всех подмножеств множества А;
- 2) (А, :>,где Л = {2”|n е N}; : — отношение «делится».
- 7. Пусть (А, линейно упорядоченное множество, которое назовем алфавитом, а его элементы — буквами. Всякую конечную последовательность букв назовем словом. Будем говорить, что слово aai…am «меньше» слова ЬЫ…Ьп, если первое слово «короче» второго, т.е. т или т = //, но существует номер к такой, что акк, а для всех номеров / к имеет место равенство а, = bt Докажите, что так определенное отношение «меньше» является отношением линейного порядка на множестве слов. Выпишите в порядке возрастания слова длины а2.
- 8. Задайте отношение линейного порядка, которое используется при составлении словарей, оно называется лексикографическим упорядочением. Рассмотрите лексикографическое упорядочение натуральных чисел как слов в алфавите цифр.
У этого термина существуют и другие значения, см. Отношение.
Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.
Понятие отношения как подмножества декартова произведения формализовано в теории множеств и получило широкое распространение в языке математики во всех её ветвях. Теоретико-множественный взгляд на отношение характеризует его с точки зрения объёма — какими комбинациями элементов оно наполнено; содержательный подход рассматривается в математической логике, где отношение — пропозициональная функция, то есть выражение с неопределёнными переменными, подстановка конкретных значений для которых делает его истинным или ложным. Важную роль отношения играют в универсальной алгебре, где базовый объект изучения раздела — множество с произвольным набором операций и отношений. Одно из самых ярких применений техники математических отношений в приложениях — реляционные системы управления базами данных, методологически основанные на формальной алгебре отношений.
Отношения обычно классифицируются по количеству связываемых объектов (арность) и собственным свойствам, таким как симметричность, транзитивность, рефлексивность.
Формальные определения и обозначения[править | править код]
-местным (-арным) отношением , заданным на множествах , называется подмножество декартова произведения этих множеств: . Факт связи -ки элементов отношением обозначается или .
Факт связи объектов и бинарным отношением обычно обозначают с помощью инфиксной записи: . Одноместные (унарные) отношения соответствуют свойствам или атрибутам, как правило, для таких случаев терминология отношений не используется. Иногда используются трёхместные отношения (тернарные), четырёхместные отношения (кватернарные); об отношениях неопределённо высокой арности говорят как о «мультиарных», «многоместных».
Универсальное отношение — это отношение, связывающее все элементы заданных множеств, то есть, совпадающее с декартовым произведением: . Нуль-отношение — отношение, не связывающее никакие элементы, то есть пустое множество: .
Функциональное отношение — отношение, образующее функцию: является функциональным, если из выполнения и следует, что (обеспечивается единственность значения функции).
Общие свойства и виды бинарных отношений[править | править код]
Наиболее распространённые в языке математики отношения — бинарные над одним множеством (), наиболее часто используются обладающие некоторыми общими свойствами[1]:
В зависимости от набора свойств бинарных отношений формируются некоторые широко используемые их виды:
- отношение эквивалентности — всякое рефлексивное, транзитивное и симметричное отношение;
- отношение предпорядка — рефлексивное и транзитивное;
- отношение частичного порядка — рефлексивное, транзитивное и антисимметричное;
- отношение строгого порядка — антирефлексивное, транзитивное, антисимметричное;
- отношение линейного порядка — связное, рефлексивное, антисимметричное.
Важную роль играет отношение равенства — отношение эквивалентности, выполненное только для двух совпадающих элементов.
Могут быть и другие комбинации свойств отношений, например, транзитивно и рефлексивно, но не обладает другими простыми свойствами, отношение делимости на множестве натуральных чисел, обычно обозначаемое символом , оно состоит из пар вида , где делит нацело. Пример тернарного отношения — образование пифагоровой тройки тремя числами, нахождение в отношении пифагоровой четвёрки — пример кватернарного отношения.
Более свободный набор свойств бинарных отношений применяется в теории графов: неориентированный граф может быть определён как множество вершин с симметричным бинарным отношением над ним, а ориентированный граф — как множество вершин с произвольным бинарным отношением над ним.
Алгебры отношений[править | править код]
Все -арные отношения над декартовым произведением образуют булеву алгебру относительно теоретико-множественных операций объединения, пересечения и дополнения.
Реляционная алгебра — замкнутая система операций над отношениями в реляционной модели данных.
Примечания[править | править код]
Литература[править | править код]
- Отношение — статья из Математической энциклопедии. Д. М. Смирнов
- Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. — М.: Издательство Московского университета, 1982. — 120 с. — 29 500 экз.