§ 4. Вектор. Прямое произведение

Вектор - это упорядоченный набор элементов. Сказанное не следует считать определением вектора, поскольку тогда потребуется давать объяснения по поводу его синонима “упорядоченный набор”. Понятие “вектор”, как и понятие “множество”, является одним из неопределяемых понятий математики. Элементы, образующие вектор, называются координатами или компонентами вектора.

В отличие от элементов множества координаты вектора могут совпадать. Векторы длины 2 часто называют упорядоченными парами (или просто парами), векторы длины 3 - тройками и т.д. Два вектора равны, если они имеют одинаковую длину и их соответствующие координаты равны, т.е. (a₁,a₂,...,a_n,...) и (b₁,b₂,...,b_m,...) равны, если m=n и a₁= b₁, a₂= b₂, ..., a_n = b_n .

Прямым произведением множеств А и В (обозначение: АВ) называется множество всех пар (a,b), таких, что аА, bB. В частности, если А=В, то обе координаты принадлежат А. Такое произведение обозначается A². Аналогично прямым произведением множеств A₁,A₂,...,A_n (обозначение: A₁A₂...A_n) называется множество всех векторов (a₁,a₂,...,a_n,...) длины n, таких, что a₁A₁, a₂A₂,..., a_nA_n. При A₁=A₂=...=A_n вместо A₁A₂...A_n записывают Aⁿ.

Примеры.

1. Пусть R - множество действительных чисел. Тогда R²=RR - это множество точек плоскости, точнее, пар вида (a,b), где a, b принадлежат R и являются координатами точек плоскости.

Координатное представление точек плоскости, предложенное французским математиком и философом Декартом, исторически первый пример прямого произведения. Поэтому иногда прямое произведение называют декартовым.

2. Пусть A ={a,b,c,d,e,f,g,h}, B={1, 2, 3, 4, 5, 6, 7, 8}. Тогда АВ={a1,a2,a3,... ,h7,h8) - множество, содержащее обозначение всех 64 клеток шахматной доски.

3. Пусть А - конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества называются алфавитами. Элементы множества Aⁿ называются словами длины n в алфавите А.

Множество всех слов в алфавите А - это множество =A¹ A² A³...

При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями, однако они могут оказаться символами самого алфавита. Поэтому слово в алфавите А - это просто конечная последовательность символов алфавита А. Напимер, десятичное натуральное число - это слово в алфавите цифр {0,1,2,...,9}. Текст, напечатанный на пишущей машинке, является словом в алфавите, определяемом клавиатурой данной машинки (включая знаки препинания и пробел).

Прямое произведение не обладает свойством коммутативности (АВ  ВА), но для него выполняются свойства дистрибутивности относительно объединения и пересечения:

(АВ) С = (АС) (ВС), А(ВС) = (АВ) (АС);

(АВ) С = (АС) (ВС), А(ВС) = (АВ) (АС).

(Доказать самостоятельно. У к а з а н и е. Воспользоваться схемой доказательства дистрибутивности операций ““ и ““; см. § 3).

§ 5. Мощность конечного множества

Мощностью конечного множества A={a₁,a₂,...,a_n,...}, называется число его элементов n (обозначение: |A|=n). Очевидно, что если А=В, то |A|=|B|. Кроме того, || = 0.

Примеры.

1. A ={-2,-1,0,1,2}, |A| = 5;

2. B ={b / b делится на 3 без остатка и b  21, bN}, |B| = 7.

Теорема 1.1 (о мощности разности). Пусть А и В - конечные множества и, кроме того, В  А. Тогда |A\B| = |A| - |B|.

Теорема 1.2 (о мощности объединения непересекающихся множеств). Пусть А и В - конечные множества и, кроме того, АВ=. Тогда |AB| = |A|+| В|.

Теорема 1.3 (о мощности объединения пересекающихся множеств). Пусть А и В - конечные множества. Тогда

|AB| = |A|+|B| - |АВ|. (1.1)

 Представим объединение двух, в общем случае пересекающихся, множеств А и В в виде объединения непересекающихся множеств А и B\(АВ): AB = (A)  (B\(АВ)).

Тогда по теореме 1.2 |AB| = |(A) (B\(АВ))| = |A| +|B\(АВ)|.

Так как (АВ)В, то по теореме 2.1 |B\(АВ)| = |B|-|АВ|.

Окончательно имеем |AB| = |A| +|B\(АВ)| = |A|+|B|-| АВ|. 

Пример. В игральной колоде 36 карт. Сколькими способами можно извлечь из колоды туза или карту бубновой масти?

Решение. Пусть А - множество тузов в колоде, а В - множество карт бубновой масти. Очевидно, что

А = {T, T, T, T}, B = {6, 7, 8, 9, 10, B, D, K, T},

АВ = {T}; |A| = 4, |B| = 9, |АВ| = 1.

По формуле (1.1) |AB| = |A| + |B| - |АВ| = 4 + 9 - 1 = 12.

Обобщим теорему 1.3 на случай n множеств. Предположим, что даны подмножества A₁,A₂,...,A_n (необязательно различные) некоторого конечного множества X. Тогда имеет место следующая теорема.

Теорема 1.4 (принцип включения и исключения).

| A_i A_j | + | A_i A_j A_k |-...+(-1)^n-1 |A₁ A₂... A_n |.

 Применим индукцию по n. Для n=2 теорема справедлива (см. ф-лу 1.1). Предположим, что для произвольных подмножеств A₁,A₂,...,A_n-1 выполняется равенство

| A_i A_j |+| A_i A_j A_k |-...+(-1)^n-2 |A₁ A₂... A_n |.

Применяя эту формулу к сумме

(A₁ A₂... A_n-1)  A_n =,

получаем

| A_i A_j A_n |+...+(-1)^n-2 |A₁ A₂... A_n |,

отсюда мощность объединения n подмножеств A₁,A₂,...,A_n множества Х будет равна:

| A_i A_j | +

+| A_i A_j A_k |-...+(-1)^n-1 |A₁ A₂... A_n |. 

Пример. В ящике хранятся разноцветные мячи. Известно, что в раскраске 14 мячей присутствует красный, 15 мячей - зелёный, 10 мячей - синий цвет; у 9 мячей - как красный, так и синий, 11 мячей - как красный, так и зелёный, 7 мячей - как синий, так и зелёный цвет; в раскраске 5 мячей присутствуют все три цвета. Сколько мячей в ящике?

Решение. Пусть А, В, С - множества мячей, в раскраске которых присутствует соответственно красный, зелёный и синий цвет. Тогда общее количество мячей составит:

|ABС| = |A| + |B| + |C| - |АВ| - |АC| - |BC| + |ABC| =

= 14 + 15 + 10 - 11 - 9 - 7 + 5 = 17.

Теорема 1.5 (обобщённое правило суммы).

Для покрытия конечного множества A=A₁ A₂... A_m справедливо неравенство

|A|  |A₁|+|A₂|+...+ |A_m|. (1.2)

 Доказательство проведём методом математической индукции.

При m=2 A=A₁A₂ и согласно теореме (1.3) имеем

|A| = | A₁ A₂| = | A₁|+| A₂| - | A₁ A₂| |A₁|+|A₂|.

Предположим, что при m=k неравенство (1.2) верно:

|A| = |A₁ A₂... A_k | |A₁|+|A₂|+...+ |A_k|. (1.2,a)

Положим m=k+1 и докажем, что и в этом случае обобщённое правило суммы остаётся верным:

|A| = |A₁ A₂... A_k A_k+1| = |(A₁ A₂... A_k) (A_k+1)| |A₁ A₂... A_k| + |A_k+1| -

- |(A₁ A₂... A_k)(A_k+1)|  |A₁ A₂... A_k| + |A_k+1||A₁|+|A₂|+...+ |A_k|+ |A_k+1|.



Задача Льюиса Керролла.

В ожесточённом бою 70 из 100 пиратов потеряли один глаз, 75 - одно ухо, 80 - одну руку и 85 - одну ногу. Каково минимальное число потерявших одновременно глаз, ухо, руку и ногу?

Решение. Пусть A₁, A₂, A₃, A₄ - множества пиратов, потерявших соответственно глаз, ухо, руку, ногу. Тогда В = (A₁A₂A₃ A₄) - это множество пиратов, потерявших одновременно глаз, ухо, руку и ногу.

Множество всех пиратов U можно представить в виде покрытия

,

причём по условию |U|=100.

Используя формулу (1.2), получим

,

откуда

100  (100-70)+(100-75)+(100-80)+(100-85)+|B| ; |B|  10.

Теорема 1.6. Для разбиения конечного множества A=A₁ A₂... A_m, A_i , A_iA_j=, ij, 1 i, j m справедливо равенство|A| = |A₁|+|A₂|+...+ |A_m|. (правило суммы), которое доказывается аналогично формуле (1.2).

Теорема 1.7. (о мощности прямого произведения).

Пусть A₁,A₂,...,A_n - конечные множества и |A₁|=m₁, |A₂|=m₂,..., |A_n|=m_n. Тогда мощность множества A₁A₂...A_n равна произведению мощностей A₁,A₂,...,A_n :

|A₁A₂...A_n| = m₁ m_2...m_n.

 Применим индукцию по n.

1. n=2. Пронумеруем элементы множеств B=A₁ и C=A₂ и составим декартово произведение BC: B={b₁,b₂,...,b_m1}, C={c₁,c₂,...,c_m2},

BC={ (b₁,c₁), (b₁,c₂),..., (b₁,c_m2),

(b₂,c₁), (b₂,c₂),..., (b₂,c_m2),

...

(b_m1,c₁), (b_m1,c₂),..., (b_m1,c_m2)}.

Ясно, что мощность множества BC равна m₁ m₂:

|A₁A₂ |= m₁ m₂. (1.3)

2. n=k. Предположим, что |A₁A₂...A_k | = m₁m_2...m_k . (1.3,а)

3. n=k+1. Докажем, что |A₁A₂...A_k A_k+1| = m₁m_2...m_k. m_k+1.

|A₁A₂...A_k A_k+1| =|(A₁A₂...A_k)A_k+1|

= |A₁A₂...A_k ||A_k+1|(m₁m_2...m_k)m_k+1= m₁m_2...m_k. m_k+1.



Следствие. Пусть А - конечное множество и |A| = m. Тогда |Aⁿ| = mⁿ .

Пример.Сколько векторов длиной 3 со значениями компонент 0 или 1 можно составить?

Решение. Эти вектора представляют собой элементы множества B³, где B={0,1}. Общее число векторов с заданными свойствами равно мощности множества B³. Так как |B|=2, то |B³|=2³=8.