%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%% file:      s2.tex                                                        %%%
%%% author:    Tatiana Jajcayová, Ján Komara                                 %%%
%%% email:     Jan.Komara@fmph.uniba.sk                                      %%%
%%% copyright: public domain                                                 %%%
%%% version:   2019/10/18
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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{\nZ}{\ensuremath{\mathbb Z}}
\newcommand{\nR}{\ensuremath{\mathcal R}}
\newcommand{\nP}{\ensuremath{\mathcal P}}

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

\begin{document}

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

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

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

%\date{}
\date{\today}

\maketitle

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

\section*{1. príklad}

Nech $A = \{u,v,w,x,y,z\}$. Určite počet relácií na $A$, ktoré sú
\begin{enumerate}
\item 
reflexívne a symetrické (zároveň);
\item 
ekvivalencie;
\item 
reflexívne a symetrické, ale nie sú tranzitívne;
\item 
ekvivalencie s práve dvoma triedami rozkladu;
\item 
ekvivalencie s $w \in [x]$;
\item 
ekvivalencie s $w \in [x]$ a $y \in [z]$;
\item 
ekvivalencie s $w \in [x]$, $y \in [z]$ a $[x] \ne [z]$.
\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 = \{1,2,3,4,5\} \times \{1,2,3,4,5\}$. 
Definujme na $A$ reláciu $\nR$ nasledovne:
$(x_1,y_1) \nR (x_2,y_2)$, ak $x_1 + y_1 = x_2 + y_2$.
\begin{enumerate}
\item 
Overte, že $\nR$ je ekvivalencia.
\item 
Určite triedy ekvivalencie $[(1,4)]$, $[(4,2)]$ a $[(1,1)]$.
\item 
Určite rozklad množiny $A$ indukovaný reláciou $\nR$.
\end{enumerate}
%
\item 
Nech $A$ je neprázdna množina a nech $B$ je jej jedna fixovaná podmnožina.
Definujme reláciu $\nR$ na $\nP(A)$ takto:
$X \nR Y$, pre $X,Y \subseteq A$, ak $B \cap X = B \cap Y$.
\begin{enumerate}
\item 
Overte, že $\nR$ je ekvivalencia na $\nP(A)$.
\item 
Pre $A = \{1,2,3\}$ a $B = \{1,2\}$ nájdite rozklad $\nP(A)$ indukovaný $\nR$.
\item 
Pre $A = \{1,2,3,4,5\}$ a $B = \{1,2,3\}$ nájdite $[X]$, ak $X=\{1,3,5\}$.
\item  
Koľko tried rozkladu bude v rozklade indukovanom $\nR$ 
pre $A = \{1,2,3,4,5\}$ a $B = \{1,2,3\}$?
\end{enumerate}
%
\end{enumerate}

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

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

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

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

\section*{3. 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
$\{f^{-1}(B_i) \mid 1 \leq i \leq n, f^{-1}(B_i) \ne \emptyset\}$ 
je rozklad množiny $A$.
%
\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 $A$ je množina a nech $\nR$, binárna relácia definovaná na potenčnej 
množine $\nP(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$.) 

Overte, že $\nR$ je čiastočné usporiadanie na $\nP(A)$. 
Má toto čiastočné usporiadanie najväčší a najmenší prvok?
%
\item 
\begin{enumerate}
\item 
Koľko  relácií čiastočného usporiadania existuje na $3$-prvkovej množine?
\item 
Koľko relácií, ktoré sú reflexívne, antisymetrické, ale nie tranzitívne, 
existuje na $3$-prvkovej množine?
\item  
Koľko existuje relácií čiastočného usporiadania na $3$-prvkovej množine bez 
najmenšieho prvku?
\item 
Koľko existuje lineárnych usporiadaní $3$-prvkovej množiny?
\end{enumerate}
%
\end{enumerate}

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

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

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

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

\section*{5. príklad}

Toto je príklad, ktorý zostal z predchádzajúcej úlohy. 
Niektorí ste ho možno riešili už vtedy. Teraz ho treba odovzdať.

\begin{enumerate}
\item 
Nech $n \in \nZ^+$,  $n>1$ a nech $A$ je množina všetkých kladných celočíselných 
deliteľov čísla $n$. Definujme reláciu $\nR$ na $A$ takto: 
$(x,y) \in  \nR $, ak $x$ delí $y$. 
Určite koľko usporiadaných dvojíc obsahuje relácia $\nR$ 
pre $n = 20$, $n = 210$ a $n = 13860$.
\item 
Nech $p_1, p_2, p_3$ sú rôzne prvočísla. 
Nech $n, k \in \nZ^+$ také, že $n = p_1^5 p_2^3 p_3^k$. 
Nech $A$ je množina kladných celočíselných deliteľov $n$. 
Reláciu $\nR$ na $A$ definujeme rovnako ako v predchádzajúcej časti: 
$x \nR y$, ak $x$ delí $y$. 
Nájdite $k$ a $|A|$, ak vieme, že $\nR$ má $5880$ usporiadaných dvojíc.
\end{enumerate}

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

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

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

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

\end{document}

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