Different Orders (exercise sheet 6 question 1)

Question

for R2 I think:

-it is total order because all the elements can be compared and

totality: ∀x, y ∈ D. x ⊑ y ∨ y ⊑ x is valid.

-it's directed set because all the elements have upper and lower bound

-it is partial order because  it satisfies reflexivity, antisymmetry and transitivity.

-it's lattice becasue all elements have sup and inf

-it's lattice complete because all elements have sup and inf

but my solution is not correct. would you please help me?

plus I don't know the meaning of these signs: {⊥,⊤} , N+

 

Answer 1

Let's go through the definitions starting from slide 3 in the µ-calculus-chapter.

Partial order:

• reflexive/transitive: given for all of the diagrams
• anti-symmetrie: given as the diagram of R2 shows no cycle

Total order:

• as you said correctly, every element can be compared to every other (in the graph: there is a path between every pair of elements)

Bounds:

• bidirected: every pair has an upper and a lower bound (trivial for total orders. one element is the upper, one is the lower bound)
• lattice: every pair has a least upper (supremum) and a greatest lower bound (infimum) (also trivial for total orders. suppose there was a greater lower bound than the smaller element of a pair, then it would be greater than the smaller element and hence not a lower bound anymore)
• complete lattice: now every (even infinite) subset needs a greatest lower, and a least upper bound. Let's pick for example the even numbers as a subset of the natural numbers. What's their lower bound? What's their upper bound?

What do the said signs mean? Here, they have no other meaning the just elements outside the natural numbers that are added to the sets with a certain order. In general, we call ⊥ bottom,⊤ top. They typically the standard examples for lower and upper bounds.

ℕ_⊥, ℕ_⊤, ℕ₊ are just the names of the sets as defined in the diagrams. We take the natural numbers and add ⊥,⊤, or both.

Comments

how should we detect the cycle? I mean as you said R2 doesn't have a cycle and is not anti-symmetrie. but then how R3 has a cycle?
regarding what you explained, I understood it to be [1,1,0,0,0]. is it correct?