SUNY Geneseo Department of Mathematics
Misc
Math Learning Center
Extended hours during finals: open at 9:30 each morning from May 3 through May 10, plus 1:00 - 3:30 and 7:30 - 9:30 Sunday.
Review Session
1:00 - 2:00 PM Wednesday, in our regular room.
Final Exam
Wednesday, May 10, 12:00 noon, in our regular classroom.
Comprehensive, but emphasizes material since second hour exam (e.g., set theory, functions, equivalence relations, infinite cardinalities, etc.)
Designed for about 1 1/2 hours, you’ll have 2 1/2.
There will be one closed-book question at the beginning of the test, then the rest will be open-book (and open-notes, open-computer, etc.)
Otherwise the rules and format will be similar to the hour exams.
I’ll bring donuts and cider.
SOFIs
5 responses as of this morning — thank you to the five.
Questions?
Practical Countability
Some definitions (which you might remember from problem set 3):
- An alphabet is a finite set. The members of an alphabet are called symbols.
- If A is an alphabet, a string over A is a finite sequence of symbols from A.
- For example, if alphabet A = {a,b,c}, strings over A include a, b, c, aa, ab, ba, aaaabbabababaabbbaccaab, empty string.
How many strings are there over any finite alphabet?
- A countably infinite quantity.
- Proof 1: enumerate strings over an n-symbol alphabet:
- empty string: 1
- all 1-symbol strings: 2 .. n+1
- all 2-symbol strings: n+2 .. (n+1)+n2
- all 3-symbol strings: n+2+ n2 .. (n+1+ n2) + n3
- etc.
- This enumeration assigns a unique natural number to every string, so it’s a bijection, showing that the set of strings is equivalent to ℕ.
- A little less rigorous: think of strings as base-(n+1) numbers: the first symbol of the alphabet is represented by 1, the second symbol by 2, etc.
- For example, with alphabet {a,b,c} abbca would be represented as 12231.
- This clearly associates each string with a unique natural number, but doesn’t use all the naturals. So the set of strings is equivalent to a subset of the naturals and so must be countable; a separate proof shows that the set of strings is infinite. That separate proof could, for example, point out that for every natural number n, the string consisting of n a’s is a finite string.
Is the set of functions from ℕ to ℕ countable or uncountable?
- Hint: define the characteristic function for a set: let U be some universal set, and A a subset of U, then the characteristic function for A = f : U → {0,1} is defined by f(x) = 1 if and only if x ∈ A
- Every subset of ℕ has a characteristic function f: ℕ → ℕ. And the power set of ℕ is uncountable, so the set of functions from ℕ to ℕ has an uncountable subset and so must be uncountable.
Which are there “more” of, things you might want to calculate with a computer program, or computer programs to calculate them? (A little more accurately, is it possible to associate a distinct program with each thing you might want to calculate with a program?)
- There are necessarily things you might want to compute that cannot be associated with programs to compute them. Perfect virus detection (i.e., a program that always answers the question “will this new program infect my computer with a virus if I run it?”) is an example of an important problem with no computer solution.
- Another corollary is that much as you might believe from earlier math courses that you can write down a definition for every function, e.g., “f(x) = x sinx + 39,” there aren’t enough strings to do that either.