Object Membership

Set theoretic representation

As an appendix to [], a set-theoretic representation of object membership, ϵ, is presented. The canonical structure of ϵ is first generalized to a structure that is essential with respect to set representation. It is shown that any such essential structure has an extension that satisfies certain consistency conditions with respect to preimages in ϵ. A consistent essential structure (O, ϵ) is then embedded into a cumulative hierarchy V of sets, called eigenclass frame. Similarly to a superstructure in non-standard analysis, V has urelement-like sets on the ground level. However, the powerset cumulation goes to ω + 1 which is one stage more than in superstructures. The V set is recognized as an essential structure of object membership with following constituents:

Inheritance, ≤, coincides with set inclusion, ⊆.
The inheritance root, r, is the ω-th stage.
The eigenclass map, .ec, is an adjusted powerset operator: x.ec = ℙ(x) ∩ r, i.e. the eigenclass of x is the set of all such subsets of x that belong to ω-th stage.

Like with abstract objects, object membership, ϵ, on V is obtained as the composition of .ec with ≤.

In addition to the above structure, the embedding map, .ν, preserves primary objects. Moreover, a partial correspondence between ∈ and ϵ is established. For every x, y from O.ν,

x ∈ y iff x ϵ y and x ∈ r.

Preface

Author

	Ondřej Pavlata
	Jablonec nad Nisou
	Czech Republic

Document date

Initial release	January 12, 2013
Last major release	January 22, 2013
Last update	January 22, 2013

(see Document history)

Warning

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

Preliminaries

Ordinal numbers up to ω + 1

Let ω denote the first infinite ordinal number so that it is just another symbol for the set ℕ of natural numbers. The set ω + 1 equals ω ∪ {ω}. Following the standard convention, we use the ≤ symbol and its variants for set inclusion between ordinal numbers. In particular, i < ω for every natural i.

For a subset X of ω + 1, we write sup(X) for the supremum of X – the least y from ω + 1 such that x ≤ y for every x from X. Equivalently,

sup(X) = 0 if X is empty,
sup(X) = max(X) if X is finite and non-empty,
sup(X) = ω if X is infinite.

Powerset cumulation

For a set X, we denote ℙ(X) the powerset of X, the set of all subsets of X. In addition, we denote

ℙ_⋆(X) = ℙ(X) ∖ {∅} ∪ X the (first) powerset cumulation of X.

We will use exponents up to ω + 1 for multiple application as follows:

ℙ_⋆⁰(X) = X,
ℙ_⋆ⁱ(X) = ℙ_⋆(ℙ_⋆^i-1(X)) for 0 < i < ω,
ℙ_⋆^ω(X) = ∪{ ℙ_⋆ⁱ(X) | i < ω },
ℙ_⋆^ω+1(X) = ℙ_⋆(ℙ_⋆^ω(X)).

Well-foundedness

For a relation R on a set X, an element x ∈ X is well-founded in R if x is not a member of an infinite descending chain in R, i.e. if there is no infinite chain of the form

… x₂ R x₁ R x₀ = x.

A relation R on a set X is well-founded if all elements x ∈ X are well-founded in R. Assuming the axiom of choice, this is equivalent to the condition that every non-empty subset Y ⊆ X contains an element y that is minimal in (Y,R) (i.e. such that R⁻¹({y}) ∩ Y is empty).

A relation S is the well-founded restriction of R if S is the domain-restricton of R to the set of elements from the domain of R that are well-founded in R, i.e.

x S y iff x R y and x is well-founded in R.

Obviously, S is a well-founded relation.

Primorder algebra

By a primorder algebra we mean a structure (X, .ec, .pr) where

X is a set (possibly empty),
.ec is a map X → X, x.ec is called the eigenclass of x,
.pr is a map X → X, x.pr is called the primary element of x.

Elements from the range X.pr are primary. Elements from the range X.ec are eigenclasses. We write x.ec(i) for i-th application of .ec to x (x.ec(0) equals x). The structure is subject to the following axioms:

(1) .ec is injective.
(2) For every x there exists a unique natural number i such that x.pr.ec(i) = x.

We denote .ce the inverse of .ec. If defined, x.ce is the (direct) eigenclass predecessor of x. The eigenclass index of x, denoted x.eci, is defined as the unique i from (2).

Proposition:

Each component of the monounary algebra (X, .ec) is isomorphic (via .eci) to the structure (ℕ, succ) of natural numbers where succ is the successor operator.
X = X.pr ⊎ X.ec, i.e. an element is either primary or an eigenclass.
For an element x the following are equivalent:
- x is primary.
- x is the primary element of itself.
- x has no eigenclass predecessor.
- x has zero eigenclass index.
A primorder algebra (X, .ec, .pr) is uniquely given by its reduct (X, .ec).

□

Terminological conventions

In this document, the term class is not used in the set-theoretic sense. Instead, the terminology from [] is applied, i.e. class means primary non-terminal object.

S1_v: The essential structure of object membership

By an S1_v structure we mean a structure (O, .ec, ≤, r) where

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.

The usual ancestor / descendant terminology is used for inheritance. Objects that are not descendants of r are terminal(s). The eigenclass chain of an object x is the set { x.ec(i) | i ≥ 0 } where x.ec(i) is the i-th application of .ec to x.

The structure is subject to the following axioms:


(S1_v~1)	Inheritance, ≤, is a partial order.
(S1_v~2)	The eigenclass map, .ec, is an order-embedding of (O, ≤) into itself.
(S1_v~3)	Objects from eigenclass chains of terminals are minimal in inheritance.
(S1_v~4)	Every eigenclass is a descendant of the inheritance root, O.ec ⊆ r.↧.
(S1_v~5)	The eigenclass chain of r (denoted R – see below) has no lower bound in ≤. In particular, r.ec ≠ r.

Proposition A:

The structure (O, .ec) is a reduct of a primorder algebra.
We will apply established notation and terminology for primorder algebras – in particular, definition of .pr, .ce and .eci.
The inheritance root r is a primary object.
For every object x and every natural i, j,
- x.ec(i) ≤ x.ec(j) implies i ≥ j.
(That is, a strict inheritance ancestor of an object x can only appear before x in the eigenclass chain, not after x, directly or indirectly.)

□ Additional notation and terminology is applied:

The object membership relation, ϵ, is the composition (.ec) ○‣ (≤).
The usual notation and terminology for ≤ and ϵ applies, in particular, .↥/.↧ and .ϵ/.϶ are the respective image/preimage operators.
The set C of classes is defined as r.↧ ∖ O.ec. Range-restriction of ϵ to C is the instance-of relation.
The set T of terminals is defined such that O = T ⊎ C ⊎ O.ec.
We denote R = {r.ec(i) | i ≥ 0} the eigenclass chain of r (which is also the set of all meta-level roots).
The set H of helix objects is the set R.↥. (In this document, we prefer to use R.↥ instead of H.)
The meta-level root operator, .re, is the closure operator O ∖ T ↠ R, see the proposition below. (As a consequence, R = r.↧.re.)
The i-th meta-level, i ≥ 0, is the set r.ec(i).϶ ∖ r.ec(i).↧.
- The 0-th meta-level is the set T of terminals.
- For i > 0, r.ec(i-1) is the top of the i-th meta-level.
- For i ≥ 0, the set O ∖ r.ec(i).↧ is the union of 0-th to i-th meta-levels.
The meta-level of an object x is the unique meta-level to which x belongs, i.e. the set x.ec.re.϶ ∖ x.ec.re.↧.
The meta-level index of an object x, denoted x.mli, is the index of the meta-level of x, i.e.
- x.mli = x.ec.re.eci - 1.
We write x.c = y if y is the bottom of x.↥ ∖ O.ec. This defines a partial closure operator O ↷ O.
The .class partial map is the composition .ec.c.
An object x is a leaf if it is primary and every y from the eigenclass chain of x (in particular, x itself) is minimal in inheritance. By (S1_v~3), every terminal is a leaf.
A subset X ⊆ O forms a substructure if the following are satisfied:
- r ∈ X, and
- X.ec = O.ec ∩ X.
Equivalently, X forms a subalgebra of the pointed primorder algebra (O, .ec, .pr, r).

Proposition B:

The set R is linearly ordered by
- r.ec(i) ≤ r.ec(j) iff i ≥ j.
The set R forms a closure system in (O ∖ T, ≤). (That is, every non-terminal object x has a least ancestor that belongs to R.) The corresponding closure operator is denoted .re. We have
- x ∈ r.ec(i).↧ ∖ r.ec(i+1).↧ iff x.re = r.ec(i).
The set R.↥ of helix objects has no lower bound in ≤.
The structure (O, .ec, ≤, r) is uniquely given by the object membership structure, (O, ϵ).
(ϵ) ○‣ (≤) = (ϵ) = (≤) ○‣ (ϵ) (= (≤) ○‣ (ϵ) ○‣ (≤)).
A substructure of an S1_v structure is an S1_v structure.
Each of the sets R and R.↥ forms a substructure.
The set R forms a minimum substructure.

□

S1_ϵ as a special case of S1_v

Proposition A: For a structure (O, ϵ) the following are equivalent:

(O, ϵ) is an S1_ϵ structure satisfying (S1_ϵ~5⁺), i.e. O.ec ∖ {r.ec} is a down-set in ≤.
(O, ϵ) is an S1_v structure such that the following conditions are satisfied:
- (1) (S1_ϵ~5⁺).
- (2) Non-helix objects are bounded, i.e. for every object x, if R ⊆ x.↧.↥ then x ∈ R.↥.
  (Equivalently, using the notation introduced later, O = r.∍ ⊎ R.↥.)
- (3) The set r.ec.↥ ∖ {r.ec} of all strict ancestors of r.ec has a bottom, denoted c.
- (4) The set c.↧ ∖ {c} of all strict descendants of c has a top, necessarily equal to r.ec.
- (5) The set r.ec.↥ is linearly ordered in ≤. Equivalently, the set R.↥ of helix objects is linearly ordered in ≤.
- (6) The .class map is total over O – every object x has its class, x.class.
- (7) For every object x, x.ec.class = x.class.class.
- (8) The set O ∖ O.ec of primary objects is finite.

Proposition B: For a structure (O, ϵ) the following are equivalent:

(O, ϵ) is an S1_ϵ structure.
(O, ϵ) is an S1_v structure satisfying conditions (1)–(8) from the previous proposition except that (1) and (4) are replaced by (1') and (4') as follows:
- (1') The set O.ec ∖ R.↥ of non-helix eigenclasses is a down-set in ≤.
- (4') For every i ≥ 0, c.ec(i).↧ = {c.ec(i)} ⊎ r.ec(i+1).↧.

Rank

An object x is ϵ-ranked or just ranked if x.↧ ⊆ T.ϵ^∗ where ϵ^∗ denotes the reflexive transitive closure of ϵ. Equivalently, for every descendant y of x there exists an ϵ-chain

x₀ ϵ x₁ ϵ ⋯ ϵ x_n = y

such that x₀ is terminal. A set (or the whole structure) is ranked if its every object is ranked.

For a ranked object x we denote x.d the supremum of lengths n of ϵ-chains ending in x. (So that x.d equals ω if there is no greatest n.)

Proposition:

For a ranked object x, the following are satisfied:
- x.d = 0 iff x is terminal.
- x.d = ω iff x is not well-founded in ϵ.
For every ranked object x,
- x.d = sup(x.↧.mli).
If x is well-founded in ϵ then the rank of x equals the index of the highest meta-level that contains a descendant a of x.

Bounded and unbounded objects

We say that an object x is bounded if it is well-founded in ϵ, i.e. if there is no infinite chain of the form

⋯ ϵ x₂ ϵ x₁ ϵ x₀ = x.

Otherwise, x is unbounded.

Observations:

For an object x the following are equivalent:
1. x is bounded.
2. R ⊈ x.↧.↥.
3. Descendants of x only occur in finitely many meta-levels.
Bounded (resp. unbounded) objects form a down-set (resp. an up-set) in ≤.
For every object x, if x.ec is bounded then so is x. (But not necessarily vice versa, see example (ⅰ).)
Every object x such that x > x.ec(i) for some i > 0 is unbounded. (But not necessarily vice versa, see example (ⅱ).) In particular, if x ϵ x then x is unbounded.

The following are examples of S1_v structures. In example (ⅰ), the A class is the only bounded object.

(ⅰ)

(ⅱ)

In example (ⅱ), all object are unbounded.

∊: the well-founded restriction of ϵ

We denote ∊ the well-founded restriction of ϵ, i.e.

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

Similar notational conventions are used for ∊ as for ϵ. In particular, x.∍ denotes the set of all bounded members of x. (So that r.∍ is the set of all bounded objects.)

Proposition:

The union of ∊ and .ec is well-founded.
For every object x,
- x.ec.∍ = x.↧ ∩ r.∍.
For a ranked object x,
- x.d = sup {a.d + 1 | a ∊ x}.

∊-consistency

An object x is called ∊-A-consistent if it satisfies the following condition:


(A)	If x is non-terminal then it has non-empty ∊-preimage and all objects y with equal or larger ∊-preimage are ancestors of x, i.e. x.∍ ≠ ∅, and x.∍ ⊆ y.∍ implies x ≤ y for every object y (so that x.∍ ⊆ y.∍ iff x ≤ y).

An object x is called ∊-B-consistent if it satisfies the following condition:


(B)	If x is a class then there exist a, b from x.∍ such that the set a.↥ ∩ b.↥ ∩ x.϶ is empty, i.e. a, b are bounded instances of x that do not have a common ancestor among (all) instances of x.

An object x is called ∊-consistent if it is both ∊-A-consistent and ∊-B-consistent. A set X of objects is ∊-(A/B)-consistent if every object from X is ∊-(A/B)-consistent. The whole structure is said to be ∊-(A/B)-consistent if so are all objects.

Proposition:


(1)	For a non-terminal object x, the following are equivalent: x is ∊-A-consistent. x = ∨x.∍.ec (i.e. x is the least upper bound of the set { a.ec \| a ∊ x }).
(2)	For an S1_v structure the following are equivalent: Every object is ∊-A-consistent. The set O.ec ∩ r.∍ of bounded eigenclasses is join-dense in (O ∖ T, ≤).
(3)	Every ∊-A-consistent S1_v structure is ranked.

Proof:

(1)

Every object x is an upper bound of the set X = { a.ec | a ∊ x }. By definition, x is the least upper bound of X iff for every object y the following are equivalent:

a.ec ≤ y for every a ∊ x,
x ≤ y.

Since (a) is equivalent to x.∍ ⊆ y.∍, we obtain the equivalence x.∍ ⊆ y.∍ ↔ x ≤ y from the definition of ∊-A-consistency.

Moreover, x ≠ ∨∅ since otherwise x would be a lower bound of R, violating (S1_v~5). Thus if (ⅱ) holds then x.∍ ≠ ∅.

(3)

Let x be an object. Since ∊ is well-founded, there is a finite chain x₀ ∊ x₁ ∊ ⋯ ∊ x_n = x such that x₀.∍ is empty. Since x₀ is ∊-A-consistent it is necessarily terminal.

□

Examples of ∊-non-consistency

The diagrams below show examples of S1_v structures in which some objects (those marked with red color) are not ∊-consistent. In both examples, bounded objects are easily recognized as those that have no helical arrow pointing to them. (In (ⅰ), bounded objects are exactly those from eigenclass chains of terminals, i.e. the set T.pr⁻¹.)

The example (ⅰ) shows that ∊-A-consistency of all classes does not necessarily imply that all objects are ∊-A-consistent. We have

A.ec.∍ = { a.ec(i) | i > 0 },
B.∍ = A.ec.∍ ⊎ { b.ec(i) | i > 0 },

so that A.ec.∍ ⊆ B.∍. But A.ec ≰ B, therefore A.ec is not ∊-A-consistent. (The set of objects that are not ∊-A-consistent equals { A.ec(i) | i > 0 }.)

(ⅰ)

(ⅱ)

In example (ⅱ), all objects are ∊-A-consistent but not ∊-consistent since the M class is not ∊-B-consistent.

Freely attached objects

For objects x, p, we say x is freely attached to p if the following are satisfied:

(1) x is a primary object.
(2) p is a parent of x.ec. (I.e. p is a direct strict ancestor of x.ec. In particular, x ϵ p.)
(3) For every object y and every i ≥ 0,
- x.ec(i) < y iff p.ec(i) ≤ y.ec.
Equivalently, for every i ≥ 0,
- x.ec(i+1).↥ = {x.ec(i+1)} ⊎ p.ec(i).↥.

We say that an object x is freely attached if x is freely attached to p for some object p.

Observations:

An object can be freely attached to at most one object.
If x is freely attached to p then x is one meta-level lower than p.
If x is freely attached to a class p, then p = x.class.

In the following example, the F class is a leaf that is freely attached to the M class. Dashed brown arrows indicate the domain-restriction of inheritance (in the reflexive transitive reduction) to the eigenclass chain of F. This is in order to illustrate proposition (A) below.

The example also illustrates propositions (E) and (F). In the restricted structure, without the eigenclass chain of F, the M class is not ∊-(A-)consistent – because M.∍ = N.∍ = {A, B}. After a free attachment of F to M, the M class becomes ∊-consistent (but not so the N class).

Proposition:


(A)	Given an S1_v structure S = (O, ϵ) and an object p ∈ O, there exists an S1_v structure S' = (O', ϵ) and an object x such that S is a substructure of S', O'.pr = O.pr ⊎ {x}, x is a leaf that is freely attached to p.
(B)	In an S1_v structure with upper-finite inheritance, i.e. such that (0) every object has finite number of ancestors, the following conditions (ⅰ) and (ⅱ) are equivalent: (1) Every primary object is freely attached. (1) Every object has at most one parent. In particular, x.class is defined for every x. (2) For every object x, x.ec.class = x.class.class. (3) R = R.↥. Note that (0) & (ⅱ)(1) is equivalent to: (O ∖ T, ≤, r) is an algebraic tree [].
(C)	In an S1_v structure with upper-finite inheritance, (ⅰ) and (ⅱ) are equivalent: (1) Except for ancestors of r.ec, every primary object is freely attached. (2) Ancestors of r.ec are linearly ordered by ≤. (Thus, the helix R.↥ is linearly ordered.) (1) Every object has at most one parent. (2) For every object x, x.ec.class = x.class.class.
(D)	For an object x, the following are equivalent: x is freely attached to itself. x equals the inheritance root r and R = R.↥.
(E)	For every object p, each of the following conditions (a) or (b) is sufficient for p.ec(i) to be ∊-consistent for every i ≥ 0: (a) p has at least 2 bounded members that are freely attached to p. (b) p has at least 2 bounded members x, y such that x is freely attached to p and y ≰ x.
(F)	Let S = (O, ϵ), S' = (O', ϵ), x, p be like in (A), i.e. S' is obtained from S by a free attachment of x to p. Then for every object y from O the following holds: y is bounded in S iff y is bounded in S'. If y is ∊-consistent in S then so is in S'. Informally, the new freely attached object x (if it is not terminal), is the only new ∊-non-consistent object.

□

Creation of an ∊-consistent structure

Proposition: Every S1_v structure is a substructure an ∊-consistent S1_v structure.

Proof:
Let S = (O, .ec, ≤, r) be an S1_v structure. We systematically perform free attachments of new instances as follows.

For a meta-level of index i > 0 consider a (possibly empty) primorder algebra (X,.ec, .pr) and extensions of .class and ≤ such that the following are satisfied:
- X is disjoint from O. Elements of X.pr are new primary instances.
- X.pr.class equals the set of classes c on i-th meta-level such that for some j, c.ec(j) is not ∊-consistent.
- Every class c from X.pr.class has exactly
  - 2 new primary instances (i.e. c.class⁻¹ ∩ X.pr is a 2-element set) if for some j, c.ec(j).∍ is empty (in particular, if c.∍ is empty),
  - 1 new primary instance otherwise.
  Of course, we can be less parsimonious and require 2 new primary instances for all classes from X.pr.class.
- Extend the inheritance to X according to the definition of a freely attached object, i.e. for every x from X.pr, every y from O, and every j ≥ 0,
  - y ≰ x.ec(j) and
  - x.ec(j) < y iff x.class.ec(j) ≤ y.ec.
Then in the structure T = (O ⊎ X, .ec, ≤, r), all classes from the i-th meta-level are ∊-consistent. In addition, all ∊-consistent objects in S are ∊-consistent in T.
For i > 0, the set O ∖ r.ec(i).↧ is made ∊-consistent by subsequently making each of its meta-levels ∊-consistent in the descending order i, i - 1, … 1 of their meta-level index. This way we can construct a sequence S = S₀, S₁, … of S1_v structures such that for each i ≥ 0,
- S_i is a substructure of S_i+1, and
- in S_i, the set O ∖ r.ec(i).↧ is ∊-consistent.
The final ∊-consistent structure is made by joining the structures S₀, S₁, … from the previous step. □

Eigenclass frame

We say that a non-empty set V is an eigenclass frame if it equals the (ω + 1)-st powerset cumulation of its urelement base, i.e. there exists a (necessarily unique) set U such that the following are satisfied:


(1)	V = ℙ_⋆^ω+1(U).
(2)	Elements of U are minimal in (V, ∈).
(3)	Elements of U are minimal in (V, ⊆).

Observations:

The set U is uniquely determined by U = { x ∈ V | x ∩ V = ∅ }.
The set U forms an antichain in ⊆.
∅ ∈ V if and only if U = {∅}.

Given an eigenclass frame V, we introduce the following notation and terminology.

We fix the U notation and call elements of U urelements. They are urelements with respect to the eigenclass frame V. In particular U is the set of atoms in (V, ∈). (The set-theoretic structure of urelements does not interfere with V.)
We also introduce shorthand notation V_i for the sets ℙ_⋆ⁱ(U). Therefore,
- V₀ = U,
- V_i = V_i-1 ∪ (ℙ(V_i-1) ∖ {∅}) for 0 < i < ω,
- V_ω = ∪{ V_i | i < ω } (= r),
- V_ω+1 = V.
For 0 ≤ i ≤ ω, the set V_i is the i-th stage.
The ω-th stage is also denoted r and called the inheritance root, so that
- r = ℙ_⋆^ω(U).
This in particular means that V is given by r as its powerset cumulation, i.e. V = ℙ_⋆(r) (= r ∪ (ℙ(r) ∖ {∅})).
The eigenclass map is a map .ec: V → V defined as an adaptation of the powerset operator to the eigenclass frame. For every x ∈ V,
- x.ec = ℙ(x) ∩ r.
For an x from V, the rank (alternatively, depth), denoted x.d, is defined as follows:
- If x ∈ r then x.d equals the smallest natural i such that x ∈ V_i.
- If x ∉ r then x.d equals ω.

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 u is another notation for the set U of urelements, then expressions U.ec and u.ec are interpreted differently:

U.ec = { x.ec | x ∈ U } = { {x} | x ∈ U } ,
u.ec = ℙ(U) ∖ {∅} .

Empty set as an urelement

The particular case U = {∅} requires an adjustment, ⊆', of set inclusion on V that disallows the urelement to be a strict subset of any other element: for every x, y in V,

x ⊆' y iff x ⊆ y and if x = ∅ then x = y.

To simplify the treatment, we disallow the empty set to be an urelement, i.e. we further assume:


(4)	∅ ∉ V.

Basic properties

Proposition:

The structure (V, .ec, ⊆, r) is an S1_v structure. In particular,
- x ϵ y iff the eigenclass of x is a subset of y.
Established notation and terminology applies with following adjustments:
- We usually refer to elements of V as elements rather than objects.
- The notational conflict for .d is resolved in favor of the definition in this section. (So that x.d is defined for every x from V.)
- As a consequence, we prefer the term ϵ-ranked over ranked.
For an element x ∈ V, the following are equivalent:
1. x is bounded.
2. x ∈ r.
3. x has finite rank.
For an element x ∈ V, the following are equivalent:
1. x is an eigenclass.
2. x is a non-empty join-closed ideal in (r, ⊆), i.e. x is a non-empty subset of r such that for every a, b, y,
  - if a ⊆ b ∈ x then a ∈ x (i.e. x is a down-set in (r, ⊆)),
  - if a ∈ x and b ∈ x then a ∪ b ∈ x (i.e. x is closed w.r.t. existing binary joins in (r, ⊆)),
  - so that x is an ideal in (r, ⊆), in particular, x is an up-directed set in (r, ⊆),
  - if y ⊆ x and ∪y ∈ r then ∪y ∈ x (i.e. x is closed w.r.t. all existing joins in (r, ⊆)).
Condition (b)(ⅲ) can be simplified to: if x ∈ r then ∪x ∈ x.
The set r of bounded elements is join-dense in (V, ⊆). As a consequence, for every x from V,
- x.ec = ∪{ a.ec | a ∈ x.ec} .
The eigenclass map, .ec, satisfies the following properties:

x.ec = {x} if x.pr is an urelement,

x.ec = ℙ(x) ∖ {∅} iff x ∈ r,

x.ec ⊂ x iff x ϵ x.
The inverse of the eigenclass map, .ce, is given by set union, i.e. for every x ∈ V.ec,
- x.ce = ∪x.
r = U ⊎ r.ec. (But for i > 0, r ≠ V_i ⊎ r.ec(i+1).)
For the rank function .d, the following recursive formula holds:
- x.d = sup { a.d + 1 | a ∈ x ∩ V }.
In particular, for an urelement x, x.d = sup(∅) = 0.
For every x ∈ V ∖ U, if y = ∪x then
- y.d = sup { a.d | a ∈ x }.
For every x from V, the meta-level index of x is the length n of the shortest ∈-chain
- x₀ ∈ x₁ ∈ ⋯ ∈ x_n = x
such that x₀ is an urelement. Equivalently, x.mli equals the smallest i such that x ∩ r.ec(i) is empty.

□

Strata

For x, y from V, x is a stratum of y if x is a maximum subset of y such that all elements of x ∩ V have the same rank. Equivalently,
- if y ∈ U then y itself equals its only stratum,
- if y ∉ U then x is a stratum of y if there exists natural d such that x = { a ∈ y | a.d = d }.
  (Necessarily, x.d = d+1.)
For x ∈ V, we denote x.ϱ, the bottom stratum of x, which is the stratum of x with minimum rank, i.e.
- if x ∈ U then x.ϱ = x,
- if x ∉ U then x.ϱ = {a ∈ x | a.d = d } where d = min { a.d | a ∈ x }.

Observations:

The bottom stratum of r is U. Other strata of r are of the form V_i+1 ∖ V_i, 0 < i < ω.
For an element x from V ∖ U, a stratum of x is a non-empty intersection of x with a stratum of r.
The eigenclass map commutes with the bottom stratum map, i.e. for every x ∈ V,
The eigenclass map preserves the (possibly infinite) number of strata.
For every element x, the meta-level of x is less than or equal to the rank of the bottom stratum of x, i.e.

Object system

We say that a set O is an object system if there is an eigenclass frame V such that

(1) O ⊆ V,
(2) r ∈ O,
(3) O.ec = V.ec ∩ O.

Equivalently, O forms a substructure of the S1_v structure induced by the eigenclass frame V.

The following table shows the correspondence between some expressions for the S1_v structure (O, .ec, ⊆, r).

Terminology	Abstract expression	Set expression
Inheritance	(O, ≤)	(O, ⊆)
Inheritance root	r	O ∩ ∪O
Eigenclass of x	x.ec	ℙ(x) ∩ r
Set of descendants of x	x.↧	ℙ(x) ∩ O (= x.ec ∩ O)

Embedding sequence

Let S = (O, ϵ) be an ∊-consistent S1_v structure and V an eigenclass frame. We say that a sequence

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

of maps from O to V is an embedding sequence (w.r.t. S and V) if the following are satisfied:

The restriction of .ν₀ to terminals is a bijection between T and U.
The restriction of .ν₀ to the set O ∖ T of non-terminal objects x is defined by well-founded recursion, using well-foundedness of ∊, by
- x.ν₀ = ∪{ a.ν₀.ec | a ∊ x }.
For every natural i,
- x.ν_i+1 = x.ν₀ if x is terminal,
- x.ν_i+1 = ∪{ a.ν_i.ec | a ϵ x }.
The last map, .ν, is defined as the limit of the previous ones, i.e.
- x.ν = ∪{ x.ν_i | i < ω }.

Note the use of ∊ / ϵ in the definition of x.ν₀ / x.ν_i+1, respectively.

The embedding theorem

Proposition: An embedding sequence (using notation from the previous subsection) satisfies the following embedding properties:


(A)	The .ν_i map is an isomorphism between (O, ∊, ≤) and (O.ν_i, ∈, ⊆), for every i ≤ ω.
(B)	The .ν map is an isomorphism between primorder algebras (O, .ec, .pr) and (O.ν, .ec, .pr).
(C)	The inheritance roots correspond, i.e. r.ν = V_ω. As a consequence, O.ν is an object system whose S1_v structure is isomorphic to S via .ν.

Corollary: There is one-to-one correspondence between object systems and S1_v structures.

Proof:

(A)

We first show that for every objects x, y from O,

(a) x.d = x.ν₀.d,
(b) x ∊ y iff x.ν₀ ∈ y.ν₀,
(c) x ≤ y iff x.ν₀ ⊆ y.ν₀.

The (a) equality is shown by well-founded induction on (O, ∊). For every a ∊ x we have

a.d < x.d (by definition of .d in O),
a.ν₀.d = a.d (by the induction assumption),
a.ν₀.d < ω (since x.d ≤ ω),
a.ν₀.ec.d = a.ν₀.d + 1 (a consequence).

Therefore,

x.ν₀.d = sup { a.ν₀.ec.d | a ∊ x } = sup { a.d + 1 | a ∊ x } = x.d .

In the (b) equivalence, the implication x ∊ y → x.ν₀ ∈ y.ν₀ is shown as follows. Since x.d < ω then (by (a)) x.ν₀.d < ω. Therefore, x.ν₀ ∈ x.ν₀.ec ⊆ y.ν₀.

The opposite implication in (b) is shown by well-founded induction on (O.ν₀, ∈). Let x.ν₀ ∈ y.ν₀. By definition of y.ν₀, there exists an object b such that b ∊ y and x.ν₀ ∈ b.ν₀.ec. We obtain

x.ν₀ ⊆ b.ν₀ ∈ y.ν₀ (by definition of .ec),
x.∍ ⊆ b.∍ (by induction assumption for x and b),
x ≤ b (by ∊-A-consistency),
x ∊ y (since x ≤ b ∊ y).

If x is a terminal object then (c) is trivially satisfied. Otherwise, (c) is proved by

x ≤ y iff x.∍ ⊆ y.∍ iff x.ν₀ ∩ O.ν₀ ⊆ y.ν₀ ∩ O.ν₀ iff x.ν₀ ⊆ y.ν₀.

We observe now that all the maps .ν_i coincide in the restriction to r.∍, i.e. for every i ≤ ω,

(d) x.ν = x.ν_i = x.ν₀ for every bounded x.

Next we show that for every objects x, y from O, and every i, j < ω the following are satisfied:

(e) x ∊ y iff x.ν_i ∈ y.ν_i,
(f) x ≤ y iff x.ν_i ⊆ y.ν_i,
(g) x.ν_i ⊆ x.ν_i+1 (equivalently, i ≤ j iff x.ν_i ⊆ x.ν_j).

The (e) equivalence is shown similarly as (b). For x ∊ y and i > 0 we have x.ν₀ = x.ν_i = x.ν_i-1 ∈ x.ν_i-1.ec ⊆ y.ν_i. The opposite implication, x ∊ y ← x.ν_i ∈ y.ν_i, follows by induction over i. Let x.ν_i ∈ y.ν_i and i > 0. By definition of y.ν_i, there exists an object b such that b ϵ y and x.ν₀ = x.ν_i = x.ν_i-1 ∈ b.ν_i-1.ec. Consequently,

x.ν_i-1 ⊆ b.ν_i-1 (by definition of .ec),
x.∍ ⊆ b.∍ (by induction assumption for x and b),
x ≤ b (by ∊-A-consistency),
x ∊ y (since x ≤ b ϵ y and x is bounded).

In (f), the implication x ≤ y → x.ν_i ⊆ y.ν_i, follows from the definition of .ν_i using (ϵ) ○‣ (≤) = (ϵ). The opposite implication is proved by

x.ν_i ⊆ y.ν_i → x.ν_i ∩ r.∍.ν₀ ⊆ y.ν_i ∩ r.∍.ν₀ ↔ x.∍ ⊆ y.∍ ↔ x ≤ y.

The (g) inclusion is proved by induction over i. The case i = 0 follows by definition of .ν₀ and .ν₁ (using the fact that ∊ is a restriction of ϵ). For i > 0 we apply the induction assumption:

x.ν_i+1 = ∪{ a.ν_i.ec | a ϵ x } ⊇ ∪{ a.ν_i-1.ec | a ϵ x } = x.ν_i.

It is easily seen that (e) and (f) also hold for .ν_i = .ν, therefore (A) is satisfied: .ν_i is an isomorphism between (O, ∊, ≤) and (O.ν_i, ∈, ⊆) for every i ≤ ω.

(B)

We show that for every object x and every natural i,

(h) x.ν ∩ V_i ⊆ x.ν_i,
(i) x.ec.ν_i+1 = x.ν_i.ec.

The (h) inclusion is proved by induction over i. If u is from x.ν ∩ U then u = a.ν = a.ν₀ for some terminal a such that a ∊ x. Therefore a.ν ∈ x.ν₀. This solves the case i = 0. For i > 0 we show that

x.ν_j+1 ∩ V_i ⊆ x.ν_i for every j ≥ 0:

x.ν_j+1 ∩ V_i	= ∪{ a.ν_j.ec \| a ϵ x } ∩ V_i
	= ∪{ a.ν_j.ec ∩ V_i \| a ϵ x } (by infinite distributivity of set inclusion)
	= ∪{ ℙ(a.ν_j ∩ V_i-1) ∩ r \| a ϵ x } (by definition of .ec)
	⊆ ∪{ a.ν_i-1.ec \| a ϵ x } (by the induction assumption)
	= x.ν_i.

The (i) equality is shown by

x.ec.ν_i+1	= ∪{ a.ν_i.ec \| a ϵ x.ec }
	= ∪{ a.ν_i.ec \| a ≤ x }
	= x.ν_i.ec (since a ≤ x implies a.ν_i ⊆ x.ν_i and thus a.ν_i.ec ⊆ x.ν_i.ec).

As a consequence, we obtain the commutativity of .ν and .ec:

x.ec.ν = ∪{ x.ec.ν_i | i < ω } = ∪{ x.ν_i.ec | i < ω } = x.ν.ec. (The last equality uses (h).)

To complete (B), it remains to show that O.pr.ν ⊆ V.pr, i.e. that .ν preserves primary objects. Equivalently, if x is a class then x.ν ∉ V.ec. Suppose the contrary, i.e. x is a class such that x.ν is an eigenclass in V. Due to ∊-B-consistency, there are a, b from x.∍ such that a.↥ ∩ b.↥ ∩ x.϶ is empty. We have

a.ν ∪ b.ν ∈ x.ν (since x.ν is up-directed w.r.t. ⊆),
a.ν ∪ b.ν ⊆ c.ν for some c ϵ x (by definition of x.ν),
a ≤ c and b ≤ c (by the (O, ≤) ↔ (O.ν, ⊆) correspondence).

Therefore, c belongs to a.↥ ∩ b.↥ ∩ x.϶, a contradiction.

(C)

We show that for every object x and every natural i,

if x ϵ x then
- (j) x.ν_i.ec ⊆ x.ν_i+1,
- (k) ℙ_⋆ⁱ(x.ν₀) ∩ V_ω ⊆ x.ν_i.

The (j) inclusion follows directly from the definition of x.ν_i+1. The (k) inclusion is shown by induction on i. If i = 0 then equality holds because ℙ_⋆⁰ is identity. For i > 0 we have

ℙ_⋆ⁱ⁺¹(x.ν₀) ∩ V_ω	= (ℙ_⋆ⁱ(x.ν₀) ∪ ℙ(ℙ_⋆ⁱ(x.ν₀)) ∩ V_ω
	⊆ x.ν_i ∪ x.ν_i.ec (by the induction assumption)
	⊆ x.ν_i ∪ x.ν_i+1 (by (j))
	= x.ν_i+1 (by (g)).

As a consequence, we obtain ℙ_⋆^ω(x.ν₀) ∩ V_ω ⊆ x.ν for every object x such that x ϵ x. For x = r we have U ⊆ x.ν, so that

V_ω = ℙ_⋆^ω(U) ⊆ ℙ_⋆^ω(r.ν) ∩ V_ω ⊆ r.ν ⊆ V_ω,

which shows that r.ν = V_ω. □

References


	C. C. Chang, H. Jerome Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics (3rd ed.), Elsevier, 1990,
	B.A. Davey, H.A. Priestley, Introduction to lattices and order, Cambridge University Press 2002
	Ondřej Pavlata, Object Membership: The core structure of object-oriented programming, 2012, http://www.atalon.cz/om/object-membership/
	Ondřej Pavlata, The Ruby Object Model: Data Structure in Detail, 2012, http://www.atalon.cz/rb-om/ruby-object-model Algebraic tree

Document history

January

2013

The initial release.

License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

x.ec = {x}	if x.pr is an urelement,
x.ec = ℙ(x) ∖ {∅}	iff x ∈ r,
x.ec ⊂ x	iff x ϵ x.

Object Membership

Set theoretic representation

Preface

Author

Document date

Warning

Table of contents

Preliminaries

Ordinal numbers up to ω + 1

Powerset cumulation

Well-foundedness

Primorder algebra

Terminological conventions

S1v: The essential structure of object membership

S1ϵ as a special case of S1v

Rank

Bounded and unbounded objects

∊: the well-founded restriction of ϵ

∊-consistency

Examples of ∊-non-consistency

Freely attached objects

Creation of an ∊-consistent structure

Eigenclass frame

Empty set as an urelement

Basic properties

Strata

Object system

Embedding sequence

The embedding theorem

References

Document history

License

S1_v: The essential structure of object membership

S1_ϵ as a special case of S1_v