Idea

The idea of an abstract data type(ADT) is fundamental to computer science. The idea of Type is equally fundamental to modern mathematics. A Type is a collection of objects with predefined operations, functions, and properties. An important difference between mathematical types and ADTs is that a computer can only work with elements of a type that can be computed! So an ADT consists only of those elemements in a type that can be generated by a finite process. Recently the word 'Object' seems to be applied to describe elements in ADTs, hence its use in the section. The objects are not particularly 'Object Oriented'. Polymorphism, inheritance and so on are part of the theory of types. Here we abstract the idea of working with the constructable objects of a type.

Key property distinguishing a data type from a logical Type, is that the ADT can only have objects generated by applying operations to a set of basic elements. If the computer can not compute some data then it does not have to work with that data. Hence the theory of Generational Systems.

This theory can be used to define the meaning of a XBNF (BNF extended into other areas) dictionary which avoids certain paradoxes [/www/dick/papers/rjb96x.xbnf.html]

Here are some examples of the Generational Systems [ GENESYS ]

Examples

 Strings	- generated by concatenating characters

 or	 	- generated by prefixing characters

 Files	 	- generated by inserting records at their end

 Trees	 	- generated from set of atoms by grafting

 Lists	 	- generated from NUL and atoms by a binary constructor.

 Natural Numbers

	 	- generated from 1 by adding 1.

 Data Bases

		- Entities and sets generated by 'PUT' and 'TAKE' operations

Natural Numbers

Peano
1. PEANO::=Net{GENESYS(Nat) and generate=map[X]{x+1||x:X} and basis={1} and free}

   Trees

2. Trees::=
   Net{

   1. leaves::Sets,
   2. graft::trees><trees->trees,
      
   3. |- (T1): generate=map [X:@trees]{graft(x,y)||x,y:X},
      
   4. |- (T2): basis=leaves,
      
   5. |- (T3): free=true,
      
   6. |- (T4): GENESYS(trees),
   7. ...

   
   }=::Trees.

   LISP

3. LISP::=
   Net{

   
   
   1. |- (L0): GENESYS(lists),
      
   2. |- (L1): generate=map X({cons(x,y)||x,y:X}),
      
   3. |- (L2): free,
   4. basis::={NUL}|atoms
   5. atoms::Sets,
   6. NUL::lists~atoms,
   7. T::atoms,
   8. cons::lists><lists->lists, car,cdr::generated->lists,
   9. atom::lists->{T,NUL}=map x (if (x in atoms then T else NUL)),
   10. null::lists->{T,NUL}=map x (if (x=NUL then T else NUL)),
       
   11. |- (L3): for all x,y:lists (car(cons(x,y))=x and cdr(cons(x,y))=y),
       
   12. |- (L4): for all x:generated (x=cons(car(x),cdr(x))),
   13. ...

   
   }=::LISP.

   Strings

   STRINGS are defined elsewhere [ math_61_String_Theories.html] .

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

Abstract Generational System

1. GENESYS::=
   Net{

   1. Objects::Sets,
   2. generate::@Objects->@Objects =an operation that combines Objects to create new ones.

      Nothing comes from nothing:
      

   3. |- (strict): generate({})={}.

      More comes from more:
      

   4. |- (monotone): for all X1,X2:@Objects, if X1==>X2 then generate(X1)==>generate(X2).

      Immortality of Objects:
      

   5. |- (immortallity): for all X:@Objects, (X==>generate(X)).

      Examples 2

      Example A

      Natural numbers (1,2,3,...) with i:=i+1 as generator:
      1. the GENESYS(Objects=>Nat, generate=>map N({n+1||n:N}))

         Example B

         "clock arithmetic" (0,1,2,3,...,n-1,0,1,2,...)
      2. (Objects=>Nat mod n, generate=>Map N({(n+1)mod n || n:N})).

         Other examples

         Relations, unary algebra, digraph, or dynamical system have maps in Objects->Objects that extend naturally to 'generative systems' with maps @Objects->@objects. In other systems new elements come from combining elements together but where a single object generates nothing new by itself.

      . . . . . . . . . ( end of section examples 2) <<Contents | End>>

      Each generative system has an associated monoid of mappings:
      

   6. (generate is a mapping)|- (monoid): ({generate^n || n:Nat0}, o, Id(@Objects)}) in Monoid.

      Novelty

      In each generation novel objects can appear:
   7. novel::@Objects->@Objects=map X(generate(X)~X),
      
   8. (above)|- (G1): for all X(generate(X)=X|novel(X) ).

      A set of Objects that generates nothing new is called an invariant set of objects:

   9. invariant::={}./novel,
      
   10. (above)|- (G2): invariant={X||generate(X)==>X},
       
   11. (above)|- (G3): Objects in invariant,
       
   12. (above)|- (G4): {} in invariant.

       
       

   13. (above)|- (G5): for I:invariant, X:@I(generate(X)==>I)

       A fixed set is one that does not grow:

   14. fixed::@Objects= {X|| generate(X) = X}.

       
       

   15. (above)|- (fixed_invariant): fixed==>invariant.

       The descendents of a set of objects is the smallest collection of objects that includes the set and is also invariant.

   16. For X1:@Objects, descendents(X1)::= {x2:Objects || for all I:invariant, if X1 ==> I then x2 in I}.

       
       

   17. (above)|- (G6): for X,x, if not x in descendents(X) then some I:invariant(X ==> I and not x in I).
       
   18. (above)|- (G7): for all X, X ==> descendents(X).

       Proof of G7

   19. For all X, X ==> descendents(X)
   20. Let{
       
       
       1. |- (G7.1): not X ==> descendents X.
          
       2. (above)|- (G7.2): some x in X and not x in descendents X.
          
       3. (G7.2)|- (G7.3): x in X.
          
       4. (G7.1)|- (G7.4): x not in descendents X.
          
       5. (G7.4)|- (G7.5): some I:invariant (X ==> I and x not in I).
          
       6. (G7.5)|- (G7.6): I in invariant.
          
       7. (G7.5)|- (G7.7): X are I,
          
       8. (G7.5)|- (G7.8): x not in I.
          
       9. (G7.3, G7.7)|- (G7.9): x in X ==> I.
          }

       
       

   21. (above)|- (G8): for X:Objects, Y:descendents(X), Z:generate(Y), ( Z are descendents(X)).

       Proof of G8

   22. For X:Objects, Y:descendents(X), Z:generate(Y), ( Z are descendents(X))
   23. Let{
       
       
       1. |- (G8.1): X:@Objects,
          
       2. |- (G8.2): Y:descendents(X),
          
       3. |- (G8.3): Z:generate(Y),
          
       4. |- (G8.4): not ( Z are descendents(X)),
          
       5. (G8.4)|- (G8.5): some z in Z~descendents(X)
          
       6. (G8.5)|- (G8.6): z in Z
          
       7. (G8.5)|- (G8.7): some I:invariant(X==>I and z not in I)
          
       8. (G8.7)|- (G8.8): I:invariant
          
       9. (G8.7)|- (G8.9): X are I
          
       10. (G8.7)|- (G8.10): z not in I
           
       11. (G8.8, G8.9, G8.2)|- (G8.11): Y are I
           
       12. (G8.11, G8.8, G8.3)|- (G8.12): Z are I
           
       13. (G8.6)|- (G8.13): z in I
           }.

       
       

   24. (above)|- (G6): for n:Nat0, generate^n ==> descendents.

       Basies

       A basis is a set objects that can, ultimately, generate any object.
   25. basies::@@Objects={X:@Objects||(descendents(X)=Objects)},
   26. basies::=those sets of of objects that will generate all other objects.

       In most Generational Systems a particular basis is given:

   27. basis::basies -- A particular starting set for generating all objects.

   28. generated::=Objects~basis.

       Example A. Nat has only one basis = {1} because all i>1 are generatable from 1, and there are no numbers less than 1 to generate 1.

       Example B. Every nonempty subset of Nat/n is a basis.

       Generations

       We assume we can attach a label to each object - its generation:
   29. 0th_generation::=basis.
   30. 1st_generation::=generate(basis)~basis.
   31. 2nd_generation::=generate(1st_generation)~1st_generation.
   32. 3rd_generation::=generate(2nd_generation)~2nd_generation.

   33. generation::Objects->Nat0,
       
   34. |- (G7a): generation(basis)=0,
       
   35. |- (G7b): for x:generated, generation(x)=min{n||x in generate^n(basis)~generate^(n-1)(basis)}.
   36. For all n:Nat0, (n)th_generation::Nat0->@Objects =n./generation

       
       

   37. |- (G8): for all n:Nat, n.th_generation= novel((n-1).th_generation).

   38. generations::={n.th_generation || n:Nat0}.

       The following define various kinds of Generational Systems. Each property can be true or false.

   39. loop_free::@=for all G1,G2:generations( if G1 & G2 then G1=G2).

       In a 'loop_free' system operations can not regenerate earlier generations.

       Example

   40. Nat is loop free but Nat/n is not.

       By choosing one object in each generation in a loop free system, we get a one-one imbedding of the natural numbers into a subset of the objects(Nat0-->Objects), therefore
       

   41. (above)|- (G9): if loop_free then Objects not in Finite_sets.

       Often the objects in the system have some notion of size and the property that bigger objects are constructed from smaller ones.

   42. growing::@, if growing then for some size:Objects->Nat0, for all X:Objects,N:novel(X), x:X, n:N, (size(n)>size(x)) ?? if growing then loop ?

       Several common classes of generational systems occurs when there the size of the set of novel objects is limitted in some way. For example the set of strings is generated from a finite alphabet by prefixing members of the alphabet onto existing strings.

   43. bounded_step::@= for some N:Nat0, all X:@Objects( |novel(X)| <= N ).
   44. finite_step::@= for all X:@Objects, some N:Nat0( |novel(X)| = N ).
   45. countable_step::@= for all X:@Objects( novel(X) --> Nat0).
       
   46. (above)|- (G9a): if bounded_step then finite_step and countable_step.
       
   47. (above)|- (G9b): if finite_step then countable_step.

       Similarly for the basis:

   48. bounded_basis::@= for some N:Nat0( |basis| <= N ).
   49. finite_basis::@= for some N:Nat0( |basis| = N ).
   50. countable_basis::@= basis --> Nat0.

       
       

   51. (above)|- (G9c): bounded_basis iff finite_basis.
       
   52. (above)|- (G9d): if bounded_basis or finite_basis then countable_basis.

       
       

   53. (above)|- (countability theorem): if finite_basis and finite_step then Objects-->Nat0.

       Proof of countability theorem

       This is just a sketch.
   54. Let{
       
       
       1. |- (CT1): finite_basis.
          
       2. |- (CT2): finite_step.
       3. Since in each generation the novel objects form a finite set we can number them.
       4. So each object has a generation and a number within that generation.
       5. So we have a pair of number identifying each object that is generated.
       6. There are several ways of mapping a pair of number one-to-one into the numbers.
          }

       The coutabillity of finitely based generational systems means that no paradox arrises from assuming that an equation like X=generate(X).

       Freedom

       Often an object can only be generated in a unique way:
   55. convergence_free::=for all X1,X2 if no X1&descendents(X2) and no (X2&descendents(X1)) then no ( descendents(X1)&descendents(X2))

       In a convergence free system there is no more than one way to generate an element. .Dangerous_bend Not convergence to a limit, but the meeting of two parallel families of generated objects.

       In the most unrestricted generational systems - the free systems - there is no convergence or loops. This is freedom in the (oldfashioned) categorical sense. It can be shown that unfree systems are the image of a free system.

   56. free::=convergence_free & loop_free.

       ?? if free then unique ancestry for every element ?

       ?? if free then isomorphic to some set of tree structures ?

       Beyond Finiteness

       The following is a generalization of the work done on defining what it means for a process to converge - as used in languages, trees, etc.

       The kind of iterative process modeled here, can often appear to be getting close to a kind of fixed point which - if it only existed, would be an "infinite" object. In some data structures for example a repeated process of adding a new element generates objects that start to behave very like a circular chain of objects... so in a sense one can claim that in LISP an equation like

   57. x=cons[A;x] has as its "smallest solution" a dotted pair whose cdr points to itself and with car equal to A. See the LISP 1.5 manual for a discussion of how such 'list structures' are actually constructed. Compare Manes & Arbib'd theory of the solution of X=A+B!X in a suitable initial algebra.

       Trying to reason with the infinite is fallacy prone. Luckily the topologists have developed a package of consistent ideas that we can use to define ideas like:

       ---

       1. converges to
       2. gets close to
       3. looks like its going to

       ---

       for proving or disproving the existence and uniqueness of limits of series and the like.

       ??... ?? @generations(Objects) in filterbases(Objects)?

       Topology of Sets of Objects

       One problem is defining a set of abstract objects recursively and not being sure whether the equations define a unique fixed point or not. The solution to this problem is a generalisation of the method used for languages and demotational semantics - define a metric space that measures how well two sets match - in particular. The trick is choose a metric so that the later a set is generated then the closer it is to an ideal (and unreachable) set of objects.

       In the case of sets of abstract objects we can construct a metric which measures how far apart two sets are - in the sense that a difference that is "younger" is a bigger difference than one that is older.

   58. weight::=map [x](2^-(generation(x))

       Thus the later an object is generated, the "lighter" it becomes.

   59. differs::@Objects><@Objects=[X,Y](X~Y|Y~X)
   60. d::(@Objects><@Objects)->Real= if X=Y then 0 else max (weight (differs(X,Y))).

       The set of Objects now has the structure of metric space with d acting as the measure of the distances between sets of objects.
       

   61. (above)|-MetricSpace(@Objects,d).

   62. complete::@.
       
   63. |- (G10): If complete then MetricSpace(@Objects,d, complete).

       By assuming completeness we assert the existence of objects that can not be generated, but which can be approximated to by a convergent sequence of generated objects.

   64. convergent::@Seq(@Objects)={S || for some L, all ε:(0..), abf i ( d(S[i],L) <= ε ) }

       Note. abf stands for All but a finite number.

   65. convergent::@Objects->@Objects={G || (G^(_))in convergent}.

       ?? if @Objects in compact then ...? [click here if you can fill this hole]

       ?? if cauchy_complete then...unique fixed points for contracting definitions ? [click here if you can fill this hole]

       ?? product spaces and so mutual recursion...? [click here if you can fill this hole]

       ?? if loop then discrete ? [click here if you can fill this hole]

   
   }=::GENESYS.

. . . . . . . . . ( end of section Abstract Generational System) <<Contents | End>>

Exercises

Work out the following generational systems:

GENESYS(Sets) [click here if you can fill this hole]

GENESYS(Bags) [click here if you can fill this hole]

GENESYS(Files) [click here if you can fill this hole]

GENESYS(Queues) [click here if you can fill this hole]

GENESYS(Stacks) [click here if you can fill this hole]

Term Paper

JWW Conway has developed a generation theory of great power and generallity. D. Knuth has written a short romantic novel featuring this system. Find a copy of the the novel, read it, and express JWW's system using 'GENESYS'.

Project

GENESYS(DataBase) [click here if you can fill this hole] Use CODASYL, Relational model, or Object-oriented models.

Project - Probabalistic Generational Systems

Develop a variation of the GENESYS model that handle probabilistic generational systems rather than non-deterministic ones. In this each novel element has a number between 0 and 1 inclusive indicating the probability of its occurence. [click here if you can fill this hole]

Project - Fuzzy Generational Systems

Develop a variation of the GENESYS model that handle Fuzzy generational systems rather than non-deterministic ones. In this each novel element has a number between 0 and 1 inclusive indicating the the degree of its membership in the novel sets. [click here if you can fill this hole]

Project - Generational Subsystems

Construct an abstract model of a relationship between generational systems such that one generates a subset of the objects in the other one. The result should be able to show that a grammar is a generational subsystem of the set strings defined above. [click here if you can fill this hole]

. . . . . . . . . ( end of section Object Theory) <<Contents | End>>

Notes on MATHS Notation

Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.

The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle = Net{radius:Positive Real, center:Point}.

For a complete listing of pages in this part of my site by topic see [ home.html ]

Notes on the Underlying Logic of MATHS

For a more rigorous description of the standard notations see