How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Outward-rounded operations are inclusion-isotone and enclose DAG evaluations
Statement
For real intervals, complex rectangles or complex balls on which an operation
is defined, enlarging either input enclosure cannot shrink the computed
enclosure: for binary , if and
, then the computed set enclosure of is contained
in that of whenever both are finite results and their domain
restrictions are preserved. The square-root enclosure is inclusion-isotone on
nonnegative intervals. Each finite ball operation in
Outward-rounded interval, rectangle and ball operations contains the exact ball
image. A split-domain, entire, domain-error, overflow, or
inconclusive status makes no finite claim. For a finite expression DAG
whose operation nodes all return finite enclosures, every exact node value
from every admissible input assignment belongs to its computed node
enclosure; in particular, the root enclosure contains the exact range. If any
node returns a non-finite status, no finite DAG enclosure is asserted.
Facts & Assumptions
Given: The interval, rectangle, ball and operation definitions in Outward-rounded interval, rectangle and ball operations and the directed rounding lemma Directed dyadic rounding encloses with explicit underflow and overflow bounds.
Outward-rounded interval, rectangle and ball operations: each finite real interval or rectangle operation uses its displayed endpoint formula and each ball operation uses its displayed origin-centered radius, followed by directed rounding; invalid domains return a non-finite status.
Directed dyadic rounding encloses with explicit underflow and overflow bounds: every finite exact endpoint lies between its downward and upward dyadic roundings.
Dyadic square-root bisection gives outward endpoints: every defined nonnegative square-root endpoint is bracketed by exact dyadic bisection, and its outward lower and upper endpoint maps are nondecreasing in the radicand.
Real and complex modulus product and triangle inequalities: complex modulus is submultiplicative with equality on products and satisfies the triangle inequality; real absolute value satisfies the triangle inequality.
Real intervals, complex rectangles and ball enclosures: for , ; an expression DAG is a finite directed acyclic graph with input nodes, constant nodes, and operation nodes whose constants carry certified enclosing intervals when needed.
Nonnegative real square roots exist uniquely: each nonnegative radicand has a unique nonnegative square root.
Dedekind-complete ordered real field: for and for , hence .
Proof
For real addition and subtraction, every exact pair value lies between the endpoint formulas. For multiplication, fixing one variable makes the product affine in the other, so a minimum or maximum over a rectangle is attained at a corner. Reciprocal is monotone on either interval avoiding zero, and square root is monotone on . Thus the exact ranges lie in the displayed pre-rounding intervals. Each computed lower endpoint is no greater than the exact lower endpoint and each upper endpoint is no smaller than the exact upper endpoint by [L2]; square-root endpoint bounds follow from [L3]. For complex rectangles, component addition and multiplication preserve the exact component formulas. If a rectangle excludes zero, at least one coordinate interval omits zero, so its exact squared interval has positive lower endpoint. The reciprocal rule retains the exact rational denominator and component quotient endpoints until final outward conversion, so underflow cannot introduce a zero divisor. Those converted components and subsequent multiplication enclose the reciprocal and quotient.
For a ball , the coordinate projection intervals in [L1] contain each real and imaginary component. By [L5]–[L6], ; the complex triangle inequality [L4] therefore gives . Also by [L7]. If , nonnegativity would imply , a contradiction. Hence ; the same argument gives . Every point of and has absolute value at least its corresponding value, so . For , [L4] gives and . If , then and . Upward radius rounding in [L1] preserves these bounds, proving soundness of all finite ball results.
Inclusion of balls implies inclusion of each coordinate projection interval. Therefore cannot decrease and cannot increase as an input ball enlarges. The ball addition, subtraction and multiplication radii in [L1] are consequently nondecreasing. If both divisor results are finite, the larger divisor ball has positive and the smaller one has at least as large an ; the quotient radius therefore cannot decrease when either ball is enlarged. For intervals and rectangles, the exact endpoint hulls and their downward/upward roundings preserve inclusion, so their finite extensions are isotone as well; for square root, [L3] gives monotonicity of the computed endpoint maps. If a domain restriction is lost, the operation returns its stated non-finite status.
In any nonempty finite acyclic graph, some node has no predecessor: otherwise, repeatedly following predecessors would revisit a node by finiteness and create a directed cycle. Remove such a node and repeat to construct a finite topological order. By [L1], input nodes contain their assigned values and constants have certified enclosures. Induct along this order: if each predecessor of an operation node contains its exact value, steps 1.1, 1.2, and 2.1 show that the operation enclosure contains the node's exact value. The induction covers every node, including the root, for every admissible assignment.
Depends on
- Outward-rounded interval, rectangle and ball operations
- Real intervals, complex rectangles and ball enclosures
- Directed dyadic rounding encloses with explicit underflow and overflow bounds
- Dyadic square-root bisection gives outward endpoints
- Real and complex modulus product and triangle inequalities
- Nonnegative real square roots exist uniquely
- Dedekind-complete ordered real field
Used by
- Budgeted ordered Hermitian eigenvalue bisection by verified inertia Algorithm
- Certified adaptive Simpson from derivative enclosures Algorithm
- Certified dyadic enclosures for unit-circle phases Algorithm
- Certified Gaussian gridding for type 1 and type 2 Algorithm
- Certified Gaussian nodes and weights by Golub–Welsch Algorithm
- Certified geometric predicate for interval-valued coordinates Algorithm
- Certified Hermitian eigenvalue intervals from residual and Gram bounds Algorithm
- Certified range evaluation for elementary real and complex functions Algorithm
- Finite certified Airy power-series evaluation Algorithm
- Finite certified evaluation of Gamma and a continued log-Gamma branch Algorithm
- Finite certified evaluation of integer-order Bessel functions Algorithm
- Finite certified evaluation of the scaled complementary error function Algorithm
- Finite certified power-series evaluation for Fresnel, erf, and Gauss functions Algorithm
- Finite checker for rational residual-tube certificates Algorithm
- Finite complex contour resolvent validator with cover and inconclusive statuses Algorithm
- Finite precision point linear solve certificate with explicit status Algorithm
- Finite primitive and contracted Gaussian integral evaluation with certified screening Algorithm
- Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms Algorithm
- Finite-budget certified evaluation of Boys function tables Algorithm
- Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration Algorithm
- Finite-budget stable block reordering for Schur and QZ forms Algorithm
- Finite-budget validated range evaluation Algorithm
- Interval Krawczyk linear system certifier with explicit statuses Algorithm
- Outward interval block LDL inertia certifier with pivot-inconclusive status Algorithm
- Outward Leibniz determinant sign and nonsingularity certifier Algorithm
- Outward-bounded floating determinant filter Algorithm
- Uniform interval linear residual certificate with inconclusive status Algorithm
- Certified special-function enclosure result Definition
- A nearly cocircular quadruple has a certified lifted sign Example
- A nearly collinear dyadic triangle falls through to the exact sign Example
- An uncertain coordinate interval does not decide orientation Example
- Division of [1,2] by [-1,1] has no finite hull Example
- Natural interval subtraction loses repeated-input correlation Example
- Certified Gaussian gridding terminates with a defined status Lemma
- Finite Riccati candidate, Newton-Kleinman, and doubling wrappers return a status Lemma
- Upward and downward Boys recurrence error amplification bounds Lemma
- Verified Lyapunov residual, descent, and stability checks make an inexact Newton-Kleinman step safe Proposition
- A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball Theorem
- A certified floating determinant filter returns only the exact sign Theorem
- A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root Theorem
…and 27 more results.
Cited to discharge well-definedness by Outward-rounded interval, rectangle and ball operations.
Dependency tree · two levels
9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Kearfott, Interval Computations: Introduction, Uses, and Resources, §1 (standard reference, not scraped)
- Rump, Verification methods: Rigorous results using floating-point arithmetic, §5.5 (standard reference, not scraped)