prac.tex

\documentclass{article}
\usepackage{geometry}
\geometry{a4paper,scale=0.8}
\usepackage{enumerate}
\usepackage{indentfirst}
\usepackage{enumitem}
\usepackage{amssymb}
\usepackage{ctex}
\usepackage{commath}
\usepackage{amsmath}


\begin{document}
\title{COMP9020 Assignment 1}
\author{Taria}
\maketitle

\section*{Problem 1}
\subsection*{(a) List all possible functions $f:\{a,b,c\}\to \{0,1\} $.}

\[
    \begin{array}{r}
    ${(a, 0), (b, 0), (c, 0)}, {(a, 0), (b, 0), (c, 1)},$\\
    ${(a, 0), (b, 1), (c, 0)}, {(a, 0), (b, 1), (c, 1)},$\\
    ${(a, 1), (b, 0), (c, 0)}, {(a, 1), (b, 0), (c, 1)},$\\
    ${(a, 1), (b, 1), (c, 0)}, {(a, 1), (b, 1), (c, 1)}$.
    \end{array}
\]

\subsection*{(b) Describe a connection between your answer for (a) and $Pow(\{a,b,c\})$.} 

$Pow(\{a,b,c\}) = \{\phi, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\} $\\
\indent$card(Pow(\{a, b, c\}))$ = number of possible function $f = 8$


\subsection*{(c) In general, if card($A$) = $m$ and card($B$) = $n$, how many:} 

\begin{itemize}

\item[(i)] $\because$ for every $a \in \mathbb{A}$, there are $n$ possible image of $a$ and there are $m$ elements in $A$\\
      $\therefore$ together there are $n^m$ functions

\item[(ii)] $a$ relation is a subset of $A \times B$
      $\therefore$ number of relations = $card(Pow(A \times B)) = 2^{\abs{A \times B}} = 2^{m \cdot n}$

\item[(iii)] $\because$ it’s symmetric\\
      $\therefore$ if $(x,y) \in \mathbb{R}$ then $(y,x) \in \mathbb{R}$ as one pair\\
      There are total $\frac{(m(m-1))}{2}$ different pairs\\
      it could also be $(x, x)$, there are $m$ possible choice\\
    $\therefore$ there are total $C_{\frac{m(m-1)}{2}+m}^{0} + C_{\frac{m(m-1)}{2}+m}^{1} + \cdots + C_{\frac{m(m-1)}{2}+m}^{\frac{m(m-1)}{2}+m} = 2^{\frac{m(m-1)}{2}+m} = 2^{\frac{m(m+1)}{2}}$ relations.

\end{itemize}

\section*{Problem 2}
For $x,y \in \mathbb{Z}$  we define the set:
\begin{center}
$S_{x,y} ={mx+ny:m,n \in \mathbb{Z}}.$
\end{center}

\subsection*{(a) Give five elements of $S_{2,-3}$.}
\indent$\{0, -1, 1, 3, 5\}$

\subsection*{(b) Give five elements of $S_{12,16}$.}
\indent$\{0, 4, 16, 20, 24\}$\\

\indent For the following questions, let $d = \gcd(x, y)$ and $z$ be the smallest positive number in $S_{x,y}$.
\subsection*{(c) Showthat $S_{x,y} \subseteq \{n:n \in \mathbb{Z}$ and $d \vert n \}$.}
\begin{itemize}
    \item[]
        $\forall a \in S_{x,y}, \exists m,n \in \mathbb{Z}, a=mx+ny \\
        \because d = \gcd(x,y) \\
        \therefore d \vert x,d \vert y \\
        \therefore d \vert mx,d \vert ny\\
        \therefore d|(mx+ny)\\
        \therefore d \vert a\\
        \therefore a \in {n:n \in \mathbb{Z} and d \vert n}\\
        \therefore \forall a \in S_{x,y}, a \in {n:n \in \mathbb{Z} and d \vert n}\\
        \therefore S_{x,y} \subseteq {n:n \in \mathbb{Z}\ and\ d \vert n}$
    
    \end{itemize}

\subsection*{(d) Showthat $\{{n:n \in \mathbb{Z}}$ and $ z \vert n \}\subseteq S_{x,y}$.}

\begin{itemize}
    \item[]
        $\because z \in S_{x,y}\\
        \therefore \exists m,n \in \mathbb{Z},z=mx+ny\\
        for\ every\ a\ \in {n:n \in \mathbb{Z}\ and\ z \vert n}\\
        \because z \vert a\\
        \therefore \exists k \in \mathbb{Z},a=k \cdot z=k(mx+ny)=kmx+kny\\
        \because k \in \mathbb{Z},m,n \in \mathbb{Z}\\
        \therefore km,kn \in \mathbb{Z}\\
        \therefore a \in S_{x,y}\\
        \therefore \forall a \in {n:n \in \mathbb{Z} and z \vert n},a \in S_{x,y}\\
        \therefore{n:n \in \mathbb{Z} and z \vert n} \in S_{x,y}$
 
\end{itemize}

\subsection*{(e) Show that d ≤ z. (Hint: use (c))}

\begin{itemize}
    \item[]
       $ \because z \in S_{x,y}\\
        according to (c), z \in {n:n \in \mathbb{Z}\ and\ d \vert n}\\
    \therefore d \vert z\\
    \therefore \exists k \in \mathbb{Z},z=k \cdot d\\
    \because d=\gcd{(x,y)},\ z\ is\ the\ smallest\ positive\ number\ in\ S_{x,y}\\
    \therefore d>0,z>0\\
    \therefore d \le z$

\end{itemize}

\subsection*{(f) Show that z ≤ d. (Hint: use (d))}

\end{document}∫