Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 29 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

29
Следовательно, X ½ Y
≠ Y ½ X.
1.6.3. Теорема о мощности
прямого произведения
Пусть A
1
, A
2
, ..., A
n
– конечные множества. Соответственно мощности
этих множеств равны: |A
1
| = m
1
, |A
2
| = m
2
, ..., |A
n
| = m
n
.
Тогда мощность прямого произведения n множеств равна произведе-
нию мощностей соответствующих множеств, т.е. |A
1
½A
2
½A
3
½...½A
n
| =
m
1
.
m
2
.
...
.
m
n
.
Доказательство методом математической индукции.
Для n = 1 теорема тривиально верна. Предположим, что она верна и
для n = k и докажем ее справедливость для n = k+1.
По предположению |A
1
½A
2
½...½A
k
| = m
1
m
2
...m
k
. Возьмем любой век-
тор (a
1
, a
2
, ... a
k
) из A
1
½A
2
½...½A
k
и припишем справа элемент a
k+1
∈ A
k+1
.
Это можно сделать m
k+1
способом, т. е. получим m
k+1
различных векторов
из A
1
½A
2
½...A
k
½A
k+1
.
Таким образом, из всех m
1
m
2
... m
k
векторов приписыванием справа
элемента из A
k+1
можно получить m
1
m
2
... m
k+1
векторов, причем все они
различны. Поэтому для n=k+1 теорема верна и, следовательно, верна для
любых n.
Следствие: |A
n
| = |A|
n
Упражнения 1.6
1. Даны множества A = {a, b}и X = {1, 2, 3}. Найти прямое произве-
дение A
× X .
A
× X = { ( a, 1); ( a, 2); . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .}.
2. Пусть M = {(a; 1), (a; 2), (b; 1), (b; 2)}. Найти пр
1
M = { . . . . . . . .. . .
.}.
3. Дано множество S = {x, y, z}. Найти прямое произведение S
2
. S
2
= {
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .}. 
        Следовательно, X ½ Y ≠ Y ½ X.

                               1.6.3. Теорема о мощности
                                 прямого произведения
         Пусть A1, A2, ..., An – конечные множества. Соответственно мощности
этих множеств равны: |A1| = m1, |A2| = m2, ..., |An| = mn.
         Тогда мощность прямого произведения n множеств равна произведе-
нию мощностей соответствующих множеств, т.е. |A1½A2½A3½...½An| =
m1.m2.....mn.
         Доказательство методом математической индукции.
         Для n = 1 теорема тривиально верна. Предположим, что она верна и
для n = k и докажем ее справедливость для n = k+1.
          По предположению |A1½A2½...½Ak| = m1m2...mk. Возьмем любой век-
тор (a1, a2, ... ak) из A1½A2½...½Ak и припишем справа элемент ak+1 ∈ Ak+1.
Это можно сделать mk+1 способом, т. е. получим mk+1 различных векторов
из A1½A2½...Ak½Ak+1.
         Таким образом, из всех m1 m2 ... mk векторов приписыванием справа
элемента из Ak+1 можно получить m1 m2 ... mk+1 векторов, причем все они
различны. Поэтому для n=k+1 теорема верна и, следовательно, верна для
любых n.
         Следствие: |An| = |A|n
         Упражнения 1.6
          1. Даны множества A = {a, b}и X = {1, 2, 3}. Найти прямое произве-
дение A × X .
          A × X = { ( a, 1); ( a, 2); . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .}.
          2. Пусть M = {(a; 1), (a; 2), (b; 1), (b; 2)}. Найти пр1 M = { . . . . . . . .. . .
.}.
          3. Дано множество S = {x, y, z}. Найти прямое произведение S2. S2 = {
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .}.




                                                    29

Страницы