Entropy structures

It is the approach and practice of Formal Methods to describe any part of Cyberspace mathematically (popular model-based formalisms consistent with our treatment here are given by Z [16] and VDM [10]). Here we adopt that approach to conceptualise the part of Cyberspace in which we are interested, at a particular time, as an object (or module, or abstract data type) having a set of precisely-defined states operated on by a family of mathematically specified actions (or methods or operations). Examples are provided in section 5.

Let $X$ denote the set of states -- the state space -- of the system under consideration. It could be one small component, like an editor, on a specific machine with the actions it offers the user, or a network with many terminals and filestores connected to the internet and all its attendant actions. In the extreme case, it is the whole of Cyberspace. We now introduce the notion of entropy structure on $X$. The elements in the definition are routine (see, for example, [3]).

We use the following notation. The symbol $\ =_{\textit{\tiny def}}\ \$ means 'equals by definition'. All variables of each predicate are assigned a type and quantification is over the appropriate type. The predicate

$$\forall x : X \spot P$$

is read for all x in X, P holds. Thus the symbol $\spot$ is used to separate the typed quantifiers from the body of the predicate. We write

$$P \implies Q$$

for the predicate P implies Q and

$$X \fun Y$$

for the space of all functions from $X$ to $Y$. Otherwise our notation is standard.

A relation $A$ on $X$ is a subset of the Cartesian product of $X$ with itself

$$A \subseteq X \times X .$$

Membership of an ordered pair to relation $A$

$$(x,x') \in A$$

is read A relates x to x' and written in infix:

$$x~A~x' .$$

The converse $A^{\sim}$ of a relation $A$ on $X$ is its 'mirror image'

$$x ~A^{\sim}~ x' \ =_{\textit{\tiny def}}\ \ x'~A~x .$$

A pre-order on $X$ consists of a relation $\leq$ on $X$ which is reflexive (i.e. includes the identity relation) and transitive (i.e. closed under sequential composition):

$$\forall x : X \spot x \leq x \\ \forall x,y,z : X \spot (x \leq y) \land (y \leq z) \implies x \leq z .$$

A pre-order $\leq$ is total iff any two elements of $X$ are related by either $\leq$ or its converse

$$\forall x,x' : X \spot x \leq x'\ \vee\ x' \leq x .$$

The equivalence relation $\sim$ of a pre-order $\leq$ is the relation on $X$ equal to the intersection of $\leq$ and its converse

$$x \sim x' \ =_{\textit{\tiny def}}\ \ (x \leq x') \land (x' \leq x) .$$

To be an equivalence relation means that it is not only a pre-order on $X$, but also symmetric (i.e. contained in its converse):

$$\forall x,x' : X \spot x \sim x' \implies x' \sim x.$$

The $\sim$-equivalence class of $x:X$ consists of all elements of $X$ equivalent to $x$

$$x^\sim \ =_{\textit{\tiny def}}\ \ \{y:X \mid x \sim y \} .$$

The definition of pre-order is sufficient to ensure that the equivalence classes of elements of $X$ partition $X$:

$$\begin{array}[t]{l} \cup \{ x^\sim \mid x \in X \} = X \\ [1... ...m \neq \{\,\} \ \ \ \implies\ \ x^\sim = y^\sim . \end{array}$$

Furthermore the pre-order $\leq$ is well-defined on equivalence classes: the relation, again called $\leq$, which is defined on equivalence classes if the original pre-order holds between representative elements of those classes

$$x^\sim \leq y^\sim \ =_{\textit{\tiny def}}\ \ x \leq y$$

is well-defined (i.e. does not depend on the representatives), is again a pre-order, and in addition is antisymmetric:

$$\forall x,y : X \spot x \leq y \land y \leq x \implies x \sim y .$$

In other words $\leq$ becomes a partial order on $\sim$-equivalence classes.
An important way to define a pre-order $\leq$ on $X$ is to define a level function $\lambda$ from $X$ to the real numbers, $\lambda : X \fun {\mathbb{R}}$, and then to define the derived pre-order $\leq_{\lambda}$ by setting

$$x \leq_{\lambda} x' \ =_{\textit{\tiny def}}\ \ \lambda (x) \leq_{\mathbb{R}} \lambda (x')$$ (1)

where the order $\leq_{\mathbb{R}}$ denotes the standard (total) ordering between real numbers. Pre-orders so defined are automatically total partial orders, by properties of $\leq_{\mathbb{R}}$. In fact, because Cyberspace is discrete by choice of an appropriate encoding, we can always ensure that $\mathbb{R}$ there is replaced by the natural numbers $\mathbb{N}$ whose ordering $\leq_{\mathbb{N}}$ is a restriction of $\leq_{\mathbb{R}}$. But use of $\mathbb{R}$ permits us the flexibility of considering also 'continuous' examples from the 'real' world.

By an entropy structure we mean a triple $(X,\leq,\sim)$ consisting of a set $X$, a pre-order $\leq$ on $X$ and the equivalence relation $\sim$ of $\leq$.

It is worth emphasising that the definitions of the ingredients of an entropy structure can be couched in whatever mathematical notions are convenient. Typically, level functions and pre-orders are expressed using concepts perceived only from 'outside' the system under consideration. That ought not to be surprising: whilst the subsystem of Cyberspace must be self-contained its description is a meta-activity.