# Phil 455: Homework 3

This homework is due by the end of the day on Fri, Feb 9.

1. What’s a more familiar name for a symmetric preorder?

2. Is the relation “is a prefix (initial substring) of” on the set of strings over an alphabet well-founded? Does it constitute a total order?

3. Examples 2 and 3 on the order webnotes were:

Example 2
`0 ⊏ 2 ⊏ 4 ⊏ ... ⊏ 1 ⊏ 3 ⊏ 5 ⊏ ...`
Example 3
`0 ⊏ 2 ⊏ 3 ⊏ 4 ⊏ 5 ⊏ ... ⊏ 1`

These are just suggestive representations of the two orderings. Specify them each more rigorously, by saying something of the form “the graph of the first relation is `{(x,y) ∈ ℕ² | blah-blah}`.”

4. Consider the order relation on elements of `ℕ²` whose graph is `{((x,y),(x′,y′)) | x ≤ x′ and y ≤ y′}`, where `≤` is the familiar less-than relation on `ℕ`. Is this order relation weakly connected? Is it well-founded? Justify your answers.

5. In Example 12 of the order webnotes, we considered the set of all strings formed from the letters `"a"` and `"b"`, ordered by the relation of being a substring of. We said that that ordering was well-founded, but not total. Consider the following, alternative ordering of these strings, which is total:

string `xs ⊏` string `ys =def` string `ys` is non-empty, and either: a. `xs` is a prefix of `ys`; or b. there are (possibly empty) strings `us`, `vs`, and `ws` such that: `xs = us ⁀ "a" ⁀ vs` (that is, `xs` is the result of concatenating string `us` to the letter `"a"` and that to the string `vs`) and `ys = us ⁀ "b" ⁀ ws`.

According to this ordering: `"a" ⊏ "aa" ⊏ "aab" ⊏ "ab" ⊏ "b"`.

This is called the lexicographic ordering of the strings, as it’s based on the way dictionaries order words. Prove that this ordering is not well-founded.

(Hint: try to add more elements into the example ordering between `aa` and `aab`.)

6. Return to the `mod` function from Homework 2 Problem 32. Let `Β` be the set `{2,3,5,6,10,15,30}` and let `R` be the relation on `Β` whose graph is `{(y,x) | x mod y = 0}`.

1. List the elements of `R` and show that it is a non-strict partial order but not a total order.
2. Identify any maximal, minimal, greatest, and/or least elements in this order.
3. Do the same as (a) and (b) but for the set 𝟚Γ, where `Γ` is `{"a","b","c"}`, and the relation is `⊆`. (Recall that 𝟚Γ means “the powerset of `Γ`.”)
7. For any set `Β`, consider the partial ordering of 𝟚Β by `⊆`. (a) Will any two elements `Γ`, `Δ` of that domain have a least upper bound or “join,” and if so, what is it? (b) Will they have a greatest lower bound or “meet,” and if so, what is it? (c) Does this partial ordering count as a lattice? If so, say whether it has a top and/or bottom element.

8. Consider the following diagrams of posets (with `a ⊏ b` being represented by `a` being below `b` and connected by an always-upwards path). Which of these posets are lattices?

9. Consider the following acyclic ugraph with just one component:

If we designate some node as the root and impose a “precedence” order on the nodes of this graph, to turn it into a tree, which of the following sequences are ones we might end up with as fringes of the tree? Defend your answers.

1. `D, C, E`
2. `D, C, G, E`
3. `E, C, D, G`
4. `G, D, E, C`
10. Let `𝔽` be the set of finite subsets of `ℕ`. Prove that `𝔽` is countably infinite, that is, that `|𝔽| = |ℕ|`.

11. Let `𝕀` be the set of infinite subsets of `ℕ` (that is, 𝕀 = 𝟚 – 𝔽). `𝕀` itself is uncountable (whenever you take away a countable set like `𝔽` from an uncountable set like 𝟚, the result will still be uncountable). But specify a countably infinite subset of `𝕀`, and justify your claim that it is countably infinite.