Phil 455: Homework 5 (on Morphisms, Cardinality)

This homework won’t be due until the end of the day on Friday (when Homework 6 is also due), and I’ll be especially flexible this time about late submissions. Do communicate with me though about when you will be able to get the homework in. As always, if you need help with Problems, you are welcome to ask about them in class or office hours, as well as to work out solutions together.

(More on properties of relations.)
1. If a relation is transitive and reflexive, must it be symmetric?
2. If a relation is transitive and irreflexive, must it be asymmetric?
3. If a relation is transitive and symmetric, must it be reflexive?
4. If a relation is asymmetric, must it be irreflexive?
5. What’s the difference betweem a pre/quasiorder and a partial order?
6. What’s a more familiar name for a symmetric pre/quasiorder?
7. What is the equivalence class of Chloe under the relation “has the same height as”?
8. Is the relation “is at least as old as” symmetric, anti-symmetric, or asymmetric?
9. Is the relation “is a brother of” symmetric?
A meet homomorphism is a total function f between meet semilattices such that for all elements x, y of the first semilattice, the meet in the second semilattice of f(x) and f(y) is identical to f(x ∧ y) (where ∧ is the meet operation of the first semilattice). The notion of a join homomorphism is defined analogously.

Specify (by drawing a diagram or otherwise) a meet homomorphism from a 4-element lattice to a 3-element total order. Does the function you provide also constitute a join homomorphism? Why or why not?

In class on Monday, I suggested that this problem may be relying on the fact that sometimes homomorphisms aren’t required to be surjective. Later I realized this is not so. It’s possible to solve this with a surjective homomorphism. Try to do so. If you can’t, then give a non-surjective homomorphism.
In Homework 4 Problem 7b, you showed that multiplication mod 7 on the domain {1,2,3,4,5,6} constituted a group. Find a set of numbers that form a group with addition mod some n, where this group is isomorphic to the one from the earlier problem. Specify the isomorphism.
Back in Homework 2 Problem 12, your considered a function f whose domain and codomain were the same finite set Α, and explained why (a) f’s being injective implied it was also surjective, and why (b) f’s being surjective implied it was also injective. Are (a) and/or (b) still true when Α is an infinite set? If not, given examples. Either way, justify your answer.
Prove that the set of pairs {(x,y) | x ∈ ℕ and y ∈ ℕ} has the same cardinality as the set of strings made from the letters "a" and "b" that never have an "a" occurring after a "b".
Here is an example proof that any infinite subset Β of a countably infinite set Α is itself countable. If Α is countably infinite, then there is an enumeration a₀, a₁, … a_k, … of its members, with k ∈ ℕ. Each member of Α appears (at least) once in this enumeration. The members of Β can then also be enumerated b₀, b₁, … b_i, …, where intuitively we take them in the same order as the Αs, skipping members of Α that aren’t in Β.

More precisely: For every i ∈ ℕ, let Γ_i be {a_k | a_k ∈ Β and ∀ j < i (b_j ≠ a_k)}. This set will always be non-empty, since for each i there must be infinitely many members of Β that haven’t yet been enumerated, and each of them will also be in Α and so correspond to some one (or more) a_k. Since the indices k are ∈ ℕ, there will be a least k where a_k ∈ Γ_i. Define b_i to be that a_k. Observe that the Γ_is are constructed so that Γ_i+1 will be Γ_i — {b_i}. Each is a proper subset of its predecessors. We know every b ∈ Β will be included in this enumeration, because it will correspond to some a_k, and for each a_k ∈ Β, there can be only finitely many a_k′ ∈ Β with k′ < k. Since the Γs keep taking away these lesser a_k′s, and never add new elements, there must be some Γ_i where a_k is the element with the least k. Then b = b_i.

What this proof did was: (a) offered an enumeration of the Βs; (b) showed that each b_i of the enumeration was well-defined (we did that by showing that Γ_i was non-empty and that it would have an element with the the “least” index k); and (c) showed that every member b ∈ Β would be included in the enumeration.

Give a proof that the union of any two countably infinite sets Α and Δ will itself be countable.
Let 𝟛 be the set {0,1,2}. Prove that the set of all total functions from ℕ → 𝟛 is not countable.
Here is a presentation of the proof that the powerset of a set Β always has a larger cardinality than set Β does. The presentation has some gaps/questions in it, which you need to fill in.

Let Γ = 𝟚^Β, and suppose for reductio that Γ is no larger than Β. Then by definition of “no larger than” for sets, there must be a total function f: Γ → Β that’s injective. (Explain what this consequence amounts to.) The members of Γ will be sets Α ⊆ Β. For each such Α, f(Α) will be some b ∈ Β, and either b ∈ Α or b ∉ Α. In the first case, call Α “happy”, else call Α “unhappy.” Every Α is either happy or unhappy, and is never both. (Why?)

Now let Δ be the image under f of all the unhappy members of Γ, that is, the set {b ∈ Β | ∃Α ∈ Γ (f(Α) = b and b ∉ Α)}. Δ is a member of Β’s powerset Γ (Why?), so Δ must be either happy or unhappy.

Suppose Δ is happy; then f(Δ) ∈ Δ. (Why?) But by definition of Δ, it includes only those f(Α) where Α is unhappy. So Δ is unhappy.

Suppose Δ is unhappy; then f(Δ) must be ∈ Δ. (Why?) But if f(Δ) ∈ Δ, then by definition of “happy”, Δ is happy.

So Δ is happy iff Δ is unhappy. But as we said, no member of Γ can be both happy and unhappy.

So our supposition that there is such a total injective function f fails. So the powerset Γ of Β must after all be larger than Β.

In addition to answering all the parenthetical questions in this proof, there is a step in the proof that implicitly relied on f’s being an injection, and would fail if we weren’t allowed to rely on that. Identify what step in the proof this is, and explain why f’s being an injection justifies it.

Homework 6 (on Grammars, Formal Languages, Automata, Decidability)

Consider an alphabet consisting of just the three letters {"a","b","c"}.
1. How many finite strings can be formed from that alphabet? — It won’t be enough to say “infinitely many.” Specify the cardinality more precisely. You could do that by saying ℶ_n for a specific n, or by saying “countably infinite” for ℶ₀ (if that’s the right answer), or by saying “the same size as ℕ, or ℝ, or …” (specifying whichever other set has the same cardinality).
2. Recalling the definition of a “formal language” as a set of sentences, how many formal languages are there whose sentences are formed from that alphabet? (Same expectations apply.)
1. Could we in principle specify each of those formal languages using finitely long sentences made from a finite vocabulary (for example, using formal grammars as in the Problems below, or with some other technique)? Justify your answer.
Is the formal language {empty} the same or different from the formal language ∅? Explain your answer.
Here is a formal grammar:

S ⟶ “a” ⁀ S ⁀ “a” S ⟶ “b” ⁀ S ⁀ “b” S ⟶ empty

Describe in English what set of strings it generates. Extra credit: is this grammar “regular”?
Here is a pattern describing a set of strings: (a|b)*a. Describe those strings in English. Write a formal grammar like the one in Problem 3 that generates those strings with no “shortcuts” (like | or *).
Here is one pattern: (a|empty)*. Here is another: a*. Do these describe the same language? Justify your answer. If they don’t, give an example of a string that belongs to one of the languages but not the other.
Here is one pattern: (a|b)*. Here is another: a*|b*. Do these describe the same language? Justify your answer. If they don’t, give an example of a string that belongs to one of the languages but not the other.
Is every sentence produced by the following grammar a well-formed and meaningful sentence of English? If not, can you give a counter-example? Either way, justify your answer.

sentence ⟶ noun ⁀ “fish” | noun ⁀ “fish” ⁀ noun noun ⟶ “fish” | “fish” ⁀ noun ⁀ “fish”
A function f: ℕ → ℕ is monotonically increasing iff for any x, y ∈ ℕ, if x < y then f(x) < f(y). Suppose g is such a function that is also effectively computable/calculable.
1. Does it follow that the range of g (the subset of ℕ whose members are g’s value for some argument) will be effectively decidable? Justify your answer.
2. For any decidable subset Δ of ℕ, must there always be some such g (an effectively computable, monotonically increasing function g: ℕ → ℕ whose range is Δ)? Why or why not?
In our first classes, we recursively defined the factorial function, using our dissect apparatus. Later we recursively defined other functions that operated on strings instead of numbers. Here’s a variation of one of those string functions, from Homework 1 Problem 3. (The changed parts are italicized.)

take0 (hs, n) =def dissect hs { λ xs if n = 0! empty; λ empty. "0" ⁀ take0(empty, n-1); λ ys ⁀ xs if letter(ys). ys ⁀ take0(xs, n-1) }

The original function take returned empty when you requested more letters than hs had to provide, but with this variant we instead return "0"s as the missing letters. So take("21", 4) would be "21", but take0("21", 4) would be "2100".

In this problem, we’re going to define a multiplication function on natural numbers, but instead of doing it in the style of our factorial definition, where we worked with the numbers directly, we’re going to work instead with numbers encoded as strings of digits. We could work with the decimal/base-10 encoding of numbers into strings of digits, which you’ll be most familiar with, but that would make this exercise longer and more tedious than it needs to be. It’d be more concise to work with, for example, a binary/base-2 number system: then the encoded numbers would be longer, but the functions we wrote to operate on them would be much shorter. The binary system might be a bit too economical, though. Its simplicity may conceal some of what’s going on. So we’ll compromise and work with a “ternary” or base-3 number system. What that means is this. In decimal, the digits range from "0" through "9", and one of the “places” in the string represents “how many ones?”, another represents “how many tens?”, another “how many hundreds?” and so on. In a ternary encoding, on the other hand, the digits only range from "0" through "2". As before, one of the “places” in the string represents “how many ones?”, but another now represents “how many threes?”, another “how many nines?” and so on.

Another twist is that, in the collection of string functions we’ve already accumulated, they work from the string’s left side. (That is, take("21010", 2) is "21", not "10".) It will be convenient for this problem to have our numbers encoded correspondingly. We’d like the smallest position, the digit that represents “how many ones?” to come on the left side of the string, and the digit that represents the biggest value to come on the right side of the string. Thus, the number nineteen = 2⋅nine + 0⋅three + 1⋅one would be encoded as "102".
1. With this encoding, what is the numerical value of the string "21"? (Give your answer in decimal or write it out in English.)
2. What is the numerical value of the string "12"?
3. How would you encode the number fifteen in this system?
4. If xs encodes the number n in this system, what does "0" ⁀ xs encode?
5. What does xs ⁀ "0" encode?
Here is the “scratch work” for a multiplication with decimal digits:
```
   19
✕  14
-----
   76
+ 19␣
-----
  266
```
Here is the same multiplication in our ternary, left-to-right number system:
```
102
211   ✕
-------
2011
␣102
␣␣102 +
-------
212001
```
We’re going to specify some recursive functions that perform this computation. One function mulRow will use the top number ("102") and extract the leftmost digit of the second number ("2") to calculate the first scratch row ("2011"). Then since there are still more digits of the second number to process, it will call mulRow again to handle those remaining. When we call mulRow the second time, one of our inputs will again be the top number ("102"), another will be the remaining digits of the second number ("11"), another will be the sum of all the scratch rows we’ve generated so far (at this point, that’s just "2011"), and finally we have to keep track of the fact that the next scratch row should be shifted one digit to the right.

We keep going in this way until we’ve handled all the digits of the second number.

We’re not going to calculate each of the rows "2011", "␣102", and "␣␣102" and only add them up at the end. It will be easier to add them as we go, instead. So our calculation actually looks more like this:
```
102
211   ✕
-------
2011
␣102  +
-------
21101
␣␣102 +
-------
212001
```
We are building up to the final result, first getting "2011" from multiplying the leftmost digit "2" of our second argument, next getting "21101" from multiplying the second digit and adding to the result from the previous step as we go, and finally getting "212001" from mutiplying the last digit and adding to the result from the previous step. We’ll call the first argument of our multiplication ("102") the xs digits, the second argument ("211") the ys digits, and the results we get at each of the steps just described the zs digits.

Our function for generating each of these results will look like this:
```
mulRow(xs, ys, zs, shift) =def dissect ys {
    empty. zs;
    w ⁀ ws if digit(w). mulRow(xs, ws, take0(zs, shift) ⁀ mulCol(...), shift + 1)
}
```
digit is a function that returns true for "0", "1", "2", and for no other arguments.

The role of the expression take0(zs, shift) ⁀ mulCol(...) is to calculate each of the results we mentioned: first "2011", then "21101", then "212001". We’ll discuss how it works in a moment. But assuming that we specify this correctly, then we can request the multiplication of two numbers xs and ys encoded in our system as mulRow(xs, ys, "0", 0). The "0" is what we use as the “previous zs value” at the start of the computation. The function we end up building will actually let you pass in empty strings for xs or ys or zs, treating them as equivalent to "0". You could check for and block that if you wanted to, but we won’t do so.

The shift argument keeps track of how many positions to the right the multiplication should be shifted as we handle each digit in ys. Our take0(zs, shift) ⁀ ... amounts to just carrying the initial shift digits of the previous zs through to the next zs.

You’ll notice that I haven’t supplied the arguments to the invocation of the mulCol function. As you’ll see, that will be your job.

How does this function mulCol work? It needs to know what the top number to multiply is (in our example, "102"), and also what digit of the second number it’s working with (so first we invoke it with "2", then with "1", then with "1" again). It needs to have some part of the previous zs value to add to the multiplication results to get the next zs value. Finally, it could turn out as we add up each column to obtain the new zs value that some of our results need to carry into the next column. For example, when processing the second digit of ys, we end up in the rightmost column adding a "1" and a "2". There is no "3" digit in our numbering system; instead we have to get a result of "0" with a "1" carried to the next column. To keep track of this, mulCol will also take an argument that represents any pending carries that need to be included.

So our mulCol function will look like this:
```
mulCol(xs, y, zs, carry) =def dissect xs {
    empty. addCarry(zs, carry);
    u ⁀ us if digit(u). dissect mulDigit(u, y, take0(zs, 1), carry) {
        c1 ^ c2 if digit(c1). c1 ⁀ mulCol(...)
    }
}
```
This calls two auxiliary functions, addCarry and mulDigit. The first of these adds the single carry digit to the string zs, returning a new version of zs (which will be either the same length or a single digit longer). The second of these takes four single-digit arguments, u, y, z and carry, and returns the two-digit result of multiplying u⋅y and adding to z and carry. For example, mulDigit("2", "2", "2", "1") returns the two-digit encoding "12" of seven. If you want to see definitions of these functions, I’ve provided them; but the details aren’t important. You can rely on them behaving as here described.
1. At two places above — once in the definition of mulRow and then again in the definition of mulCol — the function mulCol was invoked but I left the arguments unspecified. Demonstrate you understand how these functions are working by filling in those …s.
  
  Hint: you may want to make use of take0 and/or other string functions we defined in Homework 1.