Phil 455: Homework 3

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

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

35. 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?

36. 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}.”

37. 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.

38. 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.)

39. 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 Γ.”)

40. 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.

41. 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?

    

42. 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

43. Let 𝔽 be the set of finite subsets of ℕ. Prove that 𝔽 is countably infinite, that is, that |𝔽| = |ℕ|.

44. 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.