Prove that the two properties of the hierarchy function $($see Section $5\mathrm{.}2\mathrm{.}3)$ allow only trees and single nodes as organizations of objects.

Section $5\mathrm{.}2\mathrm{.}3$ is as following:

Let S be the set of subjects of a system and let O be the set of objects. Let P be the set of rights r for read, a for write, w for read$/$write$,$ and e for empty$\mathrm{.}3$ Let M be a set of possible access control matrices for the system. Let C be the set of classifications $($or clearances$),$ let K be the set of categories, and let L $=$ C $\backslash$times K be the set of security levels. Finally, let F be the set of $3-$tuples $($fs$,$ fo$,$ fc$),$ where fs and fc associate with each subject maximum and current security levels, respectively, and fo associates with each object a security level. The relation dom from Definition $51$ is defined here in the obvious way.

$3$The right called $$empty$$ here is called $$execute$$ in Bell and LaPadula $[150].$ However, they define $$execute$$ as $$neither observation nor alteration$($and note that it differs from the notion of $$execute$$ that most systems implement$).$ For clarity, we changed the e right$$s name to the more descriptive $$empty$.$

The system objects may be organized as a set of hierarchies $($trees and single nodes$).$ Let H represent the set of hierarchy functions h : O $->$ P$($O$)\mathrm{.}4$ These functions have two properties. Let oi$,$ oj$,$ ok in O$.$ Then:

$4$P$($O$)$ is the power set of O$$that is$,$ the set of all possible subsets of O$.$

If oi $!=$ oj$,$ then h$($oi$)\backslash$cap h$($oj$)=.$

There is no set $\{$o$1,$ o$2,...,$ ok$\}$ O such that oi$+1$ in h$($oi$)$ for each i $=1,...,$ k$,$ and ok$+1=$ o$1.$

$($See Exercise $5.)$

A state v in V of a system is a $4-$tuple $($b$,$ m$,$ f$,$ h$),$ where b in P$($S $\backslash$times O $\backslash$times P$)$ indicates which subjects have access to which objects, and what those access rights are; m in M is the access control matrix for the current state; f in F is the $3-$tuple indicating the current subject and object clearances and categories; and h in H is the hierarchy of objects for the current state. The difference between b and m is that the rights in m may be unusable because of differences in security levels; b contains the set of rights that may be exercised, and m contains the set of discretionary rights.

R denotes the set of requests for access. The form of the requests affects the instantiation, not the formal model, and is not discussed further here. Four outcomes of each request are possible: y for yes $($allowed$),$ n for no $($not allowed$),$ i for illegal request, and o for error $($multiple outcomes are possible$).$ D denotes the set of outcomes. The set W $$ R $\backslash$times D $\backslash$times V $\backslash$times V is the set of actions of the system. This notation means that an entity issues a request in R$,$ and a decision in D occurs, moving the system from one state in V to another $($possibly different$)$ state in V$.$ Given these definitions, we can now define the history of a system as it executes.

Let N be the set of positive integers. These integers represent times. Let X $=$ RN be a set whose elements x are sequences of requests, let Y $=$ DN be a set whose elements y are sequences of decisions, and let Z $=$ VN be a set whose elements z are sequences of states. The ith components of x$,$ y$,$ and z are represented as xi$,$ yi$,$ and zi$,$ respectively. The interpretation is that for some t in N$,$ the system is in state zt $1$ in V; a subject makes request xt in R$,$ the system makes a decision yt in D$,$ and as a result the system transitions into a $($possibly new$)$ state zt in V$.$

A system is represented as an initial state and a sequence of requests, decisions, and states. In formal terms, $\backslash$Sigma $($R$,$ D$,$ W$,$ z$0)$ X $\backslash$times Y $\backslash$times Z represents the system, and z$0$ is the initial state of the system. $($x$,$ y$,$ z$)$ in $\backslash$Sigma $($R$,$ D$,$ W$,$ z$0)$ if and only if $($xt$,$ yt$,$ zt$,$ zt$1)$ in W for all t in N$.($x$,$ y$,$ z$)$ is an appearance of $\backslash$Sigma $($R$,$ D$,$ W$,$ z$0).$