\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{fullpage}

\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\legendre}[2]{\genfrac(){}{}{#1}{#2}}
\newcommand{\hf}{\hskip -25pt $\bullet$ \hskip 17pt}
\newcommand{\hfa}{\hskip -47pt $\bullet$ \hskip 39pt}
\newcommand{\defi}{\medskip\hskip -25pt}

\begin{document}

\begin{center}
{\Large \bf Algebra 1. 2004/2005 tavasz\\
1. gyakorlat: Halmazok, relációk, leképezések}
\end{center}

\begin{enumerate}

\item 
Igazoljuk a következő, halmazokra vonatkozó állításokat!
\begin{enumerate}

\item $A=A\setminus\left(B\setminus A\right)$
\item $\left(A\cup B\right)\setminus\left(B\setminus A\right)=
(A\cap B)\cup (A\setminus B)$
\item $(A\cap B^c)\cup(A^c\cap B)=B\iff A=\emptyset$, ahol $X^c$ az $X$ 
komplementere
\item \hfa 
$(\exists X:\,\,X\cup A=B)\iff(A\cup B)\setminus(A\cap B)\subseteq B$
\end{enumerate}

\item
Mutassuk meg, hogy a relációkon értelmezett $\circ$ művelet asszociatív.

\item 
Legyenek $\rho$ és $\eta$ a valós számok következő binér relációi:
\[
\rho=\left\{(a,b)\in\R^2\,\mid\,\,a=b^2\right\},~~
\eta=\left\{(a,b)\in\R^2\,\mid\,\,b=2a\right\}.
\]
Adjuk meg a $\rho\circ\eta$ és az $\eta\circ\rho$ relációkat!
Igaz-e $\rho^{-1}\circ\eta^{-1}=(\eta\circ\rho)^{-1}$?

\item 
Jelölje $\rho_m$ az egész számokon értelmezett modulo $m$ kongruenciát,
azaz $(a,b)\in\rho_m\iff a\equiv b\pod m$. Határozzuk meg, hogy mikor áll
fenn két egész között a $\rho_{m_1}\circ\rho_{m_2}$ reláció.


\defi
$\omega=\{(a,a)\,\mid\,\,a\in X\}$ az \emph{identikus reláció}.
%$\iota=X\times X$ az \emph{univerzális reláció}.

\item 
Lássuk be, hogy egy $\rho$ reláció akkor és csak akkor 
\begin{enumerate}
\item reflexív, ha $\omega\subseteq\rho$;
\item szimmetrikus, ha $\rho^{-1}\subseteq\rho$ vagy 
$\rho\subseteq\rho^{-1}$ vagy $\rho=\rho^{-1}$;
\item antiszimmetrikus, ha $\rho^{-1}\cap\rho=\omega$;
\item tranzitív, ha $\rho\circ\rho\subseteq\rho$.
\end{enumerate}

\item \hf 
Bizonyítsuk be, hogy $\rho\subseteq X\times X$ akkor és csak akkor 
ekvivalencia reláció, ha $\omega \subseteq\rho$ és 
$\rho\circ\rho^{-1}\subseteq\rho$.

\item
Legyen $\rho$ binér reláció, $\rho^{0}:=\omega$ és $n\ge1$ esetén 
$\rho^n:=\rho^{n-1}\circ\rho$. Mutassuk meg, hogy $\rho$ tranzitív lezártja 
éppen 
\[
\rho^+:=\bigcup_{n=1}^\infty \rho^n,
\]
azaz $\rho^+$ tranzitív, és bármely $\rho$-t tartalmazó tranzitív reláció
tartalmazza $\rho^+$-t is.
Mi lehet $\rho$ reflexív lezártja?

\item \hf
Legyen $F\subseteq X\times Y$ megfeleltetés. Bizonyítsuk be, hogy 
\begin{enumerate}
\item $F$ pontosan akkor leképezés, ha 
teljesül $\omega_X\subseteq F\circ F^{-1}$ és 
$\omega_Y\supseteq F^{-1}\circ F$;
\item amennyiben $F$ leképezés, úgy $F$ injektív 
$\iff \omega_X=F\circ F^{-1}$;
\item amennyiben $F$ leképezés, úgy $F$ szürjektív
$\iff \omega_Y=F^{-1}\circ F$;
\end{enumerate}

\item
Igazoljuk, hogy szürjektív leképezések kompozíciója szürjektív,
injektíveké injektív, bijektíveké bijektív.


\end{enumerate}
\end{document}
