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
This document has been created without any prepublication review
except those made by the author himself.
Table of contents
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 mapV → V
defined as an adaptation of ℙ+ to urelements as follows:
x.ec = {x}, if x is an urelement,
x.ec = ℙ+(x) otherwise.
Proposition:
(V, .ec) is (the reduct of) a primorder algebra.
We will apply established notation and terminology,
in particular, definition of
.pr, .ce and .eci.
x.ce = ∪ x
whenever x.ce is defined and is not an urelement.
Urelements and elements containing at least 2 urelements are (among)
primary elements.
x.ec.ϱ¯ = x.ϱ¯.ec for every x ∈ V,
i.e. the eigenclass map commutes with the (extended) bottom stratum map.
For every x, y ∈ V,
x ∈ y.ec iff x.ec ⊆ y.ec.
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~4)–(S1~6) follow from (◈3a).
(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[0],
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.
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.
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
(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:
(i)
x = y.ur(i) and y ≤ a
for some y ∈ C, i ∈ {1,2}.
(ii)
x ∈ T and x.ec ≤ a.
(iii)
x ∈ℙ+(ℙ⋆k-2(U)) and a is a helix class.
(b)
If a is terminal then a.ν = a.ur.
(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:
The urobject is a primary element that is not an object
(neither it is an urelement).
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[0] 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,
