3 - Ordering

Question 1

< is ______\_ on A

if for all a in A, a < a

Answer 1

< is reflexive on A

if for all a in A, a < a

Question 2

a structure is ______\_ if all points have looping arrows to them

Answer 2

a structure is reflexive​ if all points have looping arrows to them

Question 3

< is _______\_

if for all a, b in A, B

a < b

iff

b < a

Answer 3

< is symmetric

if for all a, b in A, B

a < b

iff

b < a

Question 4

a structure is ______\_ if all arrows are bidirectional (also includes a single point with a self-loop)

Answer 4

a structure is symmetric if all arrows are bidirectional (also includes a single point with a self-loop)

Question 5

< is _______\_

if for all a,b,c in A

if a < b AND b < c

then a < c

Answer 5

< is transitive

if for all a,b,c in A

if a < b AND b < c

then a < c

Question 6

a structure is ______\_

if an arrow goes to an object with an arrow to something else, then that arrow also goes to that something else (also includes self-loop)

Answer 6

a structure is transitive

if an arrow goes to an object with an arrow to something else, then that arrow also goes to that something else (also includes self-loop)

Question 7

< satisfies ______\_

if for all a,b in A

ab

Answer 7

< satisfies trichotomy

if for all a,b in A

ab

Question 8

< is _________\_

if a !< a for all a in A

Answer 8

< is irreflexive

if a !< a for all a in A

Question 9

a structure is ______\_

if it has no looping arrows (which is NOT the same thing as saying it is not reflexive)

Answer 9

a structure is irreflexive

if it has no looping arrows (which is NOT the same thing as saying it is not reflexive)

Question 10

< is _______\_

if for all a,b in A

if a < b

then b!

Answer 10

< is asymmetric

if for all a,b in A

if a < b

then b!

Question 11

a structure is ______\_

if a relation exists then it is NOT a bidirectional arrow

(ie - there are no one directional arrows)

Answer 11

a structure is asymmetric

if a relation exists then it is NOT a bidirectional arrow

(ie - there are no one directional arrows)

Question 12

< is __________\_

if for all a,b in A

if a

then a=b

Answer 12

< is antisymmetric

if for all a,b in A

if a

then a=b

Question 13

a structure is _________\_

if there is an arrow coming one way

AND

there is an arrow coming the other way

then it MUST be a self-loop to the same point

Answer 13

a structure is antisymmetric

if there is an arrow coming one way

AND

there is an arrow coming the other way

then it MUST be a self-loop to the same point

Question 14

is a (strict) _____** **order of <

if < is ______**, **______**, and **_____\_

Answer 14

is a (strict) partial** **order of <

if < is transitive**, **irreflexive**, and **​asymmetric

Question 15

is a (total) _______ order of <

if < is ________, ________, and _​_______

AND

satisfies ______\_.

Answer 15

is a (total) linear order of <

if < is transitive, irreflexity, and ​asymmetric

AND

satisfies trichotomy​.

Question 16

< is well-founded if for all x as a subset of A:

1)

2)

Answer 16

< is well-founded if it:

1) x is not an empty set
2) x has an <-minimal element (no infinite descending chains)

Question 17

Which of the following are well-founded?

N, Z, Q, R, (0,1)

Answer 17

Which of the following are well-founded?

N = well-founded

Z = not well-founded (has not <-minimal element)

Q = not well-founded

R = not well-founded

(0,1) = no since you can keep dividing by 2 for any # and still not reach a minimal element

Question 18

a structure is well-ordered if

1)

2)

Answer 18

a structure is well-ordered if

1) well-founded

2) total / linear

Question 19

If f: W -> U Then we say f is _____**-**________\_

if for all x,y in W

if x < y

then f(x) <| f(y)

Answer 19

If f: W -> U Then we say f is order-preserving

if for all x,y in W

if x < y

then f(x) <| f(y)

Question 20

a function is _____**-**________\_

if there is a relation in the first set

then there is a relation in the mapped set

Answer 20

a function is order-preserving

if there is a relation in the first set

then there is a relation in the mapped set

Question 21

{<m>}_~ represents an <strong><u>\_\_\_\_\_\_\_\_\_\_</u></strong> <strong><u>\_\_\_\_\_</u></strong>.</m>

It is defined as the subset s which includes all the elements that are equivalent to each other where “equivalent” is dependent on a specific relationship called an “equivalence relationship”, defined {x in S | x~a}

Answer 21

{<m>}_~ represents an <b><u>equivalence class</u></b>.</m>

It is defined as the subset s which includes all the elements that are equivalent to each other where “equivalent” is dependent on a specific relationship called an “equivalence relationship”, defined {x in S | x~a}

Question 22

Equivalence classes form a partition** of a set S. This is the set of equivalence classes which is sometimes called the **quotient set** or **quotient space of S, denoted S/~

Question 23

To be a binary equivalence relation on a set X, it must satisfy 3 properties:

1)

2)

3)

Answer 23

To be a binary equivalence relation on a set X, it must satisfy 3 properties:

1) Reflexivity (all nodes have self-loops)
2) Symmetry (all arrows are bidirectional)
3) Transitivity

Question 24

Real numbers are defined in terms of a ________** **__\_. We define this as the infinite set of…

Answer 24

Real numbers are defined in terms of a Dedekind cut. We define this as the infinite set of points underneath the line but not including the line

Question 25

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

Answer 25

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

Question 26

An ______\_ number is a type of well-ordering.

Answer 26

An ordinal number is a type of well-ordering​.

Question 27

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

Answer 27

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)

Question 28

If f is a bijection and order-preserving

then

if the input and output sets are linear orders

then f is an ________\_

Answer 28

If f is a bijection and order-preserving

then

if the input and output sets are linear orders

then f is an isomorphism

Question 29

if you have 2 well-orderings then there is only one such way to make a bijective / injective / surjective map between them.

Answer 29

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

Question 30

A _______** **_______** **____** or **____\_ 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 _____\_ in the name is used as an indication that not every pair of elements needs to be comparable.

Answer 30

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

Question 31

Stricter than a partially ordered set (or a special type of poset), is a _____** **_____** otherwise known as a **_____** **_____** (or **____** **____** or **___\_) which is a set in which every pair of elements is comparable.

It exhibits the following three properties:

1)

2)

3)

Answer 31

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

Question 32

A ____**-**____\_ 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 ____**-**____\_ set.

The prototypical example of this type of set are the _____\_.

*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 _____\_, because there is linearity but no least element.

Answer 32

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.

Question 33

The ________ 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 _______ _____** **____\_ (abbreviated as GLB) is also commonly used.

The _________ 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 _______ _____** **______\_ (or LUB).

Answer 33

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!

Question 34

Any total order with unique top and bottom elements is a ________, where the meet of two elements is their infinum and the join of two elements is their supremum.

Answer 34

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)

Question 35

The _______** **_______\_ 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 35

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.

Question 36

x is ______\_ if

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

Answer 36

x is transitive if

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

Question 37

x is ______\_ iff

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

Answer 37

x is transitive iff

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

Question 38

epsilon is _______-________\_ on <x> if </x>

for all y,z,w in x, (y is in z AND z is in w IMPLIES y is in w)

Answer 38

epsilon is epsilon-transitive on <x> if </x>

for all y,z,w in x, (y is in z AND z is in w IMPLIES y is in w)

Question 39

The difference between _________ and ________-______\_ is that the former applies to the final object, and the latter applies to all relationships that are elements of the final object

Answer 39

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

Question 40

A partial order or total order < on a set X is said to be _____\_

if for all x,y in X where x<y></y>

<p>there is a z in X such that x<z>

<p>ie - for any two elements, one less than the other, there is another element in between them</p></z></p>

</y>

Answer 40

A partial order or total order < on a set X is said to be dense

if for all x,y in X where x<y></y>

<p>there is a z in X such that x<z>

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

<p>ex - Rational Numbers, Real Numbers, etc</p></z></p>

</y>

Question 41

Any ordinal is defined by the set of ordinals that _____\_ it.

Answer 41

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

Question 42

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 _____** **____\_ is the least ordinal that is not a label for an element of the set.

The smallest infinite ordinal is called _\_, which is the order type of the natural numbers (which can also be identified as the set of natural numbers itself).

Answer 42

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.

Question 43

A _____** **_____\_ is an ordinal number that is neither zero, nor a successor ordinal.

Alternatively, an ordinal Lambda is a _____** **_____\_ 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 _____** **_____\_ 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 43

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

Question 44

_________** **_______\_ 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 44

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

Question 45

___________ _______\_ 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 <  α.

Answer 45

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