3 - Ordering Flashcards

Question

A *well-ordered* relation is both **_\_\_\_\_\_\_\_\_**_ and _**\_\_\_\_\_\_\_\__**.

Answer 1

A *well-ordered* relation is both **_well-founded (no infinite descending chains and no loops)**_ and _**linearly-ordered_**.

Answer 2

An **_ordinal_** number is a type of *well-ordering*.

Answer 3

In some sense an **_order-preserving_** function is one in which the mapped set contains or is bigger than the input set (that, is all relations are maintained)

Answer 4

If f is a *bijection* and *order-preserving* then if the input and output sets are *linear orders* then f is an **_isomorphism_**

Answer 5

if you have 2 well-orderings then there is only one such way to make a **_bijective_** map between them.

Answer 6

A **_partially ordered set**_ or _**poset_** formalizes the intuitive concept of ordering/sequencing/arrangement of elements in a set. It consists of a set together with a binary relation indicating that for *certain* pairs of elements in a set, one of the elements precedes the other in the ordering. The word **_partial_** in the name is used as an indication that not *every* pair of elements needs to be comparable (only at least one *pair* needs to be able to be compared).

Answer 7

Stricter than a partially ordered set (or a special type of poset), is a **_total order**_ otherwise known as a _**linear order**_ (or _**full order**_ or _**chain_**) which is a set in which *every pair of elements* is comparable. It exhibits the following three properties: 1) **_Antisymmetry_** : If a\<=b AND b\<=a, then a=b (eliminates uncertain cases where both a precedes b and b preceeds a) 2) **_Transitivity_** : If a\<=b AND b\<=c, then a\<=c 3) **_Connexivity / Linearity_** : a\<=b OR b\<=a (grants that any pair of elements in the set are comparable *under the relation*, ie - the set can be diagrammed as a line of elements, giving it the name linear (also implies *reflexivity*, ie - a\<=a) \*There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in a *betweenness* relation (you can define how one element is between two others, but not if one element is greater than the other, or the direction, and thus has no notion of measurement). Forgetting the location of the ends results in a *cyclic* order (still has a *direction* or *orientation*, or *comparability*, but not a start nor an end point). Forgetting both of the prior concepts results in a *separation* relation (or an unoriented circle, so just has a notion of *connectedness*).

Answer 8

A **_well-ordering_** relation on a set S is a *total order* on S with the property that *every non-empty subset* of S has a least element in this ordering (an element that is smaller than every other element in S). The set S together with this relation is then called a **_well-ordered_** set. The prototypical example of this type of set are the **_ordinals_**. \*This differs from a *total order* in that *any subset* of this set will always have a *least element*. An example of a set that is a *total order* but is not the above type of order are the **_integers_**, because there is linearity but *no least element*.

Answer 9

The **infimum** of a subset S of a partially ordered set T is the greatest element in T that is less than or equal to all elements of S, if such an element exists. Consequently, the term **greatest lower bound** (abbreviated as GLB) is also commonly used. The **_supremum_** of a subset S of a partially ordered set T is the *least element in T that is greater than or equal* to all elements of S, if such an element exists. Consequently, this is also referred to as the **_least upper bound_** (or LUB). \*The concepts of *infimum* and *supremum* are similar to *minimum* and *maximum*, but are more useful in analysis because they better characterize special sets which may have no minimum or maximum. For instance, the positive real numbers ℝ+ (not including 0) does not have a minimum, because any given element of ℝ+ could simply be divided in half resulting in a smaller number that is still in ℝ+. There is, however, exactly one infimum of the positive real numbers: 0, which is smaller than all the positive real numbers and greater than any other real number which could be used as a lower bound. Ie - These are not the same as the concepts of minima and maxima!

Answer 10

Any total order with *unique* top and bottom elements is a **_lattice_**, where the *meet* of two elements is their *infinum* and the *join* of two elements is their *supremum*. (every subset of this graph *has* to have an *infinum* and *supremum* for it to be considered a lattice)

Answer 11

The **_Cartesian Product_** of two sets A and B, denoted A X B, is the set of all combinations of ordered pairs with the first element being a member of A and the second element being a member of B.

Answer 12

x is **_transitive_** if for all y, (if y is in x, then y is a subset of x)

Answer 13

x is **_transitive_** iff for all z, for all y, (z is in y AND y is in x IMPLIES z is in x)

Answer 14

epsilon is **_epsilon-transitive_** on if for all y,z,w in x, (y is in z AND z is in w IMPLIES y is in w)

Answer 15

The *difference* between **_transitivity_** and **_epsilon-transitivity_** is that the former applies to the final object, and the latter applies to *all* relationships that are elements of the final object

Answer 16

A *partial order* or *total order* \< on a set X is said to be **_dense_** if for all x,y in X where x

there is a z in X such that x

ie - for any two elements, one less than the other, there is another element in between them

ex - Rational Numbers, Real Numbers, etc

Answer 17

Any *ordinal* is defined by the set of *ordinals* that **_precede_** it.

Answer 18

Ordinals may be used to label elements of any given well-ordered set, with the smallest element being labeled 0, the one after that a 1, then a 2, etc. The *"length"* of a set, also called its **_order type_** is the *least ordinal* that is not a label for an element of the set. The smallest infinite ordinal is called **_omega_**, which is the *order type* of the natural numbers (which can also be identified *as* the set of natural numbers itself). \*ie - After all the natural numbers comes the first infinite ordinal called *omega*, then *omega+1*, then *omega+2*....after all these comes *omegax2 (omega+omega)*, etc.

Answer 19

A **_limit ordinal_** is an *ordinal* number that is neither zero, nor a successor ordinal. Alternatively, an ordinal Lambda is a **_limit ordinal_** if there is an ordinal less than Lambda called Beta, and an ordinal Gamma such that Beta \< Gamma \< Lambda. For example, Omega, the smallest ordinal greater than every natural number is a **_limit ordinal_** because for *any* smaller ordinal, ie - for any natural number n (our Beta in this case), we can find another natural number larger than it called n+1 (our Gamma), that is still less than Omega

Answer 20

**_Transfinite Induction_** is an extension to *mathematical induction* to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Proof technique is broken down into 3 steps: 1) **Zero Case**: Prove that P(0) is true 2) **Successor Case**: Prove that for any successor ordinal alpha+1 If P(alpha), then P(alpha+1) And P(beta) for all beta \< alpha 3) **Limit Case**: Prove that for any *limit ordinal* lambda, P(lambda) follows from P(beta) for all beta \< alpha

Answer 21

**_Transfinite recursion_** is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal. Given a class function G: V → V (where V is the class of all sets), there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that F(α) = G(F Î α) for all ordinals α, where Î denotes the restriction of F's domain to ordinals \< α.