Дискретная математика (стр. 8 )

 

0

b
a	y

 

6  Установим однозначное соответствие между точками интервала (0; 1) и точками полуинтервала [0; 1). Заметим, что множество (0; 1)\А и множество [0; 1)\В равны (множества А и В определены в примере 4); обозначим . Тогда , . Пусть . Если , то поставим ему в соответствие по закону, описанному в примере 4; если же , то поставим ему в соответствие себя: . Таким образом устанавливается взаимно однозначное соответствие между (0; 1) и [0; 1). Следовательно, множества (0; 1) и [0; 1) эквивалентны.

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

2.4 Декартово произведение множеств. Отображения, множество степень

Определение. Декартовым произведением множеств X и Y называется множество ХY, элементами которого являются упорядоченные пары (х; у), где хХ, уY. Равенство упорядоченных пар понимается в следующем смысле:

Пусть z= (х; y) и z= (х; у), z и z ХY, тогда

z= z(х= х)( у= у).

Справедливо следующее утверждение:

Если Х и Y – конечные множества, то ХY – конечное множество и

|ХY| = |Х| |Y|.

Определение. Пусть Х – множество и n N. Определим декартовы степени множества Х следующим образом:

Х= Х;

Х= ХХ;

…………….

Х= ХХ.

Отметим, что если Х – конечное множество, то

|Х| = |Х|

Пример. Из города А в город В ведут три дороги, а из города В в город С – 4 дороги. Сколькими способами можно добраться по указанным дорогам из А в С через В?

Решение

Понимая под способом попасть из А в С через В упорядоченную пару (дорогу, по которой перемещаемся из А в В, и дорогу, по которой перемещаемся из В в С), решение задачи можно получить, используя понятие декартова произведения. Обозначим:

АВ – множество дорог, ведущих из А в В;

ВС – множество дорог, ведущих из В в С.

Тогда исходная задача сводится к математической задаче: «Найти число элементов множества – декартова произведения АВВС». Очевидно, что

|АВВС| = |АВ||ВС| = 34 = 12.

Определение. Пусть Х и Y – два множества. Правило f (x), ставящее в соответствие каждому элементу хХ вполне определенный элемент f (x)Y, будем называть отображением множества Х в Y и обозначать

f : Х Y.

Отметим, что два отображения f: Х Y и f: Х Y считают равными, если:

Х Y , Х Y и f= f ,

т. е. для любого хХ (=Х) имеет место равенство f(х) = f(х).

Определение. Пусть Х и Y – непустые множества. Обозначим через Y множество отображений, действующих из Х в Y, т. е.