Декартово произведение множеств

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

Под парой будем понимать упорядоченную пару элементов, т. е. два элемента, расположенных в определенном поряд­ке. Элемент, занимающий первое место, называется первым эле­ментом пары, элемент, занимающий второе место, — вторым эле­ментом пары. Для обозначения пары применяют обычно круглые скобки. Символ (а, Ь) обозначает пару с первым элементом а и вторым элементом Ь.

Две пары считаются равными (совпадающими), если их соот­ветствующие элементы равны, т. е. (а\, Ь\)=-{ач, b-i) тогда и только тогда, когда а\=а% и b\-=b%.

Элементы пары могут оказаться равными, т. е. допускаются пары типа (а, а).

Если афЬ, то, исходя из определения равенства пар, полу­чаем (а, Ь)Ф{Ь, а), т. е. две пары, отличающиеся только поряд­ком элементов, различны (в то время как для двухэлементных множеств имеем {a, b)—{b, а}).

Если рассматривать пары чисел (х, у), то каждой такой паре соответствует точно одна (одна и только одна) точка плоскости при заданной системе координат — точка с координа­тами х и у. Если при этом хфу, то {х, у) и {у, х) — различные точки (рис. 5).

Рассмотрим таблицы I и II «открытых» и «закрытых» сло­гов. По существу мы имеем здесь два множества букв: мно­жество согласных С={м, н, п, р} и множество гласных Г={а, е, о, у}.

	а	е	О	У
м	ма	ме	МО	му
II	на	не	Но	ну
п	па	пе	По	пу
р	ра	ре	Ро	РУ

Таблица I Таблица II

	м	н	п	р
а	ам	ан	ап	ар
е	ем	ен	еп	ер
о	ом	он	ен	ор
У	ум	ун	уп	УР

 

I

 

В таблице I выписаны всевозможные пары, первые элементы которых принадлежат множеству С, а вторые — множеству Г. В таблице II выписаны всевозможные пары, первые элементы которых принадлежат множеству Г, а вторые — множеству С.

В первом случае множество пар называется декартовым произведением множества С на множество Г (СХГ), во втором — декартовым произведением множества Г на множество

С(ГХС).

Дадим теперь общее определение декартового произведения двух

множеств: декартовым¹ (По имени французского философа и математика Рене Декарта (1596-1650).произведением АхВ множества А на мно­жество В называется множество всевозможных пар, первые эле­менты которых принадлежат А, а вторые — В, т. е. АхВ={(х у)\х£ А и у£ В).

Ах{( у) Множество АхВ распознается по тому, что его элементами являются пары элементов двух других множеств (Л и В).Если В=А, то АХВ = АхА={{х, у)\х£ А и у£ А\ т. е. АХА — множество всевозможных пар элементов из множества Л. Это мно­жество пар обозначается также символом Л2.

Бинарные отношения

Под бинарным отношением понимают отношение между двумя предметами. Дальше, говоря «отношение», будем иметь в виду.бинарное отношение. Выясним, что интуитивно понимают под отно­шением и как это понятие можно описать математически Из курса школьной математики известны многочисленные при­меры отношений:

между числами: «равно», «неравно», «меньше», «больше», «неменьше», «не больше», «делит», «делится на»; между точками прямой: «предшествует», «следует за»; между прямыми: «параллельны», «пересекаются», «перпен­дикулярны», «скрещиваются»; между прямой и плоскостью: «параллельны», «пересекаются», «перпендикулярны»; между плоскостями: «параллельны», «пересекаются», «пер­пендикулярны»;

— между геометрическими фигурами: «равно», «подобно» и др. Это, разумеется, далеко не полный перечень встречающихся в школьной математике отношений.

Примеры бинарных отношений встречаются не только в мате­матике, но и всюду в жизни, вокруг нас. Родственные и другие отношения между людьми (быть отцом, дедушкой, матерью, бабуш­кой, братом, сестрой, другом, ровесником, старше, моложе, выше, ниже и др.) выступают как бинарные отношения. Отношения между событиями во времени (раньше, позже, одновременно), между пред­метами по их расположению в пространстве (выше, ниже, левее, правее, севернее, южнее и др.) также выступают как бинарные отношения.

Проанализируем складывающееся на базе опыта интуитивное понятие отношения. Прежде всего рассмотрим несколько приме­ров.

Пример 1. Возьмем отношение Р: «город х стоит на берегу реки у».

Всегда, когда говорим о каком-то отношении, мы имеем в виду множества предметов, между которыми установлено это отноше­ние. В нашем примере имеется в виду некоторое множество А городов и некоторое множество В рек.

Пусть А ={Астрахань, Волгоград, Киев, Минск, Могилев, Моск­ва, Ростов, Ульяновск} и В = {Волга, Днепр, Дон, Москва-река}.

Рассматриваемое отношение может быть задано следующей таб­лицей истинности:

 

А	В
	Волга	Днепр	Дои	Москва-река
Астрахань	И	Л	л	л
Волгоград	и	л	л	л
Киев	л	и	л	л
Минск	л	л	л	л
Могилев	л	и	л	л

 

 

В приведенной таблице буква И (истинно) поставлена в тех клетках, которые соответствуют парам (город, река, ) находящимся в заданном отношении, т. е. если в предложении «город х стоит на берегу реки у» вместо х и у подставить имена соответствующих городов и рек, получим истинные высказывания («Астрахань стоит на берегу Волги», «Волгоград стоит на берегу Волги», «Киев стоит на берегу Днепра» и т. д.). Буква Л (ложно) стоит в тех клетках, которые соответствуют парам (город, река), не находящимся в данном отношении. Например, «Минск стоит на берегу Волги», «Могилев стоит на берегу Дона» и др.— ложные высказывания. Эта таблица дает ответ на вопрос: какой город из множества А стоит на берегу какой реки из множества В? Ответ можно за­писать и в виде множества пар:

{(Астрахань, Волга), (Волгоград, Волга), (Киев, Днепр), (Мо­гилев, Днепр), (Москва, Москва-река), (Ростов, Дон), (Ульяновск,

Волга)}.

Сколько всего возможно пар вида (город, река), т. е. элемен­тов декартова произведения АХ.В в данном примере? В таблице всего клеток (или пар) 32. Таким образом, рассматриваемое от­ношение может быть задано с помощью множества из 7 пар, представляющего собой подмножество декартова произведения

АХ В.

 

 

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

На рисунке 6 изображен граф, задаю­щий отношение «меньше» в множестве А;

элементы множества А изображены вершинами графа, а стрелка исходит из вершины а и направлена к вершине b, если предложение a< b истинно.

Рассмотренные примеры 1 и 2 показывают, что всегда, когда речь идет о некотором отношении, имеются в виду два множества Л и В (эти множества могут, в частности, совпадать, как в при­мере 2, т. е. возможно, что В = А) и при этом некоторые элемен­ты множества А находятся в данном отношении с некоторыми элементами множества В или того же множества А. Таким образом, всякое отношение между элементами множеств А и В (или между элементами множества А) порождает множе­ство пар, первые компоненты которых принадлежат А, вторые В (или тоже А), т. е. порождает подмножество АХВ (или АХА), причем такое, что элементы каждой пары и только они находятся в данном отношении.

Как видно из проведенного анализа интуитивного понятия от­ношения, всякое отношение между элементами двух множеств А и В полностью характеризуется тремя множествами: А и В, между элементами которых установлено отношение, некоторым множеством пар Р — подмножеством АХВ, т. е. декартовым произведением. Один из путей определения математического понятия отношения и состоит в отождествлении этого понятия с указанной тройкой множеств. Если же определяют отношение вообще, без указания, между элементами каких множеств оно установлено, то обычно отождествляют его с множеством пар Р.

Отношением между элементами непустых множеств А и В назы­ вается тройка множеств

р=(Р, А, В), где Рс=АхВ.

Множество пар Р называется графиком отношения р. Об элементах пары (je, у), принадлежащей графику Р, говорят, что они находятся в отношении р, и записывают это так: «хру»

Таким образом, записи «(*, у)£ Р» и «.хру» равносильны. Если В —А, то р=(Р, А, А) называется отношением между элементами множества А. Так, в примере 2 мы имели отношение «меньше» между элементами множества А — {\, 2, 3, 4}.

Свойства отношений

 

1. Рассмотрим еще один пример отношения.

Если А = {\, 2, 3, 4}и Р = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4), Чо р — (Р, А, А) представляет собой отношение «делит» между элементами множества А. Оно представлено графом на рисунке 7.

Это отношение обладает таким свойством: каждый элемент мно­жества А находится в этом отношении с самим собой, все пары типа (х, х)— (1, Г), (2, 2), (3, 3), (4, 4) —принадлежат гра­фику этого отношения. Это свойство отражается в графе (рис. 7) тем, что в каждой вершине графа имеется петля, указывающая на то, что каждая точка находится в этом отношении сама с собой. Отношение же «меньше» (рис. 6) не обладает этим свойством, более того, ни один элемент множества не находится в. этом отно­шении «меньше» с самим собой (ни одно число не меньше са­мого -себя). Ни в одной вершине этих графов нет петли.

Свойство отношения р = (Р, А, А), - состоящее в том, что хрх для всякой пары (х, х)£ А² (или для всякого х£ Л) называется рефлексивностью, а отношение р, обладающее этим свойством, — рефлексивным.

Свойство отношения р = (Р, А, А), состоящее в том, что хрх («х не находится в отношении р (х, х)») для всякой пары (х, х)£ А² (или для всякого х£ А) называется антирефлексивностью, а отно­шение р, обладающее этим свойством, —антирефлексивным¹.

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

Среди перечисленных в § 2 отношений рефлексивными являются: «равно», «не меньше», «не больше», «делит», «делится на», «равенство и подобие фигур»; анти­рефлексивными являются отношения: «не­ равно», «меньше», «больше» между числами, «предшествует», «следует 'за» между точками прямой. Отношение «быть ро­весником» между людьми является ре­флексивным, отношение же «быть отцом»,
«быть матерью», «быть братом», «быть сестрой», «выше», «старше», «моложе» — антирефлексивными. Отношение «быть другом» не является ни рефлексивным, ни антирефлексивным (бывают случаи, ког­да человек сам себе друг, и случаи, когда человек сам себе недруг).

Рис.7.

2. Если a — b, то й = а, т. е. если пара (a, b) находится в от­ношении «равно», то и пара (Ь, а) находится в этом отношении.

Аналогичным свойством обладает и отношение «быть ровесни­ком»: если х ровесник у, то у ровесник х.

Если а< Ь, то ~16< а, т. е. если пара (а, Ь) находится в отно­шении «меньше» то пара (Ь, а) не находится в этом отношении.

Аналогично и отношение «старше»: если х старше у , то неверно, что у старше х.

Отношение «не больше» (меньше или равно: <! ) обладает таким свойством: если х^у и у^х, то х = у.

Свойство отношения р = (Р, А, А), состоящее в том, что из хру следует урх для любой пары (х, у)£ А², называется симметрич­ностью, а отношение р, обладающее этим свойством, — симметрич­ным.

Свойство отношения р, состоящее в том, что из хру следует ~\урх для любой пары (х, у)£ А², называется асимметрия-ност ь ю, а отношение р, обладающее этим свойством, — асим­метричным. Свойство отношения р, состоящее в том, что из хру и урх следует х — у для любой пары (х, у)^А², называется антисимметричностью, а отношение р, обладающее этим свойством, — антисимметричным.

Граф симметричного отношения характеризуется тем, что любые две его вершины либо не связаны стрелкой, либо связаны двумя противоположно направленными стрелками; граф асимметричного (или антисимметричного) отношения — тем, что любые две его различные вершины связаны не более чем одной стрелкой1.

3. Несложно установить истинность следующих утверждений:

если х< у и y< z, то x< z;

если х = у и y — z, то x = z;

если х ровесник у и у ровесник z, то х ровесник z;

если л: старше у а у старше г, то х старше z; если a||b и Ь\\с, то а\\с.

однако если х — отец ужу — отец z, то х не есть отец z (а дедуш­ка); если х — друг у и у — друг z, то вообще не известно, является ли х другом z.

Свойство отношения р=(Р, А, А), состоящее в том, что из хру и ypz слеует xpz для любых х, у, z£ A, называется тран­зитивностью, а отношение р, обладающее этим свойством, — транзи­тивным.

Свойство отношения р, состоящее в том, что из хру и ypz следует ~Лхрг для любых х, у, z£ A, называется антитранзитивностью, а отношение р, обладающее этим свойством, — антитранзи­тивным.

Так, отношения «меньше», «равно», «быть ровесником», «старше; », «параллельно» являются транзитивными. Отношение «быть отцом» является антитранзитивным, а отношение «быть другом» не являет­ся ни транзитивным, ни антитранзитивным.

Отношение эквивалентности

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

Среди рассмотренных выше примеров отношений имеются такие, которые являются рефлексивными, симметричными и транзитивными одновременно. К ним относятся отношения равенства чисел и гео­метрических фигур, подобия фигур, «быть ровесником».

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

Всякое рефлексивное, симметричное и транзитивное отношение, установленное в некотором множестве А, называется отношением эквивалентности.

Если между элементами некоторого множества введено или уста­новлено отношение эквивалентности, то этим самым порождается разбиение данного множества на классы таким образом, что лю­бые два элемента, принадлежащие одному классу разбиения, на­ходятся в данном отношении (иначе: эквивалентны по этому от­ношению), любые же два элемента, принадлежащие различным классам, не находятся в этом отношении (иначе: не эквивалентны по этому отношению). Такое разбиение множества на классы обычно называют разбиением множества на классы экви­валентности.

Разбиение множества блоков (или фигур) на классы эквивалент­ности можно смоделировать с помощью следующей игры с тремя обручами.

В множестве всех блоков введем отношение «иметь один цвет» (или «быть одного цвета»). Нетрудно убедиться в том, что это отношение является отношением эквивалентности, т. е. рефлек­сивным, симметричным и тран­зитивным. Этому соответствует задание: «Расположите блоки так, чтобы все блоки одного цвета оказались вместе». На­пример, имея три обруча: крас­ный, синий и желтый (рис. 8), можно потребовать, чтобы все красные блоки были располо­жены внутри красного обруча, всё синие — внутри синего, а все желтые — внутри желтого.

 

 

красный обруч синий обруч

Рис. 8.

 

 

 

 

жёлтый обруч

 

Решение этой задачи в про­цессе игры приводит к разбие­нию множества всех блоков на

 

классы эквивалентности по отношению «быть одного цвета» (области (1), (2), (3), (4) оказываются пустыми, так как нет трехцветного или двухцветного блока, область (8) пуста, так как блоков другого цвета, кроме красного, синего или желтого, нет). Нетрудно убедиться в том, что удовлетворяются условия 1) —3) правильного разбиения (глава III, § 6): 1) ни один из классов (красных, синих, желтых) блоков не пуст;.2) эти классы попарно не пересекаются и 3) их объединение равно множеству М всех блоков.

Таким же путем, т. е. с помощью отношения «быть одного цвета», формируется и само представление о цвете как о классе, объединяющем все предметы одного цвета, скажем, все красные предметы.

Аналогично формируется и представление об определенной форме предметов. С помощью отношения «иметь одну форму» мы получаем разбиение всех блоков (или фигур) на четыре класса эквивалент­ности такое, что любые два блока (или две фигуры), принадле­жащие одному классу, обладают одной и той же формой, любые же два блока (или две фигуры) различных классов обладают различной формой. Сама форма выступает здесь как класс эквивалент­ности. Так, впоследствии, например, формируются представления о круге, квадрате, треугольнике, прямоугольнике и других геометри­ческих фигурах как на плоскости, так и в пространстве.

Эти примеры показывают, с одной стороны, что отношения экви­валентности являются базой для формирования новых понятий и для классифицирующей деятельности, с другой стороны, что рас­смотренные выше (глава III) дидактические игры с обручами обу­чают этой деятельности.

 

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

Среди рассмотренных выше (§ 2) примеров отношений имеются такие, как «меньше», «больше» между числами, «предшествует», «следует за» между точками прямой; «старше», «моложе» между людьми. Эти отношения являются антирефлексивными, асимметрич­ными и транзитивными.

Эти и подобные им, т. е. обладающие такими же свойствами, отношения принадлежат другому важному классу отношений, также
находящих широкое применение, их называют отношениямипорядка. > i«; )

Всякое антирефлексивное, асимметричное и транзитивное отно­шение в некотором множестве А называется отношением порядка.

Иногда такое отношение называют отношением строгого порядка, чтобы отли­чить его от отношения нестрогого порядка, являющегося рефлексивным, антисим­метричным и транзитивным. > ч

Обратимся еще раз к примеру 2 (§ 2) отношения «меньше» в множестве Л = {1, 2, 3, 4).

Тот факт, что главная диагональ истинностной таблицы (идущая от левого верхнего угла к правому нижнему) содержит одни только Л, или ни одна вершина графа (рис. 6) не имеет петли, отражает свойство антирефлексивности отношения «меньше».

Если в одной клетке таблицы стоит И, то в симметричной ей относительно главной диагонали клетке стоит Л, или если от одной вершины графа к другой проведена стрелка, то от второй к первой стрелки нет. В этом отражается свойство асимметричности

отношения «меньше».

Более того, легко заметить, что любая клетка таблицы запол­нена (буквой И или Л), или любые две вершины графа сое­динены стрелкой. Это означает, что для любой пары (х, у)£ А² различных чисел {хФу) либо х< у, либо у< х. В таком случае говорят, что множество А упорядочено отношением «меньше» и ^.записывается так, что на первом месте располагается имя элемента, ^; который меньше всех остальных, на втором — имя элемента, мень­шего остальных, кроме первого и т. д., т. е.

Л={1, 2, 3,.4}.

Таким же отношением «меньше» упорядочивается и множество всех натуральных чисел N={1, 2, 3, ...}, к изучению которого мы перейдем в следующей главе.

Исходя из такого интуитивного понимания упорядочивания мно-' жества е- помощью отношения порядка, приходим к следующему определению упорядоченного множества.

Множество А называется упорядоченным, если введено отно­шение порядка р — {Р, А, А) и для любой пары (х, у)£ А², если хфу, то хру или урх (т. е. любые два различных элемента множе­ства А находятся в данном отношении порядка Р). В этом случае говорят также, что множество А упорядочено отношением порядка р.

Так, например, когда говорят «натуральный ряд чисел», имеют в виду множество N всех натуральных чисел, упорядоченное отно­шением порядка «меньше», т. е. N = {1, 2, 3, 4, 5, ...}.

Глава V. ЧИСЛА

⇐ Предыдущая1234567Следующая ⇒

Поделиться:

Популярное:

1. Билет Классическая и обобщенная модели множественной линейной регрессии.
2. Взаимодействие аллельных генов (полное доминирование, неполное доминирование, сверхдоминирование и кодоминирование). Множественные аллели. Наследование групп крови человека по АВО системе антигенов.
3. Воспитание и коррекция ребенка со сложными и множественными нарушениями в семье.
4. ВОСПРОИЗВЕДЕНИЕ (КОПИРОВАНИЕ)
5. Воспроизведение культурной системы изнутри
6. Воспроизведение события в действии
7. Выразительное чтение слов Фильки, обращенных к коню (в чтении передать злость мальчика, его грубость). Каким можно назвать поступок Фильки? (Назвать автора и произведение)
8. ГЛАВА 21. МНОЖЕСТВО НОВЫХ ЦЕРКВЕЙ
9. ГЛАВА 3. МОДЕЛЬ МНОЖЕСТВЕННОЙ
10. ЗАДАЧИ ИЗУЧЕНИЯ МНОЖЕСТВЕННОЙ СВЯЗИ
11. ЗАДАЧИ НА УСТАНОВЛЕНИЕ ЛОГИЧЕСКИХ СВЯЗЕЙ МЕЖДУ МНОЖЕСТВАМИ