Множества

Понятие множества является фундаментальной концепцией современной математики, поэтому точного определения множества не существует.
Однако мы можем себе представить множество как набор различных элементов. Вся современная математика основывается на концепции множества, поэтому очень важно знать и понимать теорию множеств.
Множества обычно обозначаются заглавными буквами латинского алфавита, например, $A, B, C...$. Элементы множества записываются в скобках $\lbrace$ и $\rbrace$.

Множество может быть задано несколькими способами:
1. его элементами $A=\lbrace 1,2,3,4,5 \rbrace$
2. правилом, которому удовлетворяют все элементы множества $A=\lbrace x\in \mathbb{N} \vert x<6\rbrace$

Множество, не содержащее элементов, называется пустым множеством и обозначается $\emptyset$ или $\lbrace \rbrace$.

Отношения между множествами

Равенство множеств

Два множества $A$ и $B$ равны тогда и только тогда, когда они содержат одни и те же элементы, то есть если все элементы первого множества являются элементами второго множества, и наоборот.

$A=B \overset{def}{\Leftrightarrow} (\forall x)(x\in A \Leftrightarrow x\in B)$

Поскольку отношение равенства является транзитивным, рефлексивным и симметричным, его называют отношением эквивалентности.

Подмножество

Множество $A$ является подмножеством множества $B$ тогда и только тогда, когда любой элемент множества $A$ является также элементом множества $B$.

$A \subseteq B \overset{def}{\Leftrightarrow} (\forall x)(x \in A \Rightarrow x \in B)$

Множество $B$ в таком случае называется надмножеством множества $A$ и обозначается как $B \supseteq A$.
Если множество $A$ является подмножеством множества $B$ и если множество $B$ содержит хотя бы один элемент, не принадлежащий множеству $A$, то говорят, что множество $A$ является строгим подмножеством множества $B$. Это обозначается как $A \subset B$, при этом множество $B$ называется строгим надмножеством множества $A$, что обозначается как $B \supset A$.

Отношение $\subset$ является транзитивным: $(A \subset B) \wedge (B \subset C) \Rightarrow A \subset C$.

Пустое множество является подмножеством любого множества.

Операции над множествами

Объединение двух множеств

Объединением двух множеств $A$ и $B$ называется множество, состоящее из всех элементов, принадлежащих множествам $A$ или $B$.

$A \cup B \overset{def}{=} \lbrace x \vert x \in A \vee x \in B \rbrace$

Операция объединения двух множеств является:
1. идемпотентной: $A\cup A=A$
2. коммутативной: $A \cup B = B \cup A$
3. ассоциативной: $(A \cup B) \cup C = A \cup (B \cup C)$

Пересечение множеств

Пересечением двух множеств $A$ и $B$ называется множество, которому принадлежат те и только те элементы, которые одновременно принадлежат множествам $A$ и $B$.

$A \cap B\overset{def}{=}\lbrace x \vert x\in A \wedge x\in B \rbrace$

Операция пересечения множеств является:
1. идемпотентной: $A\cap A=A$
2. коммутативной: $A \cap B = B \cap A$
3. ассоциативной: $(A \cap B) \cap C = A \cap (B \cap C)$

Разность двух множеств

Разностью двух множеств $A$ и $B$ является множество, содержащее все элементы множества $A$, не входящие в множество $B$.

$A \setminus B \overset{def}{=} \lbrace x \vert x \in A \wedge x \notin B \rbrace$

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

Симметрическая разность двух множеств $A$ и $B$ - это множество, включающее все элементы исходных множеств, которые принадлежат только одному из множеств $A$ или $B$.

$A \bigtriangleup B \overset{def}{=} (A \setminus B) \cup (B \setminus A)$

Очевидно, что операция $\bigtriangleup$ коммутативна.

Дополнение множества

Пусть $A \subset B$. Дополнением множества $A$ относительно множества $B$ называется множество, состоящее из всех элементов множества $B$, которые не входят в множество $A$.

$C_B(A)\overset{def}{=}\lbrace x\vert x\in B \wedge x\notin A\rbrace$

Булеан

Булеан (степень множества) $A$ - это множество всех подмножеств множества $A$, включая пустое множество и само множество $A$.

$P(A) \overset{def}{=} \lbrace B \vert B \subset A \rbrace$

Например: Булеаном множества $A=\lbrace 1,2,3 \rbrace $ является множество $P(A)=\lbrace \emptyset ,\lbrace 1 \rbrace , \lbrace 2\rbrace, \lbrace 3 \rbrace , \lbrace 1,2 \rbrace , \lbrace 1,3 \rbrace , \lbrace 2,3 \rbrace , \lbrace 1,2,3 \rbrace \rbrace $

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

Декартовым произведением множеств $A$ и $B$ является множество, содержащее все возможные упорядоченные пары $(x,y)$ элементов исходных множеств ($x$ - элемент множества $A$, $y$ - элемент множества $B$).

$A \times B \overset{def}{=} \lbrace(x,y) \vert x \in A \wedge y \in B \rbrace $

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

Дистрибутивный закон
$A \cup (B \cap C)=(A \cup B)\cap (A \cup B)$
$A \cap (B \cup C)=(A \cap B)\cup (A \cap B)$

Закон поглощения
$A\cup(A\cap B)=A$
$A\cap(A\cup B)=A$

Законы де Моргана
$C_U(A\cup B)=C_U(A)\cap C_U(B)$
$C_U(A\cap B)=C_U(A)\cup C_U(B)$

Отношения и функции

Отношения

Если множества $A$ и $B$ непустые, то любое подмножество $\rho$ множества $A\times B$ называется бинарным отношением между множествами $A$ и $B$.
Если $(a,b)\in \rho$, говорят, что $a$ и $b$ находятся в отношении, и это обозначается как $a\rho b$.

Отображения

Бинарное отношение $f\subset X\times Y$ называется отображением тогда и только тогда, когда для любого элемента $x\in X$ существует ровно один $y\in Y$, для которого выполняется $(x,y)\in f$ , то есть $(\forall x\in X)(\exists !y\in Y)(x,y)\in f$

В символьном обозначении: $f:X\longmapsto Y$ or $X\overset{f}{\longmapsto} Y$
Если $(x,y)\in f$, пишут $f(x)=y$. Элемент $x$ называется прообразом, а $y$ образом.
Множество $X$ называется областью определения, а множество $Y$ - областью значений $f$.
Особое значение в математике придается трем специальным типам отображений – инъекции, сюръекции и биекции.

Инъекция

Отображение $f:X\longmapsto Y$ является инъекцией или однозначным отображением тогда и только тогда, когда для каждого элемента $x\in X$ существует ровно один элемент $y\in Y$, для которого выполняется $f(x)=y$.

$f:X\overset{1-1}{\longmapsto}Y\overset{def}{=}(\forall x_1,x_2\in X)(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2))$

Сюръекция

Отображение $f:X\longmapsto Y$ сюръективно тогда и только тогда, когда для каждого элемента $y\in Y$ существует хотя бы один элемент $x\in X$, для которого истинно $f(x)=y$.

$f:X\overset{onto}{\longmapsto}Y\overset{def}{=}(\forall y\in Y)(\exists x\in X)(f(x)=y)$

Биекция

Отображение $f:X\longmapsto Y$ называется биекцией, если оно является одновременно и сюръективным, и инъективным.