Discrete maths
Author:
abra
Last Updated:
5 years ago
License:
Creative Commons CC BY 4.0
Abstract:
Discrete maths for students of mathfac hse 19-23
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Discrete maths for students of mathfac hse 19-23
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amsmath}
\title{Discrete math, 1 grade}
\author{abraham chmutin}
\date{September 2019}
\begin{document}
\maketitle
\section{Set theory}
\newtheorem{Def}{Definition}[section]
\begin{Def}
\begin{align*}
&\text{set is set if and only if for every element we can say if it is in set or not.} \\
&\in \text{--- in}
\end{align*}
\end{Def}
\subsection{Elementary properties}
\subsubsection{Russell's paradox}
\begin{Def}
\begin{align*}
&\text{set A is}\ \textit{good} \iff A\ \notin A.\\
&G\ = \left\{A\bigm|A \ is \ good\right\}\\
&G\ \in \ G?
\end{align*}
\end{Def}
We can work with one big set, but what if we need more?
\subsubsection{Axiom of power set}
\begin{Def}
\begin{align*}
&\forall \text{--- for all}\\
&\exists \text{--- exists}\\
&\exists! \text{--- exists and only one}\\
&A\ \subset \ B iff \forall x \in A \left(x \in B \right) \text{--- A is subset of B}\\
&\left| X \right| = \#X = \text{number of elements in finite set}
\end{align*}
\end{Def}
\begin{Def}
$\mathcal{P}\left(A\right) = 2^{A} = \mathcal{B}\left(A\right) = \left\{X \bigm| X \subset A\right\}$
\end{Def}
Why do we write $2^A$? Well, $\left| 2^A\right| = 2^{\left| A \right|}$, so it's justified.
\newtheorem{axiom}{Axiom}
\begin{axiom}
$\exists\ set\ \mathcal{A} \Rightarrow \exists\ set\ 2^{\mathcal{A}}$
\end{axiom}
\subsubsection{Existence of product}
\begin{Def}
$A \times B = \left\{\left(a, \ b\right) \bigm|a \in A\wedge b \in B\right\}$
\end{Def}
Why do we write $A\times B$? Well, $\left|A\times B\right| = \left|A\right|\times\left|B\right|$, so it's justified.
$\exists\ sets\ A, B \Rightarrow \exists\ A \times B$
\subsection{Functions}
Function is a relation between sets that associates to every element of a first set exactly one element of the second set.
\Def y = $f\left(x\right)$ --- here f is a function and y is an image of x.
\Def If f is function from A to B then A is domain of f and B is codomain of f. $f\colon X\to Y$.
\Def $\Gamma_f = \left\{\left(x, y\right) \in X\times Y \bigm| y = f\left(x\right)\right\}$ --- graph of a function.
\begin{Def}
\begin{align*}
&if \ f\colon X\to Y:\\
&\forall x_1, x_2 \in X\colon x_1 \neq x_2 \left(f\left(x_1\right)\neq f\left(x_2\right)\right)\iff\ \text{f is an injection (one-to-one function)}\\
&\forall y \in Y \left(\exists x \in X\colon f\left(x\right)=y\right) \iff\ \text{f is a surjection (function onto)}\\
&\text{f is an injection and a surjection }\iff \text{f is bijection (one-to-one correspondence)}
\end{align*}
\end{Def}
\Def $Y^X = \left\{f\bigm|f\colon X\to Y\right\}$ = set of functions from X to Y
Why do we write $Y^X$? Well, $\left|Y^X\right| = {\left|Y\right|}^{\left|X\right|}$, so it's justified.
\subsubsection{Composition}
\Def if
$f\colon X\to Y$\
and\
$g\colon Y \to Z$, then
$g\circ f\colon X \to Z$\
and\
$g\circ f\left(x\right) = g\left(f\left(x\right)\right)$.
If
$f \colon X \to Y,\ g \colon Y \to Z,\ h \colon Z \to W,\ then\ h\circ\left(g\circ f\right) = \left(h\circ g\right) \circ f$.
\Def $if\ X\ is\ a\ set,\ then\ Id_X = 1_X\colon X\to X, \forall x \in X \left(Id_x\left(x\right) = x\right)$ --- identity function.
\begin{Def}
if $f\colon X \to Y,\ g\colon Y\to X,\ g\circ f = Id_X,\ f\circ g = Id_Y,$
then g is called inverse function to f or anti-function to f. We write
$g = f^{-1}$.
\end{Def}
\newtheorem{Th}{Theorem}
\Th For f exists inverse function $\iff$ f is a bijection.
\begin{proof}
\begin{enumerate}
\item Proof that bijection is invertible
If we have bijection $f\colon A\to B$ then $\forall b \in B \left(\exists! a \in A\colon f\left(a\right) = b\right)$. Let $g\left(b\right)$\ be that a. Then $g = f^{-1}$.
\item Proof that invertible function is bijection.
\begin{enumerate}
\item Proof that invertible function is injection.
Let's prove by contradiction. Let's say invertible function $f\colon A\to B$ isn't injection. That means $\exists a_1, a_2\in A\colon a_1 \neq a_2 \wedge f\left(a_1\right)=f\left(a_2\right) = b$. Then $f^{-1}\left(b\right)$\ is not defined. Contradiction.
\item Proof that invertible function is surjection.
By yourself.
\end{enumerate}
\end{enumerate}
\end{proof}
\Th $\forall \Omega \left(\exists \ bijection \ f\colon 2^{\Omega} \to \left\{0,\,1\right\}^{\Omega}\right)$
\begin{proof}
\begin{Def}
\begin{align*}
&\mathcal{X}_A\left(x\right)=
\begin{cases}
1, \text{if x}\in A\\
0, \text{if x}\notin A
\end{cases}
\end{align*}
\end{Def}
$\mathcal{X}_A$
is called indicator function or characteristic function.
Lirical digression:
$\mathcal{X}_{[0;+\infty)}$
is called Heaviside step fuction.
\Def $N_{\varphi} = \left\{x\in \Omega \bigm|\varphi\left(x\right) \neq 0\right\}$
$N_{\varphi}$
is called support of the function\ $\varphi$
Obviously,\
$N_{\mathcal{X}_A} = A$\
and\
$\mathcal{X}_{N_{\varphi}} = \varphi$
.
So\
$\mathcal{X}_A$\
is a bijection on the set
$2^{\Omega}\ \forall \Omega$.
\end{proof}
\subsubsection{What is this about? Who knows? Definitely not me}
\begin{Def}
Let\
$A,\ B \subset \Omega$.
Then
\begin{enumerate}
\item $A \cup B = \left\{x\bigm|x\in A \vee x\in B\right\}$
\item $A \cap B = \left\{x\bigm|x\in A \wedge x\in B\right\}$
\item $A \setminus B = \left\{x\in A\bigm|x\notin B\right\}$
\item $\bar A = \Omega \setminus A$
\end{enumerate}
\end{Def}
Let's prove\
$\overline{A \cup B} = \overline{A\mathstrut} \cap \overline{B\mathstrut}$.
\begin{proof}
\begin{enumerate}
\item Proof\
$\overline{A \cup B} \subset \overline{A\mathstrut} \cap \overline{B\mathstrut}$
$\forall x \in \overline{A \cup B\mathstrut} \left(x \notin A \cup B \Rightarrow x\notin A \wedge x\notin B \Rightarrow x\in \overline{A\mathstrut} \wedge x\in \overline{B\mathstrut} \Rightarrow x\in \overline{A\mathstrut} \cap \overline{B\mathstrut}\right)$
\item Proof\
$\overline{A\mathstrut} \cap \overline{B\mathstrut} \subset \overline{A \cup B}$
By yourself, dudes.
\end{enumerate}
\end{proof}
Let\
$A_1,\dots ,\ A_n \subset \Omega$
. Let's choose random
$x \in \Omega$\
Let\
$\alpha_i$\
be the answer on the question if
$x\in A_i$.
Then we have some function\
$f\colon \Omega \to \left\{0;1\right\}^n$.
So\
$\exists \Omega, A_1, \dots ,A_n\colon$\
f is a surjection.
\end{document}