Операции на множествах и их свойства. Теорема о мощности декартова произведения конечных множеств. Теорема о счетности множества рациональных чисел. Изоморфизмы и автоморфизмы алгебр

Билет №1. Операции на множествах и их свойства (с доказательством).

         Множеством будем называть некоторую совокупность элементов произвольного рода.

         Объединением множеств А и В называется множество, каждый  элемент которого принадлежит хотя бы одному из этих двух множеств. 

АВ={x│xA  или xB}.

         Пересечением множеств А и В называется множество, элементы которого являются одновременно элементами обоих множеств.

АВ={x│xA и xВ}.

         Разностью множеств А и В называется множество, каждый элемент которого принадлежит множеству А, но не принадлежит множеству  В.

A\B={x│xA и xB}.

         Дополнением множества А называется разность между универсальным множеством и множеством А.

Ā=U\A.

         Универсальное множество U – множество, для которого в ходе какого-либо рассуждения все множества являются подмножествами.

Множество В является подмножеством множества А, если всякий элемент В является элементом А.

Симметрическая разность.

Свойства операций над множествами.

Пусть задан универсум U. Тогда A, B, C U выполняются следующие свойства

1. идемпотентность:

А А=А, АА=А

2. коммутативность:

АВ=ВА, АВ=ВА

      3. ассоциативность:

           А(ВС)=(АВ) С, А(ВС)=(АВ) С

4. дистрибутивность:

           А(В С)=(АВ)  (АС), А (ВС)=(АВ) (АС)

5. инволютивность (правило двойного отрицания):                                                         

       =А

6. правило де Моргана:

      =, =

7. правило склеивания:

(АВ)( А)=А, (АВ)( А)=А

8. правило поглощения:

А(АВ) =А, А(АВ) =А

9. действия с константами:

Константа – универсальное, пустое множество.

      А=; А=U

      ;

Билет №2. Теорема о мощности декартова произведения конечных множеств.

         Множества могут быть конечными и бесконечными. Мощность конечного множества равна числу элементов в нем. Обозначение мощности │А│. Если множество А не содержит ни одного элемента, то оно называется пустым: │А│=0.

Декартовым произведением  множеств А и В (А×В) называется множество всех пар (a,b), таких что aА, bВ.

А,В – множества произвольной природы

Свойства:

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

  │А₁  А₂  …  А_n│= m₁m₂… m_n              

         Доказательство (с помощью математической индукции):

1. База индукции: при n=1  теорема верна.
2. Индукционное предположение: предположим, что n=k, тогда │А₁  А₂  …  А_k│= m₁m₂… m_k .
3. Шаг индукции: возьмем любой вектор (а₁, …, а_k)  из   А₁  А₂  …  А_k  и припишем справа элемент а_k+1 A_k+1. Это можно сделать m_k+1 разными способами; при этом получится m_k+1  различных векторов из А₁  А₂  …  А_k+1. Таким образом, из всех m₁… m_k  векторов приписыванием справа элемента из  А_k+1 можно получить m₁… m_k m_k+1  векторов из  А₁  А₂  …  А_k+1 , причем все они различны, и никаких других векторов в  А₁  А₂  …  А_k+1 не содержится. Поэтому для n=k+1 теорема верна и, следовательно, верна для любых n.  

Вектор – упорядоченный набор элементов. Длина вектора – число координат.

Пример:

Сколько существует пятизначных  натуральных чисел?

Билет №3. Теорема о мощности булеана конечного множества.

         Множество всех подмножеств множества A называется булеаном и обозначается В(А). Множество В является подмножеством множества А, если всякий элемент В является элементом А.

Пример:

Теорема. Для конечного множества А{а₁,а₂,…а_n} │В(А) │=2ⁿ

         Доказательство:

(V_n-множество двоичных векторов из нулей и единиц длины n)

Установим взаимнооднозначное соответствие(т.е. биекцию) между булеаном и V_n.

Пусть

это биекция

Пример:

Если , то подмножеству  соответствует вектор

Билет №4. Теорема о счетности множества рациональных чисел.

Счетным множеством называется множество, равномощное множеству натуральных чисел (множества А и В равномощны, если существует взаимнооднозначное соответствие)

Теорема. Множество рациональных чисел счетно.

Доказательство:

, где Q – множество рациональных чисел.

Пусть  - рациональное число, где p,q- целые.

- высота дроби.

h=1 1дробь

h=2 множество дробей ,

и т.д. нумеруя дроби в порядке увеличения высот мы получим биекцию между N и Q, т.е. Q счетно.

Билет №5. Теорема о несчетности множества действительных чисел.

Теорема. Множество  действительных чисел несчетно.

Доказательство:

Рассмотрим интервал действительных чисел [0,1] R. Предположим, что оно счетно и существует его нумерация. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке этой нумерации:

0,a₁₁a₁₂a₁₃…

0,a₂₁a₂₂a₂₃…

0,a₃₁a₃₂a₃₃…

……………..

Рассмотрим любую бесконечную десятичную дробь 0,b₁b₂b₃…, такую что b₁≠a₁₁; b₂≠a_22;  b₃≠a₃₃ и т.д. Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго числа – второй цифрой и т.д. Следовательно, все числа не могут быть пронумерованы, и множество всех действительных чисел несчетно. Его мощность называется континуум.

Билет №6. Теорема о разбиении основного множества на классы эквивалентности.

Отношением эквивалентности называется бинарное отношение на множестве, если оно рефлексивно, симметрично и транзитивно.

1. a~a рефлексивность

2. a~b=b~a симметричность

3. a~b и b~c a~c транзитивность

Разбиением множества А называется совокупность попарно не пересекающихся подмножеств А таких, что каждый элемент множества А принадлежит только одному из этих подмножеств.

Пример:

тогда - разбиение множества Х.

Классом эквивалентности называется подмножество, состоящее из элемента а и всех элементов эквивалентных а.

Теорема. Эквивалентность(реф., сим., транз.) разбивает основное множество на классы эквивалентности, т.е.

1. АС_aC_b…
2. либо C_a=C_b, либо C_aC_b=Ø

Доказательство:

1. очевидно
2. пусть сC_aC_b

ac, bc

ca, cb(cим.)      (по транз.)  ab  bC_a (получилось противоречие)

Выясним, что класс эквивалентности не зависит от представителя, который мы выбираем из этого класса.

aC_a  и bC_a

ab или bc (по транзитивности)