Object Membership

Simplified Structure

A simplified description of object membership is provided. The family of basic structures [] (O, ϵ, ϵ¯⁽*⁾, r, .ec, .ɛɕ) is narrowed by three additional assumptions: 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.


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

Table of contents


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: Similarly, the extension rule for the powerclass translates to the definion of the powerset:
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: 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

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 (Classes)   = 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.
By an S1v structure (also a monotonic eigenclass structure) we mean a structure S = (O, .ec, , r) where 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 .
In an S1v structure S = (O, .ec, , r) the following additional notation and terminology applies. Note that the definitions include several statements.
Eigenclass chains
Object membership and its powers
Distinguished sets of objects
Rank and boundedness
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.
Polars of
For an object a and sets X, Y of objects we let similarly for <, and >. Moreover, denote . and . the polar maps of , that is,
Boundedly complete ideal

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 = yx. = y.϶ but does not hold in general.)
  2. For every integers i, j,  
  3. For every integers i, j, k and every objects x, y,   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.
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, 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, 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.


  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.


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 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 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:
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
(Recall that objects from O are either old or new according to whether they belong to O0 or not, respectively.)


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


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

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.


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


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

Proposition: (The completion theorem)


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
March122015 The initial release.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.