# 1.2. What is order?

## Contents

# 1.2. What is order?#

## 1.2.1. Review of sets, relations, and functions#

In general, the term *natural numbers* is more ambiguous (see Natural number) about whether it includes zero, but this definition also apparently matches an ISO defintion.

*Exercise* 1.10#

Reveal answer

See also Disjoint union.

*Exercise* 1.11#

An alternative solution:

{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

\({1} \cup {2} = \{1,2\}\)

(h,1), (h,2), (h,3), (1,1), (1,2), (1,3)

(h,1), (1,1), (1,2), (2,2), (3,2)

h, 1, 2, 3

Reveal answer

### Partitions and equivalence relations#

*Exercise* 1.16.#

A shorter answer than the authorâ€™s:

If there were more than one, then the first and second \(p'\) would share elements.

If there were not at least one, then the \(p\) would not partition the original set.

Reveal answer

*Exercise* 1.17.#

Reveal answer

*Exercise* 1.20.#

A shorter answer than the authorâ€™s:

The definition of a \((\sim)\)-connected subset includes that it is nonempty.

Consider the Contraposition. If the union of the two sets was not empty, then there would be some element in both. If that was the case then the \((\sim)\)-connected property would have unified the two sets.

Every element of \(A\) must end up in at least one partition. Even if it was equivalent to no other element in the set, it would form a \((\sim)\)-connected and \((\sim)\)-closed subset on its own.

Reveal answer

### Functions#

*Exercise* 1.24.#

An alternative solution:

\(A = \{1\}\) and \(B = \{a,b\}\), with \(F(1) = b\)

\(B = \{1\}\) and \(A = \{a,b\}\), with \(F(a) = 1\) and \(F(b) = 1\)

Yes, No, No, Yes

Not injective or surjective, not because one domain element maps to two different codomain elements, not because one domain element does not map to any codomain element, bijective.

Reveal answer

*Exercise* 1.25.#

\(A\) is empty because every domain element must map to one codomain element, and there are no codomain elements.

Reveal answer

Not the same as Function (mathematics) Â§ Empty function (sometimes called the â€śunique functionâ€ť by the author), unless the target is also the empty set.

*Exercise* 1.27.#

In reading order (top to bottom, left to right):

\(F(\bullet) = a\), \(F(\circ) = a\), \(F(\ast) = a\)

\(F(\bullet) = a\), \(F(\circ) = a\), \(F(\ast) = b\)

\(F(\bullet) = a\), \(F(\circ) = b\), \(F(\ast) = a\)

\(F(\bullet) = a\), \(F(\circ) = b\), \(F(\ast) = b\)

\(F(\bullet) = a\), \(F(\circ) = b\), \(F(\ast) = c\)

Reveal answer

## 1.2.2. Preorders#

See also Preorder.

See also Discrete category.

See also Skeleton (category theory).

*Exercise* 1.38.#

Reveal answer

*Exercise* 1.40.#

Reveal answer

*Exercise* 1.41.#

Yes, as long as there is an implicit reflexive relationship.

Reveal answer

*Exercise* 1.42.#

There are 5 relations of an element with itself, 3 relations between the first and second rank, 3 relations between the second and third rank, and 1 between the first and third. For the meaning of the word â€śrankâ€ť here see Attributes | Graphviz.

Reveal answer

*Exercise* 1.44.#

Technically no because you can compare elements to themselves.

Reveal answer

*Exercise* 1.46.#

Reveal answer

*Exercise* 1.48.#

Reveal answer

*Exercise* 1.51#

The Hasse diagram for \(P(\varnothing)\) is trivial; there are no subsets. The Hasse diagram for \(P\{1\}\) and \(P\{1,2\}\) are:

Reveal answer

*Example* 1.52#

The author is defining \(Prt(A)\), which is rather unclear initially. In the second paragraph, notice the definition allows for \(P\) to be equivalent to \(Q\) (both finer and coarser?) if \(h\) is an injective/bijective function. If \(h\) is surjective, then you would get the arguably more natural (strict) definition of fine and coarse.

*Exercise* 1.53.#

The coarsest partition corresponds to a function with a codomain of one element. The finest partition corresponds to an identity function, where every unique element gets its own partition.

Reveal answer

*Example* 1.54.#

This example and the following questions have multiple issues. Letâ€™s repeat (đť”ą,â‰¤) (the boolean preorder); notice these are not sets:

To be clear, the set đť”ą is {true,false}. An error in Exercise 1.65 makes it clear the author intended readers to compute the power set of đť”ą as part of Exercise 1.51:

Letâ€™s draw a box around these four subsets in the power set in the original boolean preorder:

The authorâ€™s definition of an â€śupper setâ€ť is any of these 4 sets (call each \(U\)) where if \(p \in U\) and \(p \leq q\), then \(q \in U\). He intends us to go through all four of these sets and check if this definition holds for them. The primary issue with this example is that his definition is just plain wrong. Consider the definition applied to the \(\{false\}\) set (calling it \(U\)); the author is claiming that this set is an upper set if \(false \in \{false\}\) in and \(false \leq q\), then \(q \in U\). When does the author even define \(q\)? If we define \(q\) to be \(\{false\}\) then thereâ€™s nothing wrong with this set.

To avoid reverse-engineering the definition from the authorâ€™s explanation of why \(\{false\}\) is not an upper set, see Upper set. Using the variables that the author uses rather than Wikipediaâ€™s, the definition of an upper set is then a set where for all \(q \in U\) and \(p \in P\), if \(q \leq p\), then \(p \in U\). An even better definition for this context is that an upper set is a set where for all \(u \in U\) and \(p \in P\), if \(u \leq p\), then \(p \in U\). With either of these new definitions, the authorâ€™s explanation of why \(\{false\}\) is not an upper set makes sense.

*Exercise* 1.55.#

A discrete preorder has no relationship between any elements, so every element on its own is an upper set. Adding a second element to any of these sets also creates an upper set, because again there is no relationship between elements. You can continue this with a third and fourth element, in any order, constructing in the end all of the possible subsets of \(X\).

Reveal answer

*Exercise* 1.57.#

The issues this question has are covered in order theory - Understanding upper set preorders - Math SE and multiple comments in the errata.

The authorâ€™s incorrect answer:

Reveal answer

## 1.2.3. Monotone maps#

See also Monotonic function.

*Exercise* 1.63.#

Taking step `1.`

from Example 1.50:

Reveal answer

*Exercise* 1.65.#

Reveal answer

*Exercise* 1.66.#

This question is a notational nightmare; see notation - Making sense of a map, given a new domain and codomain - Math SE for someone elseâ€™s helpful comments on it.

In `1.`

letâ€™s call the â†‘ operator the â€śupper closureâ€ť of an element \(p\) in \(P\) (following the
language in Upper set). The definition constructs an
upper set because it includes in its construction all elements that make \(p\) satisfy the
requirements of being an element of an upper set. Because the ordering relationship is transitive,
any other element included in the set by this construction will also have the requirements for it to
be an element of an upper set satisfied.

Part `2.`

of the question introduces the notation \(P^{op}\) out of nowhere to refer to the opposite
preorder; see this notation used in Duality (order theory) and Opposite
category.

The given construction will map every element \(p \in P^{op}\) to a set \(s \in U(P)\) where \(s\) is an â€śupperâ€ť set that includes \(p\). With respect to \(P^{op}\) this set will be the opposite of an â€śupperâ€ť set; what weâ€™ll call a â€ślowerâ€ť set with respect to \(p\).

Remove the first â€śifâ€ť from part `3.`

of the question to make it understandable/readable. To prove
the forward case, letâ€™s use the definition in `1.`

:

So if \(p \leq p'\) we have by direct proof that:

The opposite implication is left as an exercise for the reader.

Part `4.`

of this question should refer to Exercise 1.57 rather than Example 1.56:

Reveal answer

See also Yoneda lemma.

*Exercise* 1.67.#

The monotonicity requirement is that for all \(x,y \in A\), if \(x \leq_{A} y\) then \(f(x) \leq_B f(y)\). The condition of the if statement is always false for a discrete preorder, so any function will satisfy it.

Reveal answer

*Exercise* 1.69.#

Define the sets \(X\) and \(Y\):

Define the surjective function \(f\):

See Partition of a set for notation. Two different partitions \(P\) and \(Q\):

The composite \(fâ¨źs\) for \(P\) is:

The composite \(fâ¨źs\) for \(Q\) is:

Reveal answer

*Exercise* 1.71.#

The identity function is monotone because if \(x \leq y\) then \(id_X(x) \leq id_X(y)\).

The composition of monotone functions is monotone because if \(x \leq y\) then \(f;g(x) \leq f;g(y)\).

Reveal answer

*Exercise* 1.73.#

Calling a preorder skeletal removes all equivalence sets (partitions), making every element its own equivalence set (partition). This is a discrete preorder.

See also Dagger category.

Reveal answer

*Definition* 1.75.#

See also Order isomorphism.

*Exercise* 1.77.#

The function:

The preorder:

By substitution:

Reveal answer

*Exercise* 1.79.#

The function \(u\) here defines an upper set by labeling all elements of \(Q\) as either belonging to it or not. The composition \(f;u\) can then be understood as mapping an element of \(P\) to an element in \(Q\), and again labeling it as belonging to the upper set or not.

Reveal answer