# 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.
##### Author
 Ondřej Pavlata Jablonec nad Nisou Czech Republic ##### Document date
 Initial release March 2, 2012 Last major release March 2, 2012 Last update June 29, 2012
##### Warning
1. This document has been created without any prepublication review except those made by the author himself.

#### Preliminaries

##### Superstructure
For a set X, we denote (X) the powerset of X, the set of all subsets of X. In addition, we denote
• +(X) = (X) {} the set of all non-empty subsets of X,
• (X) = +(X) X (the first quasi-superstructure of X),
• (X) = {{x} | x X} the set of all singleton subsets of X.
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

• V = { i(U) | i }   (so that we could write V = ω(U))
where U is a subset of V such that
• U,
• x V = for every x U.
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

• u = a0 an = x for some x X   (necessarily, ai V, i = 0, …, n).
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
• a0 an = a   for some a0, …, an from V (necessarily, a0 is an urelement).

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.

• a.ϱ = {x a | x.d = d } where d = min { x.d | x a }.
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:
• x.ec = {x}, if x is an urelement,
• x.ec = +(x) otherwise.

Proposition:

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.ϱ¯ = x.ϱ¯.ec for every x V, i.e. the eigenclass map commutes with the (extended) bottom stratum map.
5. For every x, y V,
• x y.ec   iff   x.ec y.ec.
6. For every x, y V U, i ≥ 0,
• x y   iff   x.ec(i) y.ec(i).

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

• X.f = { x.f | x X }, i.e X.f is the image of X under .f (this might differ from the value of .f at X).
For example, if X is a set of urelements, then X.ec means (X).

#### An alternative axiomatization of S1 structure

An S1 structure is a structure (O, .ec, .pr, .sc, r, c) where
• O is a set of objects.
• .ec is a total function between objects, x.ec is called the eigenclass of x.
• .pr is a total function between objects, x.pr is called the primary object of x.
• .sc is a partial function between objects, x.sc (if defined) is called the superclass of x.
• r is an object, called the inheritance root.
• c is an object, called the instance root   (by (◈3b), c is a shorthand for r.ec.sc).
Objects from O.pr are primary. We partition this set into subsets T and C of terminals and classes, respectively, as follows:
• T consists of primary objects x such that x ≠ r and x.sc is not defined.
• C consists of primary objects that are not in T.
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 ∪ T.ec, .sc, r) is an algebraic tree such that r.sc undefined, elements of T.ec are (among the) leaves, i.e. T.ec.sc ⊆ C ⊇ C.sc. (b) x.sc equals c if x = r.ec. (c) x.sc equals x.ce.sc.ec if x ∈ O.ec ∖ ({r.ec} ∪ T.ec). (◈4) c is a leaf of (C ∪ T.ec, .sc, r), i.e. c ∉ (C ∪ T.ec).sc.
Note that (◈3) may be considered as a partial inductive definition of .sc:
Let X = (C {r}) (T.ec {r.ec}). Then (a)+(b) provide constraints for definition on X and (c) provides the induction step: if .sc is defined on X.ec(i) then (c) yields definition on X.ec(i+1), i ≥ 0.

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

• C¯ = C T.ec.

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

Proof:

• (→) (◈1)–(◈4) implies (S1~1)–(S1~8):
(S1~1) is equivalent to (◈1) by definition.
(S1~2):
Denote Ci the partial algebra (C¯.ec(i), .sc), i ≥ 0. By (◈3c), for each i > 0, Ci-1 and Ci are isomorphic, so that they are isomorphic to C0 = (C¯, .sc) which is, by (◈3a), a tree with root r. By (◈3b)+(◈3c), r.ec(i).sc = c.ec(i-1), i > 0, so that each pair (r.ec(i), c.ec(i-1)) forms an oriented bridge from Ci to Ci-1. This means that the partial algebra (O T, .sc, r) is a tree.
(S1~3) follows from (◈3c).
(S1~7) follows from (◈2).
(S1~8) follows from (◈4).
• (←) The opposite implication is proven similarly.

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,

• x y   iff   x.sc(i) = y for some i ≥ 0.

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,

• x.hancs[i] = x.sc(i)   whenever x.sc(i) is defined.
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 = x.ec.hancestors, so that the class of x is the first class (least in ) in the superclass chain of x.ec. An equivalent definition is

• x.class = x.ec.sc for x T,
• x.class = r.ec.sc = c for x O T.

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

• x y   iff   i > j and y is a helix object.
##### 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.
• Each column corresponds to an eigenclass index.
• Eigenclass links are not drawn, they are assumed to go horizontally, left to right.
• Superclass links (drawn in green) go down-up or right-to-left in case of twist links.
Legend
• … helix class
• … non-helix class
• … terminal
• … eigenclass from C¯.ec(2).

#### 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
• V is a superstructure with its set of urelements denoted U.
• O is a subset of V, elements of O are called objects. We distinguish subsets T, C and H, of terminals, classes and helix objects, respectively, as follows:
• T consists of objects that are urelements (T = O U).
• C consists of objects that contain at least 2 urelements.
• H consists of objects that have at least 2 strata.
The structure is subject to the following conditions:
 (◉1) O.pr = C ⊎ T and O.ec ⊂ O, i.e. for every object x, the primary element x.pr is a class or a terminal, the eigenclass x.ec 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, c ≠ r), (b) U0 is disjoint with T and with every non-helix class. (◉3) (C ∪ U.ec, ⊆) is a forest – therefore (C ∪ U.ec, ⊆, r) is an algebraic tree. (Recall that U.ec 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} ∪ T.ec then x.sc equals the parent of x in the (C ∪ U.ec, ⊆, r) tree. (b) and (c) – If x ∈ O.ec ∖ T.ec then x.sc is defined just like in (◈3).
We call the number k the stratality of (V, O). We also denote C¯ = C T.ec.

Observations:

• r = C = k-1(U).
• c = H.pr,   H.pr = C H.
• Terminals / non-helix classes / helix classes have rank 0 / 1 / k, respectively.
• Non-terminals x are either mono-stratal (if x H) or k-stratal (if x H).
• For every non-terminal object x and every i ≥ 0,
• x C¯.ec(i)   iff   x.ϱ.d = i+1.
• (◉1) means that (O, .ec, .pr) is a subalgebra of (V, .ec, .pr).
• (◉2b) implies that the c class has the following constraints:
• There is no class x such that x c.
• There is no terminal x such that x c.
• The bottom stratum operator .ϱ, in a restriction, is an order-embedding of (C U.ec, ) into (+(U), ). In particular, (C¯, ) is isomorphic to (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 x.ec 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.ν = a.pr.ν.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.

Proposition:

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

Proposition C: For every objects x, y,

• x.ϱ¯ y   iff   x.ec.ϱ y,

Proof:
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.ec.ϱ = {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.ϱ u.ec iff x.ϱ.ec u.ec iff x.ec.ϱ u.ec iff x.ec.ϱ y.
Let y O.ec. Then x.ϱ¯ y iff x.ϱ¯.ec y iff x.ec.ϱ y.

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

• (1) For every x, y O<k T,
• x y   iff   x.ϱ y,
i.e. x is an (.sc-)inheritance descendant of y   iff   the bottom stratum of x is a subset of y.
• (2) For every x O<k, y O<k T,
• x.ec y   iff   x.ϱ¯ y,
i.e. x is kind-of y   iff   x or its bottom stratum is an element (a member) of y.
• (3) For every x O<k,
• x.class = { y C | x.ϱ¯ y },
i.e. the class of x is the smallest class (w.r.t. inclusion) that contains x or its bottom stratum.

Proof:

• (1) Assume x, y O<k T and denote i = x.ϱ.d-1, j = y.ϱ.d-1, so that x C¯.ec(i), y C¯.ec(j).
(a) Let i = j = 0, i.e. x, y C¯. Then
• x y iff x y iff x.ϱ y.
The first equivalence is by definition: (C¯, ) is the reflexive transitive closure of (C¯, .sc) which is defined as the reflexive transitive reduction of (C¯, ) in (◉3a). The second equivalence is immediate if x is not a helix class, that is, if x.ϱ = x. If x is a helix class, then x.ϱ y implies that y is also a helix class, since, by (◉2b), non-helix classes are disjoint with c.ϱ, a subset of x.ϱ. This means that x y.
(b) Let i = j > 0, i.e. x = a.ec(i), y = b.ec(i) for some a, b C¯. Then a.ec(i) b.ec(i) iff a b iff a b iff a.ϱ b iff a.ϱ.ec(i) b.ec(i) iff a.ec(i).ϱ b.ec(i).
(c) Let i ≠ j. By proposition B from the previous section,
• x y   iff   i > j and y is a helix object.
So we should show that the same holds with x y replaced by x.ϱ y.
(c1) Let i < j, equivalently, x.ϱ.d < y.ϱ.d. This implies x.ϱ y.
(c2) Let i > j and y H. Then x.ϱ.d > y.ϱ.d = y.d, thus x.ϱ y.
(c3) Let i > j and y H. Then x = a.ec(j+1) for some a C¯.ec(i-j-1), y = b.ec(j) where b = y.pr = b.ϱ u.ec is a helix class. Since u.d = k - 1 and a.ϱ.d < x.ϱ.d k, it follows by the definition of the urobject u that a.ϱ u. We then obtain
• x.ϱ = a.ec(j+1).ϱ = a.ϱ.ec(j+1) u.ec.ec(j) b.ec(j) = y.
This shows that x.ϱ y.
• (2) follows from (1) and proposition C.
• (3) By definition, x.class equals the least element, w.r.t. , of the set S = { y C | x.ec y }. By (2), S = { y C | x.ϱ¯ y }. Since coincides with on C, a superset of S, the least element of S equals S.
##### Example
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:
• `Class`, `Module`, `Object`, `BasicObject` are the helix classes.
• `A`, `Q`, `B` are the non-helix classes.
• `b`, `M` are the terminal objects.
We assume the following relationships:
• `c = Class ⊂ Module ⊂ Object ⊂ BasicObject = r`
• `b ∈ B ⊂ A ⊂ Object`
• `Q ⊂ A`
• `M ∈ Module`
Then the structure can be created by the following code:
```class A;     end
class Q < A; end
class B < A; end
b = B.new
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 = O.pr ∖ U T the set of terminals T = O.pr ∩ U C¯ the set C ⊎ T.ec H the set of helix objects H = { x ∈ O | x.ϱ¯ ≠ x }, i.e. x ∈ H iff x has at least 2 strata H.pr the set of helix classes H.pr = C ∩ H, forms the inclusion chain c ⊂ ⋯ ⊂ r O.pr the set of primary objects O = O.pr ⊎ O.ec O.ec the set of secondary objects (eigenclasses) r the (superclass) inheritance root a class, equals ℙ⋆k-1(U) c the instance root a class, equals r.ec.sc u the urobject a non-object, equals ℙ⋆k-2(U) k the stratility of (V, O) a natural number, at least 2 x.ec the eigenclass of x object preserving map V → V x.ec equals {x} if x is an urelement, otherwise equals ℙ+(x) x.ce the (first) eigenclass predecessor of x object preserving map V ∖ V.pr → V ;   the inverse of .ec x.pr 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 x.sc the superclass of x map O ∖ (T ∪ {r}) → O ∖ T x.class the class of x map O → C ;   x.class = x.ec.hancestors x.class.class = c for all objects x x.hancs (.sc-) inheritance ancestors of x x.hancs[i] equals x.sc(i) 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), ⊆).
##### References
 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, http://www.atalon.cz/rb-om/ruby-object-model
##### Document history
 March 2 2012 The initial release. March 5 2012 Side view diagram added. April 3 2012 Improvements and corrections in proofs. June 29 2012 The definition of a primorder algebra moved to the main document.