Tag Archives: trees (math)

The n+2 Management Policy

I think this is a decent way to operate in a hierarchy–particularly when it comes to big decisions like hiring/firing/approving new policies.  We first assume the hierarchy is a tree (i.e. each member has only one immediate supervisor) and that there is a maximal element, called an “administrator”.  The setup is that if something happens at level n in the hierarchy (say hiring/firing someone at level n (presuming the action is consistent with other policy)), then the relevant supervisor makes the nomination/recommendation for the action, and his/her supervisor confirms the action.

Hence let H be a tree, x\in H, and S(x) denote the supervisor of x.  Typically in trees, minimal elements are considered level 0.  Here we reverse the ordering and call the maximal element the administrator, denoted by A, and say \mbox{rank}(A)=M.  We define a rank n policy as a policy that affects all successors (subordinates) of an element x\in H such that \mbox{rank}(x)=n.  Hence we have:

The n+2 Operational Policy.  Let P be a rank n policy and x_P denote the member whose subordinates are affected.  The policy then becomes activated provided S(x_P) proposes it and S(S(x_P)) approves it.

Hence the n+2 Operational Policy itself is a rank M policy as it affects everything in the hierarchy.  But we arrive at a problem in continuing to execute this policy at levels M-1 and M.  So we adjoin another set to the hierarchy called the board, denoted B, and redefine our hierarchy as H=T\sqcup B where T denotes the initial tree with unique maximal element A. We then define S(A)=B and S(B)=B.

The main positive of this method is the minimizing of micromanagement.  The only big negative that stands out is the possibility of actions diverging from intentions of a level n member as one goes down the ladder.  But I’d argue that this just means more level n policy needs to be implemented in order to prevent that.

The Calculus Tree

We first start with a tree structure on P, the set of real coefficient polynomials with domain and codomain \mathbb{R}, and call it the polynomial tree.  We will say f\preceq g iff g^{(n)}=\frac{d^ng}{dx^n}=f for some n\in\mathbb{N}.

Proposition 1.  This gives us a partial order on P.

Proof.  f\preceq f since f^{(0)}=f.  If f\preceq g and g\preceq h, then g^{(n)}=f and h^{(m)}=g, thus h^{(n+m)}=f; so f\preceq h.  And lastly if f\preceq g and g\preceq f, then g^{(n)}=f and f^{(m)}=g.  Thus f^{(m+n)}=f which implies m+n=0 and thus m=n=0, so f=g.

The fact that differentiation yields a unique function gives us the tree structure:  the chain of derivatives (predecessors) is well ordered with minimal element 0.  By the Weierstrass approximation theorem we can attempt to extend this to C_0^\infty(\mathbb{R}) the closure of the class of smooth functions with compact support.  We extend our indexing set to the ordinal \omega+2 and define the \omegath (and (\omega+1)th) derivative linearly by the rule

\displaystyle \frac{d^\omega }{dx^\omega}\left(\frac{x^\omega}{\omega!}\right)=1

\displaystyle \frac{d^{\omega+1}f}{dx^{\omega+1}}=\frac{d}{dx}\left(\frac{d^{\omega}f}{dx^\omega}\right)=0.

Recall integration is a set valued operation–sending a function to its set of antiderivatives which all differ by some constant.

Example 2.  Let f(x)=e^x.  We have

\displaystyle e^x=\sum_{n=0}^\infty\frac{x^n}{n!}.

Hence f^{(n)}=f for finite n, f^{(\omega)}=1 since the “last term” is x^\omega/\omega!, and f^{(\omega+1)}=0.  If we begin to integrate, we will add polynomials trailing after e^x.  Continuing this denumerably we then obtain

\displaystyle e^x\stackrel{\int\cdot\,dx^\omega}{\longmapsto}e^x+\sum_{n=1}^\infty c_m\frac{x^n}{n!}

where m=co(n) is the conumber of n in the sense that it satisfies N=n+m in the nth term of the Nth partial sum.  The denumerable integration converges if the sequence of constants chosen satisfies

\displaystyle\lim_{n\to\infty}\left|\frac{c_{m+1}}{(n+1)c_m}\right|=\lim_{m\to 1}\left|\frac{c_{m+1}}{(n+1)c_m}\right|<1.

Suppose the sequence c=(c_1,c_2,...) satisfies this condition and let us assume the sum converges to some f, then we can write

\displaystyle\int e^x\,dx^\omega=_ce^x+f=\sum_{n=0}^\infty\frac{x^n}{n!}+\sum_{n=1}^\infty c_m\frac{x^n}{n!}=1+\sum_{n=1}^\infty\left(\frac{c_m+1}{n!}\right)x^n.

In particular we thus have (e^x+f)^{(\omega)}=c_1+1 since

1=\lim_{n\to\infty} co(n):=co(\omega).

We thus have 0\preceq e^x, 0\preceq f, 0\preceq e^x+f, and 0\preceq e^xf.  We also define the degree of the functions which are not polynomials as \omega.  Let p be a polynomial with degree n and f have infinite degree.  Then we clearly have that fp and f+p have degree \omega.

Definition 3.  A function f is cyclic if f^{(n)}=f for some nonzero finite number n.  The number n is called the differential order of f, and is denoted ord(f).  If a function is not cyclic we say ord(f)=\infty (note in this definition \omega\neq\infty).

Example 4.  The functions e^x,\pm\sin(x), and \pm\cos(x) are cyclic with orders 1,4, and 4 respectively.  The only function with finite degree which is cyclic is 0 with order 1.

In fact being cyclic occurs iff

\begin{array}{lcl}f^{(n)}-f=0&\Leftrightarrow&(D^n-1)f=0\\&\Leftrightarrow&(D-1)(D^{n-1}+D^{n-2}+\cdots+1)f=0\\&\Leftarrow&(D-\zeta_n^k)f=0\end{array}

for at least some k where \zeta_n=e^{2\pi i/n} and 1\leq k\leq n.  Thus we have

\displaystyle f(x)=\sum_ic_ie^{\zeta_n^kx}.

With this presentation it is clear that the order of the ith term in the above term is n if \gcd(k,n)\neq 1.  Otherwise the order is \gcd(k,n).

Let us now define the equivalence relation where f\sim g iff f and g are cyclic with same order and where f^{(k)}=g such that k\leq ord(f)=ord(g).  Reflexivity is clear, and symmetry/transitivity involve simple \mbox{mod~}ord(f) arithmetic.

Example 5.  Hence some equivalence classes are \{\sin(x),\cos(x),-\sin(x),-\cos(x)\}, \{e^x\}, and \{p\} for any polynomial p.

Proposition 6\preceq gives a tree structure on C_0^\infty(\mathbb{R})/\sim, which we call the calculus tree.

Proof.  This is trivial considering the relation we modded out by was precisely loops in the poset–together with the fact that the poset has a unique minimal element.

Also see update.

Suslin Trees

Definition 1.  A tree is a strict poset (T,<) such that set P(x)=\{t:t<x\} of predecessors of x is well-ordered for all x\in T.

This motivates the notion of a root.  We can define the root of x as r(x)=\min\{P(x)\}.  In particular we can say an element r\in T is a root if it is the root of some element.  We define the height of x as h(x)=ord(P(x)), where ord(X) is the order-type (or ordinality) of X.  The ordinality of a toset (totally ordered set) X is the unique ordinal number to which X is isomorphic (as tosets).

Note that ord(X)\geq |X|.  For example |\omega|=|\omega+1|=\aleph_0.  But ord(\omega)\neq ord(\omega+1) since in the bijection f:\omega+1\to\omega defined by f(\omega)=0 and f(n)=n+1 for finite ordinals, we have 0\leq\omega, but f(0)=1\not\leq 0=f(\omega).

Correspondingly we define the height of T to be h(T)=\sup_{x\in T}\{h(x)\}.  An \alphatree is a tree of height \alpha.  We also define the \alphath level of a tree T as the set L_\alpha=\{x\in T:h(x)=\alpha\}.

Definition 2.  A branch in T is a maximal toset/chain in T.  That is, it is not properly contained within any chain in T.

Definition 3.  A tree T is normal if

  1. T has a unique root;
  2. each level of T is countable;
  3. if x\in L_\alpha is not maximal, then it has infinitely many successors in L_{\alpha+1};
  4. all branches have the same height;
  5. if \alpha<h(T) is a limit ordinal and x,y\in L_\alpha such that P(x)=P(y), then x=y.

Note that tosets can be endowed with a topology called an order topology.  It is generated by predecessor and successor sets.  A poset X is dense if for any comparable x,y\in X, there is a z\in X such that x<z<y.  A toset X is complete if every bounded subset has an infimum and supremum.  A toset satisfies the countable chain condition if every collection of disjoint open rays (predecessor/successor sets) is countable.

Suslin’s Problem.  Let X be a dense, complete, and unbounded toset that satisfies the countable chain condition.  Is X isomorphic to \mathbb{R}?

Note that \mathbb{R} is the unique toset which is dense, complete, unbounded and separable (has a countable dense subset).  The separability of \mathbb{R} implies that it satisfies the countable chain condition.  Since any interval in \mathbb{R} has a rational number (from denseness), then any collection of disjoint open rays must be countable.  Hence Suslin’s Problem asks if the converse is true on tosets that are dense, complete, and unbounded.  This is not provable in ZFC, ZFC+CH, ZFC+GCH, or ZFC+\lnotCH.

Definition 4.  A Suslin line is a dense, complete, and unbounded toset that satisfies the countable chain condition but is not separable.

Hence Suslin’s Problem asks whether or not a Suslin line exists.  This turns out to be equivalent to the existence of Suslin trees.  While a chain of a poset is any sub toset, an antichain is a subset in which no elements are comparable.

Definition 5.  A Suslin tree is a tree T such that h(T)=\omega_1, every branch is countable, and every antichain is countable.

Note these assumptions are not contradictory, since the height of T is not equivalent to the supremum of heights of branches (where height of a branch is defined by supremum of heights of its elements).

Lemma 6.  If there exists a Suslin tree, then there exists a normal Suslin tree.

Proposition 7.  There exists a Suslin line if and only if there exists a Suslin tree.

If SH (Suslin’s Hypothesis) is the nonexistence of a Suslin line and MA is Martin’s Axiom, then the proof of independence follows from ZFC[V=L]\vdash\lnot SH and ZFC[MA]\vdash SH where V=L is the Axiom of Constructibility.

[1] Jech, Thomas.  Set Theory.  Third Edition.  Springer Monographs in Mathematics.  Springer-Verlag.  2003.