Презентация на тему: Декартовы произведения

Декартовы произведения Под упорядоченной парой (а; b) мы будем понимать двухэлементное множество, состоящее из элементов а и b, в котором зафиксирован порядок расположения элементов. Отметим два характерных свойства упорядоченных пар

Определение 2 Определение 2 1) (a; b)={{a};{a; b}}; 2) (a1,a2,...,an,an+1)=((a1,a2,...,an),an+1). Упорядоченные наборы длины n называются также упорядоченными n-ками, векторами, кортежами. Теорема 2 .

Докажем теорему при n=k+1. Докажем теорему при n=k+1. Пусть Это можно переписать по определению следующим образом: По теореме 1 из равенства пар вытекает и По индуктивному предположению получаем

Пример Пример Пусть A={1;2}, B={a, b, c}, тогда А х В={(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)}; а В х А={(a;1);(b;1);(c;1);(a;2);(b;2);(c;2)}. Очевидно, что, вообще говоря,

Теорема 3 Теорема 3 Пусть А, В, С – произвольные множества, тогда а) ; б) ; в) . Доказательство а) Возьмем

б) Возьмем б) Возьмем

Поскольку в цепочке преобразований не везде стоят эквивалентности, а в одном месте стоит всего импликация, мы доказали включение Поскольку в цепочке преобразований не везде стоят эквивалентности, а в одном месте стоит всего импликация, мы доказали включение Необходимо доказать включение в другую сторону. Возьмем

Теорема 4 Теорема 4 Если множество А состоит из m элементов, а В – из n элементов, тогда А х В состоит из m х n элементов. Доказательство Доказываем индукцией по числу n-элементов множества В. При n=1 имеем , поэтому , то есть A х B имеет m = m х 1 элементов. Допустим, теорема верна при n=k. И пусть теперь В состоит из к+1 элемента, то есть

Первое множество состоит из m х k элементов по индуктивному предположению, второе множество Первое множество состоит из m х k элементов по индуктивному предположению, второе множество состоит из m элементов, как отмечалось в базисе индукции. Кроме того, , так как , поэтому множество А х В состоит из mk+m=m(k+1) элементов, что и требовалось доказать.