- Object Theory
- : Idea
- : Examples
- : Abstract Generational System
- : Exercises
- : Term Paper
- : Project
- : Project - Probabalistic Generational Systems
- : Project - Fuzzy Generational Systems
- : Project - Generational Subsystems
- Notes on MATHS Notation
- Notes on the Underlying Logic of MATHS
- Glossary

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

- Trees::= Net{
- leaves::Sets,
- graft::trees><trees->trees,
- |- (T1): generate=map [X:@trees]{graft(x,y)||x,y:X},
- |- (T2): basis=leaves,
- |- (T3): free=true,
- |- (T4): GENESYS(trees),
- ...

}=::Trees.### LISP

- LISP::= Net{
- |- (L0): GENESYS(lists),
- |- (L1): generate=map X({cons(x,y)||x,y:X}),
- |- (L2): free,
- basis::={NUL}|atoms
- atoms::Sets,
- NUL::lists~atoms,
- T::atoms,
- cons::lists><lists->lists, car,cdr::generated->lists,
- atom::lists->{T,NUL}=map x (if (x in atoms then T else NUL)),
- null::lists->{T,NUL}=map x (if (x=NUL then T else NUL)),
- |- (L3): for all x,y:lists (car(cons(x,y))=x and cdr(cons(x,y))=y),
- |- (L4): for all x:generated (x=cons(car(x),cdr(x))),
- ...

}=::LISP.### Strings

STRINGS are defined elsewhere [ math_61_String_Theories.html] . - |- (L0): GENESYS(lists),
- GENESYS::= Net{
- Objects::Sets,
- generate::@Objects->@Objects =an operation that combines Objects to create new ones.
Nothing comes from nothing:

- |- (strict): generate({})={}.
More comes from more:

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

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

- the GENESYS(Objects=>Nat, generate=>map N({n+1||n:N}))
#### Example B

"clock arithmetic" (0,1,2,3,...,n-1,0,1,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.

#### Example A

Natural numbers (1,2,3,...) with i:=i+1 as generator:. . . . . . . . . ( end of section examples 2) <<Contents | End>>

Each generative system has an associated monoid of mappings:

- the GENESYS(Objects=>Nat, generate=>map N({n+1||n:N}))
- (generate)|- (monoid): ({generate^n || n:Nat0}, o, Id(@Objects)}) in Monoid.
Note. Monoid is defined in [ math_33_Monoids.html ] as a semigroup with a unit.

### Proof of monoid

Generate is a function, see [ logic_5_Maps.html#fun_monoid ] for theorem.### Novelty

In each generation novel objects can appear: - novel::@Objects->@Objects=map X(generate(X)~X),
- (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:

- invariant::={}./novel,
- (above)|- (G2): invariant={X||generate(X)==>X},
- (above)|- (G3): Objects in invariant,
- (above)|- (G4): {} in invariant.
- (above)|- (G5): for I:invariant, X:@I(generate(X)==>I)
A fixed set is one that does not grow:

- fixed::@Objects= {X|| generate(X) = X}.
- (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.

- For X1:@Objects, descendents(X1)::= {x2:Objects || for all I:invariant, if X1 ==> I then x2 in I}.
- (above)|- (G6): for X,x, if not x in descendents(X) then some I:invariant(X ==> I and not x in I).
- (above)|- (G7): for all X, X ==> descendents(X).
### Proof of G7

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

}

- |- (G7.1): not X ==> descendents X.
- (above)|- (G8): for X:Objects, Y:descendents(X), Z:generate(Y), ( Z are descendents(X)).
### Proof of G8

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

}.

- |- (G8.1): X:@Objects,
- (above)|- (G6): for n:Nat0, generate^n ==> descendents.
### Basies

A basis is a set objects that can, ultimately, generate any object. - basies::@@Objects={X:@Objects||(descendents(X)=Objects)},
- basies::=those sets of of objects that will generate all other objects.
In most Generational Systems a particular basis is given:

- basis::basies -- A particular starting set for generating all objects.
- 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: - 0th_generation::=basis.
- 1st_generation::=generate(basis)~basis.
- 2nd_generation::=generate(1st_generation)~1st_generation.
- 3rd_generation::=generate(2nd_generation)~2nd_generation.
- generation::Objects->Nat0,
- |- (G7a): generation(basis)=0,
- |- (G7b): for x:generated, generation(x)=min{n||x in generate^n(basis)~generate^(n-1)(basis)}.
- For all n:Nat0, (n)th_generation::Nat0->@Objects =n./generation
- |- (G8): for all n:Nat, n.th_generation= novel((n-1).th_generation).
- generations::={n.th_generation || n:Nat0}.
The following define various kinds of Generational Systems. Each property can be true or false.

- 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

- 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

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

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

- bounded_step::@= for some N:Nat0, all X:@Objects( |novel(X)| <= N ).
- finite_step::@= for all X:@Objects, some N:Nat0( |novel(X)| = N ).
- countable_step::@= for all X:@Objects( novel(X) --> Nat0).
- (above)|- (G9a): if bounded_step then finite_step and countable_step.
- (above)|- (G9b): if finite_step then countable_step.
Similarly for the basis:

- bounded_basis::@= for some N:Nat0( |basis| <= N ).
- finite_basis::@= for some N:Nat0( |basis| = N ).
- countable_basis::@= basis --> Nat0.
- (above)|- (G9c): bounded_basis iff finite_basis.
- (above)|- (G9d): if bounded_basis or finite_basis then countable_basis.
- (above)|- (countability theorem): if finite_basis and finite_step then Objects-->Nat0.
### Proof of countability theorem

This is just a sketch. - Let{
- |- (CT1): finite_basis.
- |- (CT2): finite_step.
- Since in each generation the novel objects form a finite set we can number them.
- So each object has a generation and a number within that generation.
- So we have a pair of number identifying each object that is generated.
- 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: - |- (CT1): finite_basis.
- 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.

- 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

- 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:

- converges to
- gets close to
- 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.

- weight::=map [x](2^-(generation(x))
Thus the later an object is generated, the "lighter" it becomes.

- differs::@Objects><@Objects=[X,Y](X~Y|Y~X)
- 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.

- (above)|-MetricSpace(@Objects,d).
- complete::@.
- |- (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.

- convergent::@Seq(@Objects)={S || for some L, all ε:(0..), abf i ( d(S[i],L) <= ε ) }
Note. abf stands for All but a finite number.

- 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. - STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html
# Glossary

- above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements. The previous and previous but one statments are shown as (-1) and (-2).
- given::reason="I've been told that...", used to describe a problem.
- given::variable="I'll be given a value or object like this...", used to describe a problem.
- goal::theorem="The result I'm trying to prove right now".
- goal::variable="The value or object I'm trying to find or construct".
- let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.
- hyp::reason="I assumed this in my last Let/Case/Po/...".
- QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
- QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
- RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last
assumption (let) that you introduced.

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 ]

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

Source: Peano

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

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

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]

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

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 might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.

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

For a more rigorous description of the standard notations see