Documents/Diszkrét Matematika/Document.tex

% Compile twice!
% With the current MiKTeX, you need to install the beamer, and the translator packages directly form the package manager!

% !TEX root = ./Headers/PrezA4Page.tex

% Uncomment these to get the presentation form
%\documentclass{beamer}
%\geometry{paperwidth=200mm,paperheight=200mm, top=0in, bottom=0.2in, left=0.2in, right=0.2in}

% Uncomment these, and comment the 2 lines above, to get a paper-type article
%\documentclass[10pt]{article}
%\usepackage{geometry}
%\geometry{top=0.2in, bottom=0.2in, left=0.2in, right=0.2in}
%\usepackage{beamerarticle}
%\renewcommand{\\}{\par\noindent}
%\setbeamertemplate{note page}[plain]

% Half A4 geometry
%\geometry{paperwidth=105mm,paperheight=297mm,top=0.2in, bottom=0.2in, left=0.2in, right=0.2in}

% "1/3" A4 geometry
%\geometry{paperwidth=105mm,paperheight=455mm,top=0.1in, bottom=0.1in, left=0.1in, right=0.1in}

% "1/6" A4 geometry
%\geometry{paperwidth=105mm,paperheight=891mm,top=0.1in, bottom=0.1in, left=0.1in, right=0.1in}

% "1/5" A4 geometry
%\geometry{paperwidth=105mm,paperheight=740mm,top=0.1in, bottom=0.1in, left=0.1in, right=0.1in}

% "1/4" A4 geometry
%\geometry{paperwidth=105mm,paperheight=594mm,top=0.1in, bottom=0.1in, left=0.1in, right=0.1in}

% Uncomment these, to put more than one slide / page into a generated page.
%\usepackage{pgfpages}
% Choose one
%\pgfpagesuselayout{2 on 1}[a4paper]
%\pgfpagesuselayout{4 on 1}[a4paper]
%\pgfpagesuselayout{8 on 1}[a4paper]

% Includes
\usepackage{tikz}
\usepackage{tkz-graph}
\usetikzlibrary{shapes,arrows,automata}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{booktabs}
\usepackage{array}
\usepackage{arydshln}
\usepackage{enumerate}
\usepackage[many, poster]{tcolorbox}
\usepackage{pgf}
\usepackage[makeroom]{cancel}

\providecommand{\includecolors}{\input{../Colors/Default.tex}}% fallback definition
\includecolors

\setbeamertemplate{itemize item}{\color{black}$-$}
\setbeamertemplate{itemize subitem}{\color{black}$-$}
\setbeamercolor*{enumerate item}{fg=black}
\setbeamercolor*{enumerate subitem}{fg=black}
\setbeamercolor*{enumerate subsubitem}{fg=black}

 \renewcommand{\familydefault}{\sfdefault}
%\renewcommand{\familydefault}{\rmdefault}

\renewcommand{\footnotesize}{\fontsize{1.2em}{0.2em}}
\renewcommand{\normalsize}{\fontsize{1.2em}{0.2em}}
\renewcommand{\large}{\footnotesize}
\renewcommand{\Large}{\footnotesize}


\renewcommand{\scriptsize}{\footnotesize}
\renewcommand{\LARGE}{\footnotesize}
\renewcommand{\Huge}{\footnotesize}

\renewcommand{\tiny}{\footnotesize}
\renewcommand{\small}{\footnotesize}

\fontsize{1.2em}{0.2em}
\selectfont

\newcommand{\RHuge}{\fontsize{1.8em}{0.3em}\selectfont}

\newsavebox\CBox 
%\newcommand<>*\textBF[1]{\sbox\CBox{#1}\resizebox{\wd\CBox}{\ht\CBox}{\textbf#2{#1}}}
\newcommand<>*\textBF[1]{\only#2{\sbox\CBox{#1}\resizebox{\wd\CBox}{\ht\CBox}{\textbf{#1}}}}

% Beamer theme
\usetheme{boxes}

% tikz settings for the flowchart(s)
\tikzstyle{decision} = [diamond, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=green!15]
\tikzstyle{tcolorbox} = [rectangle, draw, fill=blue!15, text width=20em, text centered, minimum height=1em]

\tikzstyle{line} = [draw, -latex']
\tikzstyle{cloud} = [draw, ellipse,fill=red!20, node distance=3cm,
    minimum height=2em]
\tikzstyle{arrow} = [thick,->,>=stealth]

\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\renewcommand{\arraystretch}{1.2}

\setlength\dashlinedash{0.2pt}
\setlength\dashlinegap{1.5pt}
\setlength\arrayrulewidth{0.3pt}

\newcommand{\mtinyskip}{\vspace{0.2em}}
\newcommand{\msmallskip}{\vspace{0.3em}}
\newcommand{\mmedskip}{\vspace{0.5em}}
\newcommand{\mbigskip}{\vspace{1em}}


\begin{document}

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Diszkrét Matematika I}\\
\end{tcolorbox}
\end{frame}


%\begin{tcolorbox}[title={Def.: }]
%\end{tcolorbox}

% --------------------  HALMAZOK, RELÁCIÓK --------------------

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Halmazok, Relációk}
    \mmedskip
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: A halmazelmélet "Definiálatlan alapfogalmai"}]
    "Halmaznak lenni", és "eleme".\\
    $A := \{$felsorolás$\}$\\
    $A := \{ x \in B | F(x) \}$\\
    $A := \{ x \in B : F(x) \}$\\
    {\footnotesize ($|$, $:$ $\rightarrow$ ahol.)}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.:  Meghatározottsági Axióma (Halmazok egyenlősége)}]
    Az $A$ és $B$ halmaz akkor és csak akkor egyenlő, ha ugyanazok az elemeik.\\
    {\footnotesize A sorrend nem számít!)}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Az üres halaz axiómája}]
    Van olyan halmaz, amelynek nincs eleme.\\
    Jel: $\emptyset$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Részhalmaz-axióma}]
    Minden $A$ halmazra és minden $F(x)$ formulára létezik egy B halmaz, amelyhel $A$-nak pontosa azok az $x$ elemei tartoznak, amelyekre $F(x)$ igaz.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Russel-paradoxon}]
    $U = \{x : x = x \}$ (Ez Minden dolog tételnek az oka / bizonyítása)
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Minden dolog halmaza}]
    Nincs olyan halmaz, amelynek minden dolog eleme.
  \tcblower
    Bizonyítás:\\
    \mmedskip

    Legyen $A$ és $B$ tetszőleges halmaz, és $B = \{x \in A, x \neq x \}$
    \msmallskip
    
    Belátható, hogy $B \notin A$
    \msmallskip
    
    Ami azt jelenti, hogy tetszőleges halmazhoz konstruálunk olyan halmazt, amely nem lehet eleme.\\
    \mtinyskip
    
    (egy x se tartalmazza magát elemként (ne legyen tartalmazkodó (= rendes halmaz)).\\
    \mmedskip

    TFH (Indirekt):\\
    $B \in A$, ekkor:\\

    \textBF{1.eset}\\
    \msmallskip

    Ha $B \notin B$ $\rightarrow$ Definíció szerint ekkor $B \in B$ $\Rightarrow$ Ellentmondás!\\
    \msmallskip

    Ha $B \in B$ $\rightarrow$ Definíció szerint ekkor $B \notin B$ $\Rightarrow$ Ellentmondás!\\
    \msmallskip

    $\Rightarrow$ $B \notin A$.
    (Belátható, hogy $B \notin A$, mert $B$ nem lehet eleme $A$-nak.)
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Definíció: Unió}]
    Ha A és B halmazok, akkor A és B unióján a következő halmazt értjük:\\
    $$A \cup B = \{x | x \in A \vee x \in B\}$$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Az unió tulajdonságai}]
    Legyenek A, B, C tetszőleges halmazok. Ekkor:

    \begin{enumerate}
      \item $A \cup \emptyset = A$
      \item $A \cup B = B \cup A$ (Kommutativitás)
      \item $A \cup (B \cup C) = (A \cup B) \cup C)$ (Asszociativitás)
      \item $A \cup A = A$ (Idempotencia)
      \item $A \subseteq B$ akkor, és csak akkor, ha $A \cup B = B$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Definíció: Metszet}]
    Ha A és B halmazok, akkor A és B metszetén a következő halmazt értjük:\\
    $$A \cap B = \{x \in A \wedge x \in B\}$$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: A metszet tulajdonságai}]
    Legyenek A, B, C tetszőleges halmazok. Ekkor:

    \begin{enumerate}
      \item $A \cap \emptyset = \emptyset$
      \item $A \cap B = B \cap A$ (Kommutativitás)
      \item $A \cap (B \cap C) = (A \cap B) \cap C$ (Asszociativitás)
      \item $A \cap A = A$ (Idempotencia)
      \item $A \subseteq B$ akkor, és csak akkor, ha $A \cap B = A$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Unió és metszet disztributivitása}]
    Legyenek A, B, C tetszőleges halmazok. Ekkor:

    \begin{enumerate}
      \item $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ (A metszet disztributivitása az unióra nézve)
      \item $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ (Az unió disztributivitása a metszetre nézve)
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Diszjunkt, Páronként diszjunkt halmazok.}]
    Két halmaz \textBF{diszjunkt}, ha metszetük üres.\\
    Egy halmazrendszer elemei \textBF{páronként diszjunktak}, ha bármely kettő metszete üres.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Halmazok Különbsége}]
    Az $A, B$ halmaz \textBF{Különbségén} a következő halmazt értjük:\\
    $A \setminus B = \{ x \in A | x \notin B \}$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Halmazok Szimmetrikus Differenciája}]
    Az $A, B$ halmazok \textBF{szimmetrikus differenciáján} a következő halmazt értjük:\\
    $A \triangle B = \{ x | x \in A \setminus B \lor x \in B \setminus A \} = \{ x \in A \cup B | x \notin A \cap B \}$.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Definíció: Komplementer}]
    Ha X halmaz, A $\subseteq$ X, akkor A halmaz X-re vonatkoztatott komplementere:\\
    $$A' = X \setminus A$$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: A komplementer tulajdonságai}]
    Legyenek A, B $\subseteq$ X halmazok. Ekkor:

    \begin{enumerate}
      \item $(A')' = A$
      \item $\emptyset' = X$
      \item $X' = \emptyset$
      \item $A \cap A' = \emptyset$
      \item $A \cup A' = X$
      \item $A \subseteq B$ akkor, és csak akkor, ha $B' \subseteq A'$      
      \item $(A \cup B)' = A' \cap B'$
      \item $(A \cap B)' = A' \cup B'$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Definíció: Hatványhalmaz}]
    Ha $A$ halmaz, akkor azt a halmazrendszert, melynek elemei $A$ részhalmazai, az \textBF{$A$ hatványhalmazának} nevezzük.\\
    Jele: ${\wp}(A)$, (A $\wp$ betű a "Potenz" szóra utal (gyakori a $2^A$ jelölés is.)
  \end{tcolorbox}

  \begin{tcolorbox}[title={Axióma: Végtelenségi Axióma}]
    Van olyan $A$ halmaz, amelynek az $\emptyset$ eleme, és ha valamely $x$ halmaz eleme $A$-nak, akkor az $x \cup \{ x \}$ halmaz is eleme $A$-nak.\\
    $\emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \}, \{ \emptyset , \{ \emptyset \}, \{ \emptyset , \{ \emptyset \} \} \}, ...$
  \end{tcolorbox}
\end{frame}

% --------------------  RELÁCIÓK --------------------

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Relációk}
    \mmedskip
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Rendezett pár}]
    $(a_1, a_2) := \{ \{ a_1 \}, \{ a_1, a_2 \} \}$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Rendezett $n$-es}]
    $(a_1, ..., a_n) := ((a_1, ..., a_{n - 1}), a_n)$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Descartes (Direkt) szorzat}]
    $A_1 x A_2 x ... x A_n := \{ (a_1, ..., a_n) | a_i \in A_i \}$,\\
    ahol $A_1, A_2, ..., A_n$ tetszőleges halmazok.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: $n$ változós reláció}]
    $R \subseteq A_1 x A_2 x ... A_n$\\
    \mmedskip

    Jelölés binér relációknák: $(a, b) \in R$, vagy $a R b$.
    (1 változós = unér, 2 változós = binér)
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Homogén reláció}]
    ${\forall}i, j \in \{ 1, 2, ..., n \} : A_i = A_j$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Identikus leképzés}]
    $\mathbb{I}_X := \{(x, x) \in X x X : x \in X \}$, (Pl.: (1, 1), (2, 2), ...)
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Reláció értelmezési tartománya}]
    \textBF{$R \subseteq X x Y$ reláció értelmezési tartománya}\\
    $dmn(R) := \{ a \in X | {\exists}b \in Y : (a, b) \in R \}$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Reláció értékkészlete}]
    \textBF{$R \subseteq X x Y$ reláció értékkészlete}\\
    $rng(R) := \{ b \in Y | {\exists} a \in X : (a, b) \in R \}$.
  \end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Leszűkítés, kierjesztés}]
Ha $S \subseteq R$, akkor $S$ az $R$ \textBF{ledszűkítése}, $R$ az $S$ \textBF{kiterjesztése}.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Az $R$ reláció $X$ halmazra való Leszűkítése}]
Az $R$ reláció $X$ halmazra való \textBF{leszűkítése}:\\
$R|_X := \{(a, b) \in R | a \in X \}$.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Ar $r \subseteq X x Y$ reláció inverze}]
$R^{-1} = \{(b, a) \in Y x X | (a, b) \in R \}$.
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
$(R^{-1})^{-1} = R$\\
$dmn(R^{-1}) = rng(R)$\\
$rng(R^{-1}) = dmn(R)$\\
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Az $A$ halmaz képe, (ős)képe / inverz képe}]
Az $A$ halmaz \textBF{képe}:\\
$R(A) := \{ y :$ van olyan $x \in A$, hogy $(x, y) \in R \}$\\
\mmedskip

\textBF{Inverz (Ős) képe}:\\
$R^{-1}(A)$.
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
$R(A) = \emptyset \iff A \cap dmn(R) = \emptyset$.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Az $S$ és $R$ binér relációk kompozíciója}]
$R \circ S := \{ (x, y) : $ van olyan $z$, hogy $(x, z) \in S$ és $(z, y) \in R \}$
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
$rng(S) \cap dmn(R) = \emptyset \Rightarrow R \circ S = \emptyset$.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Kompozíció tulajdonságai}]
Legyenek $R, S,$ és $T$ binér relációk. Ekkor:\\
\begin{enumerate}
\item Ha $rng(S) \supseteq dmn(R)$, akkor $rng(R \circ S) = rng(R)$.
\item $R \circ (S \circ T) = (R \circ S) \circ T$ (asszociativitás).
\item $(R \circ S)^{1} = s^{-1} \circ R^{-1}$.
\end{enumerate}

Ha $R$ reláció $X$ és $Y$ között, akkor:\\
$\mathbb{I}_Y \circ R = R$ és $R \circ \mathbb{I}_X = R$.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Homogén binér relációk tulajdonságai}]
Legyen $R \subseteq A x A$ alakú, ekkor $R$\\
\begin{enumerate}
\item \textBF{Reflexív}: ${\forall}a \in A (a R a)$
\item \textBF{Irreflexív}: ${\forall}a \in A {\neg}(a R a)$
\item \textBF{Szimmetrikus}: ${\forall}a, b \in A (a R b \Rightarrow b R a)$
\item \textBF{Antiszimmetrikus}: ${\forall}a, b \in A (a R b \land b R a \Rightarrow b = a)$
\item \textBF{Szigorúan antiszimmetrikus (Asszimetrikus)}: ${\forall}a, b \in A (a R b \Rightarrow {\neg}(b R a))$
\item \textBF{Tranzitív}: ${\forall}a, b, c \in A (a R b \land b R c \Rightarrow a R c)$
\item \textBF{Intranzitív}: ${\forall}a, b, c \in A (a R b \land b R c \Rightarrow {\neg}(a R c))$
\item \textBF{Trichotom}: ${\forall}a, b \in A (1!$ (pontosan 1) áll fenn $a R b, b R a, a = b$ közül.
\item \textBF{Dichotom}: ${\forall}a, b \in A (a R b \lor b R a)$
\end{enumerate}
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Ekvivalenciareláció}]
ha \textBF{reflexív, tranzitív, szimmetrikus}.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Halmaz osztályfelbontása}]
A tetszőleges X halmazt \textBF{osztályozzuk (osztályokra bontjuk)}, ha páronként diszjunkt, nemüres részhalmazainak uniójaként állítjuk elő.
\end{tcolorbox}

\begin{tcolorbox}[title={Az x $\in$ X elem \textBF{ekvivalencia osztálya}:}]
$$\overline{x} = \{y \in X : y \sim x\}$$
\end{tcolorbox}

\begin{tcolorbox}[title={Tétel: Ekvivalenciareláció és osztályfelbontás kapcsolata}]
Valamely X halmazon értelmezett $\sim$ ekvivalenciareláció X-nek egy osztályfelbontását adja. Megfordítva, az X halmaz minden osztályfelbontása egy $\sim$ ekvivalenciarelációt hoz létre.
\tcblower
Bizonyítás:\\
\mmedskip

\textBF{1. Rész ($\Rightarrow$)}\\
\mmedskip

Tfh $\sim$ ekvivalenciareláció X-n.
\msmallskip

Reflexivitás $\Rightarrow$ $x \in \tilde{x}$ $\Rightarrow$ osztályok nem üresek.\\
\msmallskip

Mi újság a két osztály metszetével?\\
\msmallskip

\textBF{Tfh} van nem üres: $z \in \tilde{x} \cap \tilde{y}$ tranz + szimm $\Rightarrow$ $x \sim y$, továbbá:\\
\msmallskip

tranz + szimm $\Rightarrow$ $w \in \tilde{x} \Rightarrow w \in \tilde{y}$ és $w \in \tilde{y} \Rightarrow w \in \tilde{x}$.
\msmallskip

Kaptuk: $\tilde{x} \cap \tilde{y} \neq \emptyset \Rightarrow \tilde{x} = \tilde{y}$
\mmedskip

Tehát a következő halmaz $X$-nek egy osztályfelbontását adja:\\
$\tilde{X} = \{ \tilde{x} : x \in X \}$\\

\textBF{2. Rész ($\Leftarrow$)}:\\
\mmedskip

Tfh ${\exists}X$-nek osztályfelbontása:\\

$X_1 \cup X_2 \cup ... \cup X_n = X$\\

Legyen a relációnk:\\

$p := \{(a,b) \in X x X | a, b \in X_i$ valamely $1 \leq i \leq n$-re $\}$.\\
\mmedskip

Reflexív? $\rightarrow$ Igen\\
Tranzitív? $\rightarrow$ Igen\\
Szimmetrikus? $\rightarrow$ Igen
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.: Részbenrendezés, Szigorú részbenrendezés}]
Az $R \subseteq X x X$ reláció \textBF{részbenrendezés (${\leq}$)}, ha:\\
\begin{itemize}
\item Reflexív
\item Tranzitív
\item Antiszimmetrikus
\end{itemize}
\mmedskip

\textBF{Szigorú részbenrendezés (<)}, ha:\\
\begin{itemize}
\item Irreflexív
\item Tranzitív
\end{itemize}
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Teljes rendezés}]
Tetszőleges részbenrendezett halmaz esetén, ha bármely két elem relációban van, \textBF{rendezésről (teljes rendezés)} beszélünk.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Részbenrendezett, vagy rendezett struktúra}]
\textBF{$(X, {\leq})$ részbenrendezett vagy rendezett struktúra}, ha ${\leq}$ részbenrendezés vagy rendezés.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Diagonális reláció}]
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Szigorú, gyenge reláció, Lánc}]
Tetszőleges $X$, a $\leq$ relációval részbenrendezett halmaz bármely $Y$ részhalmaza részbenrendezett a $\leq \subseteq Y x Y$ relációval.\\
\msmallskip

Ha ($\leq \subseteq Y x Y$) struktúra rendezés, akkor \textBF{lánc}.\\
\mmedskip

Tfh $R$ $X$-beli reláció. Ha $S$ $X$-beli reláció olyan, hogy $xSy$ akkor áll fenn, ha $xRy$ ls $x \neq y$, akkor $S$ az $R$-nek megfelelő \textBF{szigorú reláció}.\\
\mmedskip

Tfh $R$ $X$-beli reláció. Ha $T$ $X$-beli reláció olyan, hogy $xTy$ akkor áll fenn, ha $xRy$ vagy $x = y$, akkor $T$ az $R$-nek megfelelő \textBF{gyenge reláció}.\\
\mmedskip

\textBF{< szigorú részbenrendezés}: Irreflexív, Tranzitív, Szigorúan Antiszimmetrikus.\\
\mmedskip

Ész: $\leq$ rendezés $\iff$ trichotóm.
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.: Zárt Intervallum}]
$[x, y] = \{ z \in X | x \leq z \leq y \}$.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Nyílt Intervallum}]
$(x, y) = \{ z \in X | x < z < y \}$.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Közvetlenü megelőzi, Közvetlenül követi}]
Ha $x < y$, de ugyanakkor nem létezik szigorúan $x$ és $y$ közé eső elem, akkor azt mondjuk, hogy $x$ \textBF{közvetlenül megelőzi} $y$-t, vagy $y$ \textBF{közvetlenül követi} $x$-et.\\
\mmedskip

Egy $x$ elemhez tartozó \textBF{kezdőszeletnek} a $\{ y \in X : y < x \}$ részhalmazt nevezzük.\\
\mmedskip

Jel: $] {\leftarrow}, x [$ ($\rightarrow$ = közvetlenül megelőzi)
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Minimális, Maximális, Legkisebb, Legnagyobb elem}]
Legyen $(X, {\leq})$ részbenrendezett struktúra, ekkor\\
$m \in X$\\
\msmallskip

az $X$ \textBF{minimális eleme}, ha nem létezik olyan $(m {\neq}) x \in X$, amelyre $m \geq x$.\\
\mmedskip

\textBF{legkisebb eleme}, ha minden $x \in X$-re $m \leq x$.\\
\mmedskip

\textBF{Maximális} és \textBF{legnagyobb} elem hasonlóan.
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
Legkisebb és legnagyobb elem legfeljebb egy van.\\
Minimális és maximális elem több is lehet.\\
Rendezett halmazban legkisebb és minimális elem egybeesik.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Alsó korlát, Felső korlát}]
Legyen $B \subseteq A$ ($A$ részbenrendezett), ekkor:\\
\msmallskip

$a \in A$\\
\textBF{a $B$ alsó korlátja}, ha minden $x \in B$-re $a \leq x$.\\
\mmedskip

\textBF{Felső korlátja}, ha minden $x \in B$-re $x \leq a$.\\
\mmedskip

Észrevételek:\\
\begin{itemize}
\item Lehet 0, vagy több korlát.
\item A korlát nem biztos, hogy $B$ eleme.
\item Ha egy korlát $B$-ben van, akkor 1! (Legkisebb, vagy legnagyobb elem)
\end{itemize}
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Infinum, Supremum}]
$B$ \textBF{infinuma} (inf $B$), ha létezik, $B$ legnagyobb alsó korlátja.\\
\mmedskip

\textBF{pontos felső/alsó korlát, felső/alsó határ}\\
\mmedskip

$B$ \textBF{supremuma} (sup $B$), ha létezik, $B$ legkisebb felő korlátja.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Jólrendezett halmaz}]
Tetszőleges részbenrendezett halmaz \textBF{jólrendezett}, ha bármely nemüres részhalmazának van legkisebb eleme.
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
Jólrendezett $\Rightarrow$ rendezett.
\end{tcolorbox}
\end{frame}

% ----------------   FÜGGVÉNYEK ------------------

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Függvények}
    \mmedskip
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Függvény, Parciális függvény}]
Az $f$ \textBF{reláció} függvény, ha\\
$(x, y) \in f \land (x, y') \in f \Rightarrow y = y'$.\\
\tcblower
Kapcsolódó jelölések, fogalmak:\\
\mmedskip

$f(x) = y$\\
$f : x \rightarrow y$\\
$X \rightarrow Y$ (Az összes olyan fggvény halmaza, amelynek értelmezési tartománya X-nek, értékkészlete pedig Y-nak része.)\\
\mmedskip

\textBF{Parciális függvény}:\\
\msmallskip

$f: X \rightarrow Y$, ($dmn(f) = X$)\\
$f \in X \rightarrow Y$ ($dmn(f) \subseteq X$) $\leftarrow$ Parciális függvény.\\
Mindkettőnél: $rng(f) \subseteq X$
\end{tcolorbox}

\begin{tcolorbox}[title={Mikor egyenlő két függvény?}]
$f = g \iff (dmn(f) = dmg(g)) \land ({\forall}x \in dmn(f) \Rightarrow f(x) = g(x))$\\
\mmedskip

Akkor, és csak akkor, ha minden érték megegyezik, és az értelmezési tartomány is.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Függvények típusai}]
Az $f: A \rightarrow B$ függvény\\
\begin{itemize}
\item \textBF{Szürjektív}, ha $B = rng(f)$ (Ráképzés)
\item \textBF{Injektív}, ha ${\forall} a, b \in dmn(f) : (a \neq b) \Rightarrow f(a) \neq f(b)$ (Kölcsönösen egyértelmű)
\item \textBF{Bijektív}, ha Injektív, és Szürjektív is.
\end{itemize}
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
Injektív függvény inverze is függvény.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Kanonikus leképzés}]
Ha adott egy $X$ halmazon értelmezett ekvivalenciareláció, akkor az $X$ elemeihez saját ekvivalenciaosztályukat rendelő leképzést (függvényt) \textBF{kanonikus leképzésnek (függvénynek)} nevezzük.\\
\msmallskip

Fordítva: ha $f: X \rightarrow Y$ függvény, akkor $\sim \subset X x X$ ekvivalenciareláció, ahol $(x, y) \in {\sim}$, ha $f(x) = f(y)$.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Monoton, Szigorúan monoton függvények}]
Legyen $(A, {\leq}_1), (B, {\leq}_2)$ részbenrendezett struktúra.\\
Ekkor az $f : A \rightarrow B$ függvény\\
\mmedskip

\textBF{monoton növő}, ha:\\
${\forall}x, y \in dmn(f) : x {\leq}_1 y \Rightarrow f(x) {\leq}_2 f(y)$.\\
\mmedskip

\textBF{Szigorúan monoton növő}, ha:\\
${\forall}x, y \in dmn(f) : x <_1 y \Rightarrow f(x) <_2 f(y)$.\\
\mmedskip

\textBF{Csökkenő hasonlóan!}
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
Ha $A$ és $B$ rendezettek, akkor:\\
$f$ szigorúan monoton $\Rightarrow$ $f$ injektív.\\
$f$ injektív $\land$ monoton $\Rightarrow$ szigorúan monoton és $f$ inverze is monoton.
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.: Családok (Indexhalmaz, Indexelt halmaz, Indexelt család)}]
Legyen $x$ függvény, $dmn(x) = I$ és $x(i) = y$ helyett írjuk $x(i) = x_i$-t.\\
\mmedskip

Ekkor:\\
\msmallskip

$I$ \textBF{indexhalmaz}, $rng(x)$ \textBF{indexelt halmaz}, $x$ \textBF{indexelt család}.\\
\msmallskip

Ha $rng(x)$ elemei halmazok, akkor \textBF{halmazcsaládról} beszélünk, és egy $X_i, i \in I$ \textBF{halmazcsalád unióját} így definiáljuk:\\
${\bigcup}_{i \in I} X_i := {\bigcup}\{ X_i : i \in I\}$\\
\mmedskip

$i \leq \emptyset$ esetén \textBF{halmazcsalád metszetét} így definiáljuk:\\
${\bigcap}_{i \in I} X_i := {\bigcap}\{ X_i : i \in I\}$
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.: Kiválasztási függvény, Halmazcsalád Descartes-szorzata}]
Az $X_i, i \in I$ halmazcsaládhoz tartozó \textBF{kiválasztási függvénynek} nevezzük azokat az\\
$x : I \rightarrow {\bigcup}_{i \in I} X_i$\\
alakú függvényeket, ahol ${\forall} i \in I$-re $x_i \in X_i$.\\
\mmedskip

Az $X_i \in I$ halmazcsalád \textBF{Descartes - szorzata} a hozzá tartozó összes kiválasztási függvény halmaza.\\
\mmedskip

Jel: $X_{i \in I} X_i$, vagy $x_iX_i$
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
Ha ${\exists} i \in I : X_i = \emptyset \Rightarrow x_iX_i = \emptyset$\\
$I = \emptyset \Rightarrow x_iX_i = \{ \emptyset \}$
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Leképzás $j$-edik projekciója}]
Ha $J \subseteq I$, akkor az $x \rightarrow x|_J$ leképzést $x_{i \in I}X_i$-nek $x_{j \in J}X_j$-be való projekciójának nevezzük.\\
Ha $J = \{ j \}$, akkor ez az $x \rightarrow x_j$ leképzéssel azonosítható és $j$-edik projekciónak nevezzük.
\end{tcolorbox}
\end{frame}

\begin{frame}

\begin{tcolorbox}[title={Def.: $n$-változós művelet}]
$f : A^n \rightarrow A$-n értelmezett \textBF{$n$-változós (n-ér) művelet.}\\
Jel: $f(a_1, a_2, ..., a_n)$
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Műveleti tábla, Operandus}]
----------------------------------\\
|      +      |      $a_1$       |      $a_2$       | ... |      $a_n$      |\\
|    $a_1$    | $a_1$ + $a_1$ ....\\
...\\
| $a_n$ | ...\\
---------------------------------\\
\mmedskip

+: Binér művelet\\
Felül jobb oldali operandusok.\\
Bal oldalon bal oldali operandusok.
\end{tcolorbox}
\end{frame}

% ---------------------- ALGEBRAI STRUKTÚRÁK, SZÁMHALMAZOK ---------------------

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Algebrai struktúrák, Számhalmazok}
    \mmedskip
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.:Algebrai struktúrák, izomorfiájuk}]
%\begin{tcolorbox}[title={Def.: Művelet, Eredmény, Operandus, Algebrai Struktúra, Tartóhalmaz (Alaphalmaz)}]
Ha $A$ tetszőleges halmaz, akkor egy\\
\textBF{A-n értelmezett $n$-ér műveleten ($n$-változós)} egy\\
$f : (A^n =) A x A ... x \rightarrow A$ és $n \in \mathbb{N}_0$.\\
\msmallskip

Ha $x_1, x_2, ..., x_n\in A$, akkor\\
$f(x_1, x_2, ..., x_n)$ a művelet \textBF{eredménye}, míg $x_1, x_2, ..., x_n$ a művelet \textBF{operandusai}.\\
\msmallskip

Az $(A, {\Omega})$ pár \textBF{algebrai struktúra}, ha az $A$ nem üres halmaz, és $\Omega$ az $A$-n értelmezett véges változós műveletek halmaza.\\
\msmallskip

Szokásos jelölés, ha $\Omega$ $1$ vagy $2$ elemű: $(A, {\oplus})$, ill $(A, {\oplus}, {\otimes})$,\\
ahol $\otimes$, $\oplus$, $A$-n értelmezett $n$-ér műveletek.\\
\msmallskip

$A$-t \textBF{tartóhalmaznak (alaphalmaz)} hívjuk.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Műveleti zártság}]
Ha $\otimes$ egy $A$-n értelmezett $n$-ér művelet, akkor mondjuk, hogy \textBF{${\otimes}$ zárt $A$-n ($A$ zárt a ${\otimes}$ műveletre nézve)}, azaz ${\forall}x_1, x_2, ..., x_n \in A$ esetén $x_1 \otimes x_2 \otimes ... \otimes x_n \in A$
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Grupoid}]
    Egy $(G, {\cdot})$ algebrai struktúrát, amelyben $\cdot$ binér művelet, \textBF{grupoidnak} nevezzük.
  \tcblower
    Egy $(G, {\cdot})$ grupoidban a művelet:\\

    \begin{itemize}
      \item \textBF{Asszociatívnak} nevezzük, ha minden $a, b, c \in G$ esetén $a(bc) = (ab)c$
      \item \textBF{Kommutatívnak} nevezzük, ha minden $a, b \in G$ esetén $ab = ba$
      \item \textBF{Regulárisnak} nevezzük, ha minden $a, b, c \in G$ esetén $ac = bc$-ből következik, hogy $a = b$, valamint $ca = cb$-ből is következik, hogy $a = b$
    \end{itemize}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Morfizmusok}]
    Legyen $(G, {\cdot})$ és $(G', {\otimes})$ két grupoid. A ${\phi} : G \rightarrow G'$ függvényt \textBF{homomorfizmusnak} nevezzük, ha \textBF{művelettartó}, vagyis ${\forall}a_1, a_2 \in G : {\phi}(a_1a_2) = {\phi}(a_1) \otimes {\phi}(a_2)$\\

    \textBF{Izomorfizmus}: bijektív homomorfizmus.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Félcsoport}]
    A $(G, {\cdot})$ grupoid \textBF{félcsoport}, ha $\cdot$ asszociatív.
  \tcblower
    \textBF{Baloldali, Jobboldali egységelem, Egységelem}:\\
    \mmedskip
    
    A $(G, {\cdot})$  félcsoportban:\\
    \begin{itemize}
      \item $e_b \in G$ \textBF{bal oldali egységelem}, ha minden $a \in G$ esetén $e_ba = a$
      \item $e_j \in G$ \textBF{jobb olodali egységelem}, ha minden $a \in G$ esetén $ae_j = a$
      \item $e \in G$ \textBF{egységelem}, ha egyszerre bal és jobb oldali egységelem.
    \end{itemize}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Balinverz, Jobbinverz, Inverz (Félcsoport)}]
    Legyen $(G, {\cdot})$ félcsoportban $e$ egységelem. Ekkor az $a \in G$ elemnek:\\
    \msmallskip
    
    \begin{itemize}
      \item $a_b \in G$ \textBF{balinverze}, ha $a_ba = e$.
      \item $a_j \in G$ \textBF{jobbinverze}, ha $aa_j = e$.
      \item $a' \in G$ \textBF{inverze}, ha $aa' / a'a = e$.
    \end{itemize}
    \mmedskip
    
    Legyen $(G, {\cdot})$ félcsoportban $e_b$ bal oldali egységelem. Az $a \in G$ elemnek \\
    \msmallskip
    
    $a_b \in G$ az \textBF{$e_b$-re vonatkoztatott balinverze}, ha $a_ba = e_b$\\
    illetve az \textBF{$e_b$-re vonatkoztatott jobbinverze}, ha $aa_b = e_b$\\
    \mmedskip
    
    A bal-é s jobbinverz fogalma jobboldali egységelemre hasonlóan.
  \end{tcolorbox}
\end{frame}


\begin{frame}
  \begin{tcolorbox}[title={Tétel: Egységelem és inverz félcsoportban}]
    Félcsoportban legfeljebb egy egységelem létezik (egyszerre jobb és bal), és minden elemnek legfeljebb egy, az egységelemre vonatkozó inverze létezik.
  \tcblower
    Legyen $(G, {\cdot})$ félcsoport, $e_b$ bal oldali, $e_j$ pedig jobb oldali egységelem $G$-ben.\\
    \msmallskip
    
    Ekkor $e_b = e_j$, hiszen:\\
    \msmallskip
    
    $e_be_j = e_j$ és $e_be_j = e_b$, (nyíl éshez $\rightarrow$ a függvény egyértelmű!)\\
    mert $e_b$ bal, $e_j$ jobb oldali egységelem.\\
    \msmallskip
    
    Ha az $a \in G$ elemnek $a_b$ balinverze, $a_j$ pedig jobbinverze, akkor $a_b = a_j$.\\
    \msmallskip
    
    $a_baa_j = a_b(aa_j) = a_be = a_b$ és $a_baa_j = (a_ba)a_j = ea_j = a_j$. (Asszociatív tulajdonság) (nyíl éshez ide is $\rightarrow$ a függvény egyértelmű!).
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Csoport, Abel-csoport}]
    A $(H, {\cdot})$ félcsoport \textBF{csoport}, ha:
    \begin{enumerate}
      \item Létezik benne $e$ egységelem
      \item Minden $a \in H$ elemnek létezik erre az egységelemre vonatkozó $a^{-1}$ inverze:\\
      \msmallskip
      
      $a^{-1}a = aa^{-1} = e$
    \end{enumerate}
    \mmedskip

    \textBF{Abel-csoportnak} nevezzük a kommutatív csoportokat.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: $n$ tényezős szorzat / Hatványozás egész kitevővel}]
    Ha $G$ csoport, $g \in G, n \in \mathbb{N}^+$, akkor legyen:\\
    \msmallskip
    
    $n \mapsto g^n$, ahol $g^{-n} = (g^{-1})^n$ érvényesek $g, h \in G$ és $m, n \in \mathbb{Z}$-re.\\
    \msmallskip

    $g^{n + m} = g^m \cdot g^n$ és $(g^m)^n = g^{m \cdot n}$\\
    ha $g, h$ felcserélhető, akkor $(g \cdot h)^m = g^m \cdot h^m$\\
    \msmallskip

    Additív írásmód esetén:\\
    $(m + n)g = mg + ng, m(ng) = (mn)g$ és $n(g + h) = ng + nh$
  \end{tcolorbox}
\end{frame}


\begin{frame}
  \begin{tcolorbox}[title={Def.: Gyűrűk}]
    Az $(R, +, {\cdot})$ algebrai struktúra \textBF{gyűrű}, ha $+$ és $\cdot$ $R$-ben binér műveletek, valamint:\\
    \begin{enumerate}
      \item $(R, +)$ Abel-csoport.
      \item $(R, {\cdot})$ félcsoport
      \item Teljesül mindkét oldalról a disztributivitás, vagyis:\\
      \msmallskip
      
      $a(b + c) = ab + ac$\\
      $(b+ c)a = ba + ca$,\\
      minden $a, b, c \in R$ esetén.
    \end{enumerate}
    \mbigskip

    \textBF{Kommutatív} a gyűrű, ha a szorzás kommutatív.\\
    \mmedskip

    \textBF{Nullelem}: Az additív csoport egységeleme a gyűrű \textBF{nulleleme}, jelben 0.\\
    \mmedskip

    \textBF{Egységelemes} a gyűrű, ha a szorzásra vonatkozóan van egységelem (amit $e$-vel, vagy $1$-gyel jelölünk.)\\
    \mmedskip

    \textBF{Nullgyűrű}: egyetlen elemből áll.\\
    \mmedskip

    \textBF{Zérógyűrű}: ha tetszőleges két elem szorzata a nullelem.\\
    \mmedskip

    \textBF{Nullosztó}: Az $R$ gyűrűben \textBF{$a$ bal oldali, $b$ jobb oldali nullosztó}, ha $a \neq 0$, $b \neq 0$, és $ab = 0$\\
    \mmedskip

    \textBF{Integritási tartomány}: A (legalább két elemű), kommutatív, nullosztómentes gyűrűt \textBF{integritási tartománynak} nevezzük.\\
    \mmedskip

    \textBF{Osztó}: Legyen $R$ integritási tartomány és $a, b \in R$. $a$ \textBF{osztója} $b$-nek ha létezik $c \in R$, amelyre $b = ac$, jelben $a | b$.\\
    \mmedskip

    \textBF{Egység}: $x \in R$ \textBF{egység}, ha $x | r$ minden $r \in R$-re.\\
    \mmedskip

    \textBF{Test}: Az $R$ gyűrű \textBF{test}, ha $(R^*, {\cdot})$ Abel csoport.\\
    \msmallskip
    
    {\footnotesize $R^* =$ R struktúra, additív egységelem nélkül. (0)}
  \end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Algebrai struktúrák kpacsolata (Kép)}]
% Yes this is bad, but too tired atm to mess with tables
-------------------------------------------------------------------------\\
|-----------------------|----------Gyűrű--------|-----------------------|\\
|-----------------------/-|-----------|-----------|--{\textbackslash}----------------------|\\
|--Nullosztómentes--|-----Kommutatív----|----Egységelemes-----|\\
|-----------------------|-----------|$\rightarrow$-----------|-----------|-----------|\\
|-----------------------|-Integritási Tartomány-|-------|--------------|\\
|-----------------------|------------{\textbackslash}----------|-------------|-------------|\\
|-----------------------|-----------------------|------------EIT---------|\\
|-----------------------|-----------------------|-------Gauss-gyűrű------|\\
|-----------------------|-----------------------|-------Főideál-gyűrű------|\\
|----Ferdetest-------|-----------------------|-----Euklideszi gyűrű-----|\\
|-----------I$\rightarrow$--------|-----------------------|----------Test------------|\\
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Lemma: Észrevételek gyűrűkben}]
    \begin{enumerate}
      \item \textBF{Szorzás nullelemmel:} Legyen 0 az R gyűrű nulleleme. Ekkor $a0 = 0a = 0$, minden $a \in R$ esetén.
      \item \textBF{Előjelszabály:} Legyen R gyűrű, és $a, b \in R$. Az $a$ elem additív inverzét jelöljük $-a$-val. Ekkor $-(ab) = (-a)b = a(-b)$, továbbá $(-a)(-b) = ab$.
      \item \textBF{Véges integritási tartomány test.}
      \item \textBF{Testben nincs nullosztó.}
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Lemma: Nullosztó és regularitás}]
    R gyűrűben a multiplikatív művelet \textBF{akkor, és csak akkor} reguláris, ha R zérusosztómentes.
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    \textBF{1. Rész}\\
    \msmallskip
    
    Tfh $a \neq 0$, a nem bal oldali nullosztó és $ab = ac$.\\
    \msmallskip
    
    $ab = ac$  $/ -(ac)$ (+ additív inverz)\\
    $ab + (-(ac)) = 0$. Előjel szabály + disztri.\\
    $ab + (a(-c)) = a(b+(-c)) = 0$ (Kiemeljük, csak akkor lehet, ha $(b + -1 = 0) \implies (b = c)$)\\
    \msmallskip
    
    A feltételből ($a$ nem baloldali nullosztó) következik, hogy $b + (-c) = 0)$ $\implies$\\
    $\implies$ b = c.\\
    \bigskip

    \textBF{2. Rész}\\
    \msmallskip
    
    Tfh $a$ bal oldali nullosztó, tehát $a \neq 0$ és létezik $b \neq 0\: ab = 0$.\\
    \msmallskip
    
    tetszőleges $c \in R$-re: $ac = ac$.\\
    $ac = ac$  $/ +0 (0 = ab)$\\
    $ac = ac + ab$ /(Disztributivitás)\\
    $ac = a(c + b)$ $\rightarrow$ Ellentmondás!\\
    \msmallskip
    
    Mivel $(b \neq 0) \implies (c \neq (c + b))$ (A b nem additív egységelem).
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Rendezett Integritási Tartomány}]
    $(R, +, {\cdot})$ integritási tartomány \textBF{rendezett integritási tartomány}, ha $R$ rendezett halmaz és\\
    \begin{enumerate}
      \item Ha $x, y \in R$ és $x \leq y$, akkor $x + z \leq y + z$ (Az összeadás monoton)
      \item Ha $x, y \in R$ és $x, y \geq 0$, akkor $x \cdot y \geq 0$ (A szorzás monoton)
    \end{enumerate}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Felbonthatatlan, Prím}]
    Legyen $R$ egységelemes integritási tartomány, $U(R)$ az $R$-beli egységek halmaza, ekkor:\\
    \begin{enumerate}
      \item $a \in R^* \setminus U(R)$ \textBF{felbonthatatlan}, ha $a = b \cdot c (b, c \in R)$ esetén $b \in U(R)$, vagy $c \in U(R)$
      \item $a \in R^* \setminus U(R)$ \textBF{prím}, ha $a | b \cdot c$ $(b, c \in R) \Rightarrow a|b$ vagy $a|c$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}


% ---------------------- SZÁMHALMAZOK ---------------------

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Számhalmazok}
    \mmedskip
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}
    $\mathbb{N} \rightarrow \mathbb{Z} \rightarrow \mathbb{Q} \rightarrow \mathbb{A} \rightarrow \mathbb{R} \rightarrow \mathbb{C}$\\
    \msmallskip
    
    $\mathbb{Q}$, és "felfele" $\rightarrow$ test.
    \mmedskip
    
    $\mathbb{N}$: Nem gyűrű.\\
    $\mathbb{Z}$ Gyűrű\\
  \end{tcolorbox}
\end{frame}


\begin{frame}
  \begin{tcolorbox}
    {\RHuge Természetes számok}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Peano-axiómák}]
      Halmaz, egy nullér(1) és egy injektív unér(4) művelettel (rákövetkezés (2)).\\
      \mmedskip
      
      \begin{enumerate}
        \item $0 \in \mathbb{N}$.
        \item Ha $n \in \mathbb{N}$, akkor $n^+ \in \mathbb{N}$.
        \item Ha $n \in \mathbb{N}$, akkor $n^+ \neq 0$. (Nincs benne -1 $\rightarrow$ $-1 + 1 = 0$).
        \item Ha $n, m \in \mathbb{N}$ és $n^+ = m^+$, akkor $n = m$
        \item Ha $S \subset \mathbb{N}, 0 \in S$ és ha $n \in S$, akkor $n^+ \in S$, akkor $S = \mathbb{N}$. (Teljes indukvió elve).
      \end{enumerate}
  \end{tcolorbox}

  %\begin{tcolorbox}[title={Ész}]
  %\end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Természetes számok halmaza}]
    Az a lényegében egyértelműen létező halmaz, amely eleget tesz a Peano-axiómáknak, a \textBF{természetes számok halmaza}.\\
    Jel: $\mathbb{N}$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Összeadás}]
    ${\forall}m \in \mathbb{N} : {\exists} s_m : \mathbb{N} \rightarrow \mathbb{N}$ függvény, amelyre\\
    \mmedskip

    $s_m(0) = m \land {\forall}n \in \mathbb{N} : s_m(n^+) = (s_m(n))^+$,\\
    $s_m(n)$ $m$ én $n$ szám \textBF{összege}.\\
    Jelölés: $m + n$
  \tcblower
    \textBF{Észrevételek}:\\
    \mmedskip
  
    $m^+ = (S_m(0))^+ = s_m(0^+) = S_m(1) = m + 1$\\
    $m = (S_m(0)) = m + 0$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Szorzás}]
    ${\forall}m \in \mathbb{N} : {\exists} p_m : \mathbb{N} \rightarrow \mathbb{N}$ függvény, amelyre\\
    \mmedskip

    $p_m(0) = 0 \land {\forall}n\in \mathbb{N} : p_m(n^+) = p_m(n) + m$,\\
    $p_m(n)$ $m$ és $n$ szám \textBF{szorzata}.\\
    Jelölés: $m \cdot n$ vagy $mn$
  \tcblower
    \textBF{Észrevételek}:\\
    \mmedskip
    
    $1 \cdot 1 = p_1(1) = p_1(0^+) = p_1(0) + 1 = 0 + 1 = 1$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Természetes számok}]
    A $(N, +, {\cdot})$ struktúrában mindkét művelet \textBF{asszociatív, kommutatív, reguláris}.\\
    \msmallskip
    
    Nullelem (additív egységelem): 0.\\
    Multiplikatív egységelem: 1.\\
    A szorzat mindkét oldalról disztributív az összeadásra.\\
    ${\forall}m \in N : 0 \cdot m = m \cdot 0 = 0$.
  \end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: $\mathbb{N}$ rendezése}]
  $n \leq m \iff {\exists}k \in \mathbb{N}: n + k = m$.
\end{tcolorbox}

\begin{tcolorbox}[title={Tétel: N rendezése}]
A természetes számok halmaza a $\leq$ relációval jólrendezett.\\
{\footnotesize Tetszőleges részbenrendezett halmaz jólrendezett, ha bármely nemüres részhalmazának van legkisebb eleme. Jólrendezett $\Rightarrow$ Rendezett}
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Végtelen sorozatok}]
  $\mathbb{N}^+$-on értelmezett függvények.
\end{tcolorbox}

%\begin{tcolorbox}[title={Def.: Fibonacci számok}]
%\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
  A $(\mathbb{N}, +, {\cdot})$ struktúra nem gyűrű, mert $(\mathbb{N}, +)$ nem Abel-csoport.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Egész számok}]
  $\mathbb{Z} = -\mathbb{N} \cup \mathbb{N}$
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
  A $(Z, +, {\cdot})$ struktúra egységelemes integritási tartomány.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Racionális számok}]
  $\mathbb{Q} = \{\frac{m}{n} | m,n \in \mathbb{Z}, n \neq 0 \}$.
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
  A $(Q, +, {\cdot})$ struktúra test.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}
{\RHuge Valós Számok}
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Rendezett test}]
  Egy struktúra \textBF{rendezett test}, ha test és rendezett integritási tartomány.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Arkhimédészi tulajdonság}]
  Egy $(T; +, {\cdot}; {\leq})$ rendezett test \textBF{arkhimédeszi tulajdonságú}, ha\\
  ${\forall}x, y \in T : x > 0$ esetén ${\exists}n \in \mathbb{N} : nx \geq y$\\
  \msmallskip

  Ekkor T \textBF{arkhimédeszien rendezett}.
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Felső határ tulajdonság}]
  Egy $(T; +, {\cdot}; {\leq})$ rendezett test \textBF{felső határ tulajdonságú}, ha minden nem üres felülről korlátos részhalmazának létezik $T$-ben felső határa (legkisebb felső korlátja $\rightarrow$ Supremum).
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Felső határ és arkhimédészi tulajdonság}]
    $T$ felső határ tulajdonságú test $\implies$ $T$ arkhimédészi tulajdonságú.
  \tcblower
    \textBF{Bizonyítás (Indirekt)}\\
    \mmedskip
    
    Tfh (indirekte) $T$ felső határ tulajdonságú rendezett test, de nem arkhimédészi tulajdonságú.\\
    \msmallskip
    
    $\Rightarrow {\exists}y : {\nexists}n \in \mathbb{N} : nx \geq y$.\\
    Azaz y felső korlátja az $A = \{ nx | n \in \mathbb{N} \}$ halmaznak.\\
    \msmallskip

    Ekkor viszont létezik $z = sup A$ $\Rightarrow$ $z - x < z$ ($z - x$ nem feltétlenül arkhimédeszi tulajdonságú) nem felső korlát. $\Rightarrow$\\
    $\Rightarrow$ ${\exists}n : nx > z - x \Rightarrow (n + 1)x > z$. ($(n + 1) \in A$).\\
    \msmallskip
    
    Ellentmondás, mivel ha $n \in \mathbb{N}$, akkor $n^+ \in \mathbb{N}$ $\rightarrow$ Peano axióma!
  \end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Tétel: Q nem felső határ tulajdonságú}]
$\mathbb{Q}$ arkhimédészi tulajdonságú, de nem felső határ tulajdonságú.
\end{tcolorbox}
\end{frame}


\begin{frame}
  \begin{tcolorbox}[title={Tétel: $\sqrt{2}$ nem racionális}]
    Nincs $\mathbb{Q}$-ban olyan szám, amelynek négyzete 2.
  \tcblower
    \textBF{Bizonyítás (Indirekt)}\\
    \mmedskip
    
    Tfh (indirekte) van, és ez $x$.\\
    \msmallskip
    
    $x = \frac{m}{n}, m,n \in \mathbb{N}^+$, és az $m$ minimális.\\
    \msmallskip
    
    $2 = x^2 = \frac{m^2}{n^2} \implies m^2 = 2n^2$\\
    \msmallskip
    
    Ebből következik, hogy $m$ páros. $\implies$ $m = 2k, k \in \mathbb{N}^+$\\
    \msmallskip
    
    $m^2 = 2n^2 \Rightarrow (2k)^2 = 2n^2 \Rightarrow 2k^2 = n^2$\\
    \msmallskip
    
    Ebből következik, hogy $n$ is páros: $n = 2j, j \in \mathbb{N}^+$\\
    \msmallskip
    
    Ekkor viszont $\frac{m}{n} = \frac{2k}{2j} = \frac{k}{j}$.\\
    \msmallskip
    
    Viszont ebből következik, hogy m nem minimális $\rightarrow$ Ellentmondás!
  \end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Valós számok halmaza}]
  A lényegében egyetlen, felső határ tulajdonsággal rendelkező testet a \textBF{valós számok halmazának} nevezzük.\\
  Jel.: $\mathbb{R}$
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: néhány Függvény (?)}]
  \textBF{Abszolút érték}: |x| = $x$, ha $x \geq 0$ | $-x$, ha $x < 0$.\\
  \msmallskip
  
  \textBF{Előjel}: sgn(x) = $0$, ha $x = 0$ | $x / |x|$, különben.\\
  \msmallskip
  
  \textBF{Alsó egész rész}: ${\lfloor}x{\rfloor} = \mathbb{Z}$ legnagyobb eleme, amely nem nagyobb, mint $x$\\
  \msmallskip
  
  \textBF{Felső egész rész}: ${\lceil}x{\rceil} = \mathbb{Z}$ legkisebb eleme, amely nem kisebb, mint $x$\\
  \mbigskip

  \textBF{Észrevételek:}\\
  \msmallskip

  $x = 0 \Rightarrow {\lceil}x{\rceil} = {\lfloor}x{\rfloor} = 0$,\\
  \msmallskip
  
  Ha $x > 0$: arkhi. tul. ból és $\mathbb{N}$ jólrendezettségéből $\Rightarrow$ ${\exists}n \in \mathbb{N}^+$, ahol $n$ a legkisebb olyan természetes szám, amely $n \geq x \Rightarrow n = {\lceil}x{\rceil}$, ekkor ha $x = n \in \mathbb{N}^+ \Rightarrow$ ${\lfloor}x{\rfloor} = n$, különben ${\lfloor}x{\rfloor} = n - 1$.\\
  \mmedskip

  ha $x < 0 \Rightarrow {\lceil}x{\rceil} = -{\lfloor}-x{\rfloor} = n$, különben ${\lfloor}x{\rfloor} = -{\lceil}-x{\rceil}$.
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}[title={Def.: Bővített valós számok (?)}]
  $\overline{\mathbb{R}} = \mathbb{R} \cup \{ -{\infty}, {\infty}\}$\\
  \mbigskip

  Rendezés kiterjesztése:\\
  \mmedskip
  
  $-{\infty} < x < +{\infty}$ teljesüljön minden $x$ valósra.\\
  \msmallskip
  
  Bármely részhalmaznak van szuprémuma, és infinuma:\\
  \msmallskip
  
  $sup{\emptyset} = -{\infty}, inf{\emptyset} = +{\infty}$\\
  \mmedskip

  Összeadás $x$ valósra (nem mindenütt értelmezett):\\
  \msmallskip
  
  $x + (-{\infty}) = (-{\infty}) + x = -{\infty}$, ha $x < +{\infty}$, és $x + (+{\infty}) = (+{\infty}) + x = +{\infty}$, ha $x < -{\infty}$\\
  \mmedskip

  Ellentett képzés: $-(+{\infty}) = -{\infty}$, és $-(-{\infty}) = +{\infty}$.
\end{tcolorbox}
\end{frame}


\begin{frame}
\begin{tcolorbox}
{\RHuge Komplex Számok}
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Komplex számok}]
  \textBF{Komplex számoknak} nevezzük a valós számpárok\\
  $\mathbb{C} = \mathbb{R} x \mathbb{R}$\\
  halmazát a következő műveletekkel:\\
  \msmallskip

  $a, b, c, d \in \mathbb{R}$:\\
  \begin{itemize}
    \item $(a, b) + (c, d) = (a + c, b + d)$\\
    \item $(a, b) \cdot (c, d) = (ac - bd, ad + bc)$
  \end{itemize}
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
  $(\mathbb{C}, +, {\cdot})$ test.\\
  \mmedskip

  $(\mathbb{C}, +)$ Abel-csoport:\\
  \begin{itemize}
    \item Egységelem: $(0, 0)$
    \item (a, b) additív inverze: $-(a, b) = (-a, -b)$
  \end{itemize}
  \mmedskip

  $(\mathbb{C}, {\cdot})$: Abel-csoport:\\
  \begin{itemize}
    \item Egységelem: $(1, 0)$
    \item (a, b) multiplikatív inverze: $(a, b)^{-1} = (\frac{a}{a^2 + b^2}, \frac{-b}{a^2 + b^2})$
  \end{itemize}
  \mmedskip

  Kétoldali disztributivitás teljesül.
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Alakok}]
$Re(z) = {\Re}(z)$, $Im(z) = {\Im}(z)$\\
\mmedskip

\textBF{Algebrai}: $z = x + yi$\\
(Imaginárius egység: $i = (0, 1)$, ahol $i^2 = -1$)\\
\mmedskip

\textBF{Trigonometrikus}: $z = r({\cos}(t) + i{\sin}(t))$\\
r: Abszolút érték / hossz: $|(x, y)| = \sqrt{x^2 + y^2}$\\
\mmedskip

\textBF{Euler-féle}: $z = re^{i{\phi}}$\\
\mmedskip

\textBF{Konjugált}: Ha $x = x + iy$, akkor $\overline{x} = x - iy$\\
(Tükrözés a valós tengelyre)\\
\mmedskip

A komplex számok halmaza \textBF{nem rendezhető}, mert rendezett integritási tartományban negatív szám négyzete pozitív kell hogy legyen!
\end{tcolorbox}

\begin{tcolorbox}[title={Ész}]
\begin{enumerate}
\item $\overline{\overline{z}} = z$
\item $\overline{(z + n)} = \overline{z} + \overline{n}$
\item $\overline{(z \cdot n)} = \overline{z} \cdot \overline{n}$
\item $z + \overline{z} = 2Re(z)$
\item $z - \overline{z} = 2iIm(z)$
\item $z \cdot \overline{z} = |z|^2$
\item $z \neq 0, z^{-1} = \frac{\overline{z}}{|z|^2}$
\item $|0| = 0, z \neq 0 : |z| > 0$
\item $|z| = |\overline{z}|$
\item $|zw| = |z| \cdot |w|$
\item $|Re(z)| \leq |z|, |Im(z)| \leq |z|$
\item $|z + w| \leq |z| + |w|, ||z| - |w|| \leq |z - w|$
\end{enumerate}
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: Moivre azonosságok}]
Legyen $z, w \in \mathbb{C}, z = |z|({\cos}(t) + i{\sin}(t))$ és $w = |w|({\cos}s + i {\sin}s)$, ahol $t, s \in \mathbb{R}$. Ekkor $zw$ trigonometrikus alakja\\
\mbigskip

\textBF{Szorzás}:\\
$zw = |z| \cdot ({\cos}t + i{\sin}t) \cdot |w| \cdot ({\cos}s + i{\sin}s) =$\\
$|z| \cdot |w| \cdot ({\cos}t + i{\sin}t) \cdot ({\cos}s + i{\sin}s) =$\\
$= |zw| \cdot ({\cos}t{\cos}s - {\sin}t{\sin}s + i({\cos}t{\sin}s + {\cos}s{\sin}t)) =$\\
$= |zw|({\cos}(t + s) + i{\sin}(t + s)$\\
\mbigskip

\textBF{Osztás}:\\
$w \neq 0$ esetén:\\
$\frac{z}{w} = \frac{|z|}{|w|}({\cos}(t - s) + i {\sin}(t - s))$\\
\mbigskip

\textBF{Hatványozás}:\\
$n \in \mathbb{Z}$ és $z \neq 0$:\\
$z^n = |z|^n({\cos}(nt) + i{\sin}(nt))$
\end{tcolorbox}

\begin{tcolorbox}[title={Def.: Gyökvonás komplex számokból}]
$n^n = w, z = ?$\\
$w = 0 \Rightarrow z = 0$, különben ha $t = arg(w)$\\
\msmallskip

$z_k = \sqrt[n]{|w|}({\cos}(\frac{t + 2k{\pi}}{n}) + i{\sin}(\frac{t + 2k{\pi}}{n}))$\\
$k = 0, 1, ..., n - 1$\\
\mbigskip

\textBF{$n$-edik egységgyökök} ${\epsilon}^n = 1$ esetén:\\
${\epsilon}_k = {\cos}(\frac{2k{\pi}}{n}) + i{\sin}(\frac{2k{\pi}}{n})$. $k = 0, 1, ..., n - 1$
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Def.: $n$-edik primitív egységgyökök}]
Az $n$-edik primitív egységgyökök: Hatványaikkal előállítják a többit.\\
\mmedskip

Pl.: ${\epsilon}_0$ biztos nem az, ${\epsilon}_1$ biztosan az.\\
\mmedskip

$z^n = w$ esetén $z_k$-k előállnak a következő alakban:\\
$z{\epsilon}_0, z{\epsilon}_1, ..., z{\epsilon}_{n - 1}$\\
\mmedskip

$\Rightarrow$ $n > 1$ esetén:\\
\mmedskip

$$\sum_{k = 0}^{n - 1} z{\epsilon}_k = \sum_{k = 0}^{n - 1} z{\epsilon}^k_1 = z\frac{{\epsilon}_1^n - 1}{{\epsilon}_1 - 1} = z\frac{1 - 1}{{\epsilon}_1 - 1} = 0$$\\
(Mértani sorozat összegképlete)
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Tétel: Az algebra alaptétele}]
Ha $n \in \mathbb{N}^+$, valamint $c_0, c_1, ... c_n$ komplex számok, $c_n \neq 0$, akkor van olyan $n$ komplex szám, amelyre:\\
$$\sum_{k = 0}^n c_kz^k = 0$$
\end{tcolorbox}
\end{frame}

\begin{frame}[plain]
\begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
    {\RHuge Számelmélet}
    \mmedskip
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Oszthatóság egységelemes integritási tarományban (Emlékeztető)}]
    Legyen $R$ integrritási tartomány és $a, b \in R$, $a$ \textBF{osztója} $b$-nek, ha létezik $c \in R$, amelyre $b = ac$, jelben $a | b$.\\
    \mmedskip

    $x \in R$ \textBF{egydég}, ha $x | r$ teljesül ${\forall}r \in R$-re. Az $R$-beli egységek halmaza $U(R)$.\\
    \mmedskip

    Azt mondjuk, hogy $a$ és $b$ \textBF{asszociáltak}, ha létezik olyan $c$ egység, amelyikkel $a = bc$. Ezt a tényt $a \sim b$-vel jelöljük.\\
    \mmedskip

    $a \in R^*{\setminus}U(R)$ \textBF{felbonthatatlan}, ha $a = b \cdot c, (b, c, \in R)$ esetén $b \in U(R)$ vagy $c \in U(R)$.\\
    \mmedskip

    $a \in R^*{\setminus}U(R)$ \textBF{prím}, ha $a | b \cdot c, (b, c, \in R) \Rightarrow a | b$ vagy $a | c$.\\
    \mmedskip

    Ha $a \in R^*{\setminus}U(R)$ : $a$ \textBF{triviális osztói} az egységek és önmaga egységszeresei, $a$ \textBF{összetett}, ha nem csak triviális osztója van.\\
    \mmedskip

    $R^*$: R, az additív egységeleme nélkül.\\
    $U(R)$: R egysége\\
    $R^*{\setminus}U(R)$: R, egységek, és additív ergységelem nélkül.
  \end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Tétel: Az oszthatóság tulajdonságai EIT-ban}]
\begin{enumerate}
\item Ha $b|a$ és $b'|a'$, akkor $bb'|aa'$.
\item A nullának minden elem osztója.
\item A nulla csak saját magának osztója.
\item Az 1 egységelem minden elemnek osztója.
\item Ha $b|a$, akkor $bc|ac$ minden $c \in R$-re.
\item Ha $bc|ac$ és $c \neq 0$, akkor $b|a$.
\item Ha $b|a_i$ és $c_i \in R, (i = 1, 2, ..., j)$, akkor $b|\sum^j_{i=1} c_ia_i$.\\
($z$ feletti lineáris kombináció)
\item Az $|$ reláció reflexív, és tranzitív.
\end{enumerate}
\end{tcolorbox}
\end{frame}

\begin{frame}
\begin{tcolorbox}[title={Tétel: Prím és irreducibilis elem EIT-ban}]
Tetszőleges $R$ egységelemes integritási tartományban minden $p$ elemre:\\
Ha $p$ prím $\implies$ $p$ felbonthatatlan.
\tcblower
\textBF{Bizonyítás}\\
\mmedskip

Tfh $p$ prím, és, $p = bc$\\
\msmallskip

Ekkor vagy $p|b$, vagy $p|c$ (Ez a prím definíció)\\
\msmallskip

$b = pq = b(cq) \implies cq = 1$ $\implies$ $c, q$ egység $p, b$ asszociáltak.
\end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Legnagyobb közös osztó}]
      Legyen $a_1, ..., a_n \in R$ (EIT), $L \subseteq R $ és ${\forall}d \in L$-re:\\
      \mmedskip

      $d|a_i$ $(i = 1, ..., n)$,\\
      \mmedskip

      $d' | a_i$ $(i = 1, ..., n)$ $\Rightarrow$ $d'|d$\\
      \mmedskip

      Ekkor $L$ elemei az $a_1, ..., a_n$ elemek \textBF{legnagyobb közös osztói}.\\
      \mmedskip

      Jelben: $lnko(a_1, ..., a_n) = (a_1, ..., a_n) = d$\\
      \mmedskip

      d csak az asszociáltság erejéig egyértemű $\Rightarrow$ kijelölünk egyet (megegyezés szerint alapból a pozitívat).
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Relatív prím, Páronként relatív prím}]
    $a_1, ..., a_n$ \textBF{relatív prímek}, ha $d$ egység.\\
    \mmedskip

    Erősebb: \textBF{Páronként relatív prímek}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Legkisebb közös többszörös}]
      Legyen $a_1, ..., a_n \in R$ (EIT), $T \subseteq R $ és ${\forall}t \in T$-re:\\
      \mmedskip

      $a_i|t$ $(i = 1, ..., n)$,\\
      \mmedskip

      $a_i|t'$ $(i = 1, ..., n)$ $\Rightarrow$ $t'|t$\\
      \mmedskip

      Ekkor $T$ elemei az $a_1, ..., a_n$ elemek \textBF{legkisebb közös többszörösei}.\\
      \mmedskip

      Jelben: $lkkt(a_1, ..., a_n) = [a_1, ..., a_n] = t$\\
      \mmedskip

      $t$ csak az asszociáltság erejéig egyértemű! $\Rightarrow$ Kijelölünk egyet!
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Maradékos osztás $\mathbb{Z}$-ben}]
    ${\exists}a, b({\neq}0) \in \mathbb{Z}$ számhoz egyértelműen létezik olyan $q, r \in \mathbb{Z}$, hogy\\
    $a = qb + r \land 0 \leq r < |b|$.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Euklideszi algoritmus}]
    1. Input $a, b \in \mathbb{N}$\\
    2. $a - b \cdot q + r$, $0 \leq r < |b|$\\
    3. $r ?= 0$, Ha nem, akkor legyen $a := b, b := r$, ugrás 2. ponthoz, ha igen, ugrás a 4.hez.\\
    4. $(a, b)$ az utolsó nem $0$ maradék.\\
    5. STOP
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Prím és irreducibilis elem $\mathbb{Z}$-ben}]
    Az egész számok körében $p$ prím $\iff$ $p$ felbonthatatlan.
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
  
    Már láttuk, hogy prím felbonthatatlan!\\
    \msmallskip
    
    Tfh p felbonthatatlan\\
    \msmallskip
    
    Legyen $p|bc$, ekkor vagy $p | b$-nek, ekkor kész vagyunk,\\
    \msmallskip
    
    vagy $p \nmid b$ ekkor $(p,b) = 1$.\\
    \msmallskip

    Mivel $1 = px + by$\\
    \msmallskip

    $c = pcx +bcx \implies 0 \pmod{p} \implies p | c$.\\
    \mmedskip
    
    (Észrevétel: $(a, b) = 1 \land a | bc \implies a | c$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: A számelmélet alaptétele}]
    Minden $m$ nemnulla, nemegység, egész szám sorrendre és asszociáltásgra való tekintet nélkül egyértelműen bontható fel felbonthatatlanok szorzatára.
  \tcblower
    \textBF{Bizonyítás (Pozitívakra)}
    \mmedskip
    
    \textBF{(egzisztencia)}\\
    Tfh $n > 1$\\
    \msmallskip
    
    Teljes indukció: $n = 2$ kész, tfk $n - 1$-ig kész.\\
    \msmallskip

    Ha $n$ felbonthatatlan $\rightarrow$ kész.\\
    \msmallskip
    
    Ha $n$ nem felbonthatatlan $\rightarrow$ $n = ab \land a, b$ (a, b nem egység!), $a, b < n$ $\implies$ igaz rájuk az ind. feltétel.\\
    \msmallskip
    
    $n$ felbontása $=$ $a$ felbontása szor $b$ felbontása.\\
    \bigskip

    \textBF{(unicitás) (Indirekt)}\\
    \msmallskip
    
    Tfh $n$ a legkisebb olyan szám, amely felbontása nem egyértelmű.\\
    \msmallskip
    
    $n = p_1 ... p_k = q_1 ... q_r$ $\Rightarrow$\\
    $p_1|n \Rightarrow p_1|q_1 ... q_r$\\
    $p_1|q_1$, és $p_1|q_2 ... q_r$\\
               \hspace{1em}$p_1|q_2$, és $ p_1|q_3 ... q_r$\\
                          \hspace{2em}$p_1|q_i$  $\Rightarrow p_1 = q_i \Rightarrow$\\
    $\implies$ $n_1 = \frac{n}{p_1} = p_2 ... p_k = q_1 ... q_{i-1}q_{i+1} ... q_r$\\
    \msmallskip
    
    $n_1 < n$ és van két lényegesen különböző felbontása!
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Eukleidész tétele}]
    Végetlen sok prímszám van.
  \tcblower
    \textBF{Bizonyítás (Indirekt)}
    \mmedskip
    
    Tfh véges sok van:\\
    \msmallskip
    
    $p_1, p_2, ... ,p_k$.\\
    Legyen $n = p_1p_2...p_k$.\\
    \msmallskip
    
    Számelmélet alaptételéből következik hogy létezik $p_j : p_j | n + 1$\\
    ($n$ az összes prímszám szorzata + 1 $\rightarrow$ biztosan nem osztható a benne levő prímszámokkal, de másikkal igen/lehet hogy nem osztható (prím))\\
    \msmallskip
    
    $p_j : p_j | n + 1 \implies p_j | 1$ Ellentmondás!
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Kanonikus alak, Módosított kanonikus alak}]
    Egy $n > 1$ egész\\
    \mmedskip

    $n = p_1^{{\alpha_1}}p_2^{{\alpha_2}}...p_k^{{\alpha_k}}$\\
    \mmedskip

    alakú felírását, ahol $p_i$-k különböző (pozitív) prímek és ${\alpha}_i > 0$, $n$ \textBF{kanonikus alakjának} nevezzük.\\
    \mmedskip

    \textBF{Módosított kanonikus alak}, ha ${\alpha}_i = 0$ is megengedett.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Ész}]
    $n$ osztói: $n = p_1^{{\alpha_1}}p_2^{{\alpha_2}}...p_k^{{\alpha_k}}$\\
    \mmedskip

    Módosított kanonikus alakú szám osztói: $d = p_1^{{\beta}_1}p_2^{{\beta}_2}...p_k^{{\beta}_k}$,\\
    \msmallskip
    
    ahol ${\beta}_i \in \mathbb{N}, 0 \leq {\beta}_i \leq {\alpha}_i, i = 1, 2, ..., k$.\\
    \mmedskip

    Lnko, Lkkt:\\
    \mmedskip

    Legyen $a$ és $b$ módosított kanonikus alakja:\\
    \msmallskip
    
    $a = p_1^{{\alpha}_1}p_2^{{\alpha}_2}...p_r^{{\alpha}_r}$, $b = p_1^{{\beta}_1}p_2^{{\beta}_2}...p_r^{{\beta}_r}$\\
    \mmedskip

    ekkor:\\
    \msmallskip
    
    $(a, b) = p_1^{min({\alpha}_1, {\beta}_1)}...p_r^{min({\alpha}_r, {\beta}_r)}$\\
    $[a, b] = p_1^{max({\alpha}_1, {\beta}_1)}...p_r^{max({\alpha}_r, {\beta}_r)}$\\
    \mbigskip

    Következmények:\\
    Legyen $a, b, c \in \mathbb{Z}$, ekkor:\\
    \begin{enumerate}
      \item Ha $a$ is $b$ is relatív prím $c$-hez akkor $ab$ is.
      \item $a, b$-nek mindíg létezik legkisebb közös többszöröse és $[a, b](a, b) = |ab|$
      \item $[ac, bc] = c[a, b]$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Erathosztenész Szitája}]
    Prímkereső algoritmus.\\
    \mbigskip

    1 $\rightarrow$ Egység, nem prím.\\
    2 $\rightarrow$ Prím $\Rightarrow$ a többszörösei nem prímek.\\
    3 $\rightarrow$ Prím $\Rightarrow$ a többszörösei nem prímek.\\
    4 $\rightarrow$ 2 többszöröse, kiesett.\\
    ...
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Lineáris Kongruencia}]
    $a \equiv b \pmod{m}$, ha $m | a - b$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Kongruencia tulajdonságai}]
    \begin{enumerate}
      \item Ekvivalencia reláció
      \item $a \equiv b \pmod{m} \land c \equiv d \pmod{m} \implies$ \textBF{$a + c \equiv b + d \pmod{m}$}
      \item $a \equiv b \pmod{m} \land c \equiv d \pmod{m} \implies$ \textBF{$ac \equiv bd \pmod{m}$}
      \item $a \equiv b \pmod{m} \land f(x) \in \mathbb{Z}[x] \implies$ \textBF{$f(a) \equiv f(b) \pmod{m}$}
      \item Ha $(c, m) = d$, $ac \equiv bc \pmod{m} \iff a \equiv b \pmod{\frac{m}{d}}$
    \end{enumerate}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Ész}]
    $a \equiv b \pmod{m} \Rightarrow (a, m) = (b, m)$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: TMR, RMR}]
    $\overline{a}$ az $a$ elem által reprezentált \textBF{$m$ szerinti maradékosztály} az $a$-val kongruens elemek halmaza $\pmod{m}$.\\
    {\footnotesize (Van nullosztó), (Ekvivalencia reláció osztályok)}
    \mmedskip

    \textBF{Teljes maradékrendszer (TMR) modulo $m$} tartalmaz az összes $m$ szerinti maradékosztályból pontosan 1-et.\\
    \mmedskip

    $\overline{a}$ az $a$ elem által reprezentált \textBF{$m$ szerinti redukált maradékosztály}, ha $(a, m) = 1$.\\
    {\footnotesize (Biztosan test, mivel nincs nullosztó.}\\
    \mmedskip

    \textBF{Redukált maradékrendszer (RMR) modulo $m$} tartalmaz az összes $m$ szerinti redukált maradékosztályból pontosan 1-et.\\
  \tcblower
    1. Biztosan TMR-t alkotnak a következő számhalmazok mod $m$:\\
    \begin{enumerate}
      \item $0, 1, ..., |m| - 1$
      \item Ha $m$ páratlan: $0, {\pm}1, ..., {\pm}\frac{(|m| - 1)}{2}$
      \item Ha $m$ páros: $ , {\pm}1, ..., {\pm}(\frac{|m|}{2} - 1)$ (Vagy $\frac{|m|}{2}$, vagy -$\frac{|m|}{2}$
    \end{enumerate}
    \mmedskip

    2. Legyen $m \in \mathbb{N}$, és vagyünk egy TMR-t mod $m$.\\
    \msmallskip
    
    Definiáljunk műveleteket a következőképp:\\
    \mtinyskip
    
    $\overline{a} + \overline{b} = \overline{a + b}$\\
    $\overline{a} \cdot \overline{b} = \overline{a \cdot b}$\\
    \mtinyskip
    
    Jelöljük $Z_m$-mel ezt a struktúrát.\\
    \mtinyskip

    A $(Z, +, {\cdot})$ struktúra kommutatív, egységelemes gyűrű.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Az Euler-féle $\phi$ függvény}]
    Legyen $n \in \mathbb{N}^+$, ekkor ${\phi}(n)$ jelenti az $n$-nél nem nagyobb, hozzá relatív prímek számát, azaz:\\
    $${\phi}(n) = \sum_{\substack{1 \leq k \leq n \\ (k, n) = 1}} 1$$\\

    Másképp: ${\phi}(n)$ jelenti a modulo $n$ relatív maradékosztályok számát.
  \tcblower
    \textBF{Észrevétel}: Ha $n$ prím, akkor ${\phi}(n) = n - 1$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: A $\tau$ függvény}]
    Legyen $n \in \mathbb{N}^+$, ekkor ${\tau}(n)$ jelenti az $n$ pozitív osztóinak számát.
  \tcblower
    \textBF{Észrevétel}:\\
    \msmallskip


    $n = p_1^{{\alpha}_1}p_2^{{\alpha}_2}...p_k^{{\alpha}_k}$ módosított kanonikus alak.\\
    \msmallskip
    
    $n$ osztói: $d = p_1^{{\beta}_1}p_2^{{\beta}_2}...p_k^{{\beta}_k}$, ahol\\
    ${\beta}_i \in \mathbb{N}, 0 \leq {\beta}_i \leq {\alpha}_i, i = 1, 2, ..., k$ $\Rightarrow$\\
    $\Rightarrow$ ${\tau}(n) = ({\alpha}_1 + 1)...({\alpha}_k + 1)$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Omnibusz tétel}]
    Legyen: $m > 1$ egész,\\
    $\{a_1, ..., a_m\}$ TMR modulo $m$,\\
    $\{b_1, ..., b_{{\phi}(m)}\}$ RMR modulo $m$,\\
    $c, d \in \mathbb{Z}$, és $(c,m) = 1$.\\
    \smallskip

    Ekkor:\\
    \smallskip

    $\{ ca_1 + d, ..., ca_m + d \}$ TMR modulo $m$\\
    $\{ cb_1, ..., cb{{\phi}(m)}\}$ RMR modulo $m$
  \tcblower
    \textBF{Bizonyítás (Indirekt)}
    \mmedskip
    
    Tfh van két nem inkongruens elem\\
    \msmallskip
    
    $ca_i + d = ca_i + d$\\
    ${\cancel{c}}a_i + {\cancel{d}} = {\cancel{c}}a_i + {\cancel{d}}$ $(c, m) = 1$, és pontosan $m$ db elem!\\
    \msmallskip
    
    $(c, m) = 1$ és $(b_j,m) = 1$ $\implies$ $(cb_j, m) = 1$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Euler-Fermat tétel}]
    Legyen $m > 1$ egész és $a$ relatív prím $m$-hez. Ekkor $a^{{\phi}(m)} \equiv 1 \pmod{m}$
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    Legyen $\{ r_1, ..., r_{{\phi}(m)}\}$ RMR modulo $m$, $(a, m) = 1$ (A tételben feltétel).\\
    \msmallskip

    Az omnibusz tétel miatt, ekkor $\{ ar_1, ..., ar_{{\phi}(m)}\}$ is RMR modulo $m$.\\
    Megfelelő párosítás $\implies$ $r_i \equiv ar_j \pmod{m}$,  $(r_i, m) = 1$.\\
    \msmallskip
    
    Összeszorozva:\\
    \msmallskip
    
    $$a^{{\phi}(m)} \cancel{\prod^{{\phi}(m)}_{i=1}} r_i \equiv \cancel{\prod^{{\phi}(m)}_{i=1}} r_i \pmod{m}$$\\
    (Kiemeljük $a$-t $\rightarrow$ ${\phi}(m)$ db van $\rightarrow$ Egyszerűsítünk önmagával $\rightarrow$ 1)
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: (Kis) Fermat tétel}]
    Legyen $p$ prím és $a \in \mathbb{Z}$. Ekkor\\
    \mtinyskip
    
    (első alak) ha $p \nmid a$, akkor $a^{p-1} \equiv 1 \pmod{p}$.\\
    \mtinyskip
    
    (második alak) ha $a$ tetszőleges, akkor $a^p \equiv a \pmod{p}$.
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    Első alak: ${\phi}(p) \equiv p - 1$ $\rightarrow$ előző tétel miatt kész.\\
    \mmedskip

    Második alak:\\
    Ha $p|a$ $\rightarrow$ $0 \equiv 0$ $\rightarrow$ kész.\\
    Ha $p{\nmid}a$ $\rightarrow$ ekkor ez az első alak $\rightarrow$ kész.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: A diofantikus egyenlet megoldása}]
    Rögzített $a, b, c$ egész számok esetén az \textBF{$ax + by = c$} diofantikus egyenletnek akkor, és csak akkor van megoldása, ha $(a, b)|c$.
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    Tfh $ax + by = c$ egyenletnek van megoldása.\\
    \msmallskip
    
    \textBF{1. Rész ($\implies$)}\\
    \smallskip

    Tfh $x_0, y_0$ megoldás. $\implies$ $(a, b)|a \land (a, b)|b$ $\implies$ lin. kombinációs tul. $\implies$\\
    $\implies$ $(a, b)|ax_0 + by_0 = c$ (Igaz, mert az a, b osztója az $ax_0 + by_0$-nak.)\\
    \bigskip

    \textBF{2.Rész ($\Longleftarrow$)}\\
    \smallskip

    Tfh (a, b)|c (Definíció). Ekkor:\\
    $c = (a, b)q$\\
    $c = (au + bv)q$  (u, v-t mi írjuk fel, bővített euklideszi algo. $\rightarrow$ lnko)\\
    $c = a(uq) + b(vq)$\\
    $c = a(uq) + b(vq)$ $\implies$ egy megoldás: $x = uq, y = vq$.\\
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Kínai maradéktétel}]
    Legyen $n \in \mathbb{N}^+, m_1, m_2, ..., m_n \in \mathbb{N}^+, a_i, b_i \in \mathbb{Z} (1 \leq i \leq n)$, ahol
    \begin{enumerate}
      \item $m_i, m_j$ páronként relatív prímek.
      \item $(m_i, a_i) = 1$, minden $1 \leq i \leq n$ esetén.
    \end{enumerate}
    Ekkor az\\
    \mmedskip
    
    	$a_1x \equiv b_1 \pmod{m_1}$\\
    	$a_2x \equiv b_2 \pmod{m_2}$\\
    	...\\
    	$a_nx \equiv b_n \pmod{m_n}$\\
    \mmedskip
    
    Kongruenciarendszer megoldható és bármely két megoldása kongruens modulo $m_1m_2...m_n$ (Minden modulus szorzata $\rightarrow$ közös modulus).
  \end{tcolorbox}

  \begin{tcolorbox}[title={A kínai maradéktétel megoldása}]
    \begin{enumerate}
      \item Megoldjuk a kongruenciákat külön-külön.\\
      Mivel minden  $1 \leq i \leq n$ esetén $(m_i, a_i) = 1$, mindenütt pontosan egy megoldást kapunk.\\
      \msmallskip
      
      Ezeket jelöljük: $c_1, c_2, ..., c_n$
      \item Legyen $M = m_1m_2...m_n$ és\\
       \msmallskip
       
      $M_j = \frac{m}{m_j} = m_1 \cdot m_2 \cdot ... \cdot m_{j - 1} \cdot m_{j + 1} \cdot ... \cdot m_n$ $(1 \leq j \leq n)$
      \item Oldjuk meg a következő lineáris kongruenciákat:\\
      $M_1y \equiv \pmod{m_1}$\\
      $M_2y \equiv \pmod{m_2}$\\
      ...\\
      $M_ny \equiv \pmod{m_n}$\\
      \msmallskip
      
      Mivel minden $1 \leq j \leq n$ esetén $(M_j, m_j) = 1$, ezért mindenütt pontosan 1 megoldást kapunk.\\
      Ezeket jelöljük: $y_1, y_2, ... y_n$
      \item $x_0 = \sum_{i = 1}^n M_iy_ic_i$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: A számelméleti függvények}]
    \textBF{Számelméleti függvénynek} nevezzük az:\\
    \mtinyskip
    
    $f : \mathbb{N}^+ \rightarrow \mathbb{C}$\\
    \mtinyskip
    
    alakú függvényeket.\\
    \mmedskip

    Legyen $m, n \in \mathbb{N}^+$ és $(m, n) = 1$, ekkor $f$:
    \begin{itemize}
      \item \textBF{additív}, ha $f(nm) = f(n) + f(m)$
      \item \textBF{totálisan (teljesen) additív}, ha additív $(m, n) \neq 1$ esetén is.
      \item \textBF{Multiplikatív}, ha $f(nm) = f(n)f(m)$
      \item \textBF{Totálisan (Teljesen) multiplikatív}, ha multiplikatív $(m, n) \neq 1$ esetén is.
    \end{itemize}
  \tcblower
    \textBF{Észrevételek:}\\
    \begin{enumerate}
      \item Ha $f$ additív, akkor $f(1) = 0$
      \item Ha $f$ multiplikatív, és nem azonosan nulla, akkor $f(1) = 1$
    \end{enumerate}
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Számelméleti függvények}]
    Legyen $n \in \mathbb{N}^+$ kanonikus alakja $p_1^{{\alpha}_1}...p_k^{{\alpha}_k}$ (Prímszámhelyek!). Ekkor:\\
    \begin{enumerate}
      \item Ha $f$ additív számelméleti függvény, akkor $$f(n) = f(p_1^{{\alpha}_1}) + ... + f(p_k^{{\alpha}_k})$$
      \item Ha $f$ multiplikatív számelméleti függvény, akkor $$f(n) = f(p_1^{{\alpha}_1})...f(p_k^{{\alpha}_k})$$
      \item Ha $f$ teljesen additív számelméleti függvény, akkor $$f(n) = {\alpha}_1f(p_1) + ... + {\alpha}_kf(p_k)$$
      \item Ha $f$ teljesen multiplikatív számelméleti függvény, akkor $$f(n) = f(p_1)^{{\alpha}_1}...f(p_k)^{{\alpha}_k}$$
    \end{enumerate}
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: $\phi$ multiplikativitása}]
  $\phi$ multiplikatív.
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip

    \begin{tabular}{c c c c}
    1 & 2 & ... & a \\
    a + 1 & a + 2 & ... & 2a\\
     &  & ... &  \\
    (b - 1)a + 1 & (b - 1)a + 2 & ... & ba
    \end{tabular}
    \mmedskip

    Számoljuk meg, hogy a táblázatban hány relatív prím van $ab$-hez: ennyi lesz ${\phi}(ab)$ értéke.\\
    (Ha $a$ is $b$ is relatív prím $c$-hez, akkor $ab$ is. $\implies$ azokat kell számolni, amelyek $a$-hoz és $b$-hez is rel. prímek)\\
    \msmallskip

    AZ Omnibusz tételből következik hogy minden oszlop TMR mod $b$, ha $(a, b) = 1$ $\implies$\\
    $\implies$ minden oszlopban ${\phi}(b)$ rel. prím $b$-hez.\\
    \msmallskip

    | Minden oszlom kongruens elemeket tart mod $a$.\\
    | Minden sor egy TMR mod $a$ $\implies$ minden sorban ${\phi}(a)$ db elem relatív prím $a$-hoz.\\
    \msmallskip
    
    $\implies$ ${\phi}(a)$ db oszlopnak rel prímek az elemei $a$-hoz. $\implies$ összesen ${\phi}(a){\phi}(b)$ rel. prím van $ab$-hez.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: ${\phi}$(n) kiszámolása}]
    Ha $n \in \mathbb{N}^+$ kanonikus alakja $p_1^{{\alpha}_1}...p_k^{{\alpha}_k}$, akkor\\
    $${\phi}(n) = \prod^k_{j=1} (p_j^{{\alpha}_j} - p_j^{{\alpha}_j - 1}) = n \prod^k_{j=1} (1 - \frac{1}{p_j}).$$
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    $\phi$ multiplikatív\\
    \msmallskip
    
    Kiszámoljuk az értékeket prímhatványhelyeken, majd összeszorozzuk az értékeket.\\
    \msmallskip
    
    ${\phi}(p^{\alpha}) = ?$\\
    $1, 2, ..., p, ..., 2p, ..., 3p, ..., (p-1)p, ..., p^2, ..., (p+1)p, ..., (p-1)p^{{\alpha}-1}, ..., p^{\alpha}$\\
    \msmallskip
    
    Melyek nem relatív prímek $p$-hez?\\
    \msmallskip
    
    $p^2$-ig $p - 1$ db van + maga $p^2$, azaz ${\phi}(p^2) = p^2 - p^1$.\\
    \msmallskip
    
    Tovább számolva:\\
    ${\phi}(p^{\alpha}) = p^{\alpha} - p^{\phi - 1}$
  \end{tcolorbox}
\end{frame}

\begin{frame}[plain]
  \begin{tcolorbox}[center, colback={myyellow}, coltext={black}, colframe={myyellow}]
      {\RHuge Kombinatorika}
      \mmedskip
  \end{tcolorbox}
\end{frame}


\begin{frame}
  \begin{tcolorbox}[title={Def.: Halmazok ekvivalenciája}]
    $X$ és $Y$ halmaz \textBF{ekvivalens}, ha ${\exists} f$ bijekció $X$-ből $Y$-ra. Jelben $X \sim Y$.\\
    \mmedskip

    Egy $Y$ \textBF{halmaz véges}, ha valamely $n$ természetes számra ekvivalens az $\{ 1, 2, ..., n \}$ halmazzal, egyébként \textBF{végtelen}.\\
    \mmedskip

    Ezt az egyértelműen létező $n$ számot $X$ \textBF{számosságának} nevezzük.\\
    Jelben: $|X|, \#(X), card(X)$ (Kardinális).
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Véges halmaz valódi részhalmaza}]
    Ha $n$ természetes szám, akkor nem létezik ekvivalencia $\{ 1, 2, ..., n \}$ és egy valódi részhalmaza között.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Skatulya-elv}]
    Ha $X, Y$ véges halmazok, és $|X| > |Y|$, akkor nem létezik $f: X \rightarrow Y$ bijekció.
  \tcblower
    \textBF{Bizonyítás (Indirekt)}
    \mmedskip
    
    Tfh $f$ bijektív.\\
    \msmallskip
    
    $Y ~ \{1, 2, ..., m\}$ és $X ~ \{1, 2, ..., m\}$, ahol $m < n$ $\implies$\\
    $\implies$ $\{1, 2, ..., m\}$ bármely részhalmaza $\{1, 2, ..., n\}$-nek is részhalmaza,\\
    \msmallskip
    
    $f$ bijektív $\implies$ $\{1, 2, ..., n\}$ $\sim$ saját valódi részhalmazával. $\rightarrow$ Ellentmondás (Véges halmaz valódi részhalmaza tétel miatt)!\\
    \bigskip

    \textBF{Más megfogalmazás:} Ha $n$ db tárgyat $m$ db skatulyába teszünk, akkor van olyan skatulya, amelyik legalább\\
    $\lfloor (n - 1) / m \rfloor + 1$ tárgyat tartalmaz.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Permutáció}]
    $n \in \mathbb{N}$ elemű halmaz egy \textBF{permutációján} a halmaz önmagára való bijektív leképzését értjük.\\
    $P_n$ a halmaz különböző permutációinak száma.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Permutációk száma}]
    $$P_n = n!$$
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    Teljes indukció $n$ szerint\\
    \msmallskip
    
    1. lépés: $P_0 = P_1 = 1$ Igaz. (Megegyezés szerint $0! = 1$)\\
    \msmallskip
    
    2. lépés: Tfh $n > 1$ és $n - 1$-ig már beláttuk.\\
    \msmallskip
    
    ekvivalencia reláció:\\
    \mtinyskip
    
    amely sorozatok 1. eleme megegyezik $\implies$ $n$ db osztály.\\
    Ind. feltétel $\implies$ $\forall$ osztályban $P_{n - 1}$ elem.\\
    \msmallskip
    
    $P_n = nP_{n - 1} = n(n - 1)! = n!$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Def.: Ciklikus permutáció}]
    Minden elem egy hellyel jobbra/balra kerül, az utolsó/első az első/utolsó helyre.
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.:Ismétlés nélküli variáció}]
    Egy $A$ halmaz elemeiből képezhető $k$ tagú, csupa különböző elemeket tartalmazó sorozatokat, azaz $\{ 1, 2, ..., k \}$-t $A$-ba képező injektív leképezéseket az \textBF{$A$ halmaz  $k$-ad osztályú ismétlés nélküli variációjának} nevezzük.\\
    Ha $|A| = n$, akkor $A$ összes $k$-ad osztáylú ismétlés nélküli variávcióinak száma: $V_n^k$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Variációk száma}]
    $$V_n^k = \frac{n!}{(n - k)!} = n \cdot (n - 1) \cdot (n - 2) \cdot ... \cdot (n - k + 1)$$, ha $k \leq n$, kölünben 0.
  \tcblower
    \textBF{Bizonyítás}
    \mmedskip
    
    Legyen két sorozat egy ekv. osztályban, ha első $k$ elemük megegyezik.\\
    \msmallskip
    
    Ekkor: $P_n = $ (osztályok száma ($V_n^k = \frac{P_n}{P_n - k}$)) $\cdot$ (ahány elem egy osztályban ($P_{n - k}$))
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Ismétléses Variáció}]
    Egy $A$ halmaz elemeiből képezhető $k$ tagú, nem feltétlenül különböző elemeket tartalmazó sorozatokat, azaz $\{ 1, 2, ..., k \}$-t $A$-ba képező leképezéseket az \textBF{$A$ halmaz  $k$-ad osztályú ismétléses variációjának} nevezzük.\\
    Ha $|A| = n$, akkor $A$ összes $k$-ad osztáylú ismétléses variációinak száma: $V_n^{k, i}$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Ismétléses variációk száma}]
    $$V_n^{k, i} = n^k$$
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    Teljes indukció $k$ szerint, $n$ rögzített\\
    \msmallskip
    
    1. lépés: $k = 1$-re igaz: $V_n^{1, i} = n \rightarrow n^1$\\
    \msmallskip
    
    2. lépés: Tfh $k > 1$ és $k - 1$-ig már beláttuk, ekkor\\
    $(k - 1)$-es osztályú variációból $k$-ad osztályú:\\
    \msmallskip\\
    
    $n$ db választás $\implies$ $V_n^{k, i}$ (n választás) $= V_n^{k - 1, j} \cdot n$ (n - 1 választás).
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Ismétlés nélküli Kombináció}]
    Egy $A$ halmaz $k (n \in \mathbb{N})$ elemű részhalmaza \textBF{$A$ halmaz  $k$-ad osztályú ismétlés nélküli kombinációja}.\\
    Ha $|A| = n$, akkor $A$ összes $k$-ad osztályú ismétlés nélküli kombinációinak száma: $C_n^k$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Kombinációk száma}]
    $$C_n^k = \frac{V_n^k}{P_k} = {{n}\choose{k}} = \frac{n!}{k!(n - k)!} $$, ha $k \leq n$, különben $0$.
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    $V_n^k$ db különböző $k$-tagú sorozat, sorrend nem számít $\implies$\\
    $\implies$ minden $P_k$ sb sorozat ugyanaz $\implies$ számoljuk egyszer.\\
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Ismétléses Kombináció}]
    Egy $A$ halmaz $k (n \in \mathbb{N})$ nem feltétlenül különböző elem kiválasztása sorrendre való tekintet nélkül, az \textBF{$A$ halmaz  $k$-ad osztályú ismétléses kombinációja}.\\
    \msmallskip
    
    Ha $|A| = n$, akkor $A$ összes $k$-ad osztályú ismétléses kombinációinak száma: $C_n^{k, i}$.
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Ismétléses kombinációk száma}]
    $$C_n^{k, i} = C_{n + k -1}^k = {{n + k - 1}\choose{k}} = \frac{(n + k - 1)!}{k!((n + k - 1) - k)!}$$
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    Legyen $A = \{a_1, a_2, ..., a_n\}$.\\
    \msmallskip
    
    Minden egyes választási lehetőségnek feleltessünk meg egy bitsorozatot:\\
    $1 1 ... 1 0 1 1 ... 1 0 ... 0 1 1 1 ... 1$\\
    $k_1$ db,    $k_2$ db,         $k_3$ db 1esz.\\
    \msmallskip
    
    Az $a_i$ elemet $k_i$-szer választottuk, tehát $k_1 + ... + k_n = k$ az összes $1$-es száma (ennyi elemet választottunk összesen).\\
    \msmallskip
    
    Továbbá az elválasztó $0$k száma $n - 1$, tehát a sorozatban $n - 1 + k$ pozíció lesz\\
    \mmedskip

    Ekkor a $k$ db $1$-es beírása $k$ különböző pozícióba nem más, mint $k$ db választás egy $n - 1 + k$ elemű halmazból ismétlés nélkül:\\
    $$C_{n + k - 1}^k = {n + k - 1 \choose k}$$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Def.: Ismétléses Permutáció}]
      $n$ elem valamely sorrendben való felsorolása, amelyben $k$ elem fordul elő rendre $n_1, n_2, ..., n_k$ gyakorisággal $(n_1 + n_2 + ... + n_k = n)$, \textBF{$n$ elem egy $n_1, n_2, ..., n_k$-ad osztályú ismétléses permutációja}.\\
      Ezek száma: $P_n^{n1, ..., n_k}$
  \end{tcolorbox}

  \begin{tcolorbox}[title={Tétel: Ismétléses permutációk száma}]
    $P_n^{i_1, i_2, ..., i_r} = \frac{n!}{i_1!i_2!...i_r!}$
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    Teljes indukcció $k$ szerint , $n$ rögzített\\
    \mmedskip

    1. lépés: k = 1-re igaz: $P_n^n = \frac{n!}{n!} = 1$\\
    \mbigskip

    2.lépés: Tfh $k > 1$ és $k - 1$-ig már beláttuk, ekkor:\\
    \msmallskip

    ekvivalencia reláció:\\
    amely sorozatok megegyeznek, ha kivesszük az $n_k$-szor előforduló elemet ($k$-adik elem).\\
    \msmallskip

    Ind. feltétel $\Rightarrow$ $P_{n - n_k}^{n_1, ..., n_{k - 1}}$ db osztály van.\\
    \msmallskip

    Hány elem van az osztályban? $\rightarrow$ $n - n_k$ db elem.\\
    a $k$-adik elemet $n - n_k + 1$ helyre szúrhatjuk be.\\
    \mmedskip

    $C_{n - n_k + 1}^{n_k, i} = C^{n_n}_{(n - n_k + 1) + n_k - 1} = C_n^{n_k}$\\
    \mmedskip

    $P_n^{n_1, ..., n_k} = P_{n - n_k}^{n_1, ..., n_{k - 1}} C_n^{n_k} = \frac{(n - n_k)!}{n_1!...n_{k - 1}!} \cdot \frac{n!}{(n - n_k)!n_k!} = \frac{n!}{n_1...n_k!}$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Binomiális tétel}]
    Adott $x, y \in R$ és $n \in \mathbb{N}$ esetén:\\
    $$(x + y)^n = \sum_{k = 0}^n {n \choose k} x^ky^{n - k}$$.
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    $(x + y) ... (x + y) = x^n + ... + x^ky^{n - k} + ... + y^n$ ($n$ db tényező)\\
    \mmedskip

    Hány ilyen tag van? ($x^ky^{n - k}$).\\
    \mmedskip

    $k$ db tényezőből az $x$-et $n - k$-ből az $y$-t választottuk.\\
    \msmallskip
    
    Összesen $n$ elemből $k$ elemet, sorrend nem számít! $\Rightarrow$\\
    $\Rightarrow$ ${n \choose k}$ db $x^ky^{n - k}$ alakú tag van.
  \end{tcolorbox}


  \begin{tcolorbox}[title={Tétel: Következmény (Binomiális tétel)}]
    $\displaystyle \mathop{\sum_{k = 0}^n {n \choose k} = 2^n}$ és $\displaystyle \mathop{\sum_{i = 0}^n {n \choose k} (-1)^k = 0}$
  \end{tcolorbox}
\end{frame}

\begin{frame}
  \begin{tcolorbox}[title={Tétel: Logikai szita formula}]
    Legyenek $X_1, X_2, ..., X_k$ az $X$ véges halmaz részhalmazai, $F$ az $X$-en értelmezett, értékeket egy Abel-csoportban (Kommutatívnak kell lennie) felvevő függvény.\\
    Ha $1 \leq i_1 < i_2 < ... < i_r \leq k$ akkor legyen\\
    $Y_{i_1, i_2, ..., i_r} = X_{i_1} \cap X_{i_2} \cap ... \cap X_{i_r}$.\\
    \mmedskip

    Legyen továbbá
    \mmedskip

    $\displaystyle \mathop{S = \sum_{x \in X} f(x)}$, általában $f(x) = 1$ függvényt használjuk\\
    \mmedskip

    $\displaystyle \mathop{S_r = \sum_{1 \leq i_1 < i_2 < ... < i_r \leq k} (\sum_{x \in Y_{i_1, i_2, ..., i_r}} f(x))}$ \\
    \mmedskip

    $\displaystyle \mathop{S_0 = \sum_{x \in X \setminus \bigcup^k_{i = 1} X_i} f(x)}$.\\
    \mmedskip

    Ekkor: $S_0 = S - S_1 + S_2 - S_3 + ... + (-1)^kS_k$
  \tcblower
    \textBF{Bizonyítás}\\
    \mmedskip

    Tehát $S_0 =$ azon elemekre vett függvény összegek értéke, amelyek nem rendelkeznek egyetlen tulajdonsággal sem.\\
    \mmedskip

    $S_0 =(?) S - S_1 + s_2 - S_3 + ... + (-1)^k S_k$\\
    \mmedskip

    Tfh az $x$ elem pontosan $r$ tulajdonsággal rendelkezik.\\
    \mmedskip

    ${r \choose 0} - {r \choose 1} + {r \choose 2} - {r \choose 3} + ... + (-1)^r {r \choose r} = (1 - 1)^r = 0$\\
    \msmallskip
    
    $f(x)$-et mindíg ennyiszer számoltuk be. (r alatt az x szer), minden esetben.\\
    \mbigskip

    $\Rightarrow$ a jobboldalon nem számoltuk.\\
    \mbigskip

    Ha $x$ elem $0$ tulajdonsággal rendelkezik $\Rightarrow$ $x$ csak $S_0$-ban fordul elő. $\Rightarrow$\\
    $\Rightarrow$ $f(x)$-et a jobboldalon pont egyszer számoltuk be.
  \end{tcolorbox}
\end{frame}

\end{document}