Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Tetrits, just checking FTIA...

Dan Zuras Intervals wrote:

Nate's recent assertion that {domainFalse} would serve just
as well as {} caused me to double check if the fundamental
theorem holds for either decoration assignment.

I find that it holds for {} but not for {domainFalse}.

Recall, for divide we will define:

domainFalse = {There exists x in xx & y in yy such
that x/y is not in the domain of divide}
(i.e. an x & y such that y = 0)

domainTrue = {There exists x in xx & y in yy such
that x/y is in the domain of divide}
(i.e. an x & y such that y != 0)

Here are two towers of ever decreasing intervals.  Each has
the property that the operands are contained in the operands
above & the results are contained in the results above,
including decorations:

[1,2]/[entire] = {[entire],{domainFalse,domainTrue}}
[1,2]/[-2,2] = {[entire],{domainFalse,domainTrue}}
[1,2]/[0,2] = {[1/2,oo],{domainFalse,domainTrue}}
[1,2]/[0,0] = {[empty],{domainFalse}}
[1,2]/[empty] = {[empty],{}}
[empty]/[empty] = {[empty],{}}

[1,2]/[-2,2] = {[entire],{domainFalse,domainTrue}}
[1,2]/[1,2] = {[1/2,2],{domainTrue}}
[1,2]/[1,1] = {[1,2],{domainTrue}}
[1,2]/[empty] = {[empty],{}}
[empty]/[empty] = {[empty],{}}

Notice that in the second tower a decoration of {domainFalse}
for an [empty] result would violate the fundamental theorem.

Here is a similar pair of towers for sqrt():

sqrt([entire]) = ([0,oo],{domainFalse,domainTrue}}
sqrt([-2,4]) = ([0,2],{domainFalse,domainTrue}}
sqrt([-2,-1]) = ([empty],{domainFalse}}
sqrt([empty]) = ([empty],{}}

sqrt([entire]) = ([0,oo],{domainFalse,domainTrue}}
sqrt([0,4]) = ([0,2],{domainTrue}}
sqrt([1,1]) = ([1,1],{domainTrue}}
sqrt([empty]) = ([empty],{}}

I just had to check...
One thing to keep in mind is that interval branch-and-prune methods are an application of the Nested Intervals Theorem, which says the intersection of infinitely many nested intervals over a non-empty compact (closed and bounded) domain is a non-empty set. If the width of the nested intervals are decreasing, the intersection is a unique real number.
So it is not possible that an empty interval can ever arise in a divide-and-conquer method so long as the original input domain meets these criteria.
Now, Nested Intervals Theorem does _not_ hold if the input domain is empty or unbounded. So these probably are the kinds of examples we realistically will want to examine very closely. 

Nate