Preface

Author Ondřej Pavlata Jablonec nad Nisou Czech Republic

Document date Initial release March 12, 2015 Last major release March 12, 2015 Last update March 12, 2015 (see Document history)

Warning

1. This document has been created without any prepublication review except those made by the author himself.

Table of contents

Introduction

We further assume that the .ec map is total (that is, every object has a powerclass / eigenclass).

Simplified correspondence between objects and sets

• (ϵ) ○ (≤) ⊆ (ϵ)	(all members of an object x are among members of any ancestor of x)
  (∈) ○ (⊆) ⊆ (∈)	(all elements of a set x are among elements of any superset of x).

• (.ec) ○ (϶) = (≥)	(members of the powerclass of x are the descendants of x)
  ℙ ○ (∋) = (⊇)	(elements of the powerset of x are the subsets of x).

Monotonicity

• (≤) ○ (ϵ) ⊆ (ϵ).

• (ϵ) = (.ec) ○ (≤),

We can observe that the above equations (those involving .ec) imply that the .ec map is an order embedding: Let .ce denote the inverse of .ec and substitute (.ec) ○ (≤) for (ϵ) in (≤) = (ϵ) ○ (.ce). Then

• (≤) = (.ec) ○ (≤) ○ (.ce)   (equivalently,   x ≤ y   ↔   x.ec ≤ y.ec).

Basic nomenclature of objects

class A; end; class B < A; end; u = B.new; v = B.new

S1_v: Monotonic eigenclass structure of ϵ

Axioms

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

Definitions

Eigenclass chains

• Let .ce denote the partial map between objects that is the inverse of .ec. Let .ce^∗ be the inverse of .ec^∗ so that it is the reflexive transitive closure of ce.
• For an integer i, let .ec(i) be the i-th composition of .ec with itself if i ≥ 0 (with .ec(0) being the identity on O) and the -i-th composition of the inverse of .ec otherwise. Similarly with .ce.
• Let .pr be the map between objects such that:   x = y.pr   ↔   {x} = y.ce^∗ ∖ O.ec.
• For an object x,
  • x.ec is the eigenclass of x,
  • x.ce, if defined, is the eigenclass predecessor of x,
  • x.pr is the primary object of x,
  • x.eci is the eigenclass index of x, defined as the unique natural i such that x.pr.ec(i) = x.

Object membership and its powers

• The object membership relation, ϵ, is the composition (.ec) ○ (≤).
• For an integer i, let ϵⁱ denote the i-th power of ϵ defined by
  • (ϵⁱ)   =   (≤) ○ .ec(i) ○ (≤).
  That is, (ϵ⁰) = (≤), (ϵ^-1) = (≤) ○ (.ce), and for a positive natural i,   ϵⁱ (resp. ϵ^-i) equals the i-th power of ϵ (resp. ϵ^-1) in the sense of relational composition.
• Let ϵ^∗ and ϵ^-∗ be transitive closures of (ϵ⁰) ∪ (ϵ¹) and (ϵ⁰) ∪ (ϵ^-1), respectively. Equivalently,
  • (ϵ^∗) = .ec^∗ ○ (≤)   and   (ϵ^-∗) = (≤) ○ .ce^∗.
• The usual notation and terminology for ≤ and ϵ applies, in particular, .↥/.↧ and .ϵ/.϶ are the respective image/preimage operators. Similarly for ϵⁱ and ϵ^∗.

Distinguished sets of objects

• The set O.ec consists of eigenclasses.
• The set O.pr = O ∖ O.ec is the set of primary objects.
• The set C of classes is defined as r.↧ ∖ O.ec.
• The set T of terminals is defined such that O = T ⊎ C ⊎ O.ec.
• The set R = r.ec^∗ (the eigenclass chain of r) is the reduced helix.
• The set H = r.ϵ^∗ = R.↥ is the set of helix objects.

Metalevels

• The metalevel index of an object x is denoted x.mli and defined by
  • x.mli = sup { i | x ϵ^1-i r, i ∈ ℕ },   equivalently, x.mli = min { i | x ≰ r.ec(i), i ∈ ℕ }.
  For every natural i, the set r.϶^-i = r.ec(i).↧ consists of objects x such that x.mli > i.
  • (S1_v~5) asserts that x.mli is finite for every object x. (Here we refer to the first expression of x.mli.)
• The i-th metalevel, i ∈ ℕ, is the set r.϶^1-i ∖ r.϶^-i of objects whose metalevel index equals i.
  • The 0-th metalevel is the set T of terminals.
  • The i-th metalevel equals t.϶ ∖ t.↧ where t = r.ec(i) is the top of the (i+1)-th metalevel.

Rank and boundedness

• The rank of an object x is denoted x.d and defined by
  • x.d = sup { a.mli + i | a ϵⁱ x, i ∈ ℤ }.
• The bounded membership relation, ∊, is the domain restriction of ϵ to objects with finite rank:
  • x ∊ y   iff   x ϵ y and x.d < ω.
• Objects with finite rank are bounded, the remaining are unbounded. Thus, O.∍ is the set of bounded objects.
• A set X of objects is bounded (resp. unbounded) if sup(X.d) < ω (resp. sup(X.d) = ω).

Leaf

• An object x is a leaf if it is primary all objects from x.ec^∗ are minimal in ≤. Observations:
  • (S1_v~3) states that every terminal object is a leaf.
  • x is a leaf   ↔   x.ec^∗ = x.ec^∗.∍.   (In particular, x is bounded.)
  • x is a leaf   ↔   x is primary and x.϶^-i = {x}.ec(i) for every natural i.

Instance-of and the .class map

• The instance-of relation is the range-restriction of ϵ to C.
• The .c partial map is the partial closure operator O ↷ O defined by:  
  • x.c = y   ↔   y is the bottom of x.↥ ∖ O.ec.
• The .class partial map is the composition .ec.c. Equivalently,
  • x.class = y   ↔   y is the bottom of x.ϵ ∩ C, the least container of x that is a class.
  If x.class = y then we say that y is the class of x or, equivalently, x is a direct instance of y. Obviously, direct-instance-of is a subrelation of instance-of.

Polars of ≤

• X ≤ Y   iff   x ≤ y for every x ∈ X and y ∈ Y,
• a ≤ X   iff   {a} ≤ X,

• X.▽ = { x | x ≤ X } is the set of lower bounds of X, similarly, X.△ is the set of upper bounds,
• X.⋁ = { x | x < X } is the set of strict lower bounds of X, simlarly for X.⋀,
• a.⋁ = {a}.⋁   (that is, a.⋁ is the set a.↧ ∖ {a} of strict descendants of a).

Boundedly complete ideal

• A (necessarily non-empty) set X of objects is a boundedly complete ideal if
  • X is a down-set w.r.t. ≤ (that is, X = X.↧), and
  • every bounded subset Y of X has an upper bound in X (that is, X ∩ Y.△ ≠ ∅).
• A set X of objects is a principal ideal if it is a principal ideal w.r.t. ≤, i.e. X = x.↧ for a unique object x.

Properties

Proposition: In an S1_v structure S = (O, .ec, ≤, r) the following are satisfied:

1. S is uniquely given by object membership, ϵ:

   x ≤ y	↔	x.ϵ ⊇ y.ϵ,
   x.ec = y	↔	x.ϵ = y.↥.	(In addition, x.ec = y → x.↧ = y.϶ but ← does not hold in general.)

2. For every integers i, j,  
   • (ϵⁱ) ○ (ϵ^j) ⊆ (ϵ^i+j),   (in particular, the subsumption and monotonicity rules apply)
   • (ϵⁱ) ∩ (϶^-i) = .ec(i).
3. For every integers i, j, k and every objects x, y,  
   • x.ec(i) ϵ^k y.ec(j)   ↔   x ϵ^i+k-j y     whenever x.ec(i) and y.ec(j) are defined.
   For i = j = 1 and k = 0 the statement reduces to (S1_v~2).
4. The set R is linearly ordered:   r.ec(i) ≤ r.ec(j)   iff   i ≥ j.

Embedding

(a) x.ν.ec = x.ec.ν,   (b) x ≤ y   ↔   x.ν ≤ y.ν,   (c) r.ν = r_ω.

(d) x.ν.pr = x.pr.ν,   (e) x.ν.d = x.d.

Observations:

1. Every embedding .ν is implicitly embedding w.r.t. ϵⁱ and .mli, i ∈ ℤ.
2. Let S = (O, .ec, ≤, r) be an S1_v structure.
   1. Both R and H form a faithful substructure.
   2. R forms the minimum substructure.
   3. If X forms a faithful substructure then so does X ∪ T.ec^∗.

Instances

• x = q.new   (Ruby syntax)

Free instance

• x.τ = y   ↔   x is a free member and x.pr.class.ec(i) = y where i = x.eci.

Proposition: Let x be an object and denote X = x.τ(-1). Then for every object y the following are satisfied:

1. 1. If X ⊆ y.∍   then   x ≤ y or X = ∅ or X = {y}.ce.
   2. X.↥ ∩ x.϶ = X ⊎ {x}.ce.
2. If, in addition, X has at least 2 elements then the following are satisfied:
   • If x.∍ ⊆ y.∍   then   x ≤ y.
   • If x is primary   then   X.△ ∩ x.϶ = ∅.

Example

Instantially complete structure

Observations: In an instantially complete structure S the following holds:

1. C = O.class.
2. For every non-terminal objects x, y,
   1. x.∍ ⊆ y.∍   iff   x ≤ y,
   2. if x is a class then X ⊆ x.∍ for some 2-element set X such that X.△ ∩ x.϶ = ∅.

   Corollary: S is pre-complete.

Instance 1-completion

1. Every new primary object is a (a) leaf and (b) free instance.
2. Every old class x has exactly n new direct instances where n equals
   • 2 if x has no old direct free instances,
   • 1 if x has exactly one old direct free instance,
   • 0 if x has more than one old direct free instance.

Proposition:

• Every S1_v structure S₀ has an instance 1-completion S. Moreover, S is created from S₀ in the following steps:
  1. Let (N.pr ⊎ O₀, .class) be an extension of (O₀, .class) such that
     • N.pr.class ⊆ C₀, where C₀ is the set of old classes, and
     • for every x ∈ C₀, the set x.class(-1) ∩ N.pr has exactly 0, 1 or 2 elements according to (Ⅱ).
  2. Let (N, .ec) be an extension of (N.pr, ∅) where .ec is an injective well-founded map on N such that N = N.pr ⊎ N.ec.
  3. Denote O = O₀ ⊎ N so that (O, .ec) is a disjoint union of (N, .ec) and (O₀, .ec).
  4. Let S = (O, .ec, ≤, r) be the extension of S₀ such that for every x from N.pr and every natural i,
     • x.ec(i).⋁ = ∅,   and  
     • x.ec(i).⋀ = x.class.ϵ▫^i-1   where ϵ▫ is object membership in S₀.
     Recall that for an object a,   a.⋀ (resp. a.⋁) is the image (resp. pre-image) of a under <.

Instance completion

1. Every new object (a) has no old descendants and (b) is a free instance.
2. Every class x has exactly n new direct instances where
   • n equals 0, 1 or 2 according to 1-completion if x is old
   • n equals 2 if x is new.

Proposition:

1. If S is an instance completion of S₀ then S is instantially complete.
2. Every S1_v structure S₀ has an instance completion S. Moreover, S is created from S₀ as the union of S1_v structures S_i = (O_i, …), i ∈ ℕ, such that for every natural i, S_i+1 is an instance 1-completion of S_i.

Complete monotonic structure of ϵ

(ω+1)-superstructure

Note: The x object in (co~4) is unique for X ≠ ∅. By allowing empty X in the quantification it is ensured that there is at least one object (i.e. V ≠ ∅) and, consequently, the rank of ∊ equals ω+1.

Recall that an (ω+1)-structure is definitionally equivalent to a complete structure of ϵ such that r.d = ω. The inheritance relation, ≤, is given by

• x ≤ y   ↔   x = y or ∅ ≠ x.∍ ⊆ y.∍.

Pre-complete monotonic structure

Proposition:

1. A pre-complete monotonic structure is uniquely given by its bounded membership, ∊:

   Inheritance root	r.∍	=	O.∍
   Inheritance	x ≤ y	↔	x = y or ∅ ≠ x.∍ ⊆ y.∍
   Bounded inheritance	x ∊0 y	↔	x ≤ y and x ∈ O.∍
   Eigenclass map	x.ec = y	↔	x.∍0 = y.∍
   Object membership	x ϵ y	↔	x.∍0 ⊆ y.∍

2. Pre-complete monotonic structures (O, .ec, ≤, r) can be axiomatized via (O, ∊):

   (1)	∊ is well-founded.
   (2)	∊ is extensional on O.∊, that is, for every x, y from O.∊,   if x.∍ = y.∍ then x = y.
   (3)	O.∍ is the set of all objects with finite ∊-rank.
   (4)	O.∍ = r.∍ for some (necessarily unique) object r.
   (5)	For every object x,   x.∍ is a downset.   (That is, the monotonicity rule (≤) ○ (∊) ⊆ (∊) holds.)
   (6)	For every object x,   there is an object y (= x.ec) such that x.∍0 = y.∍.
   (7)	For every object x,   if x.϶ is a boundedly complete ideal   then   x.∍.∍ = u.∍ for some object u.

3. An instantially complete S1_v structure is pre-complete.
4. Corollary: Every S1_v structure can be faithfully embedded into a pre-complete monotonic structure.

Complete monotonic structure

Proposition:

1. Every complete monotonic structure is pre-complete.
2. Complete monotonic structures can be axiomatized via bounded membership, ∊:

   (1–3)	Same as (co~1)–(co~3).
   (4)	Same as (co~4) except that subset is replaced by downset.
   (5)	(≤) ○ (∊) ⊆ (∊).

3. The lifted version L of (O.∊, ≤) is isomorphic to (D(O.∍), ⊆), where D(O.∍) is the set of all downsets in (O.∍, ≤). Consequently, L is a complete lattice that is atomic and completely distributive.
4. Let V = (V, ∊) be an (ω+1)-superstructure and let O denote the set of all hereditarily ↧-complete objects, i.e.
   • O = { x | x.∍ = x.∍.↧ ⊆ O }.
   Then S = (O, ∊) is a complete monotonic structure. The set T = O ∖ O.∊ of terminal objects of S equals the ground stage V₁ = V ∖ V.∊ of V. The .mli and .d maps in S and V are coincident on O. If .ec_V denotes the powerclass map in V (and .ec is the eigenclass map in S) then the following holds for every object x from O:
   • x.ec = x.ec_V if x ∈ T.ec^∗,
   • x.ec < x.ec_V otherwise.

Completion

• .ν₀, .ν₁, …, .ν_ω = .ν

1. The restriction of .ν_i to terminals is for every i identical and forms a bijection between T and V₁ = V ∖ V.∊.
2. The restriction of .ν_i to the set O.∊ of non-terminal objects x is recursively defined by
   • x.ν₀.∍ = x.∍.ν₀.ec.∍,
   • x.ν_i+1.∍ = x.϶.ν_i.ec.∍,
   • x.ν.∍ = ∪{ x.ν_i.∍ | i < ω }.

Proposition: (The completion theorem)

• The .ν map is a faithful embedding of S into V.

References

Document history

License