Теорема о мощности прямого произведения множеств. Принцип математической индукции

Теорема. Пусть A ₁, A ₂,…, A_n – конечные множества и | A ₁|= m ₁, | A ₂|= m ₂,…, | A_n |= m_n. Тогда | A ₁´ A ₂´…´ A_n |= m ₁× m ₂×…× m_n.

Доказательство данной теоремы проведем методом математической индукции. Данный метод применим для доказательства утверждений A (n), имеющих смысл для натуральных чисел n и заключается в следующем:

1. Доказываем, что утверждение истинно для n =1, т.е. A (1) – истинно.

2. Предполагаем, что A (k) – истинно, k=2,3,…

3. Исходя из предположения A (k)– истинно доказываем истинность A (k +1). Из данного доказательства следует истинность утверждения A (n), для любого натурального числа n.

В нашем случае для n =1 истинность теоремы очевидна (| A ₁|= m ₁).

Предположим, что теорема верна для k =2,3,…, т.е. | A ₁´…´ A_k |= m ₁×…× m_k.

Возьмем любой вектор (a ₁,…, a_k)Î A ₁´…´ A_k и припишем ему справа элемент a_{k +1}Î A_{k +1}. Поскольку | A_{k +1}|= m_{k +1}, то это можно сделать m_{k +1} различными способами, т.е. получим m_{k +1}, различных векторов из вектора (a ₁,…, a_k). Таким образом, из всех m ₁×…× m_k векторов, составляющих множество A ₁´…´ A_k, приписыванием справа элемента a_{k +1}Î A_{k +1} можно получить m ₁×…× m_k × m_{k +1} векторов. Все полученные вектора различны и составляют множество A ₁´…´ A_k ´ A_{k +1}. То есть | A ₁´…´ A_k ´ A_{k +1}|= m ₁×…× m_k × m_{k +1} - теорема верна для k +1 и, следовательно, верна для любых натуральных n. Что и требовалось доказать.

Из доказанной теоремы следует .