Solutions to Discrete Mathematics Assignment

This document contains solutions to Discrete Mathematics Assignment. It covers topics like functions, cardinality, relations, and more. The solutions are explained step by step with examples and proofs. The document is relevant for students studying Discrete Mathematics in college or university.

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\begin{document}
\title{\textbf{Solutions to Discrete Mathematics Assignment}}
\maketitle
\textbf{QUESTION ONE}\\
Given, $$f(x) = \frac {x+1}{x-1}$$
a.\\ (i) Domain of $f(x)$ is $\{x\in \mathbb{R} -\{1\}\}$. This is an implication that the function
is defined for all real numbers in exception of 1.\\
(ii) For range,\\
$$f(x)=\frac{2+(x-1)}{x-1}$$
$$ =\frac{2}{x-1} + 1$$
\hspace{30mm}$f(x)\ne1$ since $\frac{2}{x-1}\ne$ for $ x\in \mathbb{R}$\\
\hspace{10mm}The range of $\frac{2}{x-1}$ is $\{\mathbb{R} -\{0\}\} $\\
Thus Range of the function is $\{\mathbb{R} -\{1\}\} $\\
b. Proof of whether f(x) is invertible and calculation of its inverse\\
$$f^{-1} = \frac {x-1}{x+1}$$
such that $$f(x)*f^{-1}=1$$\\
$$f\circ f^{-1}(x)=f(\frac {x-1}{x+1})$$\\
$$=\frac {\frac {x-1}{x+1}+ 1}{\frac {x-1}{x+1}-1}$$
$$=\frac {\frac{x-1 + (x+1)}{x+1}}{\frac{x-1 - (x+1)}{x+1}}= -x$$
Thus $$f\circ f^{-1}(x)=-x$$
Proof that $$f\circ f^{-1}(x)=f^{-1} (\frac {x+1}{x-1})$$
$$=\frac {\frac {x+1}{x-1}- 1}{\frac {x+1}{x-1}+1}$$
$$=\frac {\frac{(x+1) - (x-1)}{x-1}}{\frac{(x+1) + (x-1)}{x-1}}= \frac {1}{x}$$
Thus $$f^{-1}\circ f(x)=\frac {1}{x}$$
\textbf{QUESTION TWO}\\
Using the concept of the golden ratio,$f(n)$ is the closed form solution of $n^{th}$ fibonacci
number. But, $n^{th}$ fibonacci number is given by:\\
$$F_n = \frac{\varphi^n-\psi^n}{\sqrt{5}}$$
where the golden ratio is $$\varphi=\frac{1+\sqrt{5}}{2}\approx 1.618$$
The domain of this problem is a natural number$\ge$ 2 with the co-domain being a set of
fibonacci numbers $\ge$ 2.\\
A bijective function is both injective and surjective i.e. $f: A\to B$. This implies that $\forall b$
in the co-domain B there is exactly one element a in the domain A such that $f(a)=b$ and vice-
versa.\\
Since $f(2)=1$, is missing in the co-domain of this example and that some elements in the co-
domain are also not fibonacci numbers, the function is not bijective.\\
\textbf{QUESTION THREE}\\

Let $\mathbb{Q}$ denote the set of rational numbers and $\mathbb{Z}$ the set of integers.
Because $\mathbb{N}$ is countable $\Rightarrow \mathbb{N}\times\mathbb{N}$ is also
countable.\\
\hspace{60mm} Defining $\mathbb{Q}= \mathbb{Q}+ \cup\{O\}\cup\mathbb{Q}$\\
$$f:\mathbb{Q}^{+}\to\mathbb{N}\times\mathbb{N}$$
$$f(p,q) = (p,q)\hspace{3mm} p,q\in v^{+}, (p,q)\in\mathbb{N}\times\mathbb{N}$$\\
$\Rightarrow$ f is one to one but not onto.\\
Since$ |\mathbb{Q}^{+}|\le|\mathbb{N}\times\mathbb{N}|$, $\mathbb{Q}^{+}$ is countable.
Similarly, $\mathbb{Q}^{-}$ is countable too.\\
Thus, $$|\mathbb{Q}|=|\mathbb{N}|$$ \hspace{90mm}...equation (i)\\
Now, $g:\mathbb{Z}\to\mathbb{N}$ defined by $g(n)=2n + 1$ if $n\in\mathbb{Z}^{+}$\\
$$g(+n)=-2n \hspace{3mm} if \hspace{1mm} n\in\mathbb{Z}^{-}$$\\
Because this is one to one and onto mapping, \\
$$|\mathbb{Z}|=|\mathbb{N}|$$ \hspace{90mm}...equation (ii)\\
Combining equations (i) and (ii),
$$|\mathbb{Q}|=|\mathbb{N}|=|\mathbb{Z}|$$
$$\Rightarrow |\mathbb{Q}|=|\mathbb{Z}|$$
\textbf{QUESTION FOUR}\\
Yes. We can infer that the cardinality of $|X|=|Y|$\\
Let,\\
X and Y be two infinite set in which X$\subseteq Y$\\
Also assume that$ f: X\to$ Y is a surjective function\\
Suppose $|X|\ne|Y|$,\\
$$As \hspace{2 mm}X\subset Y, |X|<|Y|$$\\
$\Rightarrow$ for the given function $ f: X\to Y,\exists y\in Y$ such that the function has no
pre-image in X\\
$\Rightarrow$ the given function, f is not a surjective map which contradicts $|X|<|Y|$\\
$$\therefore |X|\nless|Y|$$\hspace{90mm}...equation (i)\\
Also $$X\subseteq Y \Rightarrow |X|\le|Y|$$ \hspace{90mm}...equation (ii)\\
From (i) and (ii), $$|X|=|Y|$$
\textbf{QUESTION FIVE}\\
Given, $$Y\subset X$$\hspace{90mm}...equation 1\\
The function $ f: X\to$ Y is injective i.e. for every element in X, there is a unique element in Y \\
Therefore, $$X\subset Y$$\hspace{90mm}...equation 2\\
From (i) and (ii), $$|Y|=|X|$$\hspace{90mm}...hence proved\\
\textbf{QUESTION SIX}\\
Defining $\mathbb{R}^{+}=\{a\in\mathbb{R}:a>0\}$\\
Let, $$f:\mathbb{R}\to\mathbb{R}^{+}$$\\
$$f(x)=e^x$$
If $f(a) = f(b)$, then $e^a = e^b$ $\Rightarrow a=b$\\
$$\Rightarrow f\hspace{1mm} is \hspace{1mm}one-one$$
For any positive real number $y\in\mathbb{R}^{+}$\hspace{1mm}$\exists\hspace{1mm} \
ln(y)\in \mathbb{R}$ such that $e^{\ln(y)}= y$\\

$$\Rightarrow f \hspace{1mm}is\hspace{1mm} onto$$\\
Hence, $\exists$ a bijection between $\mathbb{R}$ and $\mathbb{R}^{+}$\\
$$\mathbb{R}\hspace{1mm}and\hspace{1mm}\mathbb{R}^{+} have\hspace{1mm}the\
hspace{1mm}same\hspace{1mm}cardinality$$\\
\textbf{QUESTION SEVEN}\\
Define the Relation R on $\mathbb{Z}$ by x R y iff $x-y=2$ for $x,y\in \mathbb{Z}$\\
(i) Not reflexive\\
For any $x\in \mathbb{Z}$, $x-x = 0$\\
Therefore, x is not R related to y\\
$$\therefore\hspace{1mm}R\hspace{1mm}is\hspace{1mm}not\hspace{1mm}Reflexive\
hspace{1mm}on\hspace{1mm}\mathbb{Z} $$
(ii) Not symmetric\\
For $x,y\in \mathbb{Z}$, suppose x R y
$$\Rightarrow x-y=2$$
But $$y-x=-(x-y)=-2$$
$$\therefore\hspace{1mm}y\hspace{1mm}is\hspace{1mm}not\hspace{1mm}R\
hspace{1mm}related\hspace{1mm}to\hspace{1mm}x $$
That is, x R y holds but y R x does not.\\
$$\therefore\hspace{1mm}R\hspace{1mm}is\hspace{1mm}symmetric\hspace{1mm}on\
hspace{1mm}\mathbb{Z} $$
(iii)Not transitive\\
Let $x,y,z\in \mathbb{Z}$ such that x R y and y R z,\\
$$\Rightarrow x-y=2\hspace{1mm}and\hspace{1mm} y-z = 2$$
but $$x-z=x+y-y-z= (x-y) + (y+z)$$
$$2+2=4$$
$$\therefore x-z = 4$$
$$\therefore x\hspace{1mm} is\hspace{1mm}not\hspace{1mm}R\hspace{1mm}related\
hspace{1mm}z$$
$$\therefore R\hspace{1mm} is\hspace{1mm}not\hspace{1mm}a\hspace{1mm}Transitive\
hspace{1mm}relation\hspace{1mm}to\hspace{1mm}z$$
\textbf{QUESTION EIGHT}\\
Let $S = \{\{1\}, \{1,2\},\{1,3\}\}$ be a set.\\
Define R on S by $A,B\in S.$\\
This implies that $(A,B)\in R$ $\Leftrightarrow$ $ A\subseteq B$\\
then\\
$R =\{(\{1\},\{1\}),(\{1,2\},\{1,2\}),(\{1,3\},\{1,3\}),(\{1\},\{1,2\}),(\{1\},\{1,3\})\}$\\
Here, R is Reflexive, Anti-Symmetric and transitive. So R is partially ordered Relation.\\
Also, for $A,B\in S$ ,we have either ARB or BRA. Therefore, R is totally ordered and hence a
totally ordered Relation.\\
\textbf{QUESTION NINE}\\
i. Reflexive: Yes\\
For (x,x), $$|x-x|=0<1, \hspace{1mm}thus\hspace{1mm} (x,y)\in\hspace{1mm}\mathbb{R}$$

ii. Symmetric: Yes\\
This is because $|x-y|=|y-x|$ so if $|x-y|<1$ then $|y-x|$ must also be $< 1$.\\
iii. Transitive: Yes\\
Considering three sets of transitive data $(2,6), (6,3), (2,3)$,\\
$$|2-6|=4\nless1, |6-3|=3\nless1, |2-3|=1\nless 1$$\\
iv. Antisymmetric: No\\
Because for for a given set of data i.e. $(x,y) = (5,2), (y,x)=(2,5)$,\\
$$|x-y|=|y-x|=3\nless1$$
v. Comparable: No\\
Since the value of $|x-y|$ when $x=y$ is $0$ which is a value $\nless 1$\\
\end{document}