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

Lab 3 - Countable and uncountable sets - Group B

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. The cross product of two sets A and B, denoted A B, is the set of all possible 2-tuples, or pairs, (a, b) where a A and b B.

For example, let A = {a, b, c} and let B = {1, 2}. Then A B = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}. If A and B are finite then A B is finite (in fact it will contain exactly |A|.|B| elements where | | denotes cardinality). It is also true that if A and B are infinite then A B is infinite. But can we be more specific about what cardinality of infinity (countable or uncountable)... if A and B are countable can we say that A B is countable? Your answer to this problem (you don't need to prove it) will be one of the following choices: Sometimes, Always, or Never.

Problem 2. Let _w be the set of whole complex numbers. For example, 5-3i, -2+7i, and 0+7i are whole complex numbers, whereas 1.5+7i is a complex number but not a whole complex number. The set _w could be regarded as having the same cardinality as the a cross product because each whole complex number is just a different pair of integers. Prove that _w is a countable set.

Your proof should consist of a sequence of steps that will enumerate _w. 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.

Your proof could also take the form of a diagram, if you wanted.

Last week, students came up with the following method (below) of enumerating the union of a finite number of countable sets (3 sets in this case: the set of TMs, the set of HTML files, and the set of Java programs). Can you use their technique, or maybe a modified version of it?

Problem 3. Diagonalisation can be used to define a language that cannot be accepted/recognised by a Turing machine. How many such `uncomputable languages' can be defined using such a technique? Is it a finite, countable, or uncountable set? Justify your answer.