Assignment 1

This assignment has to be solved individually and handed in using the fire system before Monday 9 Nov.

The system is available at https://fire.cs.chalmers.se:8018/cgi-bin/Fire

1. You can define a function f : A -› B to be surjective if for all y : B there exists an x : A such that f(x) = y. Or in predicate logic (forall y:B)(exists x:A) f(x)=y. The all-quantifier (upside A) is written as "forall" and the backward E is written "exists". Define the following properties of functions with the same level of formality: injective, total and partial.

2. Is the set of positive rational numbers enumerable? Motivate your answer with a proof. Remember that 2/4 = 1/2!

3. Show first that the set of C-programs are enumerable! You can use the fact that a subset of an enumerable set is enumerable. Explain then why this shows that some functions in N -> N cannot be expressed by a program in your favorite programming language. We assume that the set N is correctly represented as an integer in the programming language (so we ignore overflow etc).