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

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

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?

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}`

.”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.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`

.)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}`

.- List the elements of
`R`

and show that it is a non-strict partial order but not a total order. - Identify any maximal, minimal, greatest, and/or least elements in this order.
- 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`Γ`

.”)

- List the elements of
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.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?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.

`D, C, E`

`D, C, G, E`

`E, C, D, G`

`G, D, E, C`

Let

`𝔽`

be the set of finite subsets of`ℕ`

. Prove that`𝔽`

is countably infinite, that is, that`|𝔽| = |ℕ|`

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