Question

(a) Let A and B be countably infinite sets. Decide whether the following are true for all, some (but not all), or no such sets, and give reasons for your answers.  A ∪B is countably infinite  A ∩B is countably infinite  A\B is countably infinite, where A ∖ B = { x | x ∈ A ∧ X ∉ B }. (b) Let F be the set of all total unary functions f : N → N and FC the set of all total unary computable functions f : N → N.  Show that the set FC is countably infinite.  Is the set F\FC also countably infinite? Give reasons for your answers. 1 Mark per bullet point.

Answer 1

1) is always countably infinite

can be defined as and where are the bijections from N to A, B respectively

2) is possible and so is so this statement can be true or false

3) can be empty set or A itself so this statement can also be true or false