Preface

Author Ondřej Pavlata Czech Republic

Document date Initial release August 24, 2012 Last major release March 12, 2015 Last update August 21, 2016 (see Document history)

PDF Version

• http://www.atalon.cz/pdf/om/object-membership.pdf  

Warning

Membership glyphs

						(PNG images)
∊	ϵ	∈	∋	϶	∍	(HTML entities)

Table of contents

The approach

This document identifies the following three relations as the core relations of object technology:

• ϵ, the object membership relation, is the most fundamental relation between objects. It is a generalization of the instance-of relation.
• ≤, the inheritance relation, is considered the second most important.
• .ec, the powerclass map, is an auxiliary, possibly empty, one-to-one subrelation of ϵ.

Introductory sample

r = BasicObject
c = Class
A = c.new(r)
B = c.new(A)
s = A.new
u = B.new
v = B.new

class << s; end
class << v; end

The objective

The ϵ² ≠ ∅ condition and circularity

This document is predominantly concerned with structures satisfying ϵ² ≠ ∅. That is, x ϵ y ϵ z for some (not necessarily distinct) objects x, y and z. It turns out that in all the introduced structures, the following stronger condition holds:

The non-objective

The concept of type is regarded as something more complex (an therefore less fundamental) than things described in this document. We use the term type exclusively as a mean of quotation (reference) of particular concepts by other parties (e.g. types as particular objects in Dylan, or abstract power type system for the abstract structure of Cardelli's power types).

As a consequence, this document becomes virtually disjoint with the following two books, both of which claim to provide foundations of object-oriented programing. (The metaclass term can be used as an indicator for the disjointness. There is no occurrence of this word in either of the books. Similarly for meta-class, cf. [].)

• A Theory of Objects by Martin Abadi and Luca Cardelli [].

  Excerpt from the Preface: [] This book develops a theory of objects as a foundation for object-oriented languages and programming. Our theory provides explanations for object-oriented notions in terms of a few basic primitives, and can be useful for the design and understanding of programming languages.

• Foundations of Object-Oriented Programming Languages: Types and Semantics by Kim B. Bruce []

  Excerpt from the publisher's overview: [] This text explores the formal underpinnings of object-oriented languages to help the reader understand the fundamental concepts of these languages and the design decisions behind them.

Composition of ϵ and ≤

The table also indicates that ⊆ (set inclusion) and ∈ (set membership) are the respective set-theoretic counterparts in of ≤ and ϵ. However, the latter correspondence is indirect – we will further introduce ∊, a restriction of ϵ, to be the direct correspondent of ∈, see Set-theoretic interpretation.

In contrast to subsumption, the monotonicity rule has no set-theoretic counterpart. In set theory, it is not true that for every sets x, y, z,   if x ⊆ y ∈ z then x ∈ z. (For example, if x ⊂ y ∈ {y} then x ∉ {y}.) Nevertheless, monotonicity of ϵ is satisfied in the major part of object technology. The monotonicity term comes from the following equivalent formulation: for every objects x, y,

• x ≤ y → x.ϵ ⊇ y.ϵ

• x ≤ y → x.class ≤ y.class.   (If x is a subclass of y then x.class is a subclass of y.class.)

Main results

• class
• metaclass
• eigenclass
• instance-of
• inheritance
• is-a
• class-of
• eigenclass-of
• singleton-of

• The Ruby programming language is the definitive sample language for the description of the object model. The Ruby object model (ROM) provides a clean and robust implementation of the core structure. In fact, the work on this document originated in discovering the exquisite properties of ROM.
• The Python programming language can be thought of as complementary to Ruby w.r.t. core structure. The most part of the core structure of object technology can be described by combining Ruby and Python.
• The Smalltalk-80 programming language is the biggest obstacle to understanding the above fundamental notions of object technology.
• The JavaScript programming language can be thought of as a class-based language with prototypes as inverse eigenclasses.

• r, the inheritance root, is a distinguished object, that is an abstraction of the largest set within the partial universe.

• .ɛϲ is the singleton map – an abstraction of set membership between (arbitrary) sets and singleton sets,
• ∊ is the bounded membership relation, which is an abstraction of (.ɛϲ) ○ (≤) and thus an abstraction of set membership within the partial universe.

• ≤ is an abstraction of set inclusion.
• .ec is an abstraction of a relativized powerset operator. That is, if x is an object that is an abstraction of the set a, then x.ec is an abstraction of the set of all such subsets b of a such that both b and {b} belong to the partial universe. Since the empty set does not belong to the universe, .ec and .ɛϲ are coincident on singletons.
• ϵ equals (∊) ∪ (ϵ¯).

Distinguished subfamilies

• Metaobject structures are those in which .ec is total and .ɛϲ is defined for every object whose rank is not maximal. They can be presented in the signature (O, ≤, r, .ec, .ɛϲ).
• Complete structures are partial universes with urelements, devoid of the empty set. They are superstructures cumulatively built from the ground stage of memberless objects. They can be expressed as (O, ∊) – that is, ∊ is the only definitory constituent, just like ∈ in set theory.
• Monotonic structures arise from the (abstract) monotonicity condition (ϵ) = (ϵ¯) which is present virtually in all object-oriented programming. Though not imposed in ontological languages such as RDF Schema, it can be assumed that most real datasets are subject to monotonicity. (In particular, the built-in RDFS structure is monotonic.)
  • In monotonic structures, the term powerclass is interchangeable with eigenclass.
• Monotonic eigenclass structures are monotonic structures in which .ec is total. This family can serve as the essential mathematical model for the core structure of object technology. This is for the following reasons:
  • The monotonicity condition poses no restriction in most parts of object technology.
  • The .ec map can be completed for any basic structure.
  • The structures are axiomatized with 5 simple conditions which can be stated with only a few preliminary definitions.
  • The structures are fully determined by ϵ:   x ≤ y ↔ x.ϵ ⊇ y.ϵ and .ec is the unique map such that (ϵ) = (.ec) ○ (≤) (therefore, ϵ arises as the composition of infinite eigenclass regress with inheritance).
• Canonical primary structures are based on the Python object model. They describe the instance-inheritance structure that is thought to be canonical in the world of OOP.
• Canonical eigenclass structures are based on the Ruby object model. In this document, these structures are regarded as the standard core structures of OOP.

Connection between ϵ and ≤

Set-theoretic interpretation

Simple cases of ϵ

1. ϵ = ∅ (⁎)  (purely prototypal structures),
2. ϵ ≠ ∅ and ϵ² = ∅   (bipartite structures).

3. ϵ² ≠ ∅   (basic structures of ϵ and their specializations).

Note:(⁎) This case relates to prototype-based programming languages and is more carefully handled in []. An alternative interpretation is proposed, in which ϵ is equal to ≤.

Purely prototypal structures

We do not consider all prototype-based programming languages to have a purely prototypal core structure. In particular, in JavaScript [], ϵ ≠ ∅. We base this judgement on the following observations:

• The expression x instanceof y can evaluate to true for some x and y.
• The notion of a class is supported in authoritative books about JavaScript [].

Bipartite structures

Note that we did not mention the word object anywhere in the definition. This is because we have disobeyed the two-sortedness – we unified the sorts T and C into one set O. In the two-sorted view of ϵ the term object is exclusively reserved for elements of T. This is expressed by:

• Classes are not objects.   (See e.g. [], page 93.)

• Classes are objects.

• For every class x, the reificiation of x (x.reif) is an object.

Overview of atalon.cz and related documents

• Object Membership – The Core Structure of Object Technology (this document).

  This is the main document that provides an introduction to the subject as well as synthesis of other documents.

• Object Membership – Basic Structure. []

  The document describes the ultimate mathematical model of The Core and its connection to set theory. In particular, it is shown that object membership, ϵ, arises by the following fundamental equality:

  • (ϵ) = (∊) ∪ (ϵ¯)
  where ∊ is the bounded part, a well-founded relation, and ϵ¯ is the monotonic part. The main correspondence between (the core structure of) object technology and set theory can be then expressed as
  • ∊   ↔   ∈.
  If objects have sufficiently many bounded members and .ec is total, then all of ϵ, ≤ and .ec are determined by ∊ so that the core structure can be expressed as (O, ∊). In a complete structure, every non-empty subset of O.∍ equals the extension x.∍ of a unique object x. Such a structure looks like a partial universe of sets, given by the pair (ϖ+1, κ), where ϖ is a limit ordinal that is the rank of the inheritance root r, and κ is the cardinality of the ground stage of urelement-like sets. Every basic structure can be embedded into such a partial universe.
• Object Membership: Simplified Structure. []

  The assumption of monotonicity ((ϵ) = (ϵ¯)) and of totality of .ec results in the family monotonic eigenclass structures. This family has a simple description (simpler than the general case of basic structures) which is provided in the referred document. The restrictions can be considered acceptable:

  • The monotonicity condition holds for the majority of object-oriented programming and modelling.
  • Every basic structure has a powerclass completion.
  A complete monotonic structure (O, ∊) is obtained from a complete basic structure (V, ∊) by the restriction to hereditarily ↧-complete objects, i.e. O = { x | x.∍ = x.∍.↧ ⊆ O } .
• Object Membership: The core structure of object-oriented programming. []

  Historically, this document introduced the term object membership (together with the ϵ symbol) and originally was the main document. The (canonical) core structure of OOP arises by unifying core structures of Ruby and Python. It can be viewed as either the Ruby core structure with multiple inheritance and user-created explicit metaclasses allowed, or the Python core structure equipped with eigenclasses.

  The core structures of Java, Scala, Smalltalk, Objective-C, CLOS or Perl are viewed as modifications of the canonical structure. (See also Specializations of ϵ.) Additionally, refinement structures are described which provide linearization of object's ancestors.

• Object Membership: The ontological structure. []

  The document provides a generalization of object membership as it applies to ontological structures based on RDF Schema. In contrast to object-oriented programming the following features are present:

  • An object x can have multiple minimum classes of which x is an instance.
  • There is a distinguished sort of objects, called properties. Like terminals, properties are not descendants of the inheritance root. Unlike terminals, properties can have descendants.
  • Inheritance does not have to be antisymmetric – classes and properties can have distinct equivalents.
  A summary is provided in the Ontological structure of ϵ section.
• Object Membership with Prototypes. []

  As already observed on the example of the JavaScript programming language, prototype-based languages cannot be, in general, declared to be classless or to be devoid of the instance-of relation (despite the traditional view []). Moreover, it can be observed that in the JavaScript core structure (O, ϵ, ≤, r, .ec), not only ϵ but also the .ec constituent is non-empty. The following correspondence holds:

  • x.ec = y   ↔   x == y.prototype.
  That is, prototypes can be thought of as eigenclass predecessors of classes. A summary of the referred document is provided in the Prototypes section.
• Object Membership and Powertypes. []

  The document provides an explanation of the notion of a powertype in terms of the core structure. In particular, it is shown that, in a suitable axiomatic restriction, the Cardelli's Power() operator coincides with .ec. That is, Cardelli's power types are powerclasses in the abstract setting. The only difference is that Power(x) is only defined for Classes (called types).

  Subsequently, the adoption of powertypes in metamodelling is considered, as well as powertype relationship in RDF Schema.

• The Dialectic of Classes and Metaclasses in Smalltalk-80. []

  Historically, the Smalltalk programming language is of fundamental importance to the core structure of object technology:

  • Smalltalk-76 is the first language in which ϵ² ≠ ∅,
  • Smalltalk-80 is the first language in which .ec ≠ ∅.
  Unfortunately, the .ec ≠ ∅ condition has not been reflected in the terminology or documentation of Smalltalk-80. As a consequence, inconsistencies have been established and so Smalltalk-80 became the biggest obstacle for the description of the core structure of OOP, at least for the author of this document. The referred document collects evidence about the inconsistencies. A consistent resolution of the terminology is provided in a special section.
• What Is a Metaclass?. []

  The document provides a more elaborate alternative to the present document. The title question is used as a linguistic device for the exploration of the object model core in various contexts. There are about 20 investigated environments. The metaclass term is used as a label for an approach to OOP foundations. The metaclass approach is based on four rules in the spirit of Occam's razor: (1) dispense with types, (2) dispense with calculus, (3) support object identity, (4) assume metaclass pre-condition (classes are objects).

• Featherweight Java Axiomatically. []

  Featherweight Java is the most popular formalization of the most popular object-oriented programming language. In the referenced document, the formalization is adjusted to provide a clear definition of the core structure of the underlying data model.

• The Ruby Object Model: Data Structure in Detail. []

  The document provides a detailed description of the Ruby Object Model (as of version 1.9) via abstraction refinement. The object model is incrementally specified in the series of abstract structures together with their possible transitions. The most abstract, initial structure, denoted S0, just introduces the basic nomenclature of objects: terminals, classes and eigenclasses. The next structure, S1, is the core structure of Ruby in the sense introduced at the beginning of this document. The structure is (exactly what is) induced by superclass and eigenclass links between objects. The yet subsequent structure, S2, equips S1 with module inclusion lists so that the complete inheritance structure is established (referred to by MRO, which stands for method resolution order). There is an in-between structure, denoted S1_r in [], which encompasses just the extension of the Ruby's (canonical) object membership, ϵ, to the full membership, ϵ•, which can be introspected by the is_a? built-in method (see also Specializations of ϵ).

  There are more than 20 structures in the gradual description. The resulting structure (still providing just an abstraction of the Ruby object model, though far more detailed than S1) can be viewed as a naming multidigraph, consisting of nodes and uniquely labelled arrows between them.

• Ruby Object Model – S1 superstructure representation. []

  The document provides a set-theoretic representation of the core structure of Ruby (again referred to as the S1 structure) using the bottom stratum map .ϱ between objects in an (ω+1)-superstructure (V, ∈). In contrast to the embedding presented in [], the embedding from [] maps all objects to elements of finite stages. As a result, for objects x, y whose metalevel index is lower than a predefined number k,

  • x ≤ y   ↔ x.ϱ ⊆ y     and     x ϵ y   ↔ x.ϱ ∈ y.
• Ruby Object Model – The S1 structure. []

  The document focuses on the description of the S1 structure using the material from the previous two documents. In all these three documents, object membership is expressed in the composition (.ec) ○ (≤), the ϵ symbol is missing. Moreover, ≤ is considered to be defined only between non-terminal objects.

• Ruby Object Model: Comparison with Smalltalk-80. []

  Historically, this document is the first description (available at atalon.cz) of the Smalltalk-80 correspondent of the Ruby's S1 structure. The document can be regarded as a precursor to the dedicated section.

Eigenclass model (Wikipedia article)

The Wikipedia page en.wikipedia.org/wiki/Eigenclass_model containing the article has been created in October 2012 by the author of this document. Several major edits followed until January 2013. In October 2013, the page has been deleted (changed to a redirect to Ruby (programming language)#Semantics) by Wikipedia administrators on the following grounds:

• The article violates the NOR principle (No original research).
• The term eigenclass model is not an established topic in computer science.

History

Notes:

1. Bold font indicates that the introduction of Ruby is regarded in this document to be the most significant contribution to the development of the core structure of object technology. We can guess that the Ruby core structure has been created by rectification of Smalltalk-80 adopting the concept of universality of singletons in Dylan. This is best illustrated by samples from Ruby, Smalltalk-80 and Dylan.

The core structure by Forman & Danforth

Preliminaries

Well-foundedness

• … x₂ ϵ x₁ ϵ x₀ = x.

Rank

• r(x) = sup {r(a) + 1 | a ∊ x}.

• let the ∊-rank of a subset Y of X be sup {r(a) + 1 | a ∈ Y},
• let the rank of ∊ be the ∊-rank of X.

The instance-of relation

Let us write x ϵ y for the object x is an instance of the class y. By using the ϵ symbol (lunate epsilon) for the instance-of relation we suggest the correspondence:

There is a second point that should be noted in the expression x ϵ y: both the object x and the class y are denoted by a lowercase letter. This suggests that we are focused on programming languages that support the following uniformity principle of ϵ:

Sample structure

For an object x we denote x.϶ the set of all instances of x and call it the extension of x. Ordinary objects have empty extension. The sample structure is saturated in the sense that classes are distinguishable by their instances: different classes have different extensions. This allows to derive a partial order, denoted ≤, and called inheritance, between the 7 objects by:

• x ≤ y   iff   x = y or ∅ ≠ x.϶ ⊂ y.϶.

Observe that classes o and c are circular – they are instances of itself. Moreover, every object is an instance of o and classes are exactly the instances of c.

Structure creation

• x = q.new(p1, …, pn)

• A = c.new(o); B = c.new(A); s = A.new; u = B.new; v = B.new

Adding inheritance to the signature

Note that since (ϵ) = (.class) ○ (≤) we can use the signature (Ō, .class, ≤) as well.

The sample expressed in relevant languages

Where applicable, a diagram is provided showing how the sample structure is obtained as a restriction of a finer structure.

In Ruby

o = Object
c = Class
A = c.new     # class A; end
B = c.new(A)  # class B < A; end
s = A.new
u = B.new; v = B.new

In Python

o = object
c = type
A = c('A', (), dict())    # class A(): pass
B = c('B', (A,), dict())  # class B(A): pass
s = A()
u = B(); v = B()

In JavaScript

• x < y   iff   y.prototype.isPrototypeOf(x.prototype).

o = Object; c = Function
A = new c
B = new c; B.prototype.__proto__ = A.prototype
s = new A
u = new B; v = new B

In Smalltalk

o := Object. c := Class.
o subclass: #A.
A subclass: #B.
s := A new.
u := B new. v := B new.

In Java

class A {}
class B extends A {}

class Xx {
  public static void main (String[] xx) {
    Object
    o = Object.class,
    c = Class.class,
    A = A.class,
    B = B.class,
    s = new A(),
    u = new B(), v = new B();
  }
}

• x instanceof Y, or
• y.isInstance(x).

In Scala

var o = classOf[Object]
var c = classOf[Class[_]]
class A
class B extends A
var s = new A
var u = new B; var v = new B

In Dylan

let o = <object>;
let c = <class>;
let A = make(c);
let B = make(c, superclasses: list(A));
let s = make(A);
let u = make(B); let v = make(B);

In CLOS

(defvar o (find-class 'standard-object))
(defvar c (find-class 'standard-class))
(defvar A (make-instance c :name 'A))
(defvar B (make-instance c :name 'B :direct-superclasses (list A)))
(defvar s (make-instance A))
(defvar u (make-instance B)) (defvar v (make-instance B))

In RDFS

ex:B rdfs:subClassOf ex:A .
ex:s rdf:type ex:A .
ex:u rdf:type ex:B .
ex:v rdf:type ex:B .

In Objective-C

@interface A: NSObject; @end
@interface B: A;        @end
@implementation A; @end
@implementation B; @end
int
main(int argc, const char *argv[]) {
  id
  o = [NSObject class],
  s = [A new],
  u = [B new], v = [B new];
  return 0;
}

In Perl

• every class is an instance of itself, and even
• every class is the class of itself.

The diagram below shows the sample structure in the correspondent modification.

package UNIVERSAL { sub new { bless {}, $_[0] } }
package A         { }
package B         { our @ISA = A }
my
$o = UNIVERSAL,
$s = A->new,
$u = B->new, $v = B->new;

Refinement by implicit containers

Eigenclasses

• Ō' = Ō ⊎ Ō.ec,

• x.ec ≤ y.ec iff x ≤ y,   (That is, .ec is an order embedding of (Ō, ≤) into (Ō', ≤).)
• x.ec ≤ y iff x ϵ y,
• x ≰ y.ec.

Object membership

Proposition: For every x, y from Ō,

• x ϵ y iff x.ec ≤ y.

The refined class map

Observations:

1. The .aclass map coincides with .ec on primary objects and equals the the composition .ec⁻¹.class.ec on eigenclasses.
2. (ϵ) = (.aclass) ○ (≤).

Support in programming languages

• In Smalltalk-80 and Objective-C, each class has its own implicit metaclass.
• In Scala, the object construct can be used to create ordinary objects that have its own meta-object.
• In Dylan, all the 7 eigenclasses have a correspondent but the .aclass map is different (see the sample structure).

In Objective-C

id
e = object_getClass(o),
f = object_getClass(A),
g = object_getClass(B);

In Scala

object s with A
val    u = new B
object v with B
val    e = s.getClass
val    g = v.getClass

Eigenclass completion

Full uniformity of the structure provides the following simplifications:

• Object membership, ϵ, equals the composition (.ec) ○ (≤), i.e. an object x is a member of an object y iff x.ec is an inheritance descendant of y.   (However, the equality (ϵ) = (≤) ○ (.ec) ○ (≤) is still valid.)
• Inheritance is obtained from ϵ as inclusion of sets of containers. Therefore, the structure can be expressed in the simple signature (O, ϵ).

The core structure of Ruby

Sample structure

• the s object is removed to simplify the diagram, and
• all four circular classes of Ruby 1.9 are contained in the structure, not just Object and Class.

r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new

The prefix eigen stands for own – different objects have different eigenclass. In the Ruby comunity, the term eigenclass appeared around the year 2005. Previously, the term singleton class has been used. As a (historical) consequence, the corresponding introspection method is named singleton_class.

We use the notation x.ec for the eigenclass of x, so that x.ec corresponds to x.singleton_class. The .ec map is then the eigenclass map shown by gray arrows. Furthermore, let x.ec(i) be the i-th application of .ec to x. Components of the .ec map are eigenclass chains of the form x, x.ec, x.ec(2), x.ec(3), …. The inverse of .ec is denoted .ce. For x from O.ec, x.ce is the eigenclass predecessor of x. Let .ec^∗ be the reflexive transitive closure of .ec. For an object y, let y.pr be the primary object of y, that is, the first object of the eigenclass chain y.pr.ec^∗ to which y belongs.

Inheritance and membership

• x ≤ y   iff   x.ec ≤ y.ec.

• x ϵⁿ y   ↔   x = x₀ ϵ x₁ ϵ ⋯ ϵ x_n-1 ϵ x_n = y for some objects x₁, …, x_n-1.

• x.↥ (resp. x.↧) denotes the set of (non-strict) ancestors (resp. descendants) of an object x.
• Similarly, for a set X of objects, X.↥ (resp. X.↧) is the upset (resp. downset) of X.
• x.ϵ (resp. x.϶) is the set of all containers (resp. members) of an object x.
• x.ϵ^∗ is the set x.ϵ⁰ ∪ x.ϵ¹ ∪ x.ϵ² ∪ ….

• (1) x.↧ = x.ec.϶   (descendants of x are exactly the members of x.ec),
• (2) x.ϵ = x.ec.↥   (containers of x are exactly the ancestors of x.ec),
• (3) x ≤ y iff x.ϵ ⊇ y.ϵ   (x is a descendant of y iff every container of y is also a container of x),
• (4) x.ec = y iff x.ϵ = y.↥   (the eigenclass of x is the least container of x).

Direct inheritance

The notation is adapted to multiple inheritance. If single inheritance is asserted, we can use the .sc notation for ≺ so that x.sc = y iff x ≺ y. For an object x, the object x.sc, if defined, is the superclass of x. The core structure of Ruby can be then expressed as (O, .ec, .sc). []

Membership as is-a

If x is a member of an object named B then one can say that x is-a B. The set B.϶ of all members of B can be referred to as Bs. This convention can be used for nomenclature of objects. Moreover, there can be a distinction between the names that are built using this convention (these names are capitalized and styled) and those names that are not. In Ruby, the built-in classes Object, Module and Class provide such a distinction.

• Objects are objects that are not blank slate objects.
• Modules are modules together with Classes.
• Classes are classes together with eigenclasses.

• an A is a B,

• there is an is-a relationship between A and B.

• the A is a B

Note: The two different meanings of is-a have been analyzed by R. Brachman [] [].

• The ϵ meaning is called individual/generic and is exemplified by Socrates is a man.
• The ≤ meaning is called generic/generic and is exemplified by a cat is a mammal.

Basic nomenclature of objects

• O.ec (the image of the eigenclass map, shown right to the black line) is the set of eigenclasses.
• O ∖ O.ec (objects that are NOT eigenclasses, to the left of the black line) is the set of primary objects.
• T denotes the set of terminal objects or just terminals – objects without members and without strict ancestors.
• C is the set of classes, the primary non-terminal objects.
• r is the inheritance root. It is the highest non-terminal object, w.r.t. inheritance.
• c is the instance root and is also called the metaclass root and named Class. It is the unique inheritance parent of r.ec.
• R is the set of objects from the eigenclass chain of r, the reduced helix.
• H is the set of helix objects – objects x such that x ϵ x. Note that H = R.↥.

• x is non-terminal.
• x is a Class (i.e. x is a member of the c object which is named Class).
• x is an inheritance descendant of r (i.e. x ≤ r).

The terminology for the set H = r.ϵ^∗ is based on the similarity of the diagrammatization of (H, ≤) with a right-infinite helical curve.

Classification systems

• if a ≤ b then a.ec.y ≤ b.ec.y.

Note that the sets C, R and H are all classification systems. (In fact, since in Ruby the inheritance on Classes forms a tree, any subset of O ∖ T containing r is a classification system.) We denote the corresponding closure operators by .c, .re and .he, respectively.

In the case of .c, we extend the definition to all objects: we let .c to be the closure operator corresponding to the closure system C ⊎ T in (O, ≤). This allows us to conveniently express the set of all primary objects as O.c.

Metalevels

Further observations:

• The set T of terminal objects is the metalevel 0.
• For i > 0, the i-th metalevel has a top, equal to r.ec(i-1).
• The i-th metalevel, i ≥ 0, equals the set r.ec(i).϶ ∖ r.ec(i).↧.
• For an object x, the metalevel index x.mli equals the cardinality of x.↥ ∩ R.
• The last metalevel containing a primary object is isomorphic to any higher metalevel (via .ec(i) for a suitable i).

Classes and the .class map

The most important classification system is the set C of primary non-terminal objects. Objects from C are called classes. The corresponding classification map is denoted .class. (So that .class = .ec.c.) For an object x, the object x.class is said to be the class of x. Note that the just introduced meaning of class and class-of possesses the following fundamental consistency:

• Classes are primary Classes.
• Classes are classes together with eigenclasses.
• x.class ≠ x.ec for every object x.
• The .class map is derived from the eigenclass map and the inheritance relation.
• The distinguished objects r and c are classes.
• The .class map forms a tree rooted at c. In particular, c is the only object that is the class of itself.
• Unlike eigenclasses, classes cannot be in general expressed as O.class (the image of the class map).

In Ruby, all classes reside in the metalevel 1. As a consequence, .class.class maps constantly to c. The Ruby introspection method named class is in 100% correspondence with the .class map.

The instance-of relation

• x is an instance of y   iff   x ϵ y and y is a class.

By allowing indirect instances our terminology follows the semantics of the isinstance() method of Python or the instanceof operator from Java. In Ruby, the introspection method instance_of? corresponds to direct-instance-of. (However, the Ruby Specification [] allows indirect instances.) Note that

• if y is the eigenclass of x then x.instance_of?(y) always evaluates to false.

Metaclasses

• Metaclasses are exactly the inheritance descendants of c (including c itself), so that the set of all metaclasses can be expressed as c.↧.

Observations:

• The c class is the only metaclass from metalevel 1.
• The set of all metaclasses other than c can be expressed as r.ec.↧ – it consists of all objects from metalevel 2 or higher.
• Suppose that our sample structure has been extended by w = Module.new so that the Module class (which is the parent of c) has a terminal member w. Then
  • metaclasses are exactly the Classes that do not have terminal members.

Eigenclass actuality

We denote .a the corresponding closure operator and let .aclass = .ec.a be the classification map. For an object x, x.aclass is the actualclass of x – the least ancestor of x.ec that is actual. The set O.a of all actual objects is the actuality extent. We can view the (O, ϵ, .a) structure as an implementation-oriented refinement of (O, ϵ). In particular, x.aclass can be regarded as the actual startpoint of method lookup for x – non-actual eigenclasses between x.ec and x.aclass are skipped.

The diagram below shows the actuality extent of allocated objects for the sample structure. The extent arises after opening the eigenclasses of A and v. The actualclass map (in the restriction to actual objects) is shown by blue arrows. Note that the map forms a tree rooted at c.ec(2).

r = BasicObject
c = Class
class A; end
class B < A; end
u = B.new
v = B.new

class << A; end
class << v; end

As already mentioned, the diagram shows the structure for the larger extent. Objects that have been allocated but not referenced are shown in light blue. The actualclass map shown by blue links could be denoted .klass, since it is maintained by the implementation via the klass field in the C source. Note that there cannot be an introspection method for .klass due to the probe effect. There could only be an introspection method for the actualclass map for the smaller extent, but even this is not supported since it is considered to be an implementation property.

The reason for having an extra object allocated in each eigenclass chain of classes is an efficient update of the actualclass map for inheritance descendants. This does not affect terminal objects (or their eigenclasses). Since they cannot have descendants, they do not need to have their eigenclass allocated.

The core structure of Smalltalk-80

Unfortunately, the Smalltalk-80 core structure possesses uniformity deficiencies which were compensated by equivocal terminology in the Smalltalk's literature. []

To describe the Smalltalk-80 counterpart of the Ruby core structure we use a specially restrained terminology in which the following terms are (at first) avoided:

• Class — we do not say which objects are classes and which not.
• Metaclass — we do not say which objects are metaclasses and which not.
• Class-of. We do not say what is the class of an object. In particular, even if the expression x class evaluates to y we do not say that y is the class of x.
• Instance-of. We do not say what it means for objects x and y that x is an instance of y.

Sample structure

The blue links correspond to the class introspection method. A blue line starting at x and ending in y (with an arrow head pointing to y) indicates that the expression x class evaluates to y.

 r := ProtoObject.
 c := Class.
mc := Metaclass.
Object subclass: #A.
A      subclass: #B.
u := B new.
v := B new.

The built-in part forms a substructure — it contains exactly the objects reachable from the mc object via a combination of blue and green links. (Note that the substructure is generated by any single object it contains, not just mc.) Moreover, it is a minimum (nonempty) substructure, since the mc object is reachable from any object (via at most 3 blue links).

Metalevels

The division of blue links induces a division of objects into 3 metalevels.

• The metalevel 2 consists of all objects x such that x class == mc.
• The metalevel 1 consists of all objects x such that x class class == mc.
• The metalevel 0 consists of all remaining objects. For every x from the metalevel 0,
  x class class class == mc.
  However, this equality cannot be used to distinguish the metalevel 0 since it also holds for every object from the metalevel 2.

Uniformity deficiency No. 1

• Objects of metalevel 0 are mapped to objects of metalevel 1, possibly many-to-one.
• Objects of metalevel 1 are mapped to objects of metalevel 2 in a one-to-one correspondence.
• Objects of metalevel 2 are constantly mapped to the distinguished object mc from metalevel 1.

• Objects from the metalevel 1 have each an individual (meta)object from the next metalevel pointed to by a blue link. Objects from other metalevels do not have such an own meta-object.

Inheritance

• x ≤ y   iff   y is reachable from x via zero or more green links.

Further observations:

1. Objects from metalevel 0 are exactly the singletons in inheritance: they have no (strict) descendants or ancestors.
2. The object r is the top of the metalevel 1 as well as of the union of metalevels 1 and 2, w.r.t. inheritance.
3. The object r class is the top of the metalevel 2, w.r.t. inheritance.
4. The parent of r class is the object c from metalevel 1.
5. In the restriction to a metalevel, the blue links constitute a map that is monotone w.r.t. inheritance, i.e. if x and y are from the same metalevel, then
   • x ≤ y   implies   (x class) ≤ (y class).
6. Since blue links constitute bijection between metalevels 1 and 2, they constitute an order isomorphism between these metalevels, w.r.t. inheritance. If x is an object from metalevel 1 different from r, then
   • x class superclass == x superclass class.

Uniformity deficiency No. 2

• Without the restriction to a particular metalevel, the blue links do NOT constitue a monotone map.

The Ruby-Smalltalk core correspondence

• T is the set of actual objects on metalevel 0,
• C is the set of actual objects on metalevel 1,
• C.ec is the set of actual objects on metalevel 2,

• terminals (T) be the objects from metalevel 0,
• classes (C) be exactly the objects on metalevel 1, and
• implicit metaclasses (C.ec) be the objects from metalevel 2,

The differences between the core samples can be listed as follows:

1. The Smalltalk-80 core contains two more built-in classes, of which only the mc class (named Metaclass) constitutes a structural change as a receiver of blue arrows.
2. The blue arrows starting at metalevel 2 are redirected to mc.

• x.aȼlass = x.aclass if x is a class or terminal,
• x.aȼlass = mc otherwise (i.e. if x is an implicit metaclass).

Notes:

1. Note in particular, that the class introspection method in Smalltalk-80 does not correspond to the synonymous method of Ruby.
   • In Ruby, the class introspection method corresponds to the class map, .class.
   • In Smalltalk-80, the class method corresponds to the imposed actualclass map, .aȼlass. As a consequence, x class is not necessarily a class.
   The following table describes the differences:

   For x from	Smalltalk-80 x class evaluates to	Ruby x.class evaluates to
   T (terminals)	the class of x
   C (classes)	the eigenclass of x	the class of x which is constantly Class
   C.ec (implicit metaclasses)	the imposed class of x which is constantly Metaclass

2. There is no support for the above or similar definitions in the Smalltalk literature. Instead, publications about Smalltalk-80 use equivocal terminology which suggests two different delimitations of classes and metaclasses: []

   (A)	Classes are the objects from metalevels 1 and 2. Metaclasses are the objects from metalevel 2 plus the class named Metaclass.
   (B)	Classes are the objects from metalevel 1. Metaclasses are the objects from metalevel 2.

The primary structure of ϵ according to Python

• multiple inheritance (that is, an object can have multiple inheritance parents), and
• explicit metaclasses other than the built-in c class.

• (.class, .↥)   ↔   (.__class__, .__mro__)

• x ≤ y iff y ∈ x.__mro__

Note: In addition to the __mro__ attribute, Python classes also contain another inheritance related attribute: the __bases__ list. Apart from the order within the list, the intended semantics of .__bases__ is that of the .parents map. However, the correspondence is not asserted. In particular, the __mro__ and __bases__ attributes are not kept in sync if they are explicitly manipulated. We therefore think of .parents to be derived from .__mro__ (satisfying the assumption above) rather than from .__bases__.

Recursive definition

• Ō is set of objects,
• .class is the class map between objects,
• .parents is the inheritance parent set map from Ō to the powerset of Ō,
• r is the inheritance root, a distinguished object.

The structure is then subject to the following conditions:

Observations:

• Ō.parents ∪ Ō.class is the set of objects that are not minimal w.r.t. (≺) ∪ (.class).
• The restriction of the structure to c.↥ is described by (py~4). It is a built-in substructure containing no objects that are minimal w.r.t. (≺) ∪ (.class).
• Condition (py~1) could be stated just for the built-in structure. It asserts that ≺ is a reflexive transitive reduction of ≤ so that there is a one-to-one correspondence between .parents and ≤.
• (py~6) is the only recursive condition. It says that removing an object minimal w.r.t. (≺) ∪ (.class) preserves the structure.
• We avoided recursive definitions of classes and metaclasses by introducing ≤.

New object attachment

• P is the requested (possibly empty) set of inheritance parents, and
• q is the requested class,

class A():
  def __new__(a): pass
s = A()

# TypeError:
class B(s): pass

class M(type): pass
class N(type): pass
class A(metaclass=M): pass

#  metaclass conflict
class B(A,metaclass=N): pass

class M(type): pass
class X: pass
s = X()

# TypeError:
s.__class__ = M

Canonical primary structure

By a canonical primary structure of ϵ we mean a structure (O.pr, ϵ, ≤, r) where

• O.pr is set of primary objects,
• ϵ is the instance-of relation between primary objects,
• ≤ is the inheritance relation between primary objects,
• r is the inheritance root, a distinguished object.

Notes and observations:

1. In RDF Schema, condition (p~2)(a) is asserted by the rdfs9 entailment rule. Using type theoretic terminology, this can be called the subsumption rule. []
2. Conditions (p~2)(b) and (p~6) can be conveniently expressed using the .class map.
   • The .class map is monotone.   (Therefore, (p~2)(b) is the metaclass compatibility condition.)
   • The .class map forms a tree.
3. Condition (p~2) can be equivalently written as a single equality: (≤) ○ (ϵ) ○ (≤) = (ϵ).
4. Condition (p~3) means that terminals are minimal both in ϵ and ≤.

Proposition: Axiomatizations (py~1)–(py~7) and (p~1)–(p~8) are equivalent.

The canonical eigenclass structure of ϵ

• (A) Equipping Python's core structure with eigenclasses.
• (B) Relaxing Ruby's core structure by allowing multiple inheritance and classes on higher metalevels.

Eigenclass regress alone

• .ec is an injective well-founded map.

Observations:

1. For each eigenclass chain X,   (X, .ec) is isomorphic (via .eci) to the structure (ℕ, succ) of natural numbers where succ is the successor operator.
2. O = O.pr ⊎ O.ec.

Notes:

• As of version 2.0 or older, Ruby does not provide any introspection methods for .ce, .pr or .eci. Internally, the .ce links are implemented using the __attached__ instance variable.
• ABCL/R is another example of a programming language that supports infinite regress. In the documents [] [], the term metaobject (or meta-object) is used for eigenclass. An eigenclass chain is a metaobject tower. As the term suggests, the regression is diagrammatized vertically. The code expressions [meta x] and [den x] correspond to x.ec and x.ce, respectively.

Tight canonical structure by eigenclass completion

1. Equip each primary object with an eigenclass chain.
2. Extend ≤ according to (ec~3).
3. Extend ϵ by setting (ϵ) = (.ec) ○ (≤).

Canonical eigenclass structure

• The object membership relation, ϵ, is the composition (.ec) ○ (≤), .ec^∗ is the reflexive transitive closure of .ec, ϵ^∗ is the transitive closure of (≤) ∪ (ϵ). Let .ce, .ce^∗, ϶ and ϶^∗ be inverses of .ec, .ec^∗, ϵ and ϵ^∗, respectively.
• For an object x, the set x.ec^∗ is the eigenclass chain of x, the set x.↧ / x.↥ / x.϶ / x.ϵ is the set of descendants / ancestors / members / containers of x. The .pr map is defined by:   x = y.pr   ↔   {x} = y.ce^∗ ∖ O.ec.
• Let O.ec be the set of eigenclasses, the remaining object being primary, T = O ∖ r.↧ be the set of terminal objects, C = r.↧ ∖ O.ec be the set of classes, R = r.ec^∗ be the reduced helix, H = r.ϵ^∗ be the set of helix objects.

Notes and observations:

1. Axiom (e~2) is the essential axiom. It can be equivalently expressed as (≤) = (.ec) ○ (≤) ○ (.ce).
2. Axiom (e~3) asserts that terminals are unrelated by < to any object and that this property is preserved after a free instantiation of any class.
3. Axiom (e~4) asserts that r is a universal object: O = r.϶. Since r is asserted to be a class by e~(1)(2)(4)(5), every object is an instance of r.
4. Axiom (e~5) asserts that .ec is a well-founded map. Due to the injectivity asserted by (e~2), .ec establishes the infinite regress of eigenclasses.
5. Axiom (e~6) asserts that the restriction to H is (a)(b) as simple as possible but (c) non-degenerate: H ≠ R. Using the finiteness condition (e~12), H is asserted to form a closure system in (O ∖ T, ≤). In addition, the existence of a least helix class, c, is ensured.
6. Axiom (e~7) asserts that the eigenclass chain of c is not used for the connection to the helix. Using .he as the closure operator for H (i.e. such that r.↧.he = H), (e~7) can be expressed as c ∉ C.he.pr.
7. Axiom (e~8) asserts that H is exactly the non-well-founded part of the structure. Moreover, x ∈ H iff x ϵ x.
8. Axioms (e~9) and (e~10) assert a one-to-one correspondence between the well-founded part (O ∖ H, …) and its restriction (O.pr ∖ H, …) to primary objects.
9. Axiom (e~10) can be equivalently stated as any of the following:
   • the member-of-instance-of relation is equal to the instance-of-instance-of relation,
   • .ec.class = .class.class   (using (e~11)),
   • .c preserves ϵ   (using (e~11))
10. Axiom (e~11) asserts that the set O.pr of primary objects forms a closure system in inheritance. We denote .c the corresponding closure operator so that O.pr = O.c and .class = .ec.c.
    Moreover, this axioms makes (e~4) redundant. (This is because if e~(1)(2) is assumed then:   (e~4)   ↔   every object has a primary container.)

Notes and observations:

1. A canonical eigenclass structure of ϵ is expressible in the (O, ϵ) signature.
2. Since (e~4) asserts that every object has a primary container, it becomes redundant within canonical structures due to (e~11).

Correspondence between primary and eigenclass structures

Proposition:

1. The restriction of a canonical eigenclass structure to primary objects is a canonical primary structure.
2. The .c map is a homomorphic projection of (O, ϵ, ≤) onto (O.pr, ϵ, ≤).
3. A tight canonical eigenclass structure is a canonical eigenclass structure satisfying the following stronger version of axiom (e~9):

   (e~9⁺)	Descendants of eigenclasses-other-than-r.ec are eigenclasses.

The diagrams below show the correspondence between a canonical eigenclass structure, its restriction to primary objects and the subsequent tight eigenclass completion. Note that the tree structure of ≤ is not preserved.

Ruby's additional constraints

Monotonic eigenclass structure of ϵ

• Simplicity. There are five simple conditions that can be stated with only a few preliminary definitions. Moreover, the structures are fully determined solely by ϵ.
• Generality. The monotonicity condition seems to be predominant in object technology so that it can be regarded as an acceptable (or even desirable) restriction. Similarly, the requirement of every object having an eigenclass only means that the structures are expressed in their eigenclass completion (which is unique, up to isomorphism). General monotonic structures (in which .ec is partial) can be thought of as implementation-oriented refinement that records the actuality state of eigenclasses.
• Connection to algebraic set theory. Object membership, ϵ, is formed by the composition of .ec and ≤ just like the membership relation ɛ in Zermelo-Fraenkel algebras.[] The following table shows the notational correspondence:

  Monotonic eigenclass structure	x ϵ y	↔	x.ec ≤ y
  Zermelo-Fraenkel algebra	x ɛ y	↔	s(x) ≤ y

Monotonic eigenclass structure

• O is a set of objects,
• .ec is the eigenclass map O → O,   (objects from O.ec are eigenclasses)
• ≤ is the inheritance relation between objects,
• r is the inheritance root, a distinguished object.

Decomposition of ϵ

Note: For simplification, we introduce slight discrepancy with the more precise document []. The family of structures defined in the following subsection should be more correctly called membership-based monotonic structures since they rely on the prescription

Monotonic primary structure

• The usual terminology and notation is used for ≤ and ϵ. In addition, the ≤ and < symbols are also used in the polar sense for relations between sets of objects, so that e.g X < Y means that every object of X is less than every object of Y. Let T = O ∖ O.ϵ.↧ be the set of terminal objects and H = r.ϵ^∗ the set of helix objects where ϵ^∗ is the transitive closure of (≤) ∪ (ϵ). For a natural i > 0, let ϵⁱ be the i-th composition of ϵ with itself and let ϵ⁰ be equal to ≤.

Observation: For a structure S = (O, ϵ, ≤, r) the following are equivalent:

• S is a canonical primary structure.
• S is a monotonic primary structure satisfying (p~4)–(p~8).

Basic structure of ϵ

• Remove (relax) the monotonicity condition. As already observed in the introduction, in contrast to the subsumption rule, the monotonicity condition (≤) ○ (ϵ) ⊆ (ϵ) is not universally satisfied when ≤ and ϵ are interpreted as ⊆ and ∈, respectively.
• Allow partial definition of .ec. Until now we have formally described structures that either had no eigenclasses (primary structures) or in which the eigenclass map was total (eigenclass structures).
• Provide a non-monotonic counterpart to .ec. Until now, x.ec, if defined, was the least container of x. The (≥) = (.ec) ○ (϶) equality indicates that the .ec map is an abstraction of the powerset operator. However, in set theory, the least set that contains a given set x as an element is {x}, the singleton of x, which is different from the powerset of a set x (except when x is empty).

Basic structure

• O is a set of objects,
• ϵ^⁽*⁾ and ϵ¯^⁽*⁾ are bi-infinite sequences of relations between objects such that (a) (ϵⁱ) = (ϵ¯ⁱ) for i ≤ 0, (b) (ϵ^j+1) = (ϵ^j) ○ (ϵ) and (c) (ϵ¯^j+1) = (ϵ¯^j) ○ (ϵ¯) for j > 0, and where
  • (ϵ) = (ϵ¹) is the (object) membership relation,
  • (ϵ¯) = (ϵ¯¹) is the power membership relation,
  • (≤) = (ϵ⁰) is the inheritance relation (with .↧ / .↥ used for preimages / images under ≤),
  • (ϵ^-1) is the anti-membership relation,
• r is the inheritance root, a distinguished object,

• .ec is the powerclass map   (objects from O.ec are powerclasses),
• .ɛɕ is the primary singleton map   (objects from O.ɛɕ are primary singletons).

• For every integer i,   ϶ⁱ (resp. ϶¯ⁱ) denotes the inverse of ϵⁱ (resp. of ϵ¯ⁱ). For a natural i, let .ec(i) be the i-th composition of .ec with itself, with .ec(0) being the identity on O. Let .ec(-i) be the inverse of .ec(i). Let T = O ∖ O.ϵ.↧ be the set of terminal objects (or terminals). The metalevel index, x.mli, of an object x is defined by
  • x.mli = sup { i | x ϵ^1-i r, i ∈ ℕ }.
  Finally, the definition of the rank function, .d, assumes a fixed limit ordinal ϖ in the context. The rank of an object x is then recursively defined by

  x.d	= ϖ	if x is non-well-founded in ϵ,
  x.d	= ϖ ∧ (sup {a.d + 1 | a ϵ x} ∨ sup {a.mli + i-j | a ∈ x.϶i.϶-j, i,j ∈ ℕ})	if x is well-founded in ϵ.

  (We use α ∧ β (resp. α ∨ β) to refer to the minimum (resp. maximum) of ordinal numbers α and β. To be correct, the prescription requires finiteness of a.mli which is asserted by (b~10).)

The axioms

Observations:

1. For a suitable choice of (i,j) in (b~2) we obtain transitivity of ≤, subsumption of ϵ¯, and the monotonicity of ϵ¯.
2. For i = 0 in (b~3) we obtain the subsumption of ϵ: (ϵ) ○ (≤) ⊆ (ϵ). In contrast, monotonicity is not asserted.
3. For i = 0 in (b~4) we obtain the antisymmetry and reflexivity of ≤ so that ≤ is a partial order on O.
4. (b~5) asserts that O = T ⊎ r.↧. Since r ϵ x ≤ r for some object x it follows by subsumption of ϵ that r ϵ r. Since r is non-well-founded in ϵ it follows by (b~11) that r ϵ¯ r. Consequently, for every non-terminal x,   x ϵ¯ r by monotonicity of ϵ¯ and x ϵ r since (ϵ¯) ⊆ (ϵ).
5. As a particular consequence of (b~6) and (b~7)(b) we obtain that x ϵ¯ r for every terminal x. It follows that r is a universal (power) container: O = r.϶¯ = r.϶.
6. As a particular consequence of (b~7)(a) we obtain that every object from T.ec^∗ is minimal in ≤ (cf. (e~3)).

Rank

The following diagram shows an ad-hoc completion (⁎) making each object of the original structure ϵ-grounded. Added objects are displayed in khaki color. See [] for the precise definition.

Notes and observations:

1. (⁎) As indicated by the case of the a object, new member chains are added even for objects from T.ϵ^∗ so that the term completion is not quite adequate.
2. It is asserted that x.mli ≤ x.d for every object x. However, even memberless objects can have their rank strictly higher than the metalevel index. This is the case of the b object (2 = b.mli < b.d = 3).

• x.d = sup {a.mli + i-j | a ∈ x.϶ⁱ.϶^-j, i,j ∈ ℕ}.

Bounded membership

• Objects x such that x.d < ϖ are bounded.
• Objects x such that x.d = ϖ are unbounded.

• x ∊ y   iff   x ϵ y and x is bounded.

Note that axioms (b~1) and (b~11) can be stated as a single condition (ϵ) = (∊) ∪ (ϵ¯). This establishes an inclusion lattice between ϵ, ∊, ϵ¯ and ∊¯ according to the above diagram on the right.

Singletons

• x.ɛϲ = y   ↔   {x} = y.϶ and y is a singleton.

The following table shows similarities and differences between .ec and .ɛϲ.

Metaobject structure

Monotonic structures

• Monotonic eigenclass structures are definitionally equivalent to monotonic basic structures that are powerclass complete.
• Monotonic primary structures (see the note about terminological imprecision before the subsection) are obtained from monotonic basic structures by imposing the following condition to negative powers of ϵ:   For every natural k > 0,
  • x ϵ^-k y   iff   there is a natural i such that   (a) r ϵⁱ y, (b) x < r.ϵ^i+k, and (c) r.ϵ^i+k ≠ r.ϵ^i+k-1.
  This yields .ec = ∅ as a particular consequence. See [] for details.

The union map

• (.υ)  =  (.ⱷ) ⊎ ((ϵ^-1) ∩ (϶)).

Complete structure of ϵ

• S is ∊-levelled, that is, every non-terminal object has a bounded member with a lesser metalevel index.
• S is ∊-ranked, that is, x.d equals the ∊-rank of x for every object x.

Superstructure

For convenience, we let the term α-superstructure mean a superstructure (V, ∊) whose ∊-rank equals α. The axiomatization of complete structures via ∊ can be then expressed as follows:

Kinds of superstructures

• Instead of referring to r as the unique object whose existence is guaranteed, introduce a predicate x being an inheritance root:   x is such that x.∍ = V.∍.
• Add the ∅ ≠ x.∍⁰ condition in the definitions of .ec and ϵ¯.

• ZFC (Zermelo-Frankel set theory with the Axiom of Choice) if the rank of ∊ equals ϖ,
• MK (Morse-Kelley set theory) if the rank of ∊ equals ϖ + 1.

Note: In [], the singleton map .ɛϲ is total – unbounded objects have their singleton constantly set to r (considering (V, ∊) as a model of MK).

Completion

• .ν is embedding w.r.t. ϵⁱ and ϵ¯ⁱ for every integer i,
• r.ν = r_ϖ,
• .ν is embedding w.r.t. .ec and .ɛϲ,
• .ν preserves being a primary object, i.e. O₀.pr.ν ⊆ V.pr,
• .ν preserves the rank, i.e. x.d = x.ν.d for every x ∈ O₀.

Note: If R denotes a relation both in S₀ and V then .ν is an embedding w.r.t. R if the following equivalence holds for every objects x, y from O₀:

• (x,y) ∈ R   ↔   (x.ν, y.ν) ∈ R.

1. Rank pre-completion. This step can be omitted for ϖ = ω. Otherwise, attach a set X of ϖ new members to each primary non-well-founded object x that is not ∊-ranked. The members are attached in such a way that (X, ϵ, ≤) is isomorphic to (ϖ, ∈, ⊆).
2. Powerclass completion. Append an infinite powerclass chain to each object for which the powerclass is not defined. The resulting structure is powerclass complete.
3. Singleton completion. Append an infinite singleton chain to each bounded object for which the singleton is not defined. Technically, this can be done in two steps by first adding just the missing primary singletons and subsequently performing the powerclass completion.
4. Extensional pre-completion. (⁎) To every object x that is not extensionally consistent, i.e. for which there exists y such that the following equivalence is not satisfied,
   • x ≤ y   ↔   x = y or ∅ ≠ x.∍ ⊆ y.∍,
   attach two powerclass chains each of which starts in a terminal object. The resulting structure is pre-complete, that is,
   • extensionally consistent   (the above equivalence holds for every objects x, y),
   • powerclass consistent   (that is, if x is powerclass-like then x is a powerclass – see [] for details),
   • powerclass complete,
   • singleton complete   (every bounded object x has a singleton x.ɛϲ), and
   • ∊-ranked.
   In particular, the structure is fully determined by bounded membership ∊ according to the same prescription as with complete structures.

   Note: (⁎) A simplified description is provided here, see [] for the detailed description.

5. Cumulative embedding into an (ϖ+1)-superstructure. Let S = (O, ∊) be the pre-complete structure to be embedded. Choose an (ϖ+1)-superstructure V = (V, ∊) so that its ground stage V₁ has the same cardinality as the set T of terminal objects of S. Then the requested embedding map .ν is obtained as a limit of a transfinite sequence
   • .ν₀, .ν₁, …, .ν_ϖ = .ν
   of maps from O to V defined as follows:
   1. The restriction of .ν_i to terminals is for every i identical and forms a bijection between T and 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.∍.ν0,
      x.νi.∍	=	x.϶¯.νi-1.ec.∍ ∪ x.∍.ν0	if i is a successor ordinal,
      x.νi.∍	=	∪{ x.νk.∍ | k < i }	if i is a limit ordinal.

   Note that the definition of .ν₀ is by the well-founded recursion on (O, ∊), whereas the definition of .ν_i for i > 0 uses transfinite recursion over i.