FC1 Week 5 SGT

1

1. $1,4,9,16,25$
2. No, as $38$ cannot be found from $n^2$. $\sqrt{38}=6.16$

title: Correct answers.

4. Basis step: $0\in S$ Recursive step: If $n^2\in S$, then $(n+1{)}^2\in S$.

title: Taken from TA's solution.

2

1. Let $S=\{2k,k\in \mathbb{N}\text{ and }2\le k\le 10\}$

title: Correct answer.

2. Let $\mathbb{Q}=\{\frac{m}{n},m\ge 0\text{ and }n>0\text{ and }m,n\in \cancel{\mathbb{N}}\mathbb{Z}\}$

title: Should use integer not natural.

3

Set	Partial order	Linear order	Equivalence relation
a	❌	❌	❌
b	✅	❌	❌
c	❌	❌	❌
d	❌	❌	✅
e	✅	✅*	❌

* $e$ is also a linear order, consider the Hasse diagram.

Answers $b$ were originally correct.

digraph A {
	subgraph cluster_test {
		label="A"
		0->0
		1
		2->2
		3->3
	}
}
 
digraph B {
	subgraph cluster_test {
		label="B"
		0->0
		1->1
		2->0,2,3
		3->3
	}
}
 
digraph C {
	subgraph cluster_test {
		label="C"
		0->0
		1->1,2
		2->2,3
		3->3
	}
}
 
digraph D {
	subgraph cluster_test {
		label="D"
		0->0,1
		1->0,1
		2->2,3
		3->2,3
	}
}
 
digraph E {
	subgraph cluster_test {
		label="E"
		0->0,1,2,3
		1->1,2,3
		2->2,3
		3->3
	}
}

title: Make sure to consider whole set.
 
Original answer for $a$ was all true, when it is actually all false.
Graph $A$, as below, given the set $\{0,1,2,3\}$ is incorrect.
 
```graphviz
digraph A {
	subgraph cluster_test {
		label="A"
		0->0
		2->2
		3->3
	}
}
 
digraph B {
	subgraph cluster_test {
		label="B"
		0->0
		1
		2->2
		3->3
	}
}

title: Hasse diagram for $E$
 
```graphviz
graph E {
	subgraph cluster_test {
		label="E"
		3--2
		2--1
		1--0
	}
}
 
digraph E {
	subgraph cluster_test {
		label="E*"
		0->0,1,2,3
		1->1,2,3
		2->2,3
		3->3
	}
}

4

$$R=\{(1,3),(1,4),(2,4),(3,2),(4,1)\}$$ $$\left(\begin{array}{cccc}4& 1& 3& 2\\ 1& & & \\ 3& & & \\ 2& & & \end{array}\right)$$ $$M_0=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right)$$ $$M_1=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 1& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 0& 0\end{array}\right)$$ $$M_2=\left(\begin{array}{cccc}1& 1& 1& 0\\ 1& 1& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 1& 0\end{array}\right)$$ $$M_3=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 0& 0& 0& 1\\ 1& 1& 1& 1\end{array}\right)$$ $$M_4=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}\right)$$

digraph R {
	label = "R"
	1->3,4
	2->4
	3->2
	4->1
}
 
digraph S {
	label = "R*"
	1->1,2,3,4
	2->1,2,3,4
	3->1,2,3,4
	4->1,2,3,4
}

Hence our output is:

$$\begin{array}{r}R\ast =(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),\\ (3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)\end{array}$$

title: Correct answer.

5

1. $f(n)=n-1$ One-to-one as all values in the domain map to a unique value in the codomain. Onto as the entire codomain is mapped back to the domain.

   title: Correct answer.

2. $f(n)=n^2+1$ Not one-to-one: multiple values in the domain map to one value in the codomain, such as $f(1)=2,f(-1)=2$. Not onto: as not the entire codomain is mapped to the domain, the range is $f(n)\ge 1$.

   title: Correct answer.

6

Let $f$ and $g$ be $\mathbb{N}\to \mathbb{N}$ functions defined by:

$$\begin{array}{rl}f(n)& =2^n\\ g(n)& =\{\begin{array}{ll}5n& \text{if }n>10\\ 6n& \text{if }0\le n\le 10\end{array}\end{array}$$

Describe the compositions of:

1. $f\circ f$

   $$f\circ f=2^{2n}$$

2. $f\circ g$

   $$f(g(n))=\{\begin{array}{ll}{2}^{5n}& \text{if }n>10\\ 2^{6n}& \text{if }0\le n\le 10\end{array}$$

3. $g\circ f$

   $$g(f(n))=\{\begin{array}{ll}5(2^n)& \text{if }{2}^n>10\\ 6(2^n)& \text{if }0\le 2^n\le 10\end{array}=\{\begin{array}{ll}5(2^n)& \text{if }n>3\\ 6(2^n)& \text{if }0\le n\le 3\end{array}$$

4. $g\circ g$

   $$\begin{array}{rl}g(g(n))& =\{\begin{array}{ll}5(5n)& \text{if }n>5\\ 6(5n)& \text{if }0\le n\le 10\end{array}\\ & =\{\begin{array}{ll}25n& \text{if }n>10\\ 30n& \text{if }n>10,0\le 5n\le 10\\ 30n& \text{if }0\le n\le 10,6n>10\\ 36n& \text{if }0\le n\le 10,0\le 6n\le 10\end{array}\\ & =\{\begin{array}{ll}25n& \text{if }n>10\\ 30n& \text{if }2\le n\le 10\\ 36n& \text{if }0\le n\le 1\end{array}\end{array}$$

title: Correct answers.