%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%% file:      s3.tex                                                        %%%
%%% author:    Tatiana Jajcayová, Ján Komara                                 %%%
%%% email:     Jan.Komara@fmph.uniba.sk                                      %%%
%%% copyright: public domain                                                 %%%
%%% version:   2017/11/3                                                     %%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,a4paper]{article}

\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{lmodern}
\usepackage{indentfirst}

\renewcommand{\labelenumi}{{\normalfont (\alph{enumi})}}
\renewcommand{\labelenumii}{{\normalfont (\roman{enumii})}}

\newcommand{\nN}{\ensuremath{\mathbb N}}
\newcommand{\nZ}{\ensuremath{\mathbb Z}}
\newcommand{\nR}{\ensuremath{\mathcal R}}
\newcommand{\aP}[1]{\ensuremath{{\mathcal P}(#1)}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{3. domáca úloha z predmetu \\ 1-AIN-160 Matematika (3) ZS 2017/18}

\author{Tatiana Jajcayová \and Ján Komara}

%\date{}
\date{\today}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{1. príklad}

\begin{enumerate}
\item
Pre každé z nasledujúcich tvrdení o reláciách na množine $A$, kde $|A| = n$,
určite, či je pravdivé alebo nepravdivé. Ak je nepravdivé, uveďte kontrapríklad.
\begin{enumerate}
\item 
Ak $\nR$ je relácia na $A$ a $|\nR| \geq n$, tak $\nR$ je reflexívna.
\item 
Nech $\nR_1$ a $\nR_2$ sú relácie na $A$ a  $\nR_2 \supseteq \nR_1$. Ak je
$\nR_1$ reflexívna (symetrická, antisymetrická, tranzitívna), tak aj $\nR_2$ je
reflexívna (symetrická, antisymetrická, tranzitívna).
\item 
Nech $\nR_1$ a $\nR_2$ sú relácie na $A$ a  $\nR_2 \supseteq \nR_1$. Ak je
$\nR_2$ reflexívna (symetrická, antisymetrická, tranzitívna), tak aj $\nR_1$ je
reflexívna (symetrická, antisymetrická, tranzitívna).
\item 
Ak $\nR$ je ekvivalencia na $A$, tak  $n \leq |\nR| \leq n^2$.
\end{enumerate}
\item 
Nech $\nR_1$ a $\nR_2$ sú relácie na $A$. Relácia
\(
\nR = \nR_1 \circ \nR_2
\)
je nová relácia na $A$. Je toto zloženie symetrická relácia, ak pôvodné $\nR_1$
a $\nR_2 $ sú symetrické?
\item 
Nech $A$ je množina, $|A| = n$. Nech $\nR$ je relácia na $A$, ktorá je
antisymetrická. Aká je najväčšia možná hodnota  $|\nR|$? Koľko antisymetrických
relácií má takúto kardinalitu?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 1. príkladu}

Táto časť obsahuje riešenie 1. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{2. príklad}

\begin{enumerate}
\item 
Nech $A,B$ sú množiny a nech $|B| = 3$. Ak máme $4\,096$ relácií z $A$ do $B$,
nájdite $|A|$.
\item 
Ak $|A| = 4$ a existuje $1\,680$ injektívnych zobrazení z $A$ do $B$, koľko 
prvkov má $B$?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 2. príkladu}

Táto časť obsahuje riešenie 2. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{3. príklad}

\emph{Ackermanova} funkcia
\(
A : \nN \times \nN \rightarrow \nN
\)
sa dá rekurzívne definovať takto:
\begin{align*}
A(0,n) & = n+1 & \text{ak $n \geq 0$,}
\\
A(m,0) & = A(m-1,1) & \text{ak $m > 0$,}
\\
A(m,n) & = A(m-1,A(m,n-1)) & \text{ak $m,n >0$.}
\end{align*}
(Ackermanova funkcia je dôležitá v informatike v teórii rekurzívnych funkcií.
Jej hodnoty rastú veľmi rýchlo aj pre malé vstupy. Napríklad $A(4,2)$ je celé
číslo s $19\,729$ číslicami v dekadickom zápise.)
\begin{enumerate}
\item 
Vyrátajte  $A(1,3)$ a  $A(2,3)$.
\item 
Dokážte, že $A(1,n) = n + 2$ pre všetky $n \in \nN$.
\item 
Ukážte, že $A(2,n) = 3 + 2n$ pre všetky $n \in \nN$.
\item 
Overte, že $A(3,n) = 2^{n + 3} - 3$ pre všetky $n \in \nN$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 3. príkladu}

Táto časť obsahuje riešenie 3. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{4. príklad}

\begin{enumerate}
\item
Nech
\(
n,n_1,n_2,n_3,n_4 \in \nZ^+
\)
a nech $f: A \rightarrow B$, kde $|A| = n$  a $B = \{a,b,c,d\}$, je funkcia, pre
ktorú platí $|f^{-1}(a)| = n_1$, $|f^{-1}(b)| = n_2$, $|f^{-1}(c)| = n_3$,
$|f^{-1}(d)| = n_4$ a $n_1 + n_2 + n_3 + n_4 = n$. Na množine $A$ definujme
reláciu $\nR$ takto:
\begin{center} 
$x \nR y$, ak $x,y \in A$ a $f(x) = f(y)$.
\end{center}
\begin{enumerate}
\item
Nájdite $|\nR|$.
\item 
Je $\nR$ ekvivalencia? Ak áno, aký rozklad na množine $A$ indukuje?
\end{enumerate}
\item 
Nech $f: A \rightarrow B$ je funkcia. Dokážte, že ak $\{B_1, B_2, \ldots, B_n\}$
je rozklad množiny $B$, tak
\begin{align*}
\{f^{-1}(B_i) \mid 1 \leq i \leq n, f^{-1}(B_i) \ne \emptyset\}
\end{align*}
je rozklad množiny $A$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 4. príkladu}

Táto časť obsahuje riešenie 4. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{5. príklad}

\paragraph*{Definícia.} 

Binárna relácia $\nR$ na $A$ sa nazýva \emph{čiastočné usporiadanie}, ak je
$\nR$ reflexívna, antisymetrická a tranzitívna. Množina $A$ s čiastočným
usporiadaním $\nR$, označovaná ako dvojica $(A,\nR)$, sa nazýva \emph{čiastočne
usporiadaná množina}.

Nech $A$ je množina a nech $\nR$, binárna relácia definovaná na potenčnej
množine \aP{A}, je relácia "byť podmnožinou". (To znamená, že pre dve podmnožiny
$X,Y$ množiny $A$, $X \nR Y$, ak $X \subseteq Y$.)

\paragraph*{Úloha.}

Overte, že $\nR$ je čiastočné usporiadanie na \aP{A}.

\paragraph*{Poznámka.} 

Túto reláciu $\nR$ označujeme zvyčajne $\subseteq_{\aP{A}}$. To znamená, že máte
ukázať, že
\(
(\aP{A}, \subseteq_{\aP{A}})
\)
je čiastočne usporiadaná množina.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 5. príkladu}

Táto časť obsahuje riešenie 5. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
