Extra questions for Chapter 1

These questions are supposed to be relatively challenging. If you can do them, you are in good shape.

1. Find two maps f, g : N → N such that f ∘ g = Id_{N} but f ∘ g ≠ g ∘ f.

2. Suppose that A is a set and that h : A → A is a map. For each natural number n, let h^{n} be the composition of n copies of h.

(a) Show that if A is finite, then there are distinct natural numbers a, b such that f^{a} = f^{b}.

(b) Consider maps from N to N. Find and describe a function g : N → N such that if a and b are distinct natural numbers, then g^{a} ≠ g^{b}.

(c) Show that you can do part [b] if N is replaced by any infinite set.

3. Let Σ = {a, b, c, …, z} be the set of lower case leters of the Roman alphabet. Let Σ^{∗} denote the set of all words (strings of finite length) using this alphabet. Thus biscuit, boooom, uqweiuqe and the empty word are all elements of Σ^{∗}. Two words are equal if and only if they are the same length, and the letters in corresponding positions are the same.

(a) How many elements of Σ^{∗} have length n where n is a natural number or 0.?

(b) How many elements of Σ^{∗} have the property that no letter occurs more than once in the word?

(c) How many elements of Σ^{∗} of length n have the property that no letter is juxtaposed to itself in the word?

(d) Impose the dictionary ordering on Σ^{∗}, so

a < b < c < ⋯ < x < y < z

is an ordering of the words of length 1. We compare two words as follows: the first is less than the second if they have the same first i letters, and the i + 1st letter of the first word is less than the i + 1st letter of the second word. In order to compare words of different lengths, we deem every word to have an invisible extra last letter which is less than all the visible lower case letters. Thus somethin < something because the invisible letter is less than g. Similarly ∅ < empty because ∅ is a word of length 0 followed by the invisible letter, but empty is a word of length 5, and the invisible letter is less than e. Finds an infinite strictly descending chain of words

w_{1} > w_{2} > w_{3} > w_{4} > …

using this ordering on Σ^{∗}.

(e) Modify the ordering of part [d] as follows. Forget all the stuff about invisible end-of-word symbols and go back to the naive view. First: say the first word is less than the second word if the first word is of shorter length than the second. Second: if two words have the same length, compare them using the ordering of part [d]. Now show that using this new ordering on Σ^{∗}, there are no infinite strictly descending sequences.

4. Find two sets A, B such that both A ∈ B and A ⊆ B.

5. Most of the time, logical quantifiers get used casually, mixed in with less formal symbols, to express statements about mathematics (or some less interesting aspect of life). In this question you must take each assertion and try to write it clearly and economically using quantifiers.

For example, the sad line from a song which is (roughly) Into each life, some rain must fall, and today some rain is falling in mine becomes

Let L be the set of all lives, let R be the set of all falling rain, and let G be the set of my lives (a singleton set in some theologies). We have that ∀l ∈ L∃s ⊆ R such that s occurs in l, and today ∃t ⊆ R such that t occurs in m where m ∈ G. Feel free to use logical connectives. You should do the best you can with:

(a) All men are equal, but some are more equal than others.

(b) All I want for Christmas are my two front teeth.

(c) There is one born every minute.

(d) No man is an island.

(e) If some trains are late then all trains are late.

(f) There is no business like show business.

(g) You can fool some of the people all of the time, and fool all of the people some of the time, but you cannot fool all of the people all of the time.

6. Let A be a set and let S = {X | X ⊆ A}. Suppose |A| = n ∈ N (this means that the set A contains exactly n elements. In this question it may help to look at some small sets A in order to help you to work out what is going on. As well as giving a formula as the answer to each of the four parts, you should attempt to prove that your answer is correct.

(a) Determine |S|.

(b) How many pairs (X_{1}, X_{2}) are there with X_{1}, X_{2} ∈ S and X_{1} ⊆ X_{2}?

(c) How many triples (X_{1}, X_{2}, X_{3}) are there with X_{1}, X_{2}, X_{3} ∈ S and X_{1} ⊆ X_{2} ⊆ X_{3}?

(d) How many r−tuples (X_{1}, …, X_{r}) are there with X_{1}, …, X_{r} ∈ S and X_{i} ⊆ X_{i+1} for all natural Numbers i in the range 1 ≤ i < r?