# Simplified Structure

A simplified description of object membership is provided. The family of basic structures [] (O, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is narrowed by three additional assumptions:
• powerclass completeness: .ec is a total map,
• monotonicity condition: (ϵ¯) = (ϵ),
• rank minimality: the rank or r is ω.
The resulting family of monotonic eigenclass structures is axiomatized in the signature (O, .ec, , r) by five simple conditions. In comparison to basic structures, less preliminary definitions are required.

#### Preface

##### Author
 Ondřej Pavlata Jablonec nad Nisou Czech Republic ##### Document date
 Initial release March 12, 2015 Last major release March 12, 2015 Last update March 12, 2015
(see Document history)
##### Warning
1. This document has been created without any prepublication review except those made by the author himself.

#### Introduction

There are three fundamental relations that can be used for the description of the core part of data model in object technology: ϵ (object membership), (inheritance) and .ec (the powerclass / eigenclass map). All relations can be regarded as endorelations so that they are defined on a unified domain O of objects. A detailed introduction is provided in [].

We further assume that the .ec map is total (that is, every object has a powerclass / eigenclass).

##### Simplified correspondence between objects and sets
By simplification, ϵ, and .ec can be viewed as abstractions of fundamental notions of set theory: object membership corresponds to set membership, inheritance to set inclusion and the powerclass map to the powerset operator. In particular, the subsumption rule has a direct set-theoretic translation:
•  (ϵ) ○ (≤) ⊆ (ϵ) (all members of an object x are among members of any ancestor of x) (∈) ○ (⊆) ⊆ (∈) (all elements of a set x are among elements of any superset of x).
Similarly, the extension rule for the powerclass translates to the definion of the powerset:
•  (.ec) ○ (϶) = (≥) (members of the powerclass of x are the descendants of x) ℙ ○ (∋) = (⊇) (elements of the powerset of x are the subsets of x).
##### Monotonicity
In the major part of object technology, the composition of ϵ and is commutative. That is, the monotonicity rule applies:
• () (ϵ) (ϵ).
Note that this is unlike the composition of and in the standard universe of sets. The powerclass x.ec then becomes such a container of x that has the smallest ϵ-preimage. This leads to the following abstraction:
• (ϵ) = (.ec) (),
that is, x.ec is the least container of x. As a particular consequence, the core structure can be expressed in the signature (O, , .ec) of Zermelo-Fraenkel algebras known from algebraic set theory (AST).[] In terms of AST, the .ec map can be viewed as a monotone successor operator. However, we prefer to use the single term eigenclass, established in [].

We can observe that the above equations (those involving .ec) imply that the .ec map is an order embedding: Let .ce denote the inverse of .ec and substitute (.ec) () for (ϵ) in () = (ϵ) (.ce). Then

• () = (.ec) () (.ce)   (equivalently,   x y   ↔   x.ec y.ec).
##### Basic nomenclature of objects
For convenience, we provide a (slightly adjusted) diagram from [] showing the basic nomenclature of objects.
 O … objects   = T ⊎ C ⊎ O.ec O.ec … eigenclasses O.pr … primary objects   = T ⊎ C T … terminals   = O ∖ r.↧ C … classes   = O.pr ∖ T H … helix objects   = r.ϵ∗ = R.↥ R … reduced helix   = r.ec∗ r … inheritance root r.↧ … non-terminals (`Class`es)   = O.ϵ.↧
 r.ec(i).϶ ∖ r.ec(i).↧ … i-th metalevel
The diagram uses a sample Ruby core structure whose non-built-in part is created by
```class A; end; class B < A; end; u = B.new; v = B.new
```
The black line shows the division between primary objects and eigenclasses. Note that being subject to the Ruby object model, the structure is quite a special representant (rather than generic) of the family of S1v-structures.

#### S1v: Monotonic eigenclass structure of ϵ

We present the family of monotonic eigenclass structures. To emphasize the simplicity of description (in comparison with basic structures []) there are only few definitions used in the axiomatization.
##### Axioms
By an S1v structure (also a monotonic eigenclass structure) we mean a structure S = (O, .ec, , r) where
• O is a set of objects,
• .ec is the eigenclass map O O,   (elements of O.ec are eigenclasses)
• is the inheritance relation between objects,
• r is the inheritance root, a distinguished object.
The usual ancestor / descendant terminology is used for inheritance. Objects that are not descendants of r are terminal(s). Let .ec denote the reflexive transitive closure of .ec. For an object x, the set x.ec (the image of {x} under .ec) is the eigenclass chain of x.
The structure is subject to the following axioms:
 (S1v~1) Inheritance, ≤, is a partial order. (S1v~2) The eigenclass map, .ec, is an order-embedding of (O, ≤) into itself. (S1v~3) Objects from eigenclass chains of terminals are minimal in inheritance. (S1v~4) Every eigenclass is a descendant of the inheritance root, O.ec ⊆ r.↧. (S1v~5) The eigenclass chain of r has no lower bound in ≤.
##### Definitions
In an S1v structure S = (O, .ec, , r) the following additional notation and terminology applies. Note that the definitions include several statements.
###### Eigenclass chains
• Let .ce denote the partial map between objects that is the inverse of .ec. Let .ce be the inverse of .ec so that it is the reflexive transitive closure of ce.
• For an integer i, let .ec(i) be the i-th composition of .ec with itself if i ≥ 0 (with .ec(0) being the identity on O) and the -i-th composition of the inverse of .ec otherwise. Similarly with .ce.
• Let .pr be the map between objects such that:   x = y.pr   ↔   {x} = y.ce O.ec.
• For an object x,
• x.ec is the eigenclass of x,
• x.ce, if defined, is the eigenclass predecessor of x,
• x.pr is the primary object of x,
• x.eci is the eigenclass index of x, defined as the unique natural i such that x.pr.ec(i) = x.
###### Object membership and its powers
• The object membership relation, ϵ, is the composition (.ec) ().
• For an integer i, let ϵi denote the i-th power of ϵ defined by
• (ϵi)   =   () .ec(i) ().
That is, (ϵ0) = (), (ϵ-1) = () (.ce), and for a positive natural i,   ϵi (resp. ϵ-i) equals the i-th power of ϵ (resp. ϵ-1) in the sense of relational composition.
• Let ϵ and ϵ- be transitive closures of (ϵ0) (ϵ1) and (ϵ0) (ϵ-1), respectively. Equivalently,
• (ϵ) = .ec ()   and   (ϵ-) = () .ce.
• The usual notation and terminology for and ϵ applies, in particular, ./. and .ϵ/.϶ are the respective image/preimage operators. Similarly for ϵi and ϵ.
###### Distinguished sets of objects
• The set O.ec consists of eigenclasses.
• The set O.pr = O O.ec is the set of primary objects.
• The set C of classes is defined as r. O.ec.
• The set T of terminals is defined such that O = T C O.ec.
• The set R = r.ec (the eigenclass chain of r) is the reduced helix.
• The set H = r.ϵ = R. is the set of helix objects.
###### Metalevels
• The metalevel index of an object x is denoted x.mli and defined by
• x.mli = sup { i | x ϵ1-i r, i },   equivalently, x.mli = min { i | x r.ec(i), i }.
For every natural i, the set r.϶-i = r.ec(i). consists of objects x such that x.mli > i.
• (S1v~5) asserts that x.mli is finite for every object x. (Here we refer to the first expression of x.mli.)
• The i-th metalevel, i , is the set r.϶1-i r.϶-i of objects whose metalevel index equals i.
• The 0-th metalevel is the set T of terminals.
• The i-th metalevel equals t.϶ t. where t = r.ec(i) is the top of the (i+1)-th metalevel.
###### Rank and boundedness
• The rank of an object x is denoted x.d and defined by
• x.d = sup { a.mli + i | a ϵi x, i }.
• The bounded membership relation, , is the domain restriction of ϵ to objects with finite rank:
• x y   iff   x ϵ y and x.d < ω.
• Objects with finite rank are bounded, the remaining are unbounded. Thus, O. is the set of bounded objects.
• A set X of objects is bounded (resp. unbounded) if sup(X.d) < ω (resp. sup(X.d) = ω).
###### Leaf
• An object x is a leaf if it is primary all objects from x.ec are minimal in . Observations:
• (S1v~3) states that every terminal object is a leaf.
• x is a leaf   ↔   x.ec = x.ec..   (In particular, x is bounded.)
• x is a leaf   ↔   x is primary and x.϶-i = {x}.ec(i) for every natural i.
###### Instance-of and the .class map
Recall that C denotes the set of classes which are exactly the primary non-terminal objects, i.e. C = O.pr T.
• The instance-of relation is the range-restriction of ϵ to C.
• The .c partial map is the partial closure operator O O defined by:
• x.c = y   ↔   y is the bottom of x. O.ec.
• The .class partial map is the composition .ec.c. Equivalently,
• x.class = y   ↔   y is the bottom of x.ϵ C, the least container of x that is a class.
If x.class = y then we say that y is the class of x or, equivalently, x is a direct instance of y. Obviously, direct-instance-of is a subrelation of instance-of.
###### Polars of ≤
For an object a and sets X, Y of objects we let
• X Y   iff   x y for every x X and y Y,
• a X   iff   {a} X,
similarly for <, and >. Moreover, denote . and . the polar maps of , that is,
• X. = { x | x X } is the set of lower bounds of X, similarly, X. is the set of upper bounds,
• X. = { x | x < X } is the set of strict lower bounds of X, simlarly for X.,
• a. = {a}.   (that is, a. is the set a. {a} of strict descendants of a).
###### Boundedly complete ideal
• A (necessarily non-empty) set X of objects is a boundedly complete ideal if
• X is a down-set w.r.t. (that is, X = X.), and
• every bounded subset Y of X has an upper bound in X (that is, X Y. ).
• A set X of objects is a principal ideal if it is a principal ideal w.r.t. , i.e. X = x. for a unique object x.
##### Properties

Proposition: In an S1v structure S = (O, .ec, , r) the following are satisfied:

1. S is uniquely given by object membership, ϵ:
 x ≤ y ↔ x.ϵ ⊇ y.ϵ, x.ec = y ↔ x.ϵ = y.↥. (In addition, x.ec = y → x.↧ = y.϶ but ← does not hold in general.)
2. For every integers i, j,
• (ϵi) (ϵj) (ϵi+j),   (in particular, the subsumption and monotonicity rules apply)
• (ϵi) (϶-i) = .ec(i).
3. For every integers i, j, k and every objects x, y,
• x.ec(i) ϵk y.ec(j)   ↔   x ϵi+k-j y     whenever x.ec(i) and y.ec(j) are defined.
For i = j = 1 and k = 0 the statement reduces to (S1v~2).
4. The set R is linearly ordered:   r.ec(i) r.ec(j)   iff   i ≥ j.
##### Embedding
Let S = (O, .ec, , r) and V = (V, .ec, , rω) be S1v structures. We say that a map from O to V is an embedding of S into V if it is embedding w.r.t. the constituents of the definitional signature, i.e. for every objects x, y from O,
(a) x.ν.ec = x.ec.ν,   (b) x y   ↔   x.ν y.ν,   (c) r= rω.
We say that an embedding is faithful if, in addition, it is embedding w.r.t. .pr and .d, i.e. for every x O,
(d) x.ν.pr = x.pr.ν,   (e) x.ν.d = x.d.
If O V and the inclusion map O V is a (faithful) embedding then V is said to be a (faithful) extension of S. In addition, the set O, as a subset of V, is said to form a (faithful) substructure of V.

Observations:

1. Every embedding is implicitly embedding w.r.t. ϵi and .mli, i .
2. Let S = (O, .ec, , r) be an S1v structure.
1. Both R and H form a faithful substructure.
2. R forms the minimum substructure.
3. If X forms a faithful substructure then so does X T.ec.

#### Instances

In this section we introduce instantially complete structures. In these structures, each class has at least 2 direct free instances which ensures extensional consistency of objects. Creating new free instances can be thought of as class instantiation. In the canonical semantics, if q is a class then
• `x = q.new`   (Ruby syntax)
creates a new object x such that x.class = q and x. = q.ϵ-1. If q is not a metaclass (i.e. q is from the first metalevel and thus q.ϵ-1 = ) then x becomes a terminal object.
##### Free instance
We say that an object x is a free instance if the following conditions are satisfied:
 (A) x is primary. (B) x.ϵi = {x}.ec(i) ∪ x.class.ϵi-1 for every natural i. (In particular, x.class is defined.) (C) x.d = x.mli. (In particular, x is bounded.)
An object x is called a free member if x.pr is a free instance. Subsequently, a partial map .τ : O O is defined by
• x.τ = y   ↔   x is a free member and x.pr.class.ec(i) = y where i = x.eci.
That is, is the unique subrelation of ϵ that is parallel to .class and whose domain is the set of free members. If x.τ = y then x is a direct free member of y. If, in addition, y is primary (so that x.class = y) then member can be replaced by instance. We use notation for powers of just like for powers of .class. In particular, x.τ(-1) is the set of direct free members of x (or direct free instances of x if x is a class).

Proposition: Let x be an object and denote X = x.τ(-1). Then for every object y the following are satisfied:

1. If X y.   then   x y or X = or X = {y}.ce.
2. X. x.϶ = X {x}.ce.
1. If, in addition, X has at least 2 elements then the following are satisfied:
• If x. y.   then   x y.
• If x is primary   then   X. x.϶ = .
##### Example
In the following example, the `F` class is a leaf that is a free direct instance of the `M` class. Dashed brown arrows indicate the domain-restriction of inheritance (in the reflexive transitive reduction) to the eigenclass chain of `F`.
The example illustrates that adding free instances makes objects extensionally consistent. In the restricted structure, without the eigenclass chain of `F`, the `M` class is not extensionally consistent since `M`. = `N`. = {`A`, `B`}. This is changed by a free instantiation of `M`.
##### Instantially complete structure
We say that an S1v structure is instantially complete if every class has at least 2 direct free instances.

Observations: In an instantially complete structure S the following holds:

1. C = O.class.
2. For every non-terminal objects x, y,
1. x. y.   iff   x y,
2. if x is a class then X x. for some 2-element set X such that X. x.϶ = .

Corollary: S is pre-complete.

##### Instance 1-completion
Let S = (O, .ec, , r) and S0 = (O0, …) be S1v structures. We say that S is an instance 1-completion of S0 if S is a faithful extension of S0 such that the following conditions are satisfied:
1. Every new primary object is a (a) leaf and (b) free instance.
2. Every old class x has exactly n new direct instances where n equals
• 2 if x has no old direct free instances,
• 1 if x has exactly one old direct free instance,
• 0 if x has more than one old direct free instance.
(Recall that objects from O are either old or new according to whether they belong to O0 or not, respectively.)

Proposition:

• Every S1v structure S0 has an instance 1-completion S. Moreover, S is created from S0 in the following steps:
1. Let (N.pr O0, .class) be an extension of (O0, .class) such that
• N.pr.class C0, where C0 is the set of old classes, and
• for every x C0, the set x.class(-1) N.pr has exactly 0, 1 or 2 elements according to (Ⅱ).
2. Let (N, .ec) be an extension of (N.pr, ) where .ec is an injective well-founded map on N such that N = N.pr N.ec.
3. Denote O = O0 N so that (O, .ec) is a disjoint union of (N, .ec) and (O0, .ec).
4. Let S = (O, .ec, , r) be the extension of S0 such that for every x from N.pr and every natural i,
• x.ec(i). = ,   and
• x.ec(i). = x.class.ϵi-1   where ϵ is object membership in S0.
Recall that for an object a,   a. (resp. a.) is the image (resp. pre-image) of a under <.
##### Instance completion
Let S = (O, .ec, , r) and S0 = (O0, …) be S1v structures. We say that S is an instance completion of S0 if S is a faithful extension of S0 such that the following conditions are satisfied:
1. Every new object (a) has no old descendants and (b) is a free instance.
2. Every class x has exactly n new direct instances where
• n equals 0, 1 or 2 according to 1-completion if x is old
• n equals 2 if x is new.

Proposition:

1. If S is an instance completion of S0 then S is instantially complete.
2. Every S1v structure S0 has an instance completion S. Moreover, S is created from S0 as the union of S1v structures Si = (Oi, …), i , such that for every natural i, Si+1 is an instance 1-completion of Si.

#### Complete monotonic structure of ϵ

This section describes the monotonic counterparts of complete and pre-complete basic structures of ϵ, as well as the monotonic version of the completion theorem. The difference is as follows:
 In complete basic structures of ϵ, the set { x.∍ | x ∈ O } is the set of all subsets of O.∍. In complete monotonic structures of ϵ, the set { x.∍ | x ∈ O } is the set of all downsets in (O.∍, ≤).
##### (ω+1)-superstructure
By an (abstract) (ω+1)-superstructure we mean a structure (V, ) where V is a set of objects and is a relation between objects such that the following conditions are satisfied:
 (co~1) ∊ is well-founded. (co~2) ∊ is extensional on V.∊, that is, for every x, y from V.∊,   if x.∍ = y.∍ then x = y. (co~3) V.∍ is the set of all objects with finite ∊-rank. (co~4) For every subset X of V.∍ there is an object x such that x.∍ = X.

Note: The x object in (co~4) is unique for X . By allowing empty X in the quantification it is ensured that there is at least one object (i.e. V ) and, consequently, the rank of equals ω+1.

Recall that an (ω+1)-structure is definitionally equivalent to a complete structure of ϵ such that r.d = ω. The inheritance relation, , is given by

• x y   ↔   x = y or x. y..
##### Pre-complete monotonic structure
An S1v structure S = (O, .ec, , r) is said to be pre-complete if it satisfies the following conditions:
 (A) S is extensionally consistent: For every objects x, y,   x ≤ y   ↔   x = y or ∅ ≠ x.∍ ⊆ y.∍. (B) S is eigenclass consistent: For every object x,   x ∈ O.ec   ↔   x.϶ is a boundedly complete ideal.
We also say that S is a pre-complete monotonic structure.

Proposition:

1. A pre-complete monotonic structure is uniquely given by its bounded membership, :
 Inheritance root r.∍ = O.∍ Inheritance x ≤ y ↔ x = y or ∅ ≠ x.∍ ⊆ y.∍ Bounded inheritance x ∊0 y ↔ x ≤ y and x ∈ O.∍ Eigenclass map x.ec = y ↔ x.∍0 = y.∍ Object membership x ϵ y ↔ x.∍0 ⊆ y.∍
2. Pre-complete monotonic structures (O, .ec, , r) can be axiomatized via (O, ):
 (1) ∊ is well-founded. (2) ∊ is extensional on O.∊, that is, for every x, y from O.∊,   if x.∍ = y.∍ then x = y. (3) O.∍ is the set of all objects with finite ∊-rank. (4) O.∍ = r.∍ for some (necessarily unique) object r. (5) For every object x,   x.∍ is a downset.   (That is, the monotonicity rule (≤) ○ (∊) ⊆ (∊) holds.) (6) For every object x,   there is an object y (= x.ec) such that x.∍0 = y.∍. (7) For every object x,   if x.϶ is a boundedly complete ideal   then   x.∍.∍ = u.∍ for some object u.
3. An instantially complete S1v structure is pre-complete.
4. Corollary: Every S1v structure can be faithfully embedded into a pre-complete monotonic structure.
##### Complete monotonic structure
An S1v structure S = (O, .ec, , r) is said to be complete if it satisfies the following conditions:
 (A) S is extensionally consistent: For every objects x, y,   x ≤ y   ↔   x = y or ∅ ≠ x.∍ ⊆ y.∍. (B) S is extensionally ↧-complete: For every downset X of O.∍ there is an object x such that x.∍ = X.
In this case we also say that S is a complete monotonic structure. In (B), -complete should be read as downset-complete. (A set X of objects is a downset if X. = X.)

Proposition:

1. Every complete monotonic structure is pre-complete.
2. Complete monotonic structures can be axiomatized via bounded membership, :
 (1–3) Same as (co~1)–(co~3). (4) Same as (co~4) except that subset is replaced by downset. (5) (≤) ○ (∊) ⊆ (∊).
3. The lifted version L of (O., ) is isomorphic to (D(O.), ), where D(O.) is the set of all downsets in (O., ). Consequently, L is a complete lattice that is atomic and completely distributive.
4. Let V = (V, ) be an (ω+1)-superstructure and let O denote the set of all hereditarily -complete objects, i.e.
• O = { x | x. = x.. O }.
Then S = (O, ) is a complete monotonic structure. The set T = O O. of terminal objects of S equals the ground stage V1 = V V. of V. The .mli and .d maps in S and V are coincident on O. If .ecV denotes the powerclass map in V (and .ec is the eigenclass map in S) then the following holds for every object x from O:
• x.ec = x.ecV if x T.ec,
• x.ec < x.ecV otherwise.
##### Completion
Let S = (O, .ec, , r) and V = (V, .ec, , rω) be S1v structures such that S is pre-complete and V is complete. Define the embedding sequence
• 0, 1, …, ω =
of maps from O to V as follows:
1. The restriction of i to terminals is for every i identical and forms a bijection between T and V1 = V V..
2. The restriction of i to the set O. of non-terminal objects x is recursively defined by
• x.ν0. = x.0.ec.,
• x.νi+1. = x.϶i.ec.,
• x.ν. = { x.νi. | i < ω }.

Proposition: (The completion theorem)

##### References
 B.A. Davey, H.A. Priestley, Introduction to lattices and order, Cambridge University Press 2002 David Flanagan, Yukihiro Matsumoto, The Ruby Programming Language, O'Reilly 2008 Andri Joyal, Ieke Moerdijk, Algebraic set theory, Cambridge University Press 1995 Ondřej Pavlata, Object Membership: The Core Structure of Object Technology, 2012–2015, http://www.atalon.cz/om/object-membership/ Ondřej Pavlata, Object Membership – Basic Structure, 2015, http://www.atalon.cz/om/object-membership/basic/
##### Document history
 March 12 2015 The initial release.