Partnered open subsets of R^n

[Paul Taylor]

Consider the class of open subsets of R^n defined by the predicates
in the following language:

f(x1,...,xk) > 0, where f is a polynomial with rational coefficients;

finite union and intersection; and

universal and existential quantification over BOUNDED closed intervals.

The universal quantification should be restricted to closed bounded
intervals (compact subsets) will be familiar to you, but I also
intend existential quantification to be restricted in the same way,
so it is not allowed over the whole of R, or over N.

This language has a "de Morgan" duality, interchanging

+/- >/< true/false min/max sup/inf and/or all/exists.

So any predicate or open subset defined in this language has a
"partner" under this duality.

In the case of a (non-zero) polynomial in one variable, both open
subsets consist of a finite union of intervals, including those that
go to +/- infinity. If there are double zeroes, there are point
holes in some of the intervals: they don't necessarily switch sign.

If the polynomial is decreasing and has only one root, the two open
sets form a Dedekind cut, which defines the root.

Recall that a Dedekind cut is given by two subsets that are
lower or upper, rounded (open), inhabited, disjoint and located.

ANY open subset in the language above, together with its partner,
satisfy some of these properties, in particular they are open
and disjoint.

HOW CAN ONE FORMULATE AN ANALOGUE OF LOCATEDNESS (in R^n)?

Surely such a nice class of open subsets must have been studied
before. What are they called? In what discipline(s) do they arise?

Andrej Bauer's prototype Marshall calculator could handle Dedekind
cuts of this form, although with very restricted handling of
multiple variables. He and I have been trying to put together
a mathematical account of this.

There shouldn't be any issues of constructivity here, such as
hovering / locally constant functions, because functions are
polynomials with rational coefficients, so where classical
results demand decidable equality we have it.

Paul Taylor.

[Kreinovich, Vladik]

This may be related to Tarski-Seidenberg theorem, according to which any formula in the language you described, with free variables is equivalent to a propositional combination of polynomial equalities and inequalities between the free variables -- i.e., all quantifiers over real numbers can be eliminated. The corresponding sets are known as semi-algebraic.

Since you mentioned intervals, you may be interested in knowing as every semi-algebraic set can be obtained as projection of a solution set of linear interval equations with linearly dependent coefficients, see

Gotz Alefeld, Vladik Kreinovich, and Gunter Mayer, "The Shape
of the Solution Set for Systems of Interval Linear Equations with
Dependent Coefficients", Mathematische Nachrichten, 1998, Vol.
192, pp. 23-36.
https://www.cs.utep.edu/vladik/1995/tr95-39b.pdf

--
You received this message because you are subscribed to the Google Groups "constructivenews" group.
To unsubscribe from this group and stop receiving emails from it, send an email to constructivene...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/constructivenews/b151678-5c98-e731-5ff-6834f269f546%40PaulTaylor.EU.

[Paul Taylor]

Thanks to Vladik Kreinovich for his mention of semialgebraic sets
and the Tarski-Seidenberg theorem (quantifier elimination) for them,
and also his interval version of this.

Here is a freely downloadable scan of Tarski's original paper:

www.rand.org/content/dam/rand/pubs/reports/2008/R109.pdf

The only sketch of the proof the Tarski-Seidenberg theorem that
I could find freely online is a lecture note by Andrew Marks at UCLA:

www.math.ucla.edu/~marks/6c/15.pdf

This is based on Sturm's theorem for isolating roots of polynomials,
which in turn is based on Gauss's extension to polynomials of Euclid's
algorithm for hcf, applied to a polynomial and its derivative, as
a way of identifying double roots.

(Coincidentally, I mentioned this yesterday in a MathOverflow
answer, mathoverflow.net/questions/434706 )

HOWEVER, semialgebraic sets are more general than the "partnered"
ones that I described, the language for which only uses STRICT < and >,
no =, BOUNDED quantification and no negation.

I wonder whether my more restricted class of OPEN subsets of R^n
has a name and has been studied?

(My sketchy ideas for studying this class included the bit by Gauss,
so maybe the Tarski-Seidenberg theorem can be restricted appropriately.)

Ran Gutin also pointed out to me (privately) that the word "located"
is ambiguous in constructive mathematics. He took it to be what I
call "overt", whereas I had in mind the ways of saying that the two
parts of a Dedekind cut "touch" each other.

What I was asking for was a way of stating that any open subset of R^n
in my class touches its "de Morgan partner" in some similar sense.

My conjecture is this:

(1) Any open set in my restricted class can be approximated from both
inside and outside by polyhedra that are found using a generalised
Interval Newton method, converging quadratically (ie doubling the
number of valid bits at each stage).

(2) Any open set in my full "Lambda calculus for real analysis"
www.paultaylor.eu/ASD/lamcra
is a directed union of open sets from the restricted class. It can
be approximated from the inside but not necessarily from the outside
and not with any prescribed rate of convergence.

(3) A Dedekind cut consisting of two open sets in the lamcra language
can be approximated from both sides, to form a Cauchy sequence
that converges with one extra bit each time.

My friends will appreciate that all of this is well outside my comfort
zone. I am asking about it because it is entirely possible that the
mathematics and the practical computation behind this has been done
before. The motivation is what I said at CCC in Padova in September:
translating Dedekind cuts into Cauchy sequences is part of narrowing
the gap between theoretical topology and practical computation.

Paul Taylor