Basis

A set of elements is said to be ordered if it has a relationship with special properties defined on it. Here are some standard examples:

Set of Elements	Relationships that impose an order
Plans	cheaper, easier, more fun, ...
Products	safer, cheaper, faster, bigger, smaller, better, worse,...
Events	Occurs before, more likely than,...
Numbers	Less than, greater then, less then or equal, greater then equal
Natural Numbers	divides
Points in space	above, below, to the right, to the left, before, behind
Components in a system	is a part of (APO), part_whole, composition
Types of Objects	is a kind of (AKO), inheritance, derived_from, subtype_supertype
Parts of a program	depends on
Subsets of a set	==>(subset of)
Sets	functional dependency(there exists a many-one mapping from _ to _)
Sets	existence dependency(for each _ there must exist a unique fixed _)
Letters	Earlier in the alphabet
Words	dictionary order (lexographic order)
Boolean Values	implies
{a,b,c,x,y,z}	{(a,x),(a,y),(a,z), (b,x), (b,y), (b,z), (c,x), (c,y), c,z)}

Here are some relations that are not orders in this technical sense:

Set of Elements	Relationships
Pieces of a program	coupling
Points in space	close to, surrounding
Numbers	Having the same remainder with respect to a particular divisor

Take for example a set of components/modules/classes/pieces of a program and the relation of one part depending on another. Now if part A depends on part B and part B depends on part C then we would expect A to also depend on C indirectly. We call this transitivity (see standard). We would not want A part to depend B and B to depend on A, this would imply something that might not work well, rather like trying to fly by pulling hard on one's boot laces. This property is an example of antisymmetry here.

The following definitions and theorem are to be found in

1. standard::= See http://csci.csusb.edu/dick/maths/math_11_STANDARD.html

   (standard) |-For X:Sets, Quasi_orders(X) ::= Reflexivity(X) & Transitive(X) ,

   (standard) |-For X, Partial_orders(X) ::=Quasi_orders(X)& Antisymmetric(X),

   (standard) |-For X, Strict_partial_orders(X) ::= Irreflexive(X) & Transitive(X), (standard) |-For X, Total(X) ::={R:@(X,X)|| @(X,X)~R = /R },

   (standard) |-For X, Connected(X) ::={R:@(X,X)|| Total(X) and R | /R = @(X,X)}.

   
   

2. (standard)|- (ITisAT): For X:Sets, Irreflexive(X) & Transitive(X) = Asymmetric(X) & Transitive(X).

   The following defines the formal structure of all ordered sets - a set of elements and four relations that may or may not hold betwee any pair of elements in the set.

3. BASIC_ORDER::=
   Net{

   1. Set::Sets,
   2. relation::@(Set,Set),
   3. strict_relation::@(Set,Set),
   4. strict::=strict_relation,
   5. inverse::@(Set,Set),
   6. strict_inverse::@(Set,Set).
      
   7. |- (BO1): inverse = /relation.
      
   8. |- (BO2): strict_inverse = /strict_relation.

   
   }=::BASIC_ORDER.
   Note. I could have used definitions rather than declarations+axioms. Using axioms makes it clear that I wish to supply a relation and have the inverse derived from it as in ORDER and I wish to supply an inverse and derive the relation from it as in STRICT_ORDER below.

4. ORDER::=
   Net{

   
   
   1. |-BASIC_ORDER.
      
   2. |- (O0): relation in Transitive(Set) & Reflexive(Set) & Antisymmetric(Set).
      
   3. |- (O1): strict_relation=relation~Id(Set),
      
   4. (O0, def)|- (O2): strict in Transitive(Set) & Asymmetric(Set).
      
   5. (O2, ITisAT)|- (O3): strict in Irreflexive(Set).

      
      

   6. (O1, O2, O3)|- (Splitting theorem): (=)= relation & inverse.

   7. not_comparable_with::@(Set,Set)= @(Set,Set) ~strict_inverse~ strict.
   8. finite::@= (Set in FiniteSets).
   9. total::@= (relation in Total(Set)).
      
   10. (def)|- (O4): if total then not_comparable_with = {}.

   
   }=::ORDER.
   Note. The two conditions, finite and total can be asserted, denied, or left undetermined whenever the ORDER is reused: for example|- ORDER(Set=>1..100, relation=>divides, finite, not total).

   Exercise: Verify that|-ORDER( Set=>Int, relation=>(<=), inverse=>(>=), strict=>(<), strict_inverse=>(>), not finite, total, ...).

5. STRICT_ORDER::=
   Net{

   
   
   1. |-BASIC_ORDER.
      
   2. |- (SO1): strict in Transitive(Set) & Asymmetric(Set).
      
   3. |- (SO2): relation= strict | Id(Set).
      
   4. (SO1, SO2)|- (SO3): relation in Transitive(Set) & Reflexive(Set) & Antisymmetric(Set),
      
   5. (SO3)|- (SO4): ORDER.

   
   }=::STRICT_ORDER.
6. Note that by asserting that we can derive ORDER (SO4) we have claimed we can derive all of the axioms in ORDER and so all the definitions, declarations, and theorems are also automatically a part of STRICT_ORDER.

7. Strict_order::=the set of tpls satisfying STRICT_ORDER.
8. Strict_order::=$ STRICT_ORDER.
9. strict_order::=The sets which have < as a strict order
10. strict_order::=Strict_order(strict=>(<)).Set.
11. For X, strict_order(X)::=Strict_order(X).Set.

    Fishburn in 197? demonstrated that if one starts with a strict order (as defined above STRICT_ORDER) and uses it to define a relation and then takes that relation and the rules of ORDER to generate another strict relation then one gets the original relation back again.

    Quasi Ordered Sets

    Birkhoff & Bartee 70, pp258-259. (math_11_STANDARD) |-For X:Sets, Quasi_orders(X) ::= Reflexivity(X) & Transitive(X).

    Example Quasiorders

    
    
12. (number theory)|-divides in Quasi_order(Int).
    
13. (monoids)|-For all Abelian_Monoid M, divides:=rel[a,b:M](for some x(a x = b)), divides in Quasi_order(M).

    The following shows that every quasi_order has an associated partial order defined between sets of relatively unordered elements.

14. QUOSET::=
    Net{

    Set::Sets,
    1. relation::Quasi_orders(X).
    2. qr::=relation. -- shorthand

    3. equivalent::= qr & /qr.
       
    4. (def)|-(QO1); equivalent in Equivalence_relations(Set).
    5. Equivalence_classes::=Set/equivalent.
       
    6. (def)|- (QO2): For all E,F:Equivalence_classes, for all x:E, y:F(x qr y) or for no x:E,y:F(x qr y).
    7. relation::@(Equivalence_clases, Equivalence_classes)=for some x:(1st), y:(2nd) ( x relation y).
       
    8. (def)|- (QO3): For all E,F:Equivalence_classes, E relation F iff for all x:E, y:F(x qr y).

       
       

    9. (def)|- (QO4): relation in Partial_orders(Equivalence_classes).

    
    }=::QUOSET.

    
    

15. (QUOSET)|-For all QUOSET, ORDER (Set=>Equivalence_classes, relation=>relation.@(Equivalence_classes,Equivalence_classes) ).

    Posets

    Poset stands for a partially ordered set.

    
    

16. (ORDER)|- (simple_duality): For all variables(ORDER), if ORDER then ORDER (relation=>inverse, inverse=>relation, strict=>strict_inverse, strict_inverse=>inverse).

17. POSET::=ORDER.
18. Poset::= $ POSET.
19. poset::= $ POSET.Set.
20. For X, poset(X)::= $ POSET(Set=>X).Set.
21. standard_order::= $ ORDER(relation=>(<=), inverse=>(>=), strict=>(<), strict_inverse=>(>) ).Set,

22. poset(<=)::=standard_order,
23. poset(<)::=standard_order.

    All posets define a digraph:

24. For ORDER, graph::= the DIGRAPH(nodes=>Set, arcs=>strict),
    
25. (above)|- (acyclic_graph): no cycles(graph).

26. For ORDER, Haase_digraph::=the DIGRAPH(nodes=>Set, arcs=>strict~(|[n:2..] (strict^n) ) ). In words, arcs that are already implied by transitivity are not shown in the Haase graph.

    Example Posets.

    
    
27. (numbers)|- (Ex1): Integer and Real in standard_order and Net{not finite, total}.
    
28. (char)|- (Ex2): Char in standard_order and Net{finite, total}.
    
29. (numbers)|- (Ex3): Nat, Nat0 in standard_order with Left_limited(<) & not finite & total.

    
    

30. (sets)|- (Ex4): For S:Sets, ORDER(Set=>S, relation=>(==>), strict=>(=>>)).

31. Kuratowski(3,3)::=following,
    Net
    Based on Kuratowski's 3,3 complete graph.
    
    1. |- (K1): Set={a,b,c,d,e,f},
    2. (<)={a,b,c}><{d,e,f}
       
    3. ()|-ORDER.
    4. ...more below

    
    (End of Net)
    
    
    
32. (above)|-Kuratowski(3,3) in standard_order and Net{finite, not total}.

    Interval Notation

33. INTERVALS::=
    Net{

    
    
    1. |- (I0): ORDER. The [x,y] and (x,y) notation of the calculus and analysis is ambiguous.

    2. For x,y:Set, x..y::@Set= {z:Set || x relation z relation y},

    3. For x,y:Set, (x..y) ::@Set= {z:Set || x strict z strict y},

    4. For x,y:Set, [x..y) ::@Set= {z:Set || x relation z strict y},

    5. For x,y:Set, (x..y] ::@Set= {z:Set || x strict z relation y}.

       x..y is called a closed interval, and (x..y) is called an open one. The other two kinds of interval are called half open intervals. See topology for generalisations to open and closed subsets of other types [ math_91_Topology.html ]

       Notice that this notation may be confusing because when f:Set->T, f(x..y) <> f((x..y)).

       The following two definitions are inpired by the Unified Modeling Language.

    6. For x:Set, x..*::@Set= {z:Set || x relation z },
    7. For y:Set, *..y::@Set= {z:Set || z relation y},
       
    8. (above)|-x..y = x..* & *..y.

    
    }=::INTERVALS.

    Ranking

    An every day problem is sorting out our priorities. It is usually easy to compare a pair of options and see which one we prefer. With half-a-dozen options it is not so easy. One empirirical technique is to tabulate all pairs and for each pair note your preferred item. You can than count the number of times each item is preferred and get a series of numbers indicating a rough priority. Ranking is a theoretical version of this process. It is about attaching numbers to elements in a partially ordered set so that the numbers reflect the ordering of the elements in the partially ordered set. This is also called topological sorting.

    If these numbers are the heights of the nodes in a plot of the graph then we say that it is a Haase diagram of the poset.

    Define a standard ranking as a map from each element in the Set to a real number between 1 and |Set| inclusive which preserves the ordering:

34. For ORDER, Rank(Set)::= (Set,<)>->([1..|Set|], <).

    Notice that if r:Rank(Set) then we can not reason from r(x)>r(y) that x>y. We can show that not(x<y) but a partial ordering may omit certain pairs that have ordered ranks.

    Here are three rankings that are simple to calculate -- with time O(|Set|^2). For example

35. N:=|Set|.
36. above::Set>->[1..N] = map[x](1 + |x.< | ), 1+the number of items above x.
37. below::Set>->[1..N] = map[x](N - |x.> | ), N-the number items below x.
38. rank::= (above+below)/2. are all rankings. Proofs are left as an exercise (Hint: if x'>x then x' and x'.< are in x.<).

    There is a simple way to calculate the values of |x.> | and | x.< | by hand on a small number of items. Prepare a grid with every pair of items and write in the larger of each pair in the squares in the grid. Count the squares where an item appears in its own row, and where other items occur. These are the two numbers. In practice the complete grid is symmetric and so half is ommitted. The counting goes along a row to the diagonal and then down. Here is an example:

    x	a	b	c	d	e	f	g
    a
    b	a	.
    c	a	b	.
    d	a	.	.	.
    e	a	.	.	.	.
    f	a	.	.	d	e	.
    g	a	.	.	d	e	f	.
    | x.> |	6	1	0	2	2	1	0
    | x.< |	0	1	2	1	1	3	4

    Knuth[Knuth 69] gives algorithms for topological sorting.

    Van Neuman and Morgenstern take this theory a lot further in their "General Theory of Games and Economics". They show that if the set has a linear order and an operation that constructs new elements as combinations (loteries) of paris of elements, then their is a unique natural ranking that indicates (up to scale) how much different elements are worth.

    Optimal values

    1. OPTIMIZATION::=MINMAX,
    2. MINMAX::=
       Net{

       Problem - to give meaning to such words as biggest, best, largest, worst, etc - in the general case, if at all possible. This turns out to be subtler than it looks. There is no common terminology however - what will be defined as 'min' below may be called 'least' in some texts and papers and vice versa. I define several models of these words.

       
       

       1. |-ORDER.

          Least(greatest) elements in a set have no lesser(greater) elements in the set,

       2. For S:@Set ~{{}},
       3. least(S)::@Set= {x:S || for all s:S, if s relation x then s=x},
       4. greatest(S)::@Set= {x:S || for all s:S, if s inverse x then s=x}.
          
       5. (def)|- (OP1): least(S)={x || for no y:S (y strict x)}.
          
       6. (def)|- (OP2): greatest(S)={x || for no y:S (y strict_inverse x)}.

          
          

       7. (def)|- (OP3): if S in finite then some least(S) and some greatest(S).

          [ math_11_STANDARD.html ]
          

       8. (def)|- (OP4): if relation in Left_limited(S) then some least(S).
          
       9. (def)|- (OP5): if relation in Right_limited(S) then some greatest(S).
          
       10. (def)|- (OP6): if relation in Trichotometic(S) then 0..1 least(S) and 0..1 greatest(S).

           Minimal elements in a set are less than or equal to all members of that set.

       11. For S:@Set~{{}},
       12. minima(S)::@Set= {x:S || for all s:S(x relation s)},
       13. min(S)::= minima(S),
       14. maxima(S)::@Set= {x:S || for all s:S(x inverse s)},
       15. max(S)::= maxima(S),
       16. In all posets, the minima(maxima) are among the least (greatest) and if there exist any minima(maxima) then there can only be one of them.
           
       17. (above)|- (OP7): for all S:Set, min S ==> least S ==>S.
           
       18. (above)|- (OP8): 0..1 min S.
           
       19. (above)|- (OP9): max S ==> greatest S==>S.
           
       20. (above)|- (OP10): 0..1 max S.

           Most authors fail to distinguish maxima from greatest and least from minima probably because in they are the same when we talk about numbers and other total orders.
           

       21. (above)|- (OP11): if total then least=min and max=greatest and for all S:Finite(Set)(one min(S) and one max(S)).

           This is not so in a general partially ordered set:

       22. Kuratowski(3,3)::=
           Net{

           1. (K1) ...from above (K2):.
              
           2. (above)|-least(Set)={a,b,c}, |- greatest={d,e,f},
              
           3. (above)|-min(Set)=max(set)={}.

           4. ...more to follow

           
           }=::Kuratowski.
       23. Therefore there exist finite posets with any number of least/greatest elements and no maxima/minima.

           Many infinite sets have no least(greatest) elements. As an example Nat has no greatest elements and so no maxima. Also the reciprocals of the natural no-zero numbers:

       24. Reciprocals::=1/Nat ={1/n ||n:Nat} has no least elements and so no minima. Notice that the ordering relation on Nat and Reciprocals are linear orders. Thus there may be no least/minima/greatest/maxima for some subsets of linearly ordered sets.

           However Reciprocals is bounded below by 0. Further for any number x>0 there is some y such that 1/y is less than x - so that 0 is the greatest number that is below all the reciprocals. Thus 0 is the greatest lower bound on Reciprocals. To formailize these ideas we start with the ideas of upper and lower bounds. MATHS.MINMAX defines both strict and unstrict versions. The unstrict ones are common in mathematical texts and the strict versions less common.

           Now (strict) lower (upper) bounds are elements (strictly) less(greater) than all members of the set.

       25. For S:@Set,
       26. lb(S)::@Set= {x:Set || for all s:S(x relation s)},
       27. ub(S)::@Set= {x:Set || for all s:S(x inverse s)},
       28. slb(S)::@Set= {x:Set || for all s:S(x strict s)},
       29. sub(S)::@Set= {x:Set || for all s:S(x strict_inverse s)},

           
           

       30. (above)|- (OP12): lb({})=ub({})=slb({})=sub({})=Set.
           
       31. (above)|- (OP13): for all x:sub(S)|slb(S) (not x in S).

           
           

       32. (above)|- (OP14): for all s:sub(S), u:ub(S), g:greatest(S), m:max(S), (g and m relation u and g and m strict s).

           
           

       33. (above)|- (OP15): For S, not least(sub(S))==>S and not greatest(slb(S))==>S.

       34. For S,
       35. lsub(S)::@Set= least(sub(S))),
       36. gslb(S)::@Set= greatest(slb(S))).
       37. For S, lub(S)::@Set= least(ub(S))),
       38. glb(S)::= greatest(lb(S))). Note lsub and gslb are rare in mathematics. Another approach is to start with a definition of lub and/or glb and work back to the order from there. See [ SEMILATTICE in math_32_Semigroups ] and [ LATTICE in math_41_Two_Operators ]
       39. for this approach.

           Example Kuratowski Part 3

       40. Kuratowski(3,3)::=
           Net{

           from (K2)...continued
           (K3):
           
           1. (above)|-sub{a,b,e}={d,e,f},
              
           2. (above)|-lsub{a,b}=least{d,f}={d,f},
              
           3. (above)|-ub{a,b,e}={a,b,d,e,f},
              
           4. (above)|-lub{a,b}=least{a,b,d,e,f}={a,b}.
              Therefore there exist finite posets with as many of lub's and glb's as we might want.
              
           5. (above)|-least{a,b,e}={a,b}=lub{a,b,e}

           
           }=::Kuratowski.

           Most authors consider glb and the supremum to be the same, and similarly for lub and the infimum. I now define both strict and non-strict forms - as found in different texts.

           After Godement 69, Algebra, Herman, Paris, France. 5,2, pp91

       41. For S:@Set~{{}},
       42. sup(S)::=supremum(S)::@Set= the(i:ub(S) || for all b:ub(S)(b inverse i)),
       43. inf(S)::= infimum(S)::@Set= the(s:lb(S) || for all b:lb(S)(b relation s)),
           
       44. (above)|- (OP16): (inf = lub) and (sup=glb). Godement claims that for all sets of cardinal numbers the inf and sup exist, and are unique - by allowing positive and negative infinite numbers.

           After General Topology, Springer Verlag 1984, para 7.1.1

       45. For S:@Set~{{}},
       46. sinf(S)::= strict_infimum(S)::@Set= the(i:Set || for all x:S(i relation x) and for all b, if b strict_inverse i then for some x:S(b inverse x)),
       47. ssup(S)::= strict_supremum(S)::@Set= the(s:Set || for all x:S(x relation s) and for all b, if b strict s then for some x:S(b strict_inverse x)),
           
       48. (above)|- (OP17): inf(S) and sup(S) in S

           Optimizing a function or map

       49. For X:Sets~{{}}, f:X->Set, opt:{min,max,glb,lub,inf,sup,...}.
           opt functions are used for picking desirable items:

           Example of Software Transaction specification Part 1

           
           Pick_inexpensive:=Objects_available.cost.min./cost.
           Not that opt is not in @(S,S) so cost;opt;/cost is not well formed.

       50. For X:Sets~{{}}, f:X->Set, opt:{min,max,glb,lub,inf,sup,...}, (opt mod f)(X) ::= /f(opt(f(X))).
           
       51. (above)|- (OP18): X. (opt mod f)=/f(opt(f(X))).

           Example of Software Transaction specification Part 2

           
           Pick_inexpensive=Objects_available.(min mod cost).

           Don't try to Optimize Two or more Objectives.

       52. For X:Sets, |X|>=2, opt:{min,max,glb,lub,inf,sup}, if |Set|>2 then
       53. for some f,g:X->Set, no ((opt mod f)(X) & (opt mod g)(X)).

           Example of Multiple Optimization

           It is difficult to find something that is both cheapest and best.
       54. Pick_perfect=Objects_available.(min mod money) & Objects_available.(max mod quality).

           Duality

           .Road_Works_ahead There is often a kind of duality between two different attributes or criteria however. Maximizing one with the other fixed gives a function that when minimized is the less than maximizing the function of minimum with respect to the other variable with the first variable fixed.

           ---

           Was that confusing enough? I've been trying to work out a clear and correct model of this kind of duality for 16 years.

           ---

           This section follows studying A. M. Fink and Juan A. Galiter's 1992 paper in the American Mathematical Monthly (Vol65, No. 3, June 1992) entitled "For every Answer There are Two Questions".

           In some circumstances a pair of functions generate dual optimization problems.

           1. DUALITY_BASIS::=following,
              Net
              1. X:Set. f, g:: X>->Real & Positive.

              
              (End of Net)
              
              

              Example of one solution solving two problems

              
              Net
              
              
              1. |-DUALITY_BASIS( X=> Rectangle, f=> perimeter, g=> area).

              2. (primal_problem): Given a perimeter p, which rectangle has maximum area.
              3. For p:Real & Positive, M(p)::=(max mod area)(/perimeter(p)).
              4. (dual_problem): Given an area a, which rectangle has minimum perimeter.
              5. For a:Real & Positive, m(a)::=(min mod perimeter)(/area(a)).

              6. In this case the solutions to both problems are always squares.
                 
              7. (Rectangle)|-Square = Rectangle( length=breadth ).

                 
                 

              8. (above)|-img M = img m = Square.

              9. For p, M'(p) = area(M(p)),
              10. For a, m'(a)::=perimeter(m(a)).

              11. More, solving one problem discovers a solution of the other problem.
                  
              12. (above)|-For all p, m'(M'(p)) = p,
                  
              13. (above)|-For all a, M'(m'(a)) =a.

                  more TBA.

              
              (End of Net)
              
              
           2. DUALITY::=following,
              Net
              
              
              1. |-DUALITY_BASIS.
              2. For x: Real & Positive, M(x)::=(max mod f)(/g(x)).
              3. For x: Real & Positive, m(x)::=(min mod g)(/f(x)).
              4. fM::=f o M,
              5. gm::=g o m.

                 
                 

              6. |- (FinkGalliter1): img M = img m.
              7. Y::= img M.

                 Here is my best guess (so far) of the conditions needed to guarantee duality.

                 
                 

              8. |- (FinkGalliter2): for all y1,y2 ( f(y1) < f(y2) iff g(y1) < g(y2) ).
                 
              9. |- (FinkGalliter3): f|Y and g|Y in X---Real & Positive. Note: f and y are not one-one and onto in general, but they are on Y.

                 
                 

              10. (above)|- (duality): gm o fM = Id = fM o gm.

              
              (End of Net)
              
              

           . . . . . . . . . ( end of section Duality) <<Contents | End>>

           Arrow's Theorem

           Political life is rife with setting prioritites an attempting to reconcile different people's preferences. We model these situations as a set of alternatives and a set of orders (or rankings). The question then arises if there is an algorithm that (in some way or other) ballances the multiple preferences. Unfortunately there is a depressing theorem that shows that any such algorithm, given enough options and preferences will have non-democratic, or even insane properties. For example the algorithm will allow one person to be a dictator, or it might mean that when someone reverses their preferences then the algorithm will go in the opposite direction....

           Open-ended Exercise on Bentham's Definition

           When is the greatest good for the greatest number meaningful?

           However

       55. X.(opt mod f).(opt mod g) is often well defined, but not necesarily the same as
       56. X.(opt mod g).(opt mod f)

       
       }=::MINMAX.

       Conclusion re Optimal values in General Posets

       In a general poset none of the optima have to exist. Since we often need optima to exist we define and study special subsets and special posets where we can show that a particular class of optima do exist.

       Complete Posets

    3. COMPLETE::=
       Net{

       
       
       1. |-MINMAX.
       2. (complete): For all S:@Set ~{{}}, one lub(S). Manes & Arbib 86

       
       }=::COMPLETE.
    4. complete_partially_ordered_sets::=$ COMPLETE.Set,
    5. cpo::=complete_partially_ordered_sets.
    6. For X, cpo(X)::=$ COMPLETE(X).Set. In a complete partially ordered set every subset has a unique least upper bound.

       Special Subsets and Functions in Posets

    7. convergent::@Seq(S)={s || some lub(s)}.
       
    8. (above)|-For s:convergent, one lub(s). for s:convergent, lim(s) ::=the lub(s).

       Consider any map from an poset to itself then some points wil increase when the map is applied and some will decreas and some will not change.
       (fixed_points): [ UNARY in math_11_STANDARD ]

    9. For f:Set->Set,
    10. increasing_points(f)::={h:Set || h<=f(h)},
    11. decreasing_points(f)::={h:Set || h<=f(h) }.
        
    12. (above)|-fixed_points(f) = increasing_points(f) & decreasing_points(f).

    13. increasing_functions::={f:Set->Set || for all x( x <= f(x))},
    14. increasing::=increasing_functions.

        
        

    15. (above)|- (PO1): increasing={f:Set->Set || (=) in (Set,f)->(Set,<=)}
    16. monotone_functions::={f:Set->Set || for all x,y( if x<=y then f(x)<=f(y) )},
    17. monotonic::=monotone_functions.
        
    18. (above)|- (PO2): monotonic = (<=)(Set->Set).
    19. continuous::@monotonic={f || for all s:convergent ( lim(f(s))=f(lim(s)) ). Compare Math.Topology.CONTINUITY.

    20. ascending_chains::@Seq(Set)={ s || <=(s) },
    21. ascending::=ascending_chains.
    22. strict_ascending_chains::@Seq(Set)={ s || <(s) },
    23. strict_ascending::=strict_ascending_chains,
        
    24. (above)|- (PO3): for all a:ascending, some I:@Nat0( (<=)I->Set).
    25. (above) |- finite_sequence::= { s:Seq(Set)|| pre(s) in Finite_set}. [ Finite Sequences in logic_6_Numbers..Strings ]

    26. chain::@@Set={ A:@Set || for all x,y:A ( x <= y or y<=x ) }.
        
    27. (above)|- (PO4): for all a:ascending( img(a) in chain ).
        
    28. (above)|- (PO5): for all f:Set->Set, f in increasing iff map[i]f^i in ascending.

    29. descending_chains::@Seq(Set)={ s || >=(s) },
    30. descending::=descending_chains,
    31. strict_descending_chains::@Seq(Set)={ s || >(s) },
    32. strict_descending::=strict_descending_chains,

    33. directed::@@Set={P:@Set || for all u:finite@(P), some ub(P)&P}.

    34. CHAIN_COMPLETE::=
        Net{

        
        
        1. |-MINMAX.
        2. For all S:chain, some lub(S). Nielson & Nielson 92

        3. Scott_open_sets::={U:@Set|| (for all x:U, y:Set, if x <= y then y in U) and (for all M:@Set, if lub(M) in U and M in directed then M&U<>{})}.

        4. Scott_topology::=OPEN_TOPOLOGY(Space=>Set, Open=>Scott_open_sets).

        
        }=::CHAIN_COMPLETE.
    35. chain_complete_partially_ordered_sets::=$ CHAIN_COMPLETE.Set,
    36. ccpo::=chain_complete_partially_ordered_sets,
    37. For X, ccpo(X)::=$ CHAIN_COMPLETE(X).Set.

        Some use the term complete for chain complete. Gunter 92.

        Another variation of completeness is what I term Kleene Completeness, where every ascending sequence has a least upper bound. [ DOMAIN in math_24_Domains ]

    38. TARSKI_KNASTER::=
        Net{

        
        
        1. |-COMPLETE. Tarski 55, A. TARSKI "A Lattice Theoretical fixedpoint theorem and its applications," Pacific Journal of Maths, V5, 1955, pp285-309

           Tarski published the general version. The special case for (@X, ==>) by B. Knaster (1928) is often sufficient - hence the literature calls this the Knaster-Tarski Fixed Point theorem.

           
           

        2. |-MINMAX.
        3. f::monotonic,
        4. H::=increasing_points(f).
        5. L::=decreasing_points(f).

           ??|-if some lub H then the lub H = the greatest fixed_points(f). ??|-if some glb L then the glb L = the least fixed_points(f),

        
        }=::TARSKI_KNASTER.

    39. Countable_complete::=$ Net{Use MINMAX. for all S:countable, one lub(S)}.

    40. For all X:Sets, (@X,==>) in cpo and (the lub) = (|) and Seq(S)=convergent and for all f:X->X( f and /f in (continuous)@X->@X).

        ??{ For (S,<=):poset, S:@Set~{{}}, dominant(S):@S::={D:@S || for all y:S~D(y<=x)} }? ??{ For F:@@@Set, S.complete::@=for all S:F( one lub(S) ) }?

    Semi-orders

    Semi-orders are used for several urposes including the modelling of before/after relationships between events in time.
39. SEMIORDER::=
    Net{

    Luce 56, Library of Congress call number BF39.C66 and CACM, Feb 1978.
    1. Set::Sets,
    2. P::@(S,S)= previous_to.
       
    3. |- (SO1): For all x,y,z,w:S, if x P y P z then x P w or w P z,
       
    4. |- (SO2): For all x,y,z,w, if x P y and z P w then x P w or z P y,
       
    5. |- (SO3): for no x(x P x).

       
       

    6. (above)|- (SO4): for some f:Real^Set, δ:Real ~ Negative, for all x,y( f(x) > f(y)+δ iff x P y).

    7. For x,y:S, x concurrent y::= not (x P y) and not (y P x).

    
    }=::SEMIORDER.

    Parts and Whole

    .Used_in math_93_Graphics, monograph/02MATHS&TEMPO#Lift, monograph/03_Languages#Outlines, ...

    Compare work done by the elder Woodger on the axiomatisation of biology [Woodger 32].

    Conference: [ IMC.htm ]

    Applicable to: OOP ,data structures, programs, texts, documentation, ...

40. PART_WHOLE::=
    Net{

    1. objects::Sets, -- the things that are wholes and/or parts
    2. isin::strict_order(objects).
    3. APO::=isin.
       
    4. |- (PW0): MINMAX(Set=>objects, strict=>isin,...)

    5. universe::objects. -- the largest object
       
    6. |- (PW1): lub(objects)={universe}.

    7. Example1::=
       Net{

       1. objects::={auto,engine,radiator,radiator_cap,wheel1,wheel2,....}
       2. isin::={(engine,auto),(radiator,engine),(radiator,auto),..}
       3. universe::=auto.

          
          

       4. (above)|-engine isin auto.
          
       5. (above)|-radiator isin engine.

       
       }=::Example1.

       
       

    8. (above)|- (PW2): finite iff objects in Finite.

    9. parts::=/isin, -- the parts of x are those things "isin x".
       
    10. (above)|- (PW3): For x:objects, parts(x)= {y:objects || y isin x}.
        
    11. (above)|- (PW4): For no x (x in parts(x)).
        
    12. (above)|- (PW5): for all x (x in parts(universe)).

    13. elements::={x || no parts(x)},
    14. compounds::=objects~elements,
        
    15. (above)|- (PW6): objects>=={compounds, elements}.

        In many cases each object is assembled out of components, and each component is itself likely to be assembled from smaller components, and a part is a component or any part of a component...

    16. is_component_of::=isin~(|[i:2..]isin^i),
    17. components::=map[x:objects]/is_component_of(x).
        
    18. (above)|- (PW7): |[i:2..]isin^i = isin^2,
        
    19. (above)|- (PW8): For x:objects, parts(x)>=={components(x), parts(components(x)
        }

    Proof of PW7

    Consider{ |[i:2..]isin^i =isin;do(isin)=isin^2}.

    Proof of PW8

    Consider { parts(x)>=={components(x), /isin^2(x)}...
    }.

Example of a continuum