A Decent Borel Code


A few posts ago we took a look at how we might implement various operations on sets represented as sorted arrays[1], such as the union, being the set of every element that is in either of two sets, and the intersection, being the set of every element that is in both of them, which we implemented with ak.setUnion and ak.setIntersection respectively.
Such arrays are necessarily both finite and discrete and so cannot represent continuous subsets of the real numbers such as intervals, which contain every real number within a given range. Of particular interest are unions of countable sets of intervals \(I_i\), known as Borel sets, and so it's worth adding a type to the ak library to represent them.

The Borel Nature

Strictly speaking, Borel sets are defined as those that can be constructed from a countable set of closed or open subsets, being those that do or do not include their bounds respectively, of suitable universal sets using the operations of union, intersection and complement, the latter of which yields the set of elements that are in the universal set but not in the set to which it is applied. Exactly what is meant by a suitable universal set is beyond the scope of this post, but suffice it to say that the set of real numbers \(\mathbb{R}\) is one of them and it is its Borel sets that we shall concern ourselves with.

The bounds of intervals are typically represented with a round bracket if they are open and with a square bracket if they are closed, so that
\[ \begin{align*} x \in (l, u) &\rightarrow l < x < u\\ x \in [l, u) &\rightarrow l \leqslant x < u\\ x \in (l, u] &\rightarrow l < x \leqslant u\\ x \in [l, u] &\rightarrow l \leqslant x \leqslant u \end{align*} \]
where \(\in\) means within and \(\rightarrow\) means implies. Note that, for any number \(x\), we define
\[ (x) = [x) = (x] = \varnothing \]
where \(\varnothing\) is the empty set. Furthermore, given a set of numbers \(x_i\) such that
\[ i < j \rightarrow x_i < x_j \]
we have
\[ \begin{align*} \left(x_0, x_2\right) \cup \left(x_1, x_3\right) &= \left(x_0, x_3\right)\\ \left(x_0, x_2\right) \cup \left[x_2, x_3\right) &= \left(x_0, x_3\right)\\ \left(x_0, x_2\right] \cup \left(x_2, x_3\right) &= \left(x_0, x_3\right)\\ \\ \left(x_0, x_2\right) \cap \left(x_1, x_3\right) &= \left(x_1, x_2\right)\\ \left(x_0, x_2\right) \cap \left[x_2, x_3\right) &= \varnothing\\ \left(x_0, x_2\right] \cap \left(x_2, x_3\right) &= \varnothing\\ \\ \left(x_0, x_1\right)^\prime &= \left[-\infty, x_0\right] \cup \left[x_1, \infty\right] \end{align*} \]
where \(A \cup B\) is the union of \(A\) and \(B\), \(A \cap B\) is their intersection and \(A^\prime\) is the complement of \(A\). We can also define the difference between \(A\) and \(B\), containing those values in \(A\) that are not in \(B\), with
\[ A-B = A \cap B^\prime \]
and the symmetric difference between them, containing those values that are in one or the other of them but not both, with
\[ A \ominus B = (A \cup B) - (A \cap B) \]
For example, exploiting the identity
\[ A \cap (B \cup C) = (A \cap B) \cup (A \cup C) \]
we have
\[ \begin{align*} \left(x_0, x_3\right) - \left(x_1, x_2\right) &= \left(x_0, x_3\right) \cap \left(x_1, x_2\right)^\prime\\ &= \left(x_0, x_3\right) \cap \left(\left[-\infty, x_1\right] \cup \left[x_2, \infty\right]\right)\\ &= \left(\left(x_0, x_3\right) \cap \left[-\infty, x_1\right]\right) \cup \left(\left(x_0, x_3\right) \cap \left[x_2, \infty\right]\right)\\ &= \left(x_0, x_1\right] \cup \left[x_2, x_3\right) \end{align*} \]
\[ \begin{align*} \left(x_0, x_2\right) \ominus \left(x_1, x_3\right) &= \left(\left(x_0, x_2\right) \cup \left(x_1, x_3\right)\right) - \left(\left(x_0, x_2\right) \cap \left(x_1, x_3\right)\right)\\ &= \left(x_0, x_3\right) - \left(x_1, x_2\right)\\ &= \left(x_0, x_3\right) \cap \left(x_1, x_2\right)^\prime\\ &= \left(x_0, x_3\right) \cap \left(\left[-\infty, x_1\right] \cup \left[x_2, \infty\right]\right)\\ &= \left(\left(x_0, x_3\right) \cap \left[-\infty, x_1\right]\right) \cup \left(\left(x_0, x_3\right) \cap \left[x_2, \infty\right]\right)\\ &= \left(x_0, x_1\right] \cup \left[x_2, x_3\right) \end{align*} \]
Since Borel sets are simply unions of intervals we can easily extend these operations to them with the identities
\[ (A \cup B) \cap (C \cup D) = (A \cap C) \cup (A \cap D) \cup (B \cap C) \cup (B \cap D) \]
\[ (A \cup B)^\prime = A^\prime \cap B^\prime \]
We can define a kind of ordering of Borel sets, known as a partial ordering, with
\[ \begin{align*} A \subset B &\rightarrow A < B \wedge B > A\\ A \subseteq B &\rightarrow A \leqslant B \wedge B \geqslant A \end{align*} \]
where \(\subset\) stands for is a proper subset of, meaning that the sets can't be equal, and \(\subseteq\) stands for is a subset of, meaning that they can be.
Note that, for numbers \(a\) and \(b\), we can conclude that
\[ a \nless b \wedge b \nless a \rightarrow a = b \]
where \(\nless\) means not less than and \(\wedge\) means and, whereas for Borel sets we can only conclude that
\[ A \nless B \wedge B \nless A \rightarrow A \cap B \neq A \wedge A \cap B \neq B \]
In particular, for a non-empty Borel set \(A\) with a non-empty complement \(A^\prime\), we have
\[ \begin{align*} A &\neq A^\prime\\ A &\nless A^\prime\\ A^\prime &\nless A\\ A &\cap A^\prime = \varnothing \end{align*} \]

Borel Support

Clearly the first thing that we shall need is a type to represent a bound of an interval and it strikes me that the simplest way to specify that it is closed or open is with a string containing the appropriate bracket, preceding the value of a lower bound and following that of an upper bound. For example, constructor arguments of

'[', 0

should create a closed lower bound of zero and those of

1, ')'

should create an open upper bound of one. As usual, we shall implement this by dispatching to members of a constructors object, defined in listing 1, to initialise a state object according to the types of the arguments, in this case String and Number for a lower bound or Number and String for an upper bound.

Listing 1: The Basic Constructors
var constructors = {};

constructors[ak.NUMBER_T] = {};
constructors[ak.STRING_T] = {};

constructors[ak.NUMBER_T][ak.STRING_T] = function(state, value, type) {
 value = Number(value);
 type  = String(type);

 if(isNaN(value)) throw new Error('invalid value in ak.borelBound');
 if(type!==')' && type!==']') throw new Error('invalid type in ak.borelBound');

 state.value = value;
 state.type  = type;

constructors[ak.STRING_T][ak.NUMBER_T] = function(state, type, value) {
 value = Number(value);
 type  = String(type);

 if(isNaN(value)) throw new Error('invalid value in ak.borelBound');
 if(type!=='(' && type!=='[') throw new Error('invalid type in ak.borelBound');

 state.value = value;
 state.type  = type;

We shall also allow construction with an object containing type and value methods or properties, as implemented in listing 2.

Listing 2: The Object Constructor
constructors[ak.OBJECT_T] = {};

constructors[ak.OBJECT_T][ak.UNDEFINED_T] = function(state, obj) {
 var type  = (ak.nativeType(obj.type)===ak.FUNCTION_T)  ? String(obj.type())
                                                        : String(obj.type);
 var value = (ak.nativeType(obj.value)===ak.FUNCTION_T) ? Number(obj.value())
                                                        : Number(obj.value);

 if(isNaN(value)) throw new Error('invalid value in ak.borelBound');
 if(type!=='(' && type!=='[' && type!==')' && type!==']') {
  throw new Error('invalid type in ak.borelBound');

 state.value = value;
 state.type  = type;

After initialising its state using these constructors, the ak.borelBound function given in listing 3 adds to its result property access methods to retrieve the value and type of the bound together with methods to directly query whether the bound is lower or upper and open or closed. Finally, the usual string conversions are provided with lower bounds placing the appropriate bracket on the left of their values and upper bounds placing it on the right.

Listing 3: ak.borelBound
ak.BOREL_BOUND_T = 'ak.borelBound';

function BorelBound(){}
BorelBound.prototype = {
 valueOf: function(){return ak.NaN;}

ak.borelBound = function(arg0, arg1) {
 var b = new BorelBound();
 var state = {};
 var lower, open;

 constructors[ak.nativeType(arg0)][ak.nativeType(arg1)](state, arg0, arg1);

 lower = state.type==='(' || state.type==='[';
 open  = state.type==='(' || state.type===')';

 b.value  = function() {return state.value;};
 b.type   = function() {return state.type;};
 b.lower  = function() {return lower};
 b.upper  = function() {return !lower;};
 b.open   = function() {return open;};
 b.closed = function() {return !open;};

 if(lower) {
  b.toString      = function()  {return state.type+state.value.toString();};
  b.toExponential = function(d) {return state.type+state.value.toExponential(d);};
  b.toFixed       = function(d) {return state.type+state.value.toFixed(d);};
  b.toPrecision   = function(d) {return state.type+state.value.toPrecision(d);};
 else {
  b.toString      = function()  {return state.value.toString()+state.type;};
  b.toExponential = function(d) {return state.value.toExponential(d)+state.type;};
  b.toFixed       = function(d) {return state.value.toFixed(d)+state.type;};
  b.toPrecision   = function(d) {return state.value.toPrecision(d)+state.type;};

 return Object.freeze(b);

Finally, we provide overloads of the equals and not equal operators, shown in listing 4.

Listing 4: ak.borelBound Operators
function eq(l, r) {
 return l.value()===r.value() && l.type()===r.type();

function ne(l, r) {
 return l.value()!==r.value() || l.type()!==r.type();

ak.overload(ak.eq, [ak.BOREL_BOUND_T, ak.BOREL_BOUND_T], eq);
ak.overload(ak.ne, [ak.BOREL_BOUND_T, ak.BOREL_BOUND_T], ne);

These can be found together with the implementation of ak.borelBound in BorelBound.js.

To represent an interval we simply need a pair of ak.borelBound objects, such as those in the state object of the ak.borelInterval type defined in listing 5.

Listing 5: ak.borelInterval
ak.BOREL_INTERVAL_T = 'ak.borelInterval';

function BorelInterval(){}
BorelInterval.prototype = {
 valueOf: function(){return ak.NaN;}

ak.borelInterval = function() {
 var b = new BorelInterval();
 var state = {};
 var arg0 = arguments[0];
 var empty;

 constructors[ak.type(arg0)](state, arg0, arguments);
 empty = isEmpty(state.lb, state.ub);

 if(empty) {
  state.lb = ak.borelBound('(', 0);
  state.ub = ak.borelBound(0, ')');

 b.lb = function() {return state.lb;};
 b.ub = function() {return state.ub;};

 b.contains = function(x) {
  switch(ak.type(x)) {
   case ak.NUMBER_T:
    return !empty && containsNum(state.lb, state.ub, x);

   case ak.BOREL_BOUND_T:
    return !empty && x.lower() ? containsLB(state.lb, state.ub, x)
                               : containsUB(state.lb, state.ub, x);
  throw new Error('invalid argument in ak.borelInterval.contains');

 b.includes = function(x) {
  if(ak.type(x)!==ak.BOREL_INTERVAL_T) {
   throw new Error('invalid argument in ak.borelInterval.includes');
  return isEmpty(x.lb(), x.ub())
      || (!empty && containsLB(state.lb, state.ub, x.lb())
                 && containsUB(state.lb, state.ub, x.ub()));

 b.toString = function() {
  return state.lb.toString()+','+state.ub.toString();

 b.toExponential = function(d) {
  return state.lb.toExponential(d)+','+state.ub.toExponential(d);

 b.toFixed = function(d) {
  return state.lb.toFixed(d)+','+state.ub.toFixed(d);

 b.toPrecision = function(d) {
  return state.lb.toPrecision(d)+','+state.ub.toPrecision(d);

 return Object.freeze(b);

After initialising it we first determine whether it's empty and, if so, redefine it as the open interval around zero. Next, we add the lb and ub methods to provide access to the lower and upper bounds and the contains and includes methods to test whether or not a number or bound is within the interval and whether or not another interval is a subset of it respectively and which we shall discuss in detail, along with the isEmpty function, later on. Finally, we add the usual string conversion methods which simply concatenate the string representations of the bounds with a comma between them.

Once again it will often be convenient to represent the types of an interval's bounds with strings and so the first set of constructors, shown in listing 6, allow the user to do so.

Listing 6: String Bound Type Construction
var constructors = {};

constructors[ak.STRING_T] = function(state, ltype, args) {
 var lval = args[1];
 var arg2 = args[2];

 state.lb = ak.borelBound(ltype, lval);
 constructors[ak.STRING_T][ak.type(arg2)](state, arg2, args);

constructors[ak.STRING_T][ak.NUMBER_T] = function(state, uval, args) {
 var utype = args[3];
 state.ub = ak.borelBound(uval, utype);

So these expect the constructor arguments to be the string representation of the lower bound's type, the lower bound's value, the upper bound's value and the string representation of the upper bound's type and defer to the ak.borelBound constructors to check that they have valid values.

Obviously we should also be able to initialise an interval with a pair of bounds and the constructors given in listing 7 enable this.

Listing 7: ak.borelBound Construction
constructors[ak.BOREL_BOUND_T] = function(state, lb, args) {
 var arg1 = args[1];

 state.lb = ak.borelBound(lb);
 if(state.lb.upper()) throw new Error('invalid lower bound in ak.borelInterval');

 constructors[ak.BOREL_BOUND_T][ak.type(arg1)](state, arg1, args);

constructors[ak.BOREL_BOUND_T][ak.BOREL_BOUND_T] = function(state, ub) {
 state.ub = ak.borelBound(ub);
 if(state.ub.lower()) throw new Error('invalid upper bound in ak.borelInterval');

Two useful special cases are closed intervals containing single elements and empty intervals which we can create with constructors taking a numeric argument and no arguments respectively, as given in listing 8.

Listing 8: Single Element And Empty Interval Constructors
constructors[ak.NUMBER_T] = function(state, val) {
 state.lb = ak.borelBound('[', val);
 state.ub = ak.borelBound(val, ']');

constructors[ak.UNDEFINED_T] = function(state) {
 state.lb = ak.borelBound('(', 0);
 state.ub = ak.borelBound(0, ')');

Finally, we shall also be able to construct intervals from objects having lb and ub methods or properties that can be used to construct bounds, as shown by listing 9.

Listing 9: The Object Constructor
constructors[ak.OBJECT_T] = function(state, obj) {
 var lb = (ak.nativeType(obj.lb)===ak.FUNCTION_T) ? ak.borelBound(obj.lb())
                                                  : ak.borelBound(obj.lb);
 var ub = (ak.nativeType(obj.ub)===ak.FUNCTION_T) ? ak.borelBound(obj.ub())
                                                  : ak.borelBound(obj.ub);

 if(lb.upper()) throw new Error('invalid lower bound in ak.borelInterval');
 if(ub.lower()) throw new Error('invalid upper bound in ak.borelInterval');

 state.lb = lb;
 state.ub = ub;

constructors[ak.BOREL_INTERVAL_T] = constructors[ak.OBJECT_T];

Note that construction from another ak.borelInterval simply uses the general object constructor.

Borel Helpers

We're relying upon helper functions to test whether an interval is empty during initialisation and to implement the contains and includes methods and so we must implement them before we can use ak.borelInterval.
The first of these is the isEmpty function defined in listing 10, which defines an interval as being empty if the value of its lower bound is greater than that of its upper bound or if they are equal and either of them is open.

Listing 10: The isEmpty Helper Function
function isEmpty(lb, ub) {
 var lv = lb.value();
 var uv = ub.value();
 return lv>uv || (lv===uv && (lb.open() || ub.open()));

We determine whether an interval contains a number with the logical expression
!empty && containsNum(state.lb, state.ub, x)

which evaluates to false for empty intervals and defers to the containsNum helper function defined in listing 11 for non-empty intervals.

Listing 11: The containsNum Helper Function
function containsNum(lb, ub, x) {
 var lv = lb.value();
 var uv = ub.value();
 return (x>lv || (x===lv && lb.closed())) && (x<uv || (x===uv && ub.closed()));

As should be expected, this simply tests whether a number is greater than the interval's lower bound, or equal to if it if it's closed, and less than its upper bound, or equal to it if its closed.

When we say that an interval contains a bound we mean that it contains any number that is greater than, greater than or equal to, less than or less than or equal to it if it is an open lower bound, a closed lower bound, an open upper bound or a closed upper bound respectively. Once again this means that empty intervals cannot contain anything, which is reflected in the condition that we use for bounds
!empty && x.lower() ? containsLB(state.lb, state.ub, x) : containsUB(state.lb, state.ub, x)

The containsLB and containsUB functions that test whether an interval contains a lower or an upper bound are given in listing 12.

Listing 12: The containsLB And containsUB Helper Functions
function containsLB(lb, ub, x) {
 var lv = lb.value();
 var uv = ub.value();
 var xv = x.value();
 var xc = x.closed();
 return (xv>lv || (xv===lv && (lb.closed() || !xc)))
     && (xv<uv || (xv===uv && ub.closed() && xc));

function containsUB(lb, ub, x) {
 var lv = lb.value();
 var uv = ub.value();
 var xv = x.value();
 var xc = x.closed();
 return (xv>lv || (xv===lv && lb.closed() && xc))
     && (xv<uv || (xv===uv && (ub.closed() || !xc)));

Clearly we've got a slightly trickier job on our hands with these functions. This is because the containment of a bound that is equal to the lower or upper bounds of the interval depends upon whether both of them are open or closed. For example, if the lower bound of an interval is closed then it contains both open and closed lower bounds with the same value but if it is open then it only contains the open one. Conversely, it only contains a lower bound that has the same value as its upper bound if they are both closed. The condition for the containment of an upper bound follows from much the same reasoning.
Program 1 demonstrates the results of the contains method of ak.borelInterval for a variety of numbers, lower bounds and upper bounds.

Program 1: Interval Contains

The logical expression that we're using to test whether an ak.borelInterval object includes another, given by the x argument of the includes method, is
isEmpty(x.lb(), x.ub()) || (!empty && containsLB(state.lb, state.ub, x.lb()) && containsUB(state.lb, state.ub, x.ub()))

The first thing to note is that every interval contains the empty interval, including the empty interval since, by definition, every set includes itself. The second is that, if the argument isn't empty, then one interval includes another if the former isn't empty and contains both the lower and upper bounds of the latter, which we check with the helper functions that we have just defined.
Program 2 shows the results of the includes method for a few different intervals.

Program 2: Interval Includes

Borel Overloads

The most basic set operation is testing for membership, which for an interval means whether or not a value is within its bounds. Unfortunately in is a reserved word in JavaScript and so we can't use it as the name of the membership operator. Fortunately, however, when \(\in\) was first proposed as the symbol for it[2], it was defined as meaning is (it's actually an \(\epsilon\); the first letter of the Greek word for is) and so that's the name that we shall use in the ak library. A pleasing consequence of this, at least to my mind, is that we can use nis, the Middle English word for isn't, for its negation, as done in listing 13.

Listing 13: ak.is And ak.nis
function is (l, r) {return  r.contains(l);}
function nis(l, r) {return !r.contains(l);}

if(!ak.is) {
 ak.is = function(x0, x1) {return ak.is[ak.type(x0)][ak.type(x1)](x0, x1)};

if(!ak.nis) {
 ak.nis = function(x0, x1) {return ak.nis[ak.type(x0)][ak.type(x1)](x0, x1)};

ak.overload(ak.is,  [ak.BOREL_BOUND_T, ak.BOREL_INTERVAL_T], is);
ak.overload(ak.is,  [ak.NUMBER_T,      ak.BOREL_INTERVAL_T], is);
ak.overload(ak.nis, [ak.BOREL_BOUND_T, ak.BOREL_INTERVAL_T], nis);
ak.overload(ak.nis, [ak.NUMBER_T,      ak.BOREL_INTERVAL_T], nis);

Note that since these aren't in the core set of overloaded functions we must set up the dispatch mechanisms for them if they haven't already been implemented before we define their overloads for numbers and bounds, both of which simply forward to the contains method of ak.borelInterval.
Program 3 applies these overloaded operators to the same intervals, numbers and bounds that were used to demonstrate the contains method in program 1.

Program 3: Using ak.is And ak.nis

A pair of intervals are trivially equal if their lower and upper bounds are equal to each other's and are not equal if they're not, which we can test with the ak.eq and ak.ne overloads for ak.borelBound arguments, which are copied into the eqBound and neBound variables in listing 14.

Listing 14: ak.eq And ak.ne
var eqBound = ak.eq[ak.BOREL_BOUND_T][ak.BOREL_BOUND_T];
var neBound = ak.ne[ak.BOREL_BOUND_T][ak.BOREL_BOUND_T];

function eq(l, r) {
 return eqBound(l.lb(), r.lb()) && eqBound(l.ub(), r.ub());

function ne(l, r) {
 return neBound(l.lb(), r.lb()) || neBound(l.ub(), r.ub());

ak.overload(ak.eq, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], eq);
ak.overload(ak.ne, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], ne);

Program 4 demonstrates these comparisons for the intervals \([-1,1]\) and \((-1,1)\).

Program 4: Using ak.eq And ak.ne

Finally, we implement the partial ordering operators with overloads of the ak.ge, ak.gt, ak.le and ak.lt functions in listing 15.

Listing 15: The Partial Ordering Operators
function ge(l, r) {
 return l.includes(r);

function gt(l, r) {
 return l.includes(r) && (neBound(l.lb(), r.lb()) || neBound(l.ub(), r.ub()));

function le(l, r) {
 return r.includes(l);

function lt(l, r) {
 return r.includes(l) && (neBound(l.lb(), r.lb()) || neBound(l.ub(), r.ub()));

ak.overload(ak.ge, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], ge);
ak.overload(ak.gt, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], gt);
ak.overload(ak.le, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], le);
ak.overload(ak.lt, [ak.BOREL_INTERVAL_T, ak.BOREL_INTERVAL_T], lt);

Here we simply forward to the includes method of the left hand or right hand side ak.borelInterval, as appropriate, adding an inequality test to the strictly less than and greater than operators, ak.lt and ak.gt.
These operators are demonstrated by program 5 which applies them to a few pairs of intervals.

Program 5: Using The Partial Ordering Operators

The implementation of ak.borelInterval and its operators can be found in BorelInterval.js and with these building blocks we are ready to implement a type to represent Borel sets and overloaded functions to perform operations upon them, which we shall do next time.


[1] Let's Talk About Sets, www.thusspakeak.com, 2018.

[2] Peano, G., Arithmetices principia, nova methodo exposita, Augustae Taurinorum, Bocca, 1889.

Leave a comment