Tutorial Exercises

2.1

Let $S=\{s,\varnothing \}$

1. $s\in S$ is true
2. $\{s\}\in S$ is false
3. $\varnothing \subseteq S$ is true
4. $\varnothing \in S$ is true

title:
Correct answers.

2.2

Describe the following set by listing its elements

$$\{2k+1|k\text{ is an even integer between }-5\text{ and }3\}$$

$k=\{-4,-2,0,2\}$

Hence, $-7$, $-3$, $1$, $5$.

title:
Correct answer.

2.3

Describe the set of all even positive natural numbers a. in terms of a property of its elements

$$\{2x|x\in \mathbb{N}\text{ and }x>0\}$$

b. by recursion

Basis step: $2\in {\text{Even}}^{+}$ Recursive step: If $x\in {\text{Even}}^{+}$ then $x+2\in {\text{Even}}^{+}$

title:
Mis-read even positive natural numbers as just positive natural numbers.

2.4

Describe $A=\{2x+3|x\in \mathbb{Z}\}$ by recursion.

Basis step: $3\in A$ Recursive step: If $x\in A$ then $x-2\in A$ and $x+2\in A$.

title:
Correct answer.

2.5

Let $A=\{1,2,3\},B=\{1,3,5\},C=\{3,\{3,5\},5,6\}$. Describe each of the following:

1. $(A\cup B)\cap C$ $\{3,5\}$
2. $P(B)\cap C$ $\{\{3,5\}\}$
3. $(B-C)\cup (C-A)$ $\{1,\{3,5\},5,6\}$

title:
Correct answer.

2.6

Show that if $A$ and $B$ are any sets, then $\overline{A\cap B}=\overline{A}\cup \overline{B}$ always holds.

$$\begin{array}{rl}\overline{A\cap B}& =\{x|x\in \overline{A\cap B}\}\\ & =\{x|x\notin A\cap B\}\\ & =\{x|\neg (x\in \neg A\cap \neg B)\}\\ & =\{x|\neg (x\in A)\cup \neg (x\in B)\}\\ & =\{x|(x\notin A)\cup (x\notin B)\}\\ & =\{x|(x\in \bar{A})\cup (x\in \bar{B})\}\\ & =\{x|x\in \bar{A}\cup \bar{B}\}\\ & =\bar{A}\cup \bar{B}\end{array}$$

title:
From solutions.

2.7

Show that there are sets $A,B,C$ such that $(A\cap B)\cup C\ne A\cap (B\cup C)$.

$$\begin{array}{rl}A& =\{\}\\ B& =\{1\}\\ C& =\{1\}\\ & \\ LHS& =\{\}\cup \{1\}\\ & =\{1\}\\ & \\ RHS& =\{\}\cap \{1\}\\ & =\{\}\\ & \ne LHS\text{ as required}\end{array}$$

title:
Assumed to be right, check over.

2.8

Describe each of the following relations from $A$ to $B$ by listing their ordered pairs, where

$$\begin{array}{rl}A& =\{0,1,2,3,4\}\\ B& =\{1,2,3\}\end{array}$$

a. $\{(a,b)\in A\times B|a+b=4\}$

$\{(1,3),(2,2),(3,1)\}$

b. $\{(a,b)\in A\times B|a=b\}$

$\{(1,1),(2,2),(3,3)\}$

b. $\{(a,b)\in A\times B|a>b\}$

$\{(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)\}$

title:
Correct answer.

2.9

For each of the following relations on the set $\{1,2,3,4\}$, decide whether it is reflexive, and / or irreflexive, and / or symmetric, and / or antisymmetric, and / or transitive:

a. $\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$

digraph G {
	1
	2->2
	2->3
	2->4
	3->2
	3->3
	3->4
}

Reflexive: No Irreflexive: No Symmetric: No Antisymmetric: No Transitive: Yes

title:
Correct answer.

b. $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$

digraph G {
	1->1
	1->2
	2->1
	2->2
	3->3
	4->4
}

Reflexive: Yes Irreflexive: No Symmetric: Yes Antisymmetric: No Transitive: Yes

title:
Partially correct answer.
Made mistake on symmetric, they are indeed symmetric.

c. $\{(2,4),(4,2)\}$

digraph G {
	1
	3
	2->4
	4->2
}

Reflexive: No Irreflexive: Yes Symmetric: Yes Antisymmetric: No Transitive: No

title:
Partially correct answer.
Apparently not transitive though.

2.10

Take the relation in 2.9(a), $\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$.

a. Represent as directed graph.

digraph G {
	1
	2->2
	2->3
	2->4
	3->2
	3->3
	3->4
}

title:
Correct answer.
Remember to include the entire domain, e.g. stray `1`.

b. Represent it by a matrix, with elements of $\{1,2,3,4\}$ listed as $1,2,3,4$.

$$\begin{array}{cc}& \begin{array}{cccc}1& 2& 3& 4\end{array}\\ \begin{array}{c}1\\ 2\\ 3\\ 4\end{array}& \left[\begin{array}{cccc}0& 0& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\\ 0& 0& 0& 0\end{array}\right]\end{array}$$

title:
Correct answer.

b. Represent it by a matrix, with elements of $\{1,2,3,4\}$ listed as $1,4,3,2$.

$$\begin{array}{cc}& \begin{array}{cccc}1& 4& 3& 2\end{array}\\ \begin{array}{c}1\\ 4\\ 3\\ 2\end{array}& \left[\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right]\end{array}$$

title:
Correct answer.

2.11

Consider the following matrix:

$$\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 1\end{array}\right]$$

Does this matrix represent any of the relations in 2.9a-c?

It can repesent 2.9b if we list as $\{1,3,4,2\}$.

title:
Correct answer.

2.12

Take the following relation $R$ on the set $\{a,b,c\}$:

$$R=\{(a,b),(a,c),(b,b),(c,a),(c,b)\}$$

Represent $R$ by a matrix (with elements of $\{a,b,c\}$ listed as $a,b,c$) and use Warshall’s algorithm to determine the transitive closure $R^{\ast }$ of $R$. Show working.

$$M_0=\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 1& 1& 0\end{array}\right]$$

Round 1:

$$M_1=\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 1& 1& 1\end{array}\right]$$

Round 2:

$$M_2=\left[\begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 1& 1& 1\end{array}\right]$$

Round 3:

$$M_3=\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 0\\ 1& 1& 1\end{array}\right]$$

Hence $R^{\ast }=\{(a,a),(a,b),(a,c),(b,b),(c,a),(c,b),(c,c)\}$.

digraph A {
	label = "R"
	a->b,c
	b->b
	c->a,b
}
 
digraph B {
	label = "R*"
	a->a,b,c
	b->b
	c->a,b,c
}

title:
Correct answer.

2.13

Consider the divisibility relation on the set $\{1,2,3,6,12,24,36,48\}$.

a. Describe by listing ordered pairs.

$(1,1),(1,2),(1,3),(1,6),(1,12),(1,24),(1,36),(1,48),(2,6),(2,12),(2,24),(2,36),(2,48)$ $(3,6),(3,12),(3,24),(3,36),(3,48),(6,12),(6,24),(6,36),(6,48)$ $(12,24),(12,36),(12,48),(24,48)$

title:
Correct answer.

b. Draw the Hasse diagram of the relation.

digraph G {
	1->2,3,6,12,24,36,48
	2->6,12,24,36,48
	3->6,12,24,36,48
	6->12,24,36
	12->24,36,48
	24->48
}

graph G {
	rankdir = BT
 
	1--2,3
	2--6
	3--6
	6--12
	12--24,36
	24--48
}

title:
Correct answer.