A Borel Universe

By a.k. on April 6, 2018 8:00 PM | 0 Comments

Next:

Previous:
Last time[1] we took a look at Borel sets of real numbers, which are subsets of the real numbers that can be represented as unions of countable sets of intervals \(I_i\). We got as far as implementing the ak.borelInterval type to represent an interval as a pair of ak.borelBound objects holding its lower and upper bounds.
With these in place we're ready to implement a type to represent Borel sets and we shall do exactly that in this post.

A Brief Interval

Recall that the bounds of an interval can be open, in which case they do not include its value, or closed, in which case they do, and that we represent them with round and square brackets respectively. Specifically, we have the four cases
\[ \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. If the lower and upper bounds of an interval have an equal value and either of them is open then that interval is the empty set \(\varnothing\)
\[ (x) = [x) = (x] = \varnothing \]
Furthermore, for values \(x_i\) satisfying
\[ x < j \rightarrow x_i < x_j \]
we have unions, intersections and complements, represented for sets \(A\) and \(B\) as \(A \cup B\), \(A \cap B\) and \(A^\prime\) respectively, of
\[ \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*} \]

The State Of The Union

A natural way to represent Borel sets in JavaScript is with arrays of intervals. It also makes sense to merge any overlapping intervals so that two equal Borel sets, containing exactly the same subset of the real numbers, will be represented by the same set of intervals. To do this efficiently we need to sort the intervals by their bounds and so the first thing that we need are comparison functions for them, as given in listing 1.

Listing 1: The Bounds Comparators
function lbCompare(l, r) {
 var lv = l.value();
 var rv = r.value();
 if(lv===rv) {
  lv = Number(l.open());
  rv = Number(r.open());
 }
 return lv-rv;
}

function ubCompare(l, r) {
 var lv = l.value();
 var rv = r.value();
 if(lv===rv) {
  lv = Number(l.closed());
  rv = Number(r.closed());
 }
 return lv-rv;
}

Now these are a little terse and so its worth explaining exactly what they're doing.
Firstly, if the values of the ak.borelBound arguments are different then both lbCompare and ubCompare simply compare those values numerically by subtraction, conforming to the Array.sort requirement of returning a negative result if the first argument comes before the second, a positive result if the former comes after the latter and zero if they compare equal.
Secondly, if their values are equal an open lower bound should compare greater than a closed lower bound whereas a closed upper bound should compare greater than an open one, both of which we achieve by coercing a Boolean indicating whether a bound is of the greater type to a Number, which maps true to one and false to zero, so that the final subtractions yield correct results for the comparisons.
Note that we don't have to worry about the corner cases of subtracting NaNs or equal infinities since we don't allow the former as values of ak.borelBound objects and the latter will result in comparing the types of the bounds, not their values.

When comparing ak.borelInterval objects we shall firstly rank empty intervals as greater than non-empty intervals. We shall then rank one non-empty interval before another if its lower bound comes before the latter's, or if they are equal and its upper bound comes after the latter's. Conversely, we shall rank it after if its lower bound is greater than the latter's or if they are equal and its upper bound comes first. Finally, we shall rank them equal if both of their bounds compare equal.
The reason for this somewhat unintuitive ordering, which makes little sense mathematically and is implemented by intervalCompare in listing 2, is that it will make it ever so slightly easier to correctly merge overlapping intervals.

Listing 2: The Interval Comparator
function nonEmptyInterval(i) {
 var lb = i.lb();
 var ub = i.ub();
 return lb.value()!==ub.value() || lb.closed();
}

function intervalCompare(l, r) {
 var lne = nonEmptyInterval(l);
 var rne = nonEmptyInterval(r);
 var c;

 if(lne && rne) {
  c = lbCompare(l.lb(), r.lb());
  return c!==0 ? c : ubCompare(r.ub(), l.ub());
 }
 return Number(rne)-Number(lne);
}

Note that when testing for a non-empty interval we only need to check that its bounds are different or that one of them is closed since we represent all empty intervals with open lower and upper bounds of zero. Furthermore, we are again exploiting the Boolean to Number conversion rules to ensure that empty intervals compare greater than non-empty intervals and equal to each other.
Program 1 demonstrates the result of using this comparator to sort an array of intervals.

Program 1: Sorting Intervals

Once we have sorted the intervals and removed the empty ones, we know that the lower bound of an interval must be less than or equal to that of the next in the array. The criterion for merging them into a single interval is consequently that there aren't any numbers between the lower bound of the first and the upper bound of the second that are not included in either of them. This will be the case if the value of the first interval's upper bound is greater than that of the second's lower bound or if their values are equal and either of them is closed.
If this criterion has been met then the first interval will wholly include the second if its upper bound is greater than or equal to the latter's.
These criteria are implemented by the touchesNextLB and includesNextUB functions respectively, both of which are defined in listing 3.

Listing 3: Testing For Overlap And Inclusion
function touchesNextLB(ub0, lb1) {
 var v0 = ub0.value();
 var v1 = lb1.value();
 return v0>v1 || (v0===v1 && (ub0.closed() || lb1.closed()));
}

function includesNextUB(ub0, ub1) {
 var v0 = ub0.value();
 var v1 = ub1.value();
 return v0>v1 || (v0===v1 && (ub0.closed() || ub1.open()));
}

With these in place we are ready to transform an array of ak.borelInterval objects into the smallest sorted, and hence unique, array of ak.borelInterval objects that represents the same Borel set, as done by the compress function given in listing 4.

Listing 4: Compressing The State
function compress(state) {
 var n, i0, i1;

 state.sort(intervalCompare);
 n = state.length;
 while(n>0 && !nonEmptyInterval(state[n-1])) --n;

 if(n>1) {
  i0 = i1 = 0;
  while(i1<n) {
   while(++i1<n && touchesNextLB(state[i0].ub(), state[i1].lb())) {
    if(!includesNextUB(state[i0].ub(), state[i1].ub())) {
     state[i0] = ak.borelInterval(state[i0].lb(), state[i1].ub());
    }
   }
   if(i1<n) state[++i0] = state[i1];
  }
  state.length = i0+1;
 }
 else {
  state.length = n;
 }
}

So the first thing that we do after sorting the intervals is to find the index of the first empty one, if there are any, by iterating backward from the end of the array. If there's more than one non-empty interval we enter a loop to merge any that are overlapping, otherwise we set the length of the array to that index, removing any empty intervals.
The loop works by keeping track of the index of the interval into which we might merge another in i0 and the index of a candidate to be merged in i1. While, after incrementing i1, the interval it indexes is touching the one indexed by i0, we merge them. If the former is entirely included in the latter this is done by simply skipping past it, which we can safely do because our unusual ordering always puts an interval that is a subset of another after it. Otherwise we replace the latter with a new ak.borelInterval having its lower bound and the former's upper bound. If we find an interval that isn't touching the one at i0 we increment it and copy that interval into its place, which will contain the same interval if we haven't merged any or an interval that has been merged if we have. We continue looping until there are no more candidates for merging and finally set the length of the array to i0+1, removing any intervals that have been merged.
Program 2 demonstrates the effect of this function on an array of ak.borelInterval objects.

Program 2: Compressing The State

ak.borelSet

As you may have guessed by the name of its argument, we shall use the compress function to ensure that the state array of our type to represent Borel sets, ak.borelSet defined in listing 5, has a canonical form so that two equivalent Borel sets will represented by objects with equal state arrays.

Listing 5: ak.boralSet
ak.BOREL_SET_T = 'ak.borelSet';

function BorelSet(){}
BorelSet.prototype = {
 TYPE: ak.BOREL_SET_T,
 valueOf: function(){return ak.NaN;}
};

ak.borelSet = function(set) {
 var b = new BorelSet();
 var state = [];
 
 constructors[ak.nativeType(set)](state, set);
 compress(state);

 b.intervals = function() {return state.length;};
 b.at = function(i) {return state[Number(i)];};

 b.contains = function(x) {
  switch(ak.type(x)) {
   case ak.NUMBER_T:      return containsNumber(state, x);
   case ak.BOREL_BOUND_T: return containsBound(state, x);
  }
  throw new Error('invalid argument in ak.borelSet.contains');
 };

 b.includes = function(x) {
  switch(ak.type(x)) {
   case ak.BOREL_INTERVAL_T: return includesInterval(state, x);
   case ak.BOREL_SET_T:      return includesSet(state, x);
  }
  throw new Error('invalid argument in ak.borelSet.includes');
 };

 b.toArray  = function() {return state.slice(0);};
 b.toString = function() {return '{' + state.join('+') + '}';};

 b.toExponential = function(d) {
  return '{'+state.map(function(x){return x.toExponential(d);}).join('+')+'}';
 };

 b.toFixed = function(d) {
  return '{'+state.map(function(x){return x.toFixed(d);}).join('+')+'}';
 };

 b.toPrecision = function(d) {
  return '{'+state.map(function(x){return x.toPrecision(d);}).join('+')+'}';
 };

 return Object.freeze(b);
};

Here we do so directly after initialising it with our usual technique of dispatching to a constructors object according to the type of the set argument.
Next we add property access methods, intervals and at, to return the number of intervals in the set and the interval at a given index. The contains method tests whether a number or a bound is within the set by forwarding to helper functions that we shall describe later. Similarly, the includes method tests whether an interval or a Borel set are subsets of it.
Finally we have the conversion method toArray to extract an array containing the intervals in the set and the usual string conversion methods that join their string representations with plus signs to represent the union operation and enclose them in the curly braces typically used to represent sets.

The constructors are reasonably simple, allowing initialisation from an array of objects from which ak.borelInterval objects can be constructed and from an object having an intervals property or method indicating the number of intervals and an at method to return an object from which an ak.borelInterval can be constructed at a given index, as shown by listing 6.

Listing 6: ak.boralSet Constructors
var constructors = {};

constructors[ak.ARRAY_T] = function(state, set) {
 var n = set.length;
 var i;

 state.length = n;
 for(i=0;i<n;++i) state[i] = ak.borelInterval(set[i]);
};

constructors[ak.OBJECT_T] = function(state, set) {
 var n = (ak.nativeType(set.intervals)===ak.FUNCTION_T) ? Number(set.intervals())
                                                        : Number(set.intervals);
 var i;

 state.length = n;
 for(i=0;i<n;++i) state[i] = ak.borelInterval(set.at(i));
};

Program 3 initialises a pair of ak.borelSet objects from arrays of different intervals representing equivalent Borel sets and then prints them to show that they are equal.

Program 3: Constructing ak.borelSet Objects

Returning to the contains method, listing 7 shows the containsNumber and containsBound helper functions that we used to implement it.

Listing 7: The containsNumber And containsBound Helper Functions
function numberCompare(li, rv) {
 return li.lb().value()-rv;
}

function containsNumber(state, x) {
 var n = state.length;
 var i = ak._unsafeLowerBound(state, x, numberCompare, 0, n);
 return (i>0 && state[i-1].contains(x)) || (i<n && state[i].contains(x));
}

function containsBound(state, x) {
 var n = state.length;
 var i = ak._unsafeLowerBound(state, x.value(), numberCompare, 0, n);
 return (i>0 && state[i-1].contains(x)) || (i<n && state[i].contains(x));
}

These both use our private, by convention rather than enforcement, ak._unsafeLowerBound function, which you will recall returns the first position in a sorted array before which a value can be inserted whilst keeping the array sorted[2], to find the first interval in the state array that has a lower bound with a value greater than or equal to the number or the value of the bound. Note that the numberCompare function relies upon our knowing the implementation details of ak._unsafeLowerBound; specifically that the first argument is always an element of the array and the second is always the value whose insertion point we're looking for.
Since the value of the lower bound of the interval at that position might be greater than or equal to the value we must check for inclusion in both the interval at the previous position, if there is one, and at the position itself, if it isn't after the last in the array.
Program 4 demonstrates the results of the contains method of an ak.borelSet for a range of numbers and open and closed, lower and upper bounds.

Program 4: The contains Method

The helper functions for includes, includesInterval and includesSet defined in listing 8, use the same approach to find the intervals that might include the ak.borelInterval argument or each of them in the ak.borelSet argument.

Listing 8: The includesInterval And includesSet Helper Functions
function includesInterval(state, x) {
 var n = state.length;
 var i = ak._unsafeLowerBound(state, x.lb().value(), numberCompare, 0, n);
 return (i>0 && state[i-1].includes(x)) || (i<n && state[i].includes(x));
}

function includesSet(state, x) {
 var n = state.length;
 var m = x.intervals();
 var i = 0;
 var j, xj;

 for(j=0;j<m;++j) {
  xj = x.at(j);
  i = ak._unsafeLowerBound(state, xj.lb().value(), numberCompare, i, n);
  if(!(i>0 && state[i-1].includes(xj)) && !(i<n && state[i].includes(xj))) {
   return false;
  }
 }
 return true;
}

Note that in the latter function we only need to search the elements of the state from the previously located interval since the intervals in x are also sorted.
Program 5 shows the results of the includes method of two ak.borelSet objects for a few different ak.borelInterval and ak.borelSet arguments.

Program 5: The includes Method

ak.borelSet Operators

Once again we shall use is and nis to represent the membership operator \(\in\) and its negation \(\notin\), as shown by listing 9.

Listing 9: The is And nis Operators
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_SET_T], is);
ak.overload(ak.is,  [ak.NUMBER_T,      ak.BOREL_SET_T], is);
ak.overload(ak.nis, [ak.BOREL_BOUND_T, ak.BOREL_SET_T], nis);
ak.overload(ak.nis, [ak.NUMBER_T,      ak.BOREL_SET_T], nis);

We shall also again use the relational operators to test for the inclusion of one Borel set within another, reflecting the fact that we can define a partial ordering of Borel sets 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 \(\subseteq\) means is a subset of, \(\subset\) means is a proper subset of or, in other words, is a subset of, but is not equal to and \(\wedge\) means and. Note that, unlike the total ordering of numbers, it is possible for one set to be neither less than, equal to nor greater than another; specifically, if they both contain at least one element that is not within the other.
Listing 10 gives the definitions of these operators, together with those of equality and inequality.

Listing 10: The Equality, Inequality And Relational Operators
var eqInterval = ak.eq[ak.BOREL_INTERVAL_T][ak.BOREL_INTERVAL_T];

function eq(l, r) {
 var n = l.intervals();
 var i = 0;

 if(r.intervals()!==n) return false;
 while(i<n && eqInterval(l.at(i), r.at(i))) ++i;
 return i===n;
}

function ne(l, r) {
 var n = l.intervals();
 var i = 0;

 if(r.intervals()!==n) return true;
 while(i<n && eqInterval(l.at(i), r.at(i))) ++i;
 return i<n;
}

function le(l, r) {return r.includes(l);}
function lt(l, r) {return r.includes(l) && ne(l, r);}
function ge(l, r) {return l.includes(r);}
function gt(l, r) {return l.includes(r) && ne(l, r);}

ak.overload(ak.eq, [ak.BOREL_SET_T, ak.BOREL_SET_T], eq);
ak.overload(ak.ge, [ak.BOREL_SET_T, ak.BOREL_SET_T], ge);
ak.overload(ak.gt, [ak.BOREL_SET_T, ak.BOREL_SET_T], gt);
ak.overload(ak.le, [ak.BOREL_SET_T, ak.BOREL_SET_T], le);
ak.overload(ak.lt, [ak.BOREL_SET_T, ak.BOREL_SET_T], lt);
ak.overload(ak.ne, [ak.BOREL_SET_T, ak.BOREL_SET_T], ne);

We have previously implemented the set operations of union, intersection, difference and symmetric difference for sorted arrays representing multisets[3] with ak.setUnion, ak.setIntersection, ak.setDifference and ak.setSymmetricDifference.
Since we have a type to represent Borel sets it makes sense to implement these operations as overloads such as the arithmetic ak.add operation and the ak.or logical one for the union and the logical ak.not for the complement. Once we have these we can implement the intersection, difference and symmetric difference using the identities
\[ \begin{align*} A \cap B &= \left(A^\prime \cup B^\prime\right)^\prime\\ A - B &= A \cap B^\prime = \left(A^\prime \cup B\right)^\prime\\ A \ominus B &= \left(A \cup B\right) - \left(A \cap B\right) = \left(\left(A \cup B\right)^\prime \cup \left(A^\prime \cup B^\prime\right)^\prime\right)^\prime \end{align*} \]
To implement the union of two ak.borelSet object we can simply convert them to arrays, concatenate them and construct a new ak.borelSet with the result, trusting its constructor to transform its intervals into the smallest set of intervals that contain every number in them which is necessarily their union.
To create the complement we must construct intervals of the numbers lying before the lower bound of the first interval, between the upper bounds of each interval and the lower bounds of the next and after the upper bound of the last interval, as done by the not function in listing 11.

Listing 11: The Complement Operator
function flipLB(lb) {
 return ak.borelBound(lb.value(), lb.open() ? ']' : ')');
}

function flipUB(ub) {
 return ak.borelBound(ub.open() ? '[' : '(', ub.value());
}

function not(x) {
 var n = x.intervals();
 var a = new Array(n+1);
 var i = 0;
 var l = ak.borelBound('[', -ak.INFINITY);
 var b;

 while(i<n) {
  b = x.at(i);
  a[i++] = ak.borelInterval(l, flipLB(b.lb()));
  l = flipUB(b.ub());
 }
 a[i] = ak.borelInterval(l, ak.borelBound(ak.INFINITY, ']'));
 return ak.borelSet(a);
}

This captures all of the numbers less than the lower bound of the first interval with an initial closed lower bound at minus infinity. It then iteratively creates new intervals between the current lower bound and an upper bound with a value equal to that of the lower bound of the current interval but of the opposite type, so that a closed lower bound yield an open upper bound and an open lower bound yields a closed upper bound. The current lower bound is the replaced with the equivalent opposite of the interval's upper bound. Finally, we create an interval from the current lower bound to a closed upper bound at infinity to capture the numbers greater than the last upper bound. Note that since half open intervals with the same value for their lower and upper bounds are empty, the first and last intervals in the result will be empty if the set includes minus and plus infinity respectively.

Listing 12 overloads the ak.not logical operation with this ak.borelSet complement, ak.add and ak.or for its union operation, ak.and for the intersection, ak.sub for the difference and ak.xor for the symmetric difference. Furthermore, it overloads ak.nand with the complement of the intersection, ak.nand with that of the union and ak.xnor with that of the symmetric difference.

Listing 12: The Set Operators
function and (l, r) {return not(or(not(l), not(r)));}
function nand(l, r) {return or(not(l), not(r));}
function nor (l, r) {return not(or(l, r));}
function or  (l, r) {return ak.borelSet(l.toArray().concat(r.toArray()));}
function sub (l, r) {return not(or(not(l), r));}
function xnor(l, r) {return or(not(or(l, r)), not(or(not(l), not(r))));}
function xor (l, r) {return not(or(not(or(l, r)), not(or(not(l), not(r)))));}

ak.overload(ak.not, ak.BOREL_SET_T, not);

ak.overload(ak.add,  [ak.BOREL_SET_T, ak.BOREL_SET_T], or);
ak.overload(ak.and,  [ak.BOREL_SET_T, ak.BOREL_SET_T], and);
ak.overload(ak.nand, [ak.BOREL_SET_T, ak.BOREL_SET_T], nand);
ak.overload(ak.nor,  [ak.BOREL_SET_T, ak.BOREL_SET_T], nor);
ak.overload(ak.or,   [ak.BOREL_SET_T, ak.BOREL_SET_T], or);
ak.overload(ak.sub,  [ak.BOREL_SET_T, ak.BOREL_SET_T], sub);
ak.overload(ak.xnor, [ak.BOREL_SET_T, ak.BOREL_SET_T], xnor);
ak.overload(ak.xor,  [ak.BOREL_SET_T, ak.BOREL_SET_T], xor);

Program 6 demonstrates some of these operations for a pair of Borel sets.

Program 6: Some Set Operations

Finally, you will find the implementation of ak.borelSet and its operators in BorelSet.js.

References

[1] A Decent Borel Code, www.thusspakeak.com, 2018.

[2] I Still Haven't Found What I'm Looking For, www.thusspakeak.com, 2017.

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

Next:

Previous:


Categories:

Tags:


submit to reddit  

Leave a comment