T Naughton, NUIM
Back to CS403/SE307/CS355 home

Lab 3 - Countable and uncountable sets - Group A

First, find out what team you are in here and go to the space allocated for your team. If you do not have a team, or are not scheduled for this lab, then please wait at the whiteboard and you will be seated presently.

The object of this lab is to work in teams to prove or disprove certain assertions. The team will also be asked to provide specific examples and to comment on various consequences of their proofs. One team member will then make a very short presentation of the team's results to the entire lab. It will be important for each team to ensure that nobody is left behind in the group discussions, as explained next.

At 3pm, each team will submit a 1-page (single-sided) written presentation containing its proof(s), example(s), and comment(s). Your page will be photocopied onto a transparency and you will use this in your presentation (so write with a dark pen and make sure all illustrations are clear). A single person will be chosen randomly from the team to give the presentation. Presentations will last no more than 3 minutes each. All team members will receive the same mark. The assessment will be based on an equal weighting of (i) the quality of the written submission, and (ii) how well the randomly chosen presenter convinces the demonstrators that they understand the group's submission. Presentation skills (or lack of same) will not be taken into account in the assesment, so don't worry if you're nervous!

Your proof(s) can be very high level pseudocode algorithms or even a diagram if it is expressive enough. Also, try not to clutter the page with minor details that you could easily explain in your presentation.

You may use your lecture notes (and Sipser's book, if you have it) but no other material (including WWW material) for this lab.

Problem 1. Prove that the union of a finite number of countable sets is a countable set. Your proof should consist of a sequence of steps that will enumerate the union of k countable sets, for any k . It does not matter if you include the same element multiple times in your enumeration (because this is a set we're talking about) just don't leave any out.