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

A ´ B=í(x, y): xÎA & yÎBý.

Пример: А={-1;0;2}, В={3;6}

Ах В={(-1;3), (-1;6), (0;3), (0;6), (2;3), (2;6)}.

Пример: А=[-1;4), В=R

Нарисовать декартово произведение окружности с отрезком, длиной [0,1]

Свойства декартова произведения

1° АхВ¹ВхА

2° Если у нас имеются 3 непустых множества А, В, С и множество АÍВ, тогда декартово произведение АхСÍВхС

3° Если даны любые три непустые множества А, В, С и АхВÍВхСÞ АÍС

4° Пусть нам даны любые три непустые множества А, В, С, тогда

Ах(В С)=(АхВ) (АхС)

G F

При доказательстве будем использовать антисимметричность отношения включения.

Доказательство разобьется на 2 этапа:

1) GÍF

Þ F=G

2) FÍG

1. Покажем, что GÍF, для этого зафиксируем пару (х,у)ÎG или (х,у)ÎАх(В С)

хÎА и уÎ(В С) Þ хÎА и уÎВ или уÎС Þ (х,у)Î АхВ или (х,у)Î АхС Þ

Þ (х,у)Î(АхВ) (АхС) Þ GÍF

2. Покажем, что FÍG (доказать самостоятельно)

Из (1) и (2) Þ G=F

Утверждение: Пусть nÎN. Множество А₁, А₂,…, А_n непустые. Пусть множество А_i – конечное, тогда |А₁хА₂х…хА_n|=|А₁|×|А₂|×…×|А_n| (*)

Для доказательства будем использовать метод математической индукции. База индукции: n=2. Рассмотрим два множества с мощностями |А₁|=n и |А₂|=m.

1) Пусть А₁={а₁, а₂,…, а_n}, множество А₂={ b₁,b₂,…, b_m}. Выполним декартово произведение множеств.

А₁х А₂={(а₁,b_1), (а₁,b₂),…,(а₁,b_m),(а₂,b_1), (а₂,b₂),…,(а₂,b_m),…,(а_n,b_1), (а_n,b₂),…,(а_n,b_m)}

|А₁хА₂|=nхm=|А₁|×|А₂|.

2) Предположим, что наша функция (*) верна для всех k=n-1, т.е.

|А₁хА₂х…хА_n-1|=|А₁|× |А₂|×…×|А_n-1| (**)

3) Осуществляем индукционный переход, рассмотрим мощность декартова произведения n множеств, по пункту (1).

Можно записать |А₁хА₂х…хА_n|=|А₁|×|В|, где В=А₂х…хА_n, т.е. формула (**) может быть использована

|А₁хА₂х…хА_n|=|А₁|×|В|=|А₁|×|А₂|×…×|А_n|

Из (1-3) следует, что наша формула (*) верна для всех nÎN/{1}.