Ruby Object Model

Data structure in detail

S1 superstructure representation

As an appendix to [], a set-theoretical model of the Ruby S1 structure is presented. In particular, a correspondence is provided between inheritance and set inclusion as well as between kind-of relation and set membership.
Ondřej Pavlata
Jablonec nad Nisou
Czech Republic
Document date
Initial releaseMarch 2, 2012
Last major release March 2, 2012
Last updateJune 29, 2012
  1. This document has been created without any prepublication review except those made by the author himself.

Table of contents


For a set X, we denote (X) the powerset of X, the set of all subsets of X. In addition, we denote We will also use exponents for multiple application, e.g. +i(X) means i-th application of + to X (we put +0(X) = X).

We call a set V a superstructure [], if it equals the infinite union

where U is a subset of V such that This means that U is uniquely given as the set U(V) = { x V | x V = }. Elements of U can be considered urelements (and we will call them so) – their set-theoretic structure does not interfere with the superstructure so that they are atoms in V with respect to set membership.

Given a superstructure V, for a subset X V we denote U(X) the urelement-set of X, defined as the set of all urelements u such that there is a membership chain

For a V, we denote a.d the rank (alternatively, depth) of a to be the smallest i such that a i(U). Equivalently, a.d is the maximal n such that

The superstructure is naturaly stratified according to the rank function. The set U of urelements is exactly the set of elements with rank 0. For every natural n > 0, the difference n(U) n-1(U) is the set of elements with rank n. For a V U, non-empty intersections of a with strata of V form strata of a. We denote a.ϱ the bottom stratum of a, i.e.

We also denote .ϱ¯ the extension of .ϱ to V by putting x.ϱ¯ = x if x is an urelement.
We denote by .ec the eigenclass map V V defined as an adaptation of + to urelements as follows:


  1. (V, .ec) is (the reduct of) a primorder algebra.
    We will apply established notation and terminology, in particular, definition of .pr, .ce and .eci.
  2. x.ce = x   whenever x.ce is defined and is not an urelement.
  3. Urelements and elements containing at least 2 urelements are (among) primary elements.
  4.ϱ¯ = x.ϱ¯.ec for every x V, i.e. the eigenclass map commutes with the (extended) bottom stratum map.
  5. For every x, y V,
  6. For every x, y V U, i ≥ 0,

We adopt the convention that if a subset X of V is denoted by a capital letter and .f is a function on V then

For example, if X is a set of urelements, then means (X).

An alternative axiomatization of S1 structure

An S1 structure is a structure (O, .ec, .pr, .sc, r, c) where Objects from are primary. We partition this set into subsets T and C of terminals and classes, respectively, as follows: The structure is subject to the following conditions:
(◈1) (O, .ec, .pr) is a primorder algebra.
We will apply established notation and terminology, in particular, definition of .ce and .eci.
(◈2) r and c are different classes.
(◈3) The superclass partial map .sc satisfies the following:
  • (a) (C, .sc, r) is an algebraic tree such that
    • undefined,
    • elements of are (among the) leaves, i.e. C
  • (b) equals c if x =
  • (c) equals if x ({}
(◈4) c is a leaf of (C, .sc, r), i.e. c (C
Note that (◈3) may be considered as a partial inductive definition of .sc:
Let X = (C {r}) ( {}). Then (a)+(b) provide constraints for definition on X and (c) provides the induction step: if .sc is defined on then (c) yields definition on, i ≥ 0.

As shown in (◈3) and (◈4), the set C is distinguished. We make the distinction explicit by denoting

Proposition A: (◈1) – (◈4) are equivalent to (S1~1) – (S1~8).


We recall additional notation and terminology introduced for S1 structures.

As a partial order, the .sc-inheritance can be written as (O T, ) which is just the reflexive transitive closure of .sc, with the reflexive closure only applied to non-terminals, i.e. for every non-terminal objects x, y,

Note: When using the symbol for superclass inheritance, we have to be careful about restricting to non-terminals. In an S2 structure, is extended to the set of includers (the domain difference being the set of terminals called modules).

The list corresponding to the superclass chain of a non-terminal x is denoted x.hancs,

The list x.hancs C, i.e. x.hancs without eigenclasses, is denoted x.hancestors.

The class map, .class : O C, is defined by x.class =[0], so that the class of x is the first class (least in ) in the superclass chain of An equivalent definition is

Proposition B: Let x, y be non-terminal objects such that x C¯.ec(i), y C¯.ec(j) for i ≠ j (i.e. x and y appear in different components Ci from the proof of proposition A). Then

Side view diagram
The following diagram shows a sample S1 structure from the side view – tree structue of C¯ c.hancs is displayed as a chain.

Ruby S1 superstructure representation

By a superstructure representation of the Ruby S1 structure (or an S1 superstructure for short) we mean a structure (V, O) where The structure is subject to the following conditions:
(◉1) = C T and O, i.e. for every object x,
  • the primary element is a class or a terminal,
  • the eigenclass is an object.
(◉2) The set C H of helix classes is a finite set { c = h0, h1, …, hn-1 = r }, n ≥ 2, such that
  • hi = Ui +(k-2(U))
for some k ≥ 2 and some sets of urelements U0, U1, …, Un-1, i = 0, …, n-1, such that
  • (a) U0 U1 Un-1 = U   (in particular, cr),
  • (b) U0 is disjoint with T and with every non-helix class.
(◉3) (C, ) is a forest – therefore (C, , r) is an algebraic tree.
(Recall that is equal to (U), the set of all singleton subsets of U).

In a correspondence, we define the superclass map .sc : O ({r} T) O as follows:

  • (a) If x C {r} then equals the parent of x in the (C, , r) tree.
  • (b) and (c) – If x then is defined just like in (◈3).
We call the number k the stratality of (V, O). We also denote C¯ = C


Proposition A: (O, .ec, .pr, .sc, r, c) is an S1 structure.

Proof: The proof is a straightforward verification of (◈1)–(◈4).  

Proposition B: Every S1 structure S has a superstructure representation, for any given stratality k ≥ 2.

Proof: Given an S1 structure S, with all the established notation, we construct its representation (V, O.ν) as follows. Let U = T C.ur(1) C.ur(2) be the set of urelements of a superstructure V where .ur : T U and .ur() : C × {1,2} U are injective maps (so that U contains exactly one copy of each terminal and two copies of each class).

We define an injective map .ν : O V by

  1. (a) If a is a class then a.ν is a subset of k-1(U) such that   x a.ν   iff   one of the following conditions is satisfied:
    1. (i) x = y.ur(i) and y a for some y C, i {1,2}.
    2. (ii) x T and a.
    3. (iii) x +(k-2(U)) and a is a helix class.
  2. (b) If a is terminal then a.ν = a.ur.
  3. (c) If a is an eigenclass then a.ν =ν.ec(i) where i = a.eci.
The structure (V, O.ν) is then a superstructure representation of S, with .ν being an isomorphism between S and the S1 structure induced by (V, O.ν).  
We denote u = k-2(U) and call this element the urobject.


  1. The urobject is a primary element that is not an object (neither it is an urelement).
  2. h = h.ϱ for every helix class h.

Proposition C: For every objects x, y,

If y is a terminal then neither side of the logical equivalence (iff) can be satisfied.
Let x be a terminal. Then x.ϱ¯ = x y iffϱ = {x} y.
Let y be a non-helix class, x a non-terminal. Then neither side of iff can be satisfied.
Let y be a helix class, x a non-terminal. Then x.ϱ y iff x.ϱ iff x.ϱ.ec iffϱ iffϱ y.
Let y Then x.ϱ¯ y iff x.ϱ¯.ec y iffϱ y.  

Proposition D: Let x O<i denote the set of objects with the eigenclass index less that i.


The following diagram shows an S1 superstructure with 15 urelements, 2 terminals and 7 classes (4 of them are helix classes). Note that except for terminals, object eigenclasses are not displayed.
We assume the following notation: We assume the following relationships: Then the structure can be created by the following code:
class A;     end
class Q < A; end
class B < A; end
b =
module M;    end

Notation summary

The following table provides a summary of the notation introduced for a structure (V, O) that is a superstructure representation of a Ruby S1 structure.
Notation Terminology Description
+(X) the set of non-empty subsets of X
(X) the (first) quasi-superstructure of X (X) = +(X) X
U the set of urelements
V set-theoretic superstructure
the set of elements
equals ω(U)
O the set of objects
C the set of classes C = U
T the set of terminals T = U
C¯ the set C
H the set of helix objects H = { x O | x.ϱ¯ ≠ x }, i.e. x H iff x has at least 2 strata the set of helix classes = C H, forms the inclusion chain c r the set of primary objects O = the set of secondary objects
r the (superclass) inheritance root a class, equals k-1(U)
c the instance root a class, equals
u the urobject a non-object, equals k-2(U)
k the stratility of (V, O) a natural number, at least 2 the eigenclass of x object preserving map V V equals {x} if x is an urelement, otherwise equals +(x)
x.ce the (first) eigenclass predecessor of x object preserving map V V ;   the inverse of .ec the primary element of x object preserving map V V, the root map for the forest (V, .ce)
x.eci the eigenclass index of x map V
x.d the rank (depth) of x map V
x.ϱ¯ the bottom stratum of x idempotent map V V
identity on O H ;   maps to non-objects on H the superclass of x map O (T {r}) O T
x.class the class of x map O C ;   x.class =[0]
x.class.class = c for all objects x
x.hancs (.sc-) inheritance ancestors of x x.hancs[i] equals
x.hancestors primary (.sc-) inheritance ancestors of x Obtained by removing the non-class prefix p from x.hancs = p + x.hancestors
(O T, ) the (.sc-) inheritance the reflexive transitive closure of (O T, .sc)
For each i , (C¯.ec(i), ) coincides with (C¯.ec(i), ).


C. C. Chang, H. Jerome Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, 1990,
Ondřej Pavlata, The Ruby Object Model: Data Structure in Detail, 2012,
Document history
March22012 The initial release.
March52012 Side view diagram added.
April32012 Improvements and corrections in proofs.
June292012 The definition of a primorder algebra moved to the main document.
This document is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.