.Open Orders . 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: .Table Set of Elements Relationships that impose an order .Row Plans cheaper, easier, more fun, do_before, ... .Row Products safer, cheaper, faster, bigger, smaller, better, worse,... .Row Events Occurs before, more likely than,... .Row Numbers Less than, greater then, less then or equal, greater then equal .Row Natural Numbers divides .Row Points in space above, below, to the right, to the left, before, behind .Row Components in a system is a part of (APO), part_whole, composition .Row Types of Objects is a kind of (AKO), inheritance, derived_from, subtype_supertype .Row Parts of a program depends on .Row Subsets of a set ==>(subset of) .Row Sets functional dependency(there exists a many-one mapping from _ to _) .Row Sets existence dependency(for each _ there must exist a unique fixed _) .Row Letters Earlier in the alphabet .Row Words dictionary order (lexographic order) .Row Boolean Values implies .Row {a,b,c,x,y,z} {(a,x),(a,y),(a,z), (b,x), (b,y), (b,z), (c,x), (c,y), c,z)} .Close.Table Here are some relations that are not orders in this technical sense: .Table Set of Elements Relationships .Row Points in space close to, surrounding .Row Numbers Having the same remainder with respect to a particular divisor .Close.Table Take for example a set of components/modules/classes/pieces of a program and the relation of one part depending on another. In other words if one changes then the dependent module may also have to be changed. 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). But, We would not want A part to depend B and B to depend on A, this would imply a difficult time making changes. The property that stops this is called antisymmetry. The following definitions and theorems are to be found in standard::=http://www/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)}. (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. BASIC_ORDER::=Net{ Set::Sets, relation::@($Set,$Set), strict_relation::@($Set,$Set), strict::=strict_relation, inverse::@($Set,$Set), strict_inverse::@($Set,$Set). |-(BO1):$inverse = /$relation. |-(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. ORDER::=Net{ |-$BASIC_ORDER. |- (O0): relation in Transitive($Set) & Reflexive($Set) & Antisymmetric($Set). |- (O1): strict_relation=relation~Id($Set), (O0, def)|-(O2): strict in Transitive($Set) & Asymmetric($Set). (O2, ITisAT)|-(O3): strict in Irreflexive($Set). (O1,O2, O3)|-(Splitting theorem): (=)= relation & inverse. not_comparable_with::@($Set,$Set)= @($Set,$Set) ~strict_inverse~ strict. (Sets)|- finite::@= ($Set in FiniteSets). total::@= ($relation in Total($Set)). (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)|-$ORDER(Set=>1..100, relation=>divides, finite, not total). Exercise: Verify that (ORDER)|- $ORDER( Set=>Int, relation=>(<=), inverse=>(>=), strict=>(<), strict_inverse=>(>), not finite, total, ...). STRICT_ORDER::=Net{ |-$BASIC_ORDER. |- (SO1): strict in Transitive($Set) & Asymmetric($Set). |- (SO2): relation= $strict | Id($Set). (SO1, SO2) |- (SO3): relation in Transitive($Set) & Reflexive($Set) & Antisymmetric($Set), (SO3) |- (SO4):$ORDER. }=::STRICT_ORDER. 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. Strict_order::=the set of tpls satisfying STRICT_ORDER. Strict_order::=STRICT_ORDER. strict_order::=The sets which have < as a strict order strict_order::=Strict_order(strict=>(<)).$Set. For X, strict_order(X) ::=Strict_order(X).$Set. Any set with an empty relation is a trivial order. A singleton set {x} has a strict order relation{}. A set{a,b} with two sets is ordered by {(a,b)} or by {(b,a)} but not by {(a,b), (b,a)}. 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 .Source Birkhoff & Bartee 70, pp258-259. (math_11_STANDARD)|- For X:Sets, Quasi_orders(X) ::= Reflexivity(X) & Transitive(X). . Example Quasiorders (number theory)|- divides in Quasi_order(Int). (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. QUOSET::=Net{$Set::Sets, relation::Quasi_orders(X). qr::=relation. -- shorthand equivalent::= $qr & /$qr. (def)|-(QO1); equivalent in Equivalence_relations($Set). Equivalence_classes::=$Set/equivalent. (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). relation::@(Equivalence_clases, Equivalence_classes)=for some x:(1st), y:(2nd) ( x relation y). (def)|-(QO3): For all E,F:Equivalence_classes, E relation F iff for all x:E, y:F(x $qr y). (def)|-(QO4): relation in Partial_orders(Equivalence_classes). }=::QUOSET. (QUOSET)|- For all QUOSET,$ORDER (Set=>Equivalence_classes, relation=>relation.@(Equivalence_classes,Equivalence_classes) ). . Posets Poset stands for a partially ordered set. (ORDER)|-(simple_duality): For all variables(ORDER), if ORDER then ORDER (relation=>inverse, inverse=>relation, strict=>strict_inverse, strict_inverse=>inverse). POSET::=$ORDER. Poset::=$ $POSET. poset::=$ $POSET.$Set. For X, poset(X) ::= POSET(Set=>X).$Set. standard_order::=$ $ORDER(relation=>(<=), inverse=>(>=), strict=>(<), strict_inverse=>(>) ).$Set, poset(<=) ::=$standard_order, poset(<) ::=$standard_order. All posets define a digraph: For $ORDER, graph::= the DIGRAPH(nodes=>$Set, arcs=>strict), ()|-(acyclic_graph): no cycles(graph). 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. (numbers)|-(Ex1): Integer and Real in $standard_order and Net{not$finite, $total}. (char)|-(Ex2): Char in$standard_order and Net{$finite,$total}. (numbers)|-(Ex3): Nat, Nat0 in standard_order with Left_limited(<) & not $finite &$total. (sets)|-(Ex4): For S:Sets, $ORDER(Set=>S, relation=>(==>), strict=>(=>>)). Kuratowski(3,3) ::=following, .Net .Image k33.gif [picture of set described below] Based on Kuratowski's 3,3 complete graph. |-(K1):$Set={a,b,c,d,e,f}, (<)={a,b,c}><{d,e,f} () |- $ORDER. ...more below .Close.Net ()|- Kuratowski(3,3) in standard_order and Net{finite, not total}. . Interval Notation INTERVALS::=Net{ |-(I0):$ORDER. The [x,y] and (x,y) notation of the calculus and analysis is ambiguous. For x,y:$Set, x..y ::@$Set= {z:$Set || x$relation z $relation y}, For x,y:$Set, (x..y) ::@$Set= {z:$Set || x $strict z$strict y}, For x,y:$Set, [x..y) ::@$Set= {z:$Set || x$relation z $strict y}, 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 .See http://www/dick/maths/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. For x:$Set, x..* ::@$Set= {z:$Set || x$relation z }, For y:$Set, *..y ::@$Set= {z:$Set || z$relation y}, (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: 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->[1..N] = map[x](1 + |x.< | ), 1+the number of items above x. below::Set>->[1..N] = map[x](N - |x.> | ), N-the number items below x. 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: .Table x a b c d e f g .Row a .Row b a . .Row c a b . .Row d a . . . .Row e a . . . . .Row f a . . d e . .Row g a . . d e f . .Row | x.> | 6 1 0 2 2 1 0 .Row | x.< | 0 1 2 1 1 3 4 .Close.Table 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 (lotteries) of elements, then there is a unique natural ranking that indicates (up to scale) how much different elements are worth. .Open Optimal values OPTIMIZATION::=$MINMAX, MAXMIN::=$MINMAX. 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 - what will be defined as 'min' below may be called 'least' in some texts and papers and vice versa. So I define several models of these words. |- $ORDER. Least(greatest) elements in a set have no lesser(greater) elements in the set, For S:@$Set ~{{}}, least(S) ::@$Set= {x:S || for all s:S, if s relation x then s=x}, greatest(S) ::@$Set= {x:S || for all s:S, if s inverse x then s=x}. (def)|-(OP1): least(S)={x || for no y:S (y strict x)}. (def)|-(OP2): greatest(S)={x || for no y:S (y strict_inverse x)}. (def)|-(OP3): if finite S then some least(S) and some greatest(S). .See http://www/dick/maths/math_11_STANDARD.html (def)|-(OP4): if $relation in Left_limited(S) then some least(S). (def)|-(OP5): if$relation in Right_limited(S) then some greatest(S). (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. For S:@$Set~{{}}, minima(S)::@$Set= {x:S || for all s:S(x relation s)}, min(S) ::= minima(S), maxima(S)::@$Set= {x:S || for all s:S(x inverse s)}, max(S) ::= maxima(S), 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. ()|-(OP7): for all S:$Set, min S ==> least S ==>S. ()|-(OP8): 0..1 min S. ()|-(OP9): max S ==> greatest S==>S. ()|-(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. ()|-(OP11): if$total then least=min and max=greatest and for all S:Finite_sets($Set)(one min(S) and one max(S)). This is not so in a general partially ordered set: Kuratowski(3,3) ::=Net{$K1 ...from above .Image k33.gif [picture of set described below] (K2): ()|- least($Set)={a,b,c}, ()|- greatest={d,e,f}, ()|- min($Set)=max(set)={}. ...more to follow $K3 }=::Kuratowski. 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: 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. For S:@$Set, lb(S) ::@$Set= {x:$Set || for all s:S(x relation s)}, ub(S) ::@$Set= {x:$Set || for all s:S(x inverse s)}, slb(S) ::@$Set= {x:$Set || for all s:S(x strict s)}, sub(S) ::@$Set= {x:$Set || for all s:S(x strict_inverse s)}, ()|-(OP12): lb({})=ub({})=slb({})=sub({})=$Set. ()|-(OP13): for all x:sub(S)|slb(S) (not x in S). ()|-(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). ()|-(OP15): For S, not least(sub(S))==>S and not greatest(slb(S))==>S. For S, lsub(S) ::@$Set= least(sub(S))), gslb(S) ::@$Set= greatest(slb(S))). For S, lub(S) ::@$Set= least(ub(S))), 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 .See http://www/dick/maths/math_32_Semigroups.html#SEMILATTICE and .See http://www/dick/maths/math_41_Two_Operators.html#LATTICE for this approach. . Example Kuratowski Part 3 Kuratowski(3,3) ::=Net{ from ($K2)...continued .Image k33.gif [picture of set described below] (K3): ()|- sub{a,b,e}={d,e,f}, ()|- lsub{a,b}=least{d,f}={d,f}, ()|- ub{a,b,e}={a,b,d,e,f}, ()|- 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. ()|- 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. .Source After Godement 69, Algebra, Herman, Paris, France. 5,2, pp91 For S:@$Set~{{}}, sup(S) ::=supremum(S), supremum(S)::@$Set= the(i:ub(S) || for all b:ub(S)(b inverse i)), inf(S) ::=infimum(S), infimum(S)::@$Set= the(s:lb(S) || for all b:lb(S)(b relation s)), ()|-(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. .Source After General Topology, Springer Verlag 1984, para 7.1.1 For S:@$Set~{{}}, sinf(S) ::=strict_infimum(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)), ssup(S) ::=strict_suprememum(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)), ()|-(OP17): inf(S) and sup(S) in S . Optimizing a function or map 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. For X:Sets~{{}}, f:X->$Set, opt:{min,max,glb,lub,inf,sup,...}, (opt mod f)(X) ::= /f(opt(f(X))). ()|-(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. For X:Sets, |X|>=2, opt:{min,max,glb,lub,inf,sup}, if |$Set|>2 then 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. Pick_perfect=Objects_available.(min mod money) & Objects_available.(max mod quality). .Open 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. .Box Was that confusing enough? I've been trying to work out a clear and correct model of this kind of duality for 16 years. .Close.Box 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. DUALITY_BASIS::=following, .Net X:$Set. f, g:: $X>->Real & Positive. .Close.Net . Example of one solution solving two problems .Net |-$DUALITY_BASIS( X=> Rectangle, f=> perimeter, g=> area). (primal_problem): Given a perimeter p, which rectangle has maximum area. For p:Real & Positive, M(p)::=(max mod area)(/perimeter(p)). (dual_problem): Given an area a, which rectangle has minimum perimeter. For a:Real & Positive, m(a)::=(min mod perimeter)(/area(a)). In this case the solutions to both problems are always squares. (Rectangle)|- Square = Rectangle( length=breadth ). ()|- img M = img m = Square. For p, M'(p) = area(M(p)), For a, m'(a)::=perimeter(m(a)). More, solving one problem discovers a solution of the other problem. ()|-For all p, m'(M'(p)) = p, ()|-For all a, M'(m'(a)) =a. more $TBA. .Close.Net DUALITY::=following, .Net |-$DUALITY_BASIS. For x: Real & Positive, M(x)::=(max mod f)(/g(x)). For x: Real & Positive, m(x)::=(min mod g)(/f(x)). fM::=f o M, gm::=g o m. |-(FinkGalliter1): img M = img m. Y::= img M. Here is my best guess (so far) of the conditions needed to guarantee duality. |- (FinkGalliter2): for all y1,y2 ( f(y1) < f(y2) iff g(y1) < g(y2) ). |- (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. ()|-(duality): gm o fM = Id = fM o gm. .Close.Net .Close Duality . 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 X.(opt mod f).(opt mod g) is often well defined, but not necesarily the same as 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 COMPLETE::=Net{ |- $MINMAX. (complete): For all S:@$Set ~{{}}, one lub(S). .Source Manes & Arbib 86 }=::COMPLETE. complete_partially_ordered_sets::=COMPLETE.$Set, cpo::=$complete_partially_ordered_sets. 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 convergent::@Seq(S)={s || some$lub(s)}. ()|-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): .See http://www/dick/maths/math_11_STANDARD.html#UNARY For f:$Set->$Set, increasing_points(f) ::={h:$Set || h<=f(h)}, decreasing_points(f) ::={h:$Set || h<=f(h) }. ()|- $fixed_points(f) =$increasing_points(f) & $decreasing_points(f). increasing_functions::={f:$Set->$Set || for all x( x <= f(x))}, increasing::=$increasing_functions. ()|-(PO1): $increasing={f:$Set->$Set || (=) in ($Set,f)->($Set,<=)} monotone_functions::={f:$Set->$Set || for all x,y( if x<=y then f(x)<=f(y) )}, monotonic::=$monotone_functions. ()|-(PO2): monotonic = (<=)($Set->$Set). continuous::@monotonic={f || for all s:convergent ( lim(f(s))=f(lim(s)) ). Compare Math.Topology.CONTINUITY. ascending_chains::@Seq($Set)={ s || <=(s) }, ascending::=$ascending_chains. strict_ascending_chains::@Seq($Set)={ s || <(s) }, strict_ascending::=$strict_ascending_chains, ()|-(PO3): for all a:$ascending, some I:@Nat0( (<=)I->$Set). ()|-finite_sequence::= { s:Seq($Set)|| pre(s) in Finite_sets($Set)}. .See http://www/dick/maths/logic_6_Numbers..Strings.html#Finite Sequences chain::@@$Set={ A:@$Set || for all x,y:A ( x <= y or y<=x ) }. ()|-(PO4): for all a:$ascending( img(a) in$chain ). ()|-(PO5): for all f:$Set->$Set, f in $increasing iff map[i]f^i in$ascending. descending_chains::@Seq($Set)={ s || >=(s) }, descending::=$descending_chains, strict_descending_chains::@Seq($Set)={ s || >(s) }, strict_descending::=$strict_descending_chains, directed::@@$Set={P:@$Set || for all u:Finite_sets(P), some ub(P)&P}. CHAIN_COMPLETE::=Net{ |- $MINMAX. For all S:$chain, some $lub(S). .Source Nielson & Nielson 92 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<>{})}. Scott_topology::=OPEN_TOPOLOGY(Space=>$Set, Open=>Scott_open_sets). }=::CHAIN_COMPLETE. chain_complete_partially_ordered_sets::=$ $CHAIN_COMPLETE.$Set, ccpo::=$chain_complete_partially_ordered_sets, For X, ccpo(X) ::=$ $CHAIN_COMPLETE(X).$Set. Some use the term complete for chain complete. .Source Gunter 92. Another variation of completeness is what I term Kleene Completeness, where every ascending sequence has a least upper bound. .See http://www/dick/maths/math_24_Domains.html#DOMAIN TARSKI_KNASTER::=Net{ |- $COMPLETE. .Source 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. |-$MINMAX. f::$monotonic, H::=$increasing_points(f). 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. Countable_complete::=$ Net{Use MINMAX. for all S:countable, one lub(S)}. 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) ) }? .Close . Semi-orders Semi-orders are used for several urposes including the modelling of before/after relationships between events in time. SEMIORDER::=Net{ .Source Luce 56, Library of Congress call number BF39.C66 and CACM, Feb 1978. Set::Sets, P::@(S,S)= previous_to. |-(SO1):For all x,y,z,w:S, if x P y P z then x P w or w P z, |-(SO2): For all x,y,z,w, if x P y and z P w then x P w or z P y, |-(SO3): for no x(x P x). ()|-(SO4): for some f:Real^Set, \delta:Real ~ Negative, for all x,y( f(x) > f(y)+\delta iff x P y). 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: .See http://www.soc.unitn.it/dsrs/IMC.htm Applicable to: OOP ,data structures, programs, texts, documentation, ... PART_WHOLE::=Net{ objects::Sets, -- the things that are wholes and/or parts isin::$strict_order(objects). APO::=isin. |-(PW0):$MINMAX(Set=>objects, strict=>isin,...) universe::objects. -- the largest object |-(PW1): $lub($objects)={$universe}. Example1::=Net{ objects::={auto,engine,radiator,radiator_cap,wheel1,wheel2,....} isin::={(engine,auto),(radiator,engine),(radiator,auto),..} universe::=auto. ()|- engine isin auto. ()|- radiator isin engine. }=::Example1. ()|-(PW2): finite iff finite$objects. parts::=/isin, -- the parts of x are those things "isin x". ()|-(PW3): For x:objects, $parts(x)= {y:$objects || y $isin x}. ()|-(PW4): For no x (x in$parts(x)). ()|-(PW5): for all x (x in $parts($universe)). elements::={x || no $parts(x)}, compounds::=$objects~$elements, ()|-(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... is_component_of::=$isin~(|[i:2..]$isin^i), components::=map[x:$objects]/$is_component_of(x). ()|-(PW7): |[i:2..]$isin^i =$isin^2, ()|-(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 In some cases there are no components. For example: Example2::= Net{ objects={(0..r]| r:(0..)}, for all r1,r2:objects, (0..r1] isin (0,r2] iff r1parts^2(x0), () |-(4): for y:parts(x0), some y' (y isin y' in parts(x0)), () |-(5): R:@(parts(x0),parts(x0)) ::={y,y'||y isin y' parts(x0)}, () |-(6): R==>(<>), () |-(7): R in (any)-(some), (choice)|-(8): some f:(any)-(1)(f==>R), () |-(9): map[i](x0.f^i): Nat-->parts(x), () |-(10): not finite. . Proof of 4 Let{ |- (4.1): y in parts(x0), (3) |-(4.2): y in parts^2(x0), (4.2) |-(4.3): y in parts(x2) and x2 in parts(x0), (4.3) |-(4.4): y <> y' in parts(x0) } } choice::=See .See http://www/dick/maths/logic_5_Maps.html#Choice For x, components(x) = greatest(slb{x}). For x,y:Things, common(x,y) ::= slb{x,y}. For x,y, interface(x,y) ::= gslb{x,y}, (def)|-(PW9): For x,y, interface(x,y)= {z:objects||z in common(x,y) and for no w:objects~{z} (z isin w in common(x,y) ) } (def)|-(PW10): For x,y, interface(x,y)=glb{x,y}. TAGGING::=Net{ Tagging is a process of assigning a string to every part so that we can (1) identify each part, and (2) encode the structure of the objects. labels::Sets, tags::#labels. The notation for strings of symbols (#, !, ...) is in .See http://www/dick/logic_6_Numbers..Strings.html and .See http://www/dick/math_62_Strings.html Dewey_decimal::@. Dewey_decimal iff labels=Nat. Knuth has an excellent discussion of "Dewey Decimal Notation". tag::objects-->tags, universe.tag=(). For all x,y:objects, some t:tags ( y.tag = (x.tag!t) iff y isin x). For all x,y:objects, (if y in components x then for one l:labels( x.tag = (y.tag!l) )). }=::TAGGING. hierarchy::@ for all x,y (no$common(x,y)). tree::@= $discrete and$hierarchy. branches(x) ::=|[I:@Nat]{B:I-->$objects||$components($objects) and B[1]=x). infinite_branches(x) ::={B:$branches||not finite cor(B) ). expansion::Nat0=fun[x]Card($components(x)). A Version of Konig's Infinity Lemma [Knuth 69,Vol 1, 2.3.4.3 Theorem K.] ()|-(Konig1): if not$finite and $tree and for all x( finite$components(x)) then for some $infinite_branches($universe). . Proof of Konig1 Let{ |-(Konig0): not $finite, |-(Konig1):$tree, |-(Konig2): for all x(not finite $components(x)). ()|-(Konig3): for all x:$objects, if not finite $parts(x) then for some y:$components(x)(not finite $parts(y)) B1:=$universe, ()|-(Konig4):not finite $parts(B1), ()|-(Konig5):some y:$components(B1)(not finite y ), ()|-(Konig6):B2 in $components(B1) and not finite$parts(B2), ... . Proof of Konig3 Let{ |-(Konig3a): x:$objects, |-(Konig3b): not_finite$parts(x), |-(Konig3c): all y:$components(y)( not finite$parts(x)). ()|-(Konig3d): not finite $components(x), ()|-(Konig3e):$parts(x)>=={$parts(y)||y:$components(x)} and $finite parts($components(x). ()|-(Konig3f): Card($parts(x))=+[y:$components(x)]Card($parts(y))<>infinity ()|-(Konig3g): finite parts(x). } } }=::PART_WHOLE. Part_whole::=$ $PART_WHOLE. FINITE_PART_WHOLE::=Net{ |-$PART_WHOLE |-(FPW0): finite. ()|-(FPW1): one N:Nat, all x($expansion(x)<=N). N::=the N:Nat, all x($expansion(x)<=N) .Hole ()|-(FPW2): for all x, some l:$components(x)-->1..N ()|-(FPW3): for some D:Nat, t:1..D->1..N, (TAGGING(labels=>1..N, tags=>1..D->1..N, tag=>t)) . Proof of FPW1 Consider{N::=lub$expansion($objects)}. }=::FINITE_PART_WHOLE. . Is_a IS_A::=Net{ for describing generaliaztion, subtyping, subclasses, inheritance, exported... objects::Sets, isa::strict_order(objects). AKO::isa. |- MINMAX(Set=>objects, strict=>isa,...) universe::objects. |-(isa1): lub(objects)={universe}. super::@(objects,objects). |-(isa2): isin =super;do(super). |-(isa3): sub=/super. For A:Sets, p:objects->A, inheritted(p) ::@=for all objects x,y(if x isa y then p(x)=p(y)). For A, p, exported(p) ::@=for all objects x,y(if y isa x then p(x)=p(y)). }=::IS_A. .Open Specially Ordered Sets . Totally Ordered Sets TOSET::=$ORDER and Net{total}. totally_ordered_set::=$Toset. Toset::= Totally Ordered Sets Toset::=$ $TOSET, For X, toset(X) ::=$Toset(X).$Set, toset::=$Toset.$Set. Totally ordered sets are also known as linearly ordered sets: Linearly_ordered_sets::=$loset. loset::=$toset. Loset::=$Toset. . Well Ordered Sets WOSET::=Net{ A partially ordered set where every subset has one least element. $ORDER. |-(WO0): for all S:@$Set~{{}} (one least(S)). bottom::=the least($Set), \bot::=$bottom. |-|-(WO_induction): invariants(strict) & (in(\bot))={$Set}. }=::WOSET. well_ordered_set::=$woset. Woset::=WOSET, Well ordered sets. For X,woset(X) ::=$Woset(X).$Set, woset::=$Woset.$Set. (Nat, <=) in WOSET. Knuth has a different definition .Source Knuth 69, 1.2.1.Ex15. KWOSET::=Net{ Knuth's Well Ordered Set. S::$Set, (<) ::Transitive(S) and Trichotomettic(S). (<=) ::=(<|=), (>) ::=(/<), (>=) ::=(/<=). |-(KWO0):For all A:@S~{{}}, some min(A). ()|-(KWO1): For all A, one min(A). ()|-(KWO2):(<) in Left_limited(S). [Knuth 69, 1.2.1.Ex15.f]. .See http://www/dick/maths/math_11_STANDARD.html#Kinds of relations ()|- (KWO3): no s:Nat->S(>(s)). ()|- (Induction principle): for P:@S(if for all x(if for all y(if y,>=). |-(WF1): (<) in Left_limited(S). .See http://www/dick/maths/math_11_STANDARD.html#Kinds of relations Minimal::=Set of elements greater than nothing else:@S, Minimal::= {x:S || for all y:S(not y < x)}. }=::WELL_FOUNDED_SET. NOETHERIAN_INDUCTION::=Net{ Emmy Noether's discovery - The Strongest Induction Principle Known to Humanity. WELL_FOUNDED_SET(S=>X). |-|-(Noether1): For P:X^@, if for all x:Minimal( P(x) ) and for all x:X~ Minimal (if for all z:X(if z P and for all x:X~Minimal (if \<(x)==>P then x in P) then P=X. }=::NOETHERIAN_INDUCTION. . Lattices lattice_order::=$ $MINMAX and Net{for all F:Finite_sets($Set), one lub(F) and one glb(F)}. complete_lattice_order::= MINMAX and Net{for all F:@(\$Set), one lub(F) and one glb(F)}. .Close Specially Ordered Sets . See Also See .See http://www/dick/maths/math_24_Domains.html and .See http://www/dick/maths/math_41_Two_Operators.html#LATTICE for further developments in the theory of orders. .Close Orders