Дискретная математика

14 Декартовьш (прямьш) произведением двух множеств А к В называется множество упорядоченных пар (а,Ь), таких, что asA vi ЬеВ. Декартово (прямое) произведение обозначается через АхВ. Итак; АхВ={(а,Ь): аеА и bsB}. Пусть Л={0,1}, В= {а,6}, тогдаЛхВ = {(0,аД(1,аД (0,ЬД Упорядоченной п-кой элементов aj, ai,..., а„ a/sAj, ап £ А„, называется объект (aj,a2, ...,а„Х такой что (a;,a2,:.,aj={bi,b2,...,b „), bisAi, b2sA2,...,b„sA„, тогда и только тогда, когда ai=b,, a2=b2, а„=Ь„. Декартовым произведением множеств Ai,A2 А„ называется множество упорядоченных п-ок: AixA2X...xA „={(ai, 02, a,sAi и атеАгЯ ...иа„еА„}. Введём обозначение; Л"=АхАх...хА. у ^ «-раз Можно доказать, что, например, выполняются следующие равенства: (А иВ) хС =(АхС) и(ВхС); (АпВ)хС =(АхС)п (ВхС); (А\В)хС =(АхС)\(ВхС) и т.п. § 4. Отношения Бинарным отношением на (двух) множествах А а В называется подмножество R декартового произведения АхВ. Таким образом, если задано подмножество R множества АхВ, т.е. некоторое подмножество упорядоченных пар (а,Ь} таких, что аеА, ЬеВ, то говорим, что задано бинарное (двуместное) отношение R, и пишем (а,Ь) € Л или aRb. Последнее читается: элемент а находится в отношении Rcb. Следовательно, изучение отношений сводится к изучению подмножеств множества Л хВ. Отношение на множествах А и А, т.е. подмножество множества АхА называется бинарным отношением на множестве А. Рассмотрим пример. Пусть А =(-оо,оо). Рассмотрим АхА, т.е. плоскость и выберем: Л/ - биссектрису первого квадранта, R2 - полуплоскость выше R3 - полуплос'^ость ниже /?/, см. Рис. 1.7. Очевидно, что й , Ri и Rj есть следующие отношения: Ri - отношение равенства: у'^х-, R- - отношение неравенства: у>х; R3 - отношение неравенства: у<х.