# Michael Sipser Edition 3 Exercise 4 Question 9 (Page No. 211)

35 views
Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.

## Related questions

1
25 views
Let $T = \{(i, j, k)\mid i, j, k \in N \}$. Show that $T$ is countable.
Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.