Differential Equation Axiomatization
The Impressive Power of Differential Ghosts

arXiv:1802.01226v1 [cs.LO] 5 Feb 2018

André Platzer

Yong Kiam Tan ∗

Abstract
We prove the completeness of an axiomatization for differential equation invariants. First,
we show that the differential equation axioms in differential dynamic logic are complete for
all algebraic invariants. Our proof exploits differential ghosts, which introduce additional variables that can be chosen to evolve freely along new differential equations. Cleverly chosen
differential ghosts are the proof-theoretical counterpart of dark matter. They create new hypothetical state, whose relationship to the original state variables satisfies invariants that did not
exist before. The reflection of these new invariants in the original system enables its analysis.
We then show that extending the axiomatization with existence and uniqueness axioms
makes it complete for all local progress properties, and further extension with a real induction
axiom makes it complete for all real arithmetic invariants. This yields a parsimonious axiomatization, which serves as the logical foundation for reasoning about invariants of differential
equations. Moreover, our approach is purely axiomatic, and so the axiomatization is suitable
for sound implementation in foundational theorem provers.
Keywords: differential equation axiomatization, differential dynamic logic, differential ghosts

1

Introduction

Classically, differential equations are studied by analyzing their solutions. This is at odds with
the fact that solutions are often much more complicated than the differential equations themselves.
The stark difference between the simple local description as differential equations and the complex global behavior exhibited by solutions is fundamental to the descriptive power of differential
equations.
Poincaré’s qualitative study of differential equations crucially exploits this difference by deducing properties of solutions directly from the differential equations. This paper completes an
important step in this enterprise by identifying the logical foundations for proving invariance properties of polynomial differential equations.
We exploit the differential equation axioms of differential dynamic logic (dL) [13, 15]. dL is a
logic for deductive verification of hybrid systems that are modelled by hybrid programs combining discrete computation (e.g., assignments, tests and loops), and continuous dynamics specified
∗

Computer Science Department, Carnegie Mellon University, Pittsburgh, USA {aplatzer|yongkiat}@cs.cmu.edu

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

using systems of ordinary differential equations (ODEs). By the continuous relative completeness
theorem for dL [13, Theorem 1], verification of hybrid systems reduces completely to the study of
differential equations. Thus, the hybrid systems axioms of dL provide a way of lifting our findings
about differential equations to hybrid systems. The remaining practical challenge is to find succinct real arithmetic system invariants; any such invariant, once found, can be proved within our
calculus.
To understand the difficulty in verifying properties of ODEs, it is useful to draw an analogy
between ODEs and discrete program loops.1 Loops also exhibit the dichotomy between global
behavior and local description. Although the body of a loop may be simple, it is impractical for
most loops to reason about their global behavior by unfolding all possible iterations. Instead, the
premier reasoning technique for loops is to study their loop invariants, i.e., properties that are
preserved across each execution of the loop body.
Similarly, invariants of ODEs are real arithmetic formulas that describe subsets of the state
space from which we cannot escape by continuously following the local dynamics specified by the
ODEs. The three basic dL axioms for reasoning about such invariants are: (1) differential invariants, which prove simple invariants by analyzing their local (Lie) derivatives, (2) differential cuts,
which refine the state space with additional provable invariants, and (3) differential ghosts, which
add differential equations for new ghost variables to the existing system of differential equations.
We may relate these reasoning principles to their discrete loop counterparts: (1) corresponds to
loop induction and analysis of the loop body, (2) corresponds to progressive refinement of the loop
guards, and (3) corresponds to adding discrete ghost variables to remember intermediate program
states. At first glance, differential ghosts seem counter-intuitive: they increase the dimension of
the system, and should be adverse to analyzing it! However, just as discrete ghosts [11] allow the
expression of new relationships between variables along execution of a program, differential ghosts
that suitably co-evolve with the ODEs crucially allow the expression of new relationships along
solutions to the differential equations. Unlike the case for discrete loops, differential cuts strictly
increase the deductive power of differential invariants for proving invariants of ODEs; differential
ghosts further increase this deductive power [14].
This paper has the following contributions:
1. We show that all algebraic invariants, i.e., where the invariant set is described by a formula
formed from finite conjunctions and disjunctions of polynomial equations, are provable using
only the three ODE principles outlined above.
2. We introduce two axioms internalizing the existence and uniqueness theorems for solutions
of differential equations. We show that they suffice for reasoning about all local progress
properties of ODEs for all real arithmetic formulas.
3. We introduce a real induction axiom that allows us to reduce invariance to local progress.
The resulting calculus can prove all real arithmetic invariants of differential equations.
1

In fact, this analogy can be made precise: dL also has a converse relative completeness theorem [13, Theorem 2]
that reduces ODEs to discrete Euler approximation loops.

2

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Just as discrete ghosts can make a program logic relatively complete [11], our first completeness result shows that differential ghosts do the same for algebraic invariants in dL. We extend
the result to larger classes of hybrid programs, including, e.g., loops that switch between multiple
different ODEs.
We note that there already exist prior, complete procedures for checking algebraic, and real
arithmetic invariants of differential equations [7, 9]. Our result identifies a list of axioms that
serve as a logical foundation from which these procedures can be implemented as derived rules.
This logical approach allows us to precisely understand the underlying properties of differential
equations that are needed for invariance reasoning. Our axiomatization is also not limited to invariance properties, and other qualitative properties such as local progress can also be proved with
the axiomatization.
Finally, our axioms are a list of concrete formulas without any side conditions. This is crucial
to make our axiomatization amenable to sound implementation and verification in foundational
theorem provers [6, 3] using dL’s uniform substitution calculus [15], and is in stark contrast to
previous highly schematic procedures [7, 9].
Some of our results appear in a previous technical report [16]. We take a more elegant axiomatization here, which gives significantly simpler correctness proofs.

2

Background

This section briefly reviews the relevant continuous fragment of dL, and establishes the notational
conventions that we will use in this paper. We refer readers to the literature [13, 15] and Appendix A for a complete exposition of dL, including its discrete fragment.

2.1

Syntax

Terms in dL are generated by the following grammar, where x is a variable, and c is a rational
constant:
e ::= x | c | e1 + e2 | e1 · e2
These terms correspond to polynomials over the variables under consideration. For the purposes
of this paper, we write x to refer to a vector of variables x1 , . . . , xn , and we use p(x), q(x) to
stand for polynomial terms over these variables. When the variable context is clear, we write p, q
without arguments instead. Vectors of polynomials are written in bold p, q, with pi , qi for their
i-th components.
The formulas of dL are given by the following grammar, where ∼ is a comparison operator
=, ≥, >, and α is a hybrid program:
φ ::= e1 ∼ e2 | φ1 ∧ φ2 | φ1 ∨ φ2 | φ1 → φ2 | ¬φ | ∀x φ | ∃x φ | [α]φ | hαiφ
By appropriately normalizing terms, it is enough to assume that all the formulas of the form e1 ∼ e2
have 0 on the right-hand side. We write p & 0 if there is a free choice of & between ≥ or >.
def

We define p . 0 ≡ −p & 0, where . stands for ≤ or <, and & is correspondingly chosen.
3

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

1

0

-1

-2

0

2

Figure 1: A visualization of αe . The red dashed circle u2 + v 2 = 1 is approached by solutions from
all points except the origin. Both the circle and the blue region u2 ≤ v 2 + 32 are invariants of the
system.
Other logical connectives, such as ↔ can be defined similarly. We write P (x), Q(x) for firstorder formulas of real arithmetic, i.e., formulas not containing the modal connectives. We drop the
dependency on x when the variable context is clear. The modal formula [α]φ is true iff φ is true
after all transitions of α, and its dual hαiφ is true iff φ is true after some transition of α.
Hybrid programs α allow us to express both discrete and continuous dynamics. We shall primarily use the continuous fragment2 :
α ::= · · · | x0 = f (x) & Q
We write x0 = f (x) & Q for an autonomous vectorial ODE system in variables x1 , . . . , xn where
the RHS of the system for each xi is a polynomial term fi (x). The evolution domain constraint
Q is a formula of real arithmetic, which restricts the set of states in which we are allowed to
continuously evolve. When Q ≡ true, we write x0 = f (x). We will use the following system,
which is visualized in Fig. 1 as a running example:
def

αe ≡ u0 = −v + u(1 − u2 − v 2 ), v 0 = u + v(1 − u2 − v 2 )
Following our analogy in Section 1, solutions of x0 = f (x) must continuously (locally) follow
its RHS, f (x). We visualize this in Fig. 1 with directional arrows corresponding to the RHS of αe
evaluated at points on the plane. Even though the RHS of αe are polynomials, its solutions, which
must locally follow the arrows, already exhibit complex global behavior. In Fig. 1, we see, e.g.,
that all points (except the origin) globally evolve towards the unit circle.
2

We only consider weak-test dL, where Q is a first-order formula of real arithmetic.

4

A. Platzer and Y. K. Tan

2.2

Differential Equation Axiomatization

Semantics

A state ω : V → R assigns a real value to each variable in the (finite) set V. We may let V =
{x1 , . . . , xn } since we only need to consider the variables occurring in differential equations x0 =
f (x). Hence, we shall also write states as n-tuples ω : Rn where the i-th component is the value
of xi in that state.
Terms are given the usual interpretation in first-order real arithmetic with respect to a state.
We write ω[[e]] for the valuation of term e in state ω. The semantics of comparison operations
and logical connectives (except the modal ones) are also defined in the standard way. We write
[[φ]] for the set of states in which φ is true. For example, ω ∈ [[e1 ≤ e2 ]] iff ω[[e1 ]] ≤ ω[[e2 ]], and
ω ∈ [[φ1 ∧ φ2 ]] iff ω ∈ [[φ1 ]] and ω ∈ [[φ2 ]].
Hybrid programs are interpreted as transition relations, [[α]] ⊆ Rn × Rn , between states. In
particular, the transition semantics of a system of ODEs is defined as:
(ω, ν) ∈ [[x0 = f (x) & Q]] iff there is T ≥ 0 and a function
ϕ : [0, T ] → Rn with ϕ(0) = ω, ϕ(T ) = ν, ϕ |= x0 = f (x) & Q
The ϕ |= x0 = f (x) & Q condition checks that ϕ is indeed a solution of the system x0 = f (x),
and that ϕ(ζ) ∈ [[Q]] for all ζ ∈ [0, T ]. Given any such solution ϕ, we may restrict its interval of
def
definition to obtain a truncation ϕ|ζ : [0, ζ] → Rn , where ϕ|ζ (τ ) = ϕ(τ ) for all τ ∈ [0, ζ]. Since
all such truncations are themselves solutions, we also have (ω, ϕ(ζ)) ∈ [[x0 = f (x) & Q]] for all
ζ ∈ [0, T ].
Finally, ω ∈ [[[α]φ]] iff for all states ν such that (ω, ν) ∈ [[α]], φ is true in ν. Dually, ω ∈ [[hαiφ]]
iff there exists a state ν, where (ω, ν) ∈ [[α]] and φ is true in ν.
Formulas P , where the formula P → [x0 = f (x) & Q]P is valid, are called invariants of the
system x0 = f (x) & Q. Unfolding the semantics above, this means that from any initial state ω ∈
[[P ]], any solution ϕ from ω, which does not leave the evolution domain [[Q]], stays in [[P ]] for its
entire duration.
Returning to Fig. 1, we immediately identify several invariants. The unit circle, u2 + v 2 = 1, is
an equational invariant because the direction of flow on the circle is always tangential to the circle.
The region described by u2 ≤ v 2 + 23 is also invariant. This is not immediately obvious, however,
and requires a careful proof. The equilibrium point at the origin is also trivially invariant.

2.3

Differentials and Lie Derivatives

The Lie derivative of a polynomial p along x0 = f (x) is:
def

Lf (x) (p) =

X ∂p
fi (x) = ∇p · f (x)
∂x
i
x
i

For polynomial differential equations and polynomials p, Lf (x) (p) is also a polynomial. We shall
.
write p for Lf (x) (p), because x0 = f (x) will be clear from the context. We use Lf (x) (·) only when
considering Lie derivation as an operator. Note that Lf (x) (·) satisfies the familiar sum and product
rules of differentiation.
5

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

A calculus for reasoning about differential equations must suitably handle Lie derivatives. The
uniform substitution calculus [15] for dL uses the differential, (p)0 , and differential variables x0 . As
.
the notation suggests, (p)0 is closely related to p. By the differential lemma [15, Lemma 35], along
solutions to the system x0 = f (x), the value of the differential, (p)0 , coincides exactly with that of
.
the Lie derivative p. This is internalized in dL by the differential effect axiom DE, and axioms for
computing derivatives by axioms for differentials c0 ,x0 ,+0 ,·0 [15, Lemmas 36-37]. Crucially, these
axioms allow Lie derivation to be performed purely syntactically and mechanically. For this paper,
we work directly with the Lie derivatives. Under the hood, the computation of these Lie derivatives
is done using differentials and DE, as we show in Appendix A.2.
. (i)
We write p for the i-th Lie derivative of p along x0 = f (x), where higher Lie derivatives
are defined by iterating the Lie derivation operator. By the aforementioned closure property of
polynomials under derivation, all of the higher Lie derivatives of p exist, and are also polynomials
in the indeterminates x.
. (0) def

p

2.4

= p,

. (i+1) def

p

. (i)

= Lf (x) (p ),

. def . (1)

p=p

Axiomatization

The reasoning principles for differential equations in dL are stated as axioms in its uniform substitution calculus [15, Figure 3]. For ease of presentation in this paper, we shall work with a sequent
calculus presentation, with derived rule versions of these principles. The derivation of these rules
from the axioms is shown in Appendix A.2.
We assume a standard classical sequent calculus with all the usual rules for manipulating logical connectives and sequents, e.g., ∨L,∃R, and cut. Since we are only reasoning about a single
succedent, we gather all additional context in the antecedents as Γ. In addition, because the theory
of first-order real arithmetic is decidable [2], we assume access to such a decision procedure, and
we label steps with R whenever they follow as a consequence of first-order real arithmetic. We
write ∗ to indicate a completed (closed) derivation.
Theorem 1 (Differential equation axiomatization [15]). The following sound proof rules derive
from the axioms of dL:
.
Γ, Q ` p = 0
Q`p=0
dI=
Γ ` [x0 = f (x) & Q]p = 0
.
Γ, Q ` p & 0
Q`p≥0
dI&
(where & is either ≥ or >)
Γ ` [x0 = f (x) & Q]p & 0
Γ ` [x0 = f (x) & Q]C
Γ ` [x0 = f (x) & Q ∧ C]P
dC
Γ ` [x0 = f (x) & Q]P
Q`P
dW
Γ ` [x0 = f (x) & Q]P
Γ ` ∃y [x0 = f (x), y 0 = a(x) · y + b(x) & Q]P
dG
Γ ` [x0 = f (x) & Q]P

6

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Differential invariants (dI) reduces questions about invariance of p = 0, p & 0 to questions
about their respective Lie derivatives. In this way, it reduces a global invariance property (along
solutions of the ODE) to a question about its local Lie derivatives. We have only shown two
instances (dI= ,dI& ) of the more general dI rule [15] that we will need for this paper. These instances
internalize the mean value theorem3 (see Appendix A.2). Differential cut (dC) asserts that if we
can separately prove that the systems never leaves C while staying in Q (the left premise), then we
may additionally assume C when proving the postcondition P (the right premise).
Once we have sufficiently enriched the evolution domain using dI,dC, differential weakening
(dW) allows us to remove the ODEs, and instead prove the postcondition P directly from the
evolution domain constraint Q. In the same vein, the following derived rule and axiom from dL
will be useful to manipulate postconditions:
M[·]

φ2 ` φ1
Γ ` [α]φ2
Γ ` [α]φ1

[·]∧ [α](φ1 ∧ φ2 ) ↔ [α]φ1 ∧ [α]φ2

The M[·] monotonicity rule allows us to strengthen the postcondition to φ2 if it implies φ1 . The
[·]∧ axiom allows us to prove conjunctive postconditions separately.
Even if dC increases the deductive power over dI, the deductive power increases even further [14] with the differential ghosts rule dG. It allows us to add a fresh variable y to the system
of equations. The main soundness restriction of dG is that the new ODE must be linear4 in y. This
restriction is enforced by ensuring that a(x), b(x) do not mention y. For our purposes, we will
allow y to be vectorial, i.e. we allow the existing differential equations to be extended by a system
that is linear in a vector of variables y. In this setting, a(x) (resp. b(x)) is a matrix (resp. vector)
of polynomials in x.
As mentioned, adding auxiliary differential ghost variables using dG crucially allows us to
express new relationships between variables along the differential equations. The next section
shows how dG can be used along with the rest of the rules to prove a class of invariants satisfying
Darboux-type properties. We exploit this increased deductive power in full in later sections.

3

Darboux Polynomials

This section illustrates the use of dG in proving invariance properties involving Darboux polynomials [5]. A polynomial p is a Darboux polynomial for the system x0 = f (x) iff it satisfies the
.
polynomial identity p = gp for some polynomial cofactor g.

3.1

Darboux Equalities

We first recall the following useful notion from algebraic geometry:
3

.

Note that for rule dI& , we only require p ≥ 0 even for the p > 0 case.
4
Linearity prevents the newly added equation from unsoundly restricting the duration of existence for solutions to
the differential equations.

7

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Definition 1 (Ideal [2]). The ideal generated by the polynomials p1 , . . . , ps ∈ R[x] is defined as
the set of polynomials5 :
def
s
(p1 , . . . , ps ) = {Σi=1 gi pi : gi ∈ R[x]}
.

Let us assume that p satisfies the Darboux polynomial identity p = gp. Taking Lie derivatives
on both sides, we get:
. (2)

p

.

=Lf (x) (p) = Lf (x) (gp) = Lf (x) (g)p + Lf (x) (p)g
.

.

.

=gp + pg = (g + g 2 )p ∈ (p)
By repeatedly taking Lie derivatives, it is easy to see that all higher Lie derivatives of p are contained in the ideal (p). Now, let us consider an initial state ω where p evaluates to ω[[p]] = 0, then
we have:
.
ω[[p]] = ω[[gp]] = ω[[g]] · ω[[p]] = 0
Similarly, because every higher Lie derivative of a Darboux polynomial is contained in the ideal
generated by p, all of them are simultaneously 0 in state ω. Thus, it should be the case6 that
p = 0 stays invariant along solutions to the ODE starting at ω. The question is how to prove it
axiomatically.
In the first derivation below, we give a proof of invariance for p = 0 using dG. We explain the
derivation in detail as it further illustrates the use of the surrounding proof calculus.
Lemma 2 (Darboux equalities are differential ghosts). The proof rule for Darboux equalities derives from dG (and dI):
.
Q ` p = gp
dbx
p = 0 ` [x0 = f (x) & Q]p = 0
Proof. Let 1 denote the use of the premise of dbx, and 2 abbreviate the right premise in the
following derivation.
p=0 `
[·]∧,∧R
p = 0, y 6= 0 `
M[·],∃R
p=0`
dG
p=0`

2
[x0 = f (x), y 0 = −gy & Q]py=0
0
0
[x = f (x), y = −gy & Q](y 6= 0 ∧ py = 0)
∃y [x0 = f (x), y 0 = −gy & Q]p = 0
[x0 = f (x) & Q]p = 0

In the first dG step, we introduce a new ghost variable y satisfying a carefully chosen differential
equation y 0 = −gy as a counterweight. Next, ∃R allows us to pick an initial value for y. We simply
pick any y 6= 0. We then observe that in order to prove p = 0, it suffices to prove the stronger
invariant y 6= 0 ∧ py = 0, so we use the monotonicity rule M[·] to strengthen the postcondition.
Next, [·]∧,∧R lets us prove each conjunct in the new postcondition separately.
5
6

R[x] denotes the ring of polynomials in indeterminates x.
This requires the solutions to the ODEs to be analytic, which is the case here.

8

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Continuing on the left premise:
∗
∗

1

R

p = 0 ` py = 0

dI

R

cut

` gpy − gyp = 0

.

Q ` py − gyp = 0

p = 0 ` [x0 = f (x), y 0 = −gy & Q]py = 0

We use dI to prove the equational invariant py = 0; its left premise is a consequence of real
arithmetic. On the right premise, we compute the Lie derivative of py using the usual product rule
as follows:
.
Lf (x),−gy (py) = Lf (x),−gy (p)y + pLf (x),−gy (y) = py − gyp
We complete the derivation by cutting in the premise of dbx ( 1 ). Note that our choice of differential ghost y 0 = −gy was precisely chosen so that the final arithmetic step closes trivially.
The remaining premise 2 is:
y 6= 0 ` [x0 = f (x), y 0 = −g(x)y & Q]y 6= 0
Its proof continues using a second ghost z 0 = gz:
∗
`
dI
yz = 1 `
M[·],∃R
y 6= 0 `
dG
y 6= 0 `
R

−(gy)z + y(gz) = 0
[x0 = f (x), y 0 = −gy, z 0 = gz & Q]yz = 1
∃z [x0 = f (x), y 0 = −gy, z 0 = gz & Q]y 6= 0
[x0 = f (x), y 0 = −gy & Q]y 6= 0

This derivation is similar to the one for the previous premise. In the M[·],∃R step, we observe that
if y 6= 0 initially, then there exists z such that yz = 1. Moreover, yz = 1 is sufficient to imply
y 6= 0 in the postcondition. The differential ghost z 0 = gz is chosen so that yz = 1 can be proved
invariant along the differential equation.
Fig. 2 illustrates the effect of the second ghost in the proof above for g = −1, where y = 1, z =
1 initially. Although y decays exponentially towards y = 0, the ghost z balances this by growing
exponentially so that yz stays constant at its initial value 1.

3.2

Darboux Inequalities

Using a variation of the derivation proving Lemma 2, we can also derive invariant inequality properties for Darboux polynomials using dG. In fact, we will only require that p satisfies a Darboux
.
inequality p ≥ gp for some cofactor polynomial g.
Lemma 3 (Darboux inequalities are differential ghosts). The proof rule for Darboux inequalities
derives from dG (and dI,dC):
.

Q ` p ≥ gp
dbx&
p & 0 ` [x0 = f (x) & Q]p & 0
9

(where & is either ≥ or >)

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

3

2

1

0

0.2

0.4

0.6

0.8

1

Figure 2: The differential ghost z 0 = z (in orange) balances out y 0 = −y (in blue) so that the value
of yz (the red dotted line) remains constant at 1. The horizontal axis tracks the evolution of time.
Proof Summary (See Appendix C). The derivation is similar to the one used for Lemma 2; we use
the same first choice of differential ghost y 0 = −gy. However, instead of y 6= 0 ∧ py = 0, we prove
a stronger sign condition on y, namely y > 0 ∧ py & 0. Consequently, in the second differential
ghost step, we use z 0 = g2 z and prove the invariant yz 2 = 1, which implies y > 0.
Example 1 (Proving continuous properties in dL). Returning to the running example, we show that
the unit circle u2 + v 2 − 1 = 0 is an equational invariant for αe . This follows by an immediate
application of dbx with cofactor −2(u2 + v 2 ):
R
dbx

∗
` L αe
+ − 1) = −2(u2 + v 2 )(u2 + v 2 − 1)
u2 + v 2 − 1 = 0 ` [αe ]u2 + v 2 − 1 = 0
(u2

v2

By a similar derivation with dbx&, we can show that the disk u2 + v 2 − 1 & 0 and its complement
are inequational invariants.
These derivations demonstrate the clever use of differential ghosts. In fact, we have already
exceeded the deductive power of dI,dC because the formula y > 0 → [y 0 = −y]y > 0 is valid but
not provable with dI,dC alone but needs a dG [14]. It is a simple consequence of dbx&, since the
.
polynomial y satisfies the Darboux equality y = −y with cofactor −1. We can intuitively see why
this is difficult from Fig. 2; y evolves exponentially towards y = 0, i.e., we get closer to violating
the postcondition y > 0 along the solution.

4

Algebraic Invariants

We now consider polynomials that are not Darboux for the given differential equations, but instead
satisfy a differential radical property [7] with respect to its higher Lie derivatives. Let gi be cofactor
10

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

polynomials, we assume that p satisfies the polynomial identity:
. (N )

p

=

N
−1
X

. (i)

gi p

(1)

i=0

Following the intuition from Section 3.1, we again take Lie derivatives on both sides of the
equation:
. (N +1)

p

. (N )

=Lf (x) (p

N
−1
X

) = Lf (x) (

. (i)

gi p ) =

i=0

=

N
−1 
X

. . (i)

gi p

. (i+1)

+ gi p



N
−1
X

. (i)

Lf (x) (gi p )

i=0
.

. (N −1)

∈ (p, p, . . . , p

)

i=0
. (N )

In the last step, ideal membership follows by observing that, by (1), p is contained in the ideal
generated by the lower Lie derivatives. By repeatedly taking Lie derivatives on both sides, we
. (N ) . (N +1)
.
. (N −1)
again see that p , p
, . . . are all contained in the ideal (p, p, . . . , p
). Thus, if we start in
.
. (N −1)
state ω where ω[[p]], ω[[p]], . . . , ω[[p
]] all simultaneously evaluate to 0, then p = 0 (and all of its
higher Lie derivatives) must stay invariant along solutions to the ODE.
This section shows how to axiomatically prove this invariance property using (vectorial) dG.
We shall see at the end of the section that this allows us to prove all true algebraic invariants.

4.1

Vectorial Darboux Equalities

We first derive a vectorial generalization of the Darboux rule dbx, which will allow us to derive the
rule for algebraic invariants as a special case by exploiting a vectorial version of (1). Let us assume
.
that the n-dimensional vector of polynomials p satisfies the vectorial polynomial identity p = Gp,
.
where G is an n × n matrix of polynomials, and p denotes component-wise Lie derivation of p.
def
Similarly, let ω[[p]] be the vector where (ω[[p]])i = ω[[pi ]]. In states ω where ω[[p]] = 0, we have
.
ω[[pi (x)]] = 0 for all i, and therefore, ω[[p]] = ω[[Gp]] = 0.
Lemma 4 (Vectorial Darboux equalities are vectorial ghosts). The vectorial Darboux proof rule
derives from vectorial dG.
.

Q ` p = Gp
vdbx
p = 0 ` [x0 = f (x) & Q]p = 0
Proof. Let G be an n × n matrix of polynomials, and p be an n-dimensional vector of polynomials
satisfying the premise of vdbx.
First, we develop a proof that we will have occasion to use repeatedly. This proof adds an
n-dimensional vectorial ghost y such that the vanishing of the scalar product, i.e., p · y = 0, is a
provable invariant. In the derivation below, we have suppressed the initial choice of values for y.

11

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

1 denotes the use of the premise of vdbx. In the dC step, we mark the remaining open premise
with 2 .
∗
R

Q ` Gp · y − Gp · y = 0
Q ` Gp · y − p · GT y = 0

R

1
.

cut
dI

2

Q ` p · y − p · GT y = 0

p · y = 0 ` [x0 = f (x), y0 = −GT y & Q]p · y = 0

dC

p = 0 ` ∃y [x0 = f (x), y0 = −GT y & Q]p = 0

dG

p = 0 ` [x0 = f (x) & Q]p = 0

The open premise 2 now includes p · y = 0 in the evolution domain:
2

p = 0 ` [x0 = f (x), y0 = −GT y & Q ∧ p · y = 0]p = 0

The proof thus far is similar to the first ghost step in dbx. Unfortunately, for n > 1, the
postcondition p = 0 does not follow from the evolution domain constraint p · y = 0 even when
y 6= 0, because p · y = 0 merely implies that p and y are orthogonal, not that p is 0.
The idea is to repeat the above proof sufficiently often to obtain an entire matrix Y of differential ghost variables such that both Y p = 0 and det(Y ) 6= 0 can be proved invariant.7 The latter
implies that Y is invertible, so that Y p = 0 implies p = 0.
We obtain the matrix Y by repeating n times the derivation above on the premise 2 , using dG
to add n copies of the ghost vectors, y1 , . . . , yn , each satisfying the system yi0 = −GT yi . As we
have seen above, each of these ghost vectors satisfies the provable invariant yi · p = 0. We write
this concisely as a system of equations:
Y

z






y11
y21
..
.

}|
y12 . . .
y22 . . .
..
..
.
.

yn1 yn2 . . .

p
{ z }| {
y1n
p1
y1n 
p2 

=0
..  
.  ... 
pn
ynn

Using dI,[·]∧, we prove:
0

p=0 ` [x =

f (x), y10

T

= −G

y1 , . . . , yn0

T

= −G yn & Q]

n
^

yj · p=0

j=1

which we summarize using the above matrix notation as:
3

p = 0 ` [x0 = f (x), Y 0 = −Y G & Q]Y p = 0

For a square matrix of polynomials Y , we write det(Y ) for its determinant, Y T for its transpose, adj(Y ) for its
adjugate, and tr(Y ) for its trace.
7

12

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

because when Y 0 is the component-wise derivative of Y , all the differential ghost equations are
summarized as Y 0 = −Y G.8 Now that we have the invariant Y p = 0 from 3 , it remains to show
the invariance of det(Y ) > 0 to complete the proof.
Since Y only contains yij variables, det(Y ) is a polynomial term in the variables yij . These
yij are ghost variables that we have introduced, and so we are free to pick their initial values. For
convenience, we shall pick initial values forming the identity matrix Y = I, so that det(Y ) =
det(I) = 1 > 0 is true initially.
In order to show that det(Y ) > 0 is an invariant, we first observe the following critical polynomial identity:
.
.


det(Y ) = tr(adj(Y )Y ) = tr adj(Y )(−Y G) = − tr (Y T adj(Y ))G

= − tr det(Y ) I G = − tr (G) det(Y )

The first equality is Liouville’s formula [21, §15.III], and the others are properties of linear algebra.
We take Lie derivatives with respect to the extended system of equations x0 = f (x), Y 0 = −Y G.
Thus, det(Y ) is a Darboux polynomial over the variables yij , with polynomial cofactor − tr(G).
Therefore, this is a valid deduction:
.

4

Q ` det(Y ) = − tr(G) det(Y )
dbx&
det(Y )>0 ` [x0 = f (x), Y 0 = −Y G & Q] det(Y )>0

Putting 3 and 4 together allows us to complete the derivation for the invariance of p = 0.
We start with the dG step, and abbreviate the ghost matrix as above.
p = 0 ` ∃Y [x0 = f (x), Y 0 = −Y G & Q]p = 0
p = 0 ` ∃y1 , . . . , yn [x0 = f (x), y10 = −GT y1 , . . . , yn0 = −GT yn & Q]p = 0
dG

p = 0 ` [x0 = f (x) & Q]p = 0

Now, we carry out the rest of the proof as outlined above.
∗
Q ∧ Y p=0 ∧ det(Y )>0 `
dW
4
p=0 `
dC
3
p=0, det(Y )>0 `
dC
p=0, det(Y )>0 `
cut
p=0, Y = I `
∃R
p=0 `
R

p=0
[x0 = f (x), Y 0 = −Y G & Q ∧ Y p=0 ∧ det(Y )>0]p=0
[x0 = f (x), Y 0 = −Y G & Q ∧ Y p = 0]p=0
[x0 = f (x), Y 0 = −Y G & Q]p=0
[x0 = f (x), Y 0 = −Y G & Q]p=0
∃Y [x0 = f (x), Y 0 = −Y G & Q]p=0

The order of the differential cuts 3 and 4 is irrelevant.
This can be seen explicitly by examining the entries on both sides of the differential equations: Yij0 = (yij )0 =
Pn
Pn
Pn
−(GT yi )j = − k=1 GTjk yik = − k=1 Gkj yik = − k=1 yik Gkj = −(Y G)ij .
8

13

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Since det (Y ) 6= 0 is invariant, we can view the n × n ghost matrix Y in the proof of vdbx as a
basis matrix for Rn that continuously evolves along the differential equations. To see what Y does
geometrically, let p0 be the initial values of p, and Y = I initially. With our choice of Y , we can
show, using a variation of 3 in the proof of vdbx, that Y p=p0 is invariant. Thus, the evolution of
Y balances out the evolution of p, so that p remains constant with respect to the evolving basis Y .
This generalizes the intuition illustrated in Fig. 2 to the n-dimensional case. Crucially, differential
ghosts let us express this time-varying change of basis purely syntactically.

4.2

Differential Radical Invariants

We now return to polynomials p satisfying property (1), and show how to prove p = 0 invariant
using an instance of vdbx.
Theorem 5 (Differential radical invariants are vectorial Darboux). The differential radical invariant proof rule derives from vdbx (which in turn derives from vectorial dG).
V −1 . (i)
P −1 . (i)
. (N )
Γ, Q ` N
=0 Q`p
= N
i=0 p
i=0 gi p
dRI
Γ ` [x0 = f (x) & Q]p = 0
Proof Summary (See Appendix C).

0 1

 0 0

G =  ... ...

 0 0
g0 g1

This follows from vdbx with:


0
...
0
p
.
..
..
.. 
.
.
.
 p(1)



..
..
, p=
..
.
.
0 


.

. (N −1)
...
0
1
p
. . . gN −2 gN −1







The matrix G has 1 on its superdiagonal, and the gi cofactors in the last row. The left premise
of dRI is used to show p = 0 initially, while the right premise is used to show the premise of
vdbx.

4.3

Completeness for Algebraic Invariants

Algebraic formulas are formed from finite conjunctions and disjunctions of polynomial equations.
We may, however, restrict attention to a single equation p = 0 because all algebraic formulas can
be normalized to this form using the real arithmetic equivalences:
p = 0 ∧ q = 0 ↔ p2 + q 2 = 0,

p = 0 ∨ q = 0 ↔ pq = 0

The key insight behind completeness of dRI is that higher Lie derivatives stabilize. Since
the polynomials R[x] form a Noetherian ring, for every polynomial p and differential equation
x0 = f (x), there is a smallest natural number N called order [10, 7, 9] where:
. (N )

p

=

N
−1
X
i=0

14

. (i)

gi p

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

This N is computable by successive ideal membership checks [7].
Thus, a suitable order at which the right premise of dRI proves always exists for any polynomial
9
p. We call the succedent in the remaining left premise of dRI the differential radical formula.
. (∗)

Definition 2 (Differential radical formula). The differential radical formula p = 0 of a polynomial p with order N and Lie derivatives with respect to x0 = f (x) is defined to be:
. (∗)

p

def

=0 ≡

N
−1
^

. (i)

p

=0

i=0
. (−∗)

We write p

= 0 when the Lie derivatives are taken with respect to x0 = −f (x) instead.

The completeness of dRI can be proved semantically [7]. However, using the extensions developed in Section 5, we derive the following characterization for algebraic invariants axiomatically.
Theorem 6 (Algebraic invariant completeness). Let Q be a real arithmetic formula that characterizes an open set. The following is a derived axiom in dL:
. (∗)

DRI [x0 = f (x) & Q]p = 0 ↔ Q → p


=0

Proof Summary (See Appendix B.1). The “←” direction follows by an application of dRI (whose
right premise closes immediately for any Q). The “→” direction relies on the existence and
uniqueness of solutions to differential equations, which are internalized as additional axioms in
Section 5.
For the proof of Theorem 6, we emphasize that additional axioms are only required for syntactically deriving the “→” direction (completeness) of DRI. Hence, the base dL axiomatization with
differential ghosts is complete for proving properties of the form [x0 = f (x) & Q]p = 0 because
. (∗)
dRI reduces all such questions to Q → p = 0, which is a formula of real arithmetic, and hence,
decidable. The same applies for our next result, which is a corollary of Theorem 6, but applies
beyond the continuous fragment of dL.
Corollary 7 (Test-free decidability). Let α be a hybrid program without tests or evolution domain
constraints (see Appendix B.1), and P be an algebraic formula. There is a (computable) polynomial q such that the equivalence [α]P ↔ q = 0 is derivable in dL.
Proof Summary (See Appendix B.1). By structural induction on α, using Theorem 6 for the differential equations case.
. (N )

9

Our derivation shows that it is sound to additionally assume Q when proving ideal membership of p . However,
since the order of p exists even without this assumption, our rule may also be seen as an optimization that helps reduce
the number of Lie derivatives p that need to be considered.

15

A. Platzer and Y. K. Tan

5

Differential Equation Axiomatization

Extended Axiomatization

In this section, we present the axiomatic extensions that we will use for the rest of this paper.
Without loss of generality, we assume that the system of differential equations, x0 = f (x), already
contains t0 = 1, which makes t act as a clock to track the passage of time. Such a clock variable
can always be added using dG if necessary.

5.1

Existence, Uniqueness, and Continuity

The differential equations considered in this paper have polynomial right-hand sides, which are
smooth and analytic. In particular, they satisfy the premises of the Picard-Lindelöf theorem [21,
§10.VI], which guarantees that for any initial state ω ∈ Rn , a unique solution of the system
x0 = f (x), i.e. ϕ : [0, T ] → Rn with ϕ(0) = ω, exists for some non-empty time interval T > 0.
Moreover, the solution ϕ may be extended (uniquely) to its maximal open interval of existence [21,
§10.IX]. The solution ϕ(ζ) is, by definition, differentiable, and hence continuous with respect to ζ.
Lemma 8 (Existence, uniqueness and continuity). The following axioms are sound. In Cont, t0 is
a fresh variable (not in x, f (x) or p).
hx0 = f (x) & Q1 iP1 ∧ hx0 = f (x) & Q2 iP2
Uniq
→ hx0 = f (x) & Q1 ∧ Q2 i(P1 ∨ P2 )

Cont t = t0 → p > 0 → hx0 = f (x) & p > 0it 6= t0
Proof Summary (See Appendix A.3). Uniq internalizes uniqueness, while Cont internalizes continuity and existence of solutions.
Axiom Uniq can be intuitively read as follows. Suppose that we had two solutions ϕ1 , ϕ2
respectively staying in evolution domains Q1 , Q2 and whose endpoints satisfy P1 , P2 . Then one of
ϕ1 or ϕ2 is a prefix of the other, and therefore, the prefix stays in the evolution domain Q1 ∧ Q2 ,
and satisfies P1 ∨ P2 at its endpoint.
Axiom Cont uses the clock variable t to express a notion of local progress for differential
equations. Intuitively, it says that from the current time t0 , the system can locally progress to some
different time t 6= t0 by following the differential equations while staying in the open set of states
characterized by p > 0. This notion can be encoded in dL in several ways. We have used a clock
variable for simplicity. For emphasis, we use the following syntax for local progress within domain
Q:
def
hx0 = f (x) & Qi◦ ≡ hx0 = f (x) & Qit 6= t0
For the remaining derivations in this paper, we only encounter hx0 = f (x) & Qi◦ when we have an
assumption t = t0 . In this case, where ω[[t]] = ω[[t0 ]], the modality has the following semantics:
ω ∈ [[hx0 = f (x) & Qi◦]] iff there is a function ϕ : [0, T ] → Rn
with T > 0, ϕ(0) = ω, ϕ(T ) = ν, ϕ |= x0 = f (x) & Q

16

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

This resembles a continuous version of the next modality ◦ of temporal logic. For brevity, we
directly use hx0 = f (x) & Qi◦, and drop t = t0 from the antecedents, e.g., with this derived rule:
cont

p>0`

hx0

∗
= f (x) & p > 0i◦

To make use of Uniq and Cont, it will be useful to derive rules and axioms that allow us to
work directly in the diamond modality, rather than the box modality that we have used so far.
Corollary 9 (Derived diamond modality rules and axioms). The following derived rules and axioms are sound for dL:
Γ ` [x0 = f (x) & R]Q Γ ` hx0 = f (x) & RiP
h·idR
Γ ` hx0 = f (x) & QiP
R ` Q Γ ` hx0 = f (x) & RiP
h·idRW
Γ ` hx0 = f (x) & QiP
hx0 = f (x) & Q ∧ RiP
&∧
↔ hx0 = f (x) & QiP ∧ hx0 = f (x) & RiP
Proof Summary (See Appendix A.4). The h·idR rule derives from the diamond version of the dL
refinement axiom that underlies dC; if we never leave Q when staying in R (its left premise), then
any solution staying in R for its entire duration (its right premise) must also stay in Q for its entire
duration (its conclusion).
The rule h·idRW follows from h·idR by simplifying its left premise with dW. The equivalence
&∧ follows from h·idRW for the “→” direction, while the “←” direction is an instance of Uniq by
setting P1 , P2 to P , and Q1 , Q2 to Q, R respectively.

5.2

Real Induction

We state a symmetric version of the real induction principle [4].
Definition 3 (Inductive subset [4]). The subset S ⊆ [a, b] is called an inductive subset of the
interval [a, b] with reals a ≤ b iff:
1. a ∈ S
2. If a ≤ x < b and x ∈ S , then [x, x + ] ⊆ S for some 0 < 
3. If a < x ≤ b and x ∈ S { , then [x − , x] ⊆ S { for some 0 < , where we write S { for the
complement [a, b] \ S.
Proposition 10 (Real induction principle [4]). The subset S ⊆ [a, b] is inductive if and only if
S = [a, b].
Crucially, this induction principle can be lifted to invariance properties for differential equations. For brevity, we present the axiom for systems without evolution domain constraints, leaving
the general version to Appendix A.3.
17

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Lemma 11 (Real induction). The following real induction axiom and its corresponding derived
rule are sound (t0 is fresh).
[x0 = f (x)]P ↔ P ∧[x0 = f (x)]∀t0 t = t0 →

RInd
(P → hx0 = f (x) & P i◦) ∧ (¬P → hx0 = −f (x) & ¬P i◦)
P ` hx0 = f (x) & P i◦ ¬P ` hx0 = −f (x) & ¬P i◦
rInd
P ` [x0 = f (x)]P
Proof Summary (See Appendix A.3). The RInd axiom follows from the real induction principle and
the Picard-Lindelöf theorem. The rInd rule derives from RInd with dW.
RInd reduces invariance of P to local progress of P and local progress backwards of ¬P . Rule
rInd shows what this principle buys us: instead of a global invariance property on the ODEs, its
premises only require reasoning about local progress properties. These properties can be proved
using Cont,Uniq, as we show next.

6

Semialgebraic Invariants

Throughout this section, we will let Q ≡ true to simplify notation since Q is not central to our
remaining discussion.10 Any first-order formula of real arithmetic, P , characterizes a semialgebraic set, and by quantifier elimination [2] may equivalently be written as a finite, quantifier-free
formula (pij , qij are polynomials):
P ≡

m(i)
M
^
_
i=0

n(i)

pij = 0 ∨

j=0

_


qij > 0

(2)

j=0

We therefore refer to P as a semialgebraic formula, and the first step in our invariance proofs for
semialgebraic P will be to apply the rInd rule, yielding premises of the form (modulo sign changes
and negation): P ` hx0 = f (x) & P i◦.

6.1

Local Progress

Our objective shall be to derive local progress rules of the form
Γ`R
Γ, P ` hx0 = f (x) & P i◦
where R is a formula of real arithmetic, computable from the form of P . We proceed in cases,
starting from the simplest forms of P .
10

The case of arbitrary semialgebraic Q can be found in Appendix B.

18

A. Platzer and Y. K. Tan

6.1.1

Differential Equation Axiomatization

Atomic Equations
. (∗)

Let P ≡ p = 0. By Theorem 6, p = 0 is a sufficient condition for p = 0 to be invariant. It is
also a sufficient condition for local progress, i.e., we have the derived rule:
. (∗)

Γ`p =0
h·idRI
Γ, p = 0 ` hx0 = f (x) & p = 0i◦
which derives using cont and the trivial arithmetic fact 1 > 0:
. (∗)

∗
Γ`p =0
dRI
R,cont
Γ ` [x0 = f (x) & 1 > 0]p = 0
` hx0 = f (x) & 1 > 0i◦
h·idR
Γ, p = 0 ` hx0 = f (x) & p = 0i◦
6.1.2

Strict Open Inequalities
W
Let P ≡ ni=0 qi > 0. Topologically, this case is easy, because a continuous solution that starts
in an open set must locally stay in that open set. Indeed, the derivation here uses continuity, and
does not need any premises. We have collapsed the multiple (similar) cases arising
Wn from ∨L into a
single case, indexed by i. In the h·idRW step, we used the tautology qi > 0 → i=0 qi > 0.
∗
qi > 0 ` hx0 = f (x) & qi > 0i◦
W
h·idRW
qi > 0 ` hx0 = f (x) & ni=0 qi > 0i◦
W
W
∨L
Γ, ni=0 qi > 0 ` hx0 = f (x) & ni=0 qi > 0i◦
cont

We summarize with the following derived rule:
conto
6.1.3

Γ,

Wn

i=0 qi

>0`

hx0

∗
W
= f (x) & ni=0 qi > 0i◦

Mixed Equality and Strict Inequality
def

The interesting case arises with P ≡ p = 0 ∨ q > 0. The inequality pe ≥ 0, pe = v 2 − u2 + 23 in
our running example can be written in this form, because of the arithmetic equivalence p ≥ 0 ↔
p = 0 ∨ p > 0. We first note a simple reduction using ∨L:
∗
Γ, p = 0 ` hx = f (x) & p = 0 ∨ q > 0i◦
q > 0 ` ...
∨L
0
Γ, p = 0 ∨ q > 0 ` hx = f (x) & p = 0 ∨ q > 0i◦
h·idRW,cont

0

One possibility for dealing with the open (left) premise is to use h·idRI. However, this does not
. (∗)
provide necessary conditions in general. In our example, this would require us to show pe = 0,
i.e., points satisfying pe = 0 locally stay on pe = 0. From Fig. 1, this is clearly false because the
19

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

arrows at pe = 0 point inwards, i.e., towards pe > 0. More generally, the open premise requires
us to find conditions where we start on p = 0, but locally enter q > 0 for any q. However, the
disjunction in the evolution domain is not easy to work with in dL. We remove it with the following
observations:
V . (i)
V
. (i)
Proposition 12. Let r = p2 , then ni=0 p = 0 → n+1
= 0 is a consequence of real
i=0 r
arithmetic.
. (k)

Proof. Since r = p2 , applying the Leibniz rule yields that r

equals:

k  
k−1  
k−1  
X
X
k . (k−i) . (i)
k . (k−i) . (i) X k . (k−i) . (i)
. (k)
p
p = pp +
p
p =
p
p
i
i
i
i=0
i=0
i=0

The last equality follows by the assumption p = 0 (recall that n ≥ 0). Now, consider 0 ≤ k ≤ n+1.
. (i)
By assumption, for 0 ≤ i < k, p = 0, and therefore the remaining term in the sum is also 0. In
.
. (n+1)
other words, r = 0, r = 0, . . . , r
= 0.
V . (i)
Corollary 13. Let r = p2n for any n ∈ N, p = 0 → ni=0 r = 0 is a consequence of real
arithmetic.
Proof. By repeated squaring, and applying Proposition 12.
Using Corollary 13, we note that by choosing r = p2n for sufficiently large n ≥ 1, we have the
following derivation11 :
Γr ` hx0 = f (x) & q ≥ ri◦
h·idRW
h·idRW
cut

Γr ` hx0 = f (x) & r = 0 ∨ q > 0i◦
. (n)

Γ, r = 0, . . . , r

= 0 ` hx0 = f (x) & p = 0 ∨ q > 0i◦

Γ, p = 0 ` hx0 = f (x) & p = 0 ∨ q > 0i◦

The first h·idRW step, uses the arithmetic equivalence p = 0 ↔ p2n = 0. In the second h·idRW
step, we observe that since r = p2n ≥ 0, we have q ≥ r ≥ 0 which implies r = 0 ∨ q > 0 as
. (n)
required. We abbreviate the antecedents Γ extended with the r = 0, . . . , r = 0 assumptions
as Γr . The disjunction in the evolution domain constraint has been changed to a single weak
inequality. We work on this inequality with the following derived rules:
Lemma 14 (Local progress). These rules derive from cont,dI,dC.
Γ`q>r
lp>
0
Γ ` hx = f (x) & q ≥ ri◦
.
.
Γ ` q ≥ r Γ, q = r ` x0 = f (x) & q ≥ r ◦
lp≥
Γ ` hx0 = f (x) & q ≥ ri◦
With a more careful analysis in Proposition 12, we actually only need to pick r = p2(O(log n)) to achieve the same
conclusion.
11

20

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Proof. lp> derives from lp≥ , because q > r implies q ≥ r, but contradicts q = r (in the right
premise of lp≥ ). To derive lp≥ , let us denote the use of its left (resp. right) premise by 1 (resp. 2 ).
We start using 1 immediately, and then perform a simple arithmetic case split on the left. In the
q > r case, we apply cont and h·idRW to close the premise. The remaining premise arising from
the q = r case is abbreviated with 3 .
∗
cont

3
1
cut

R,∨L

q > r ` hx0 = f (x) & q > ri◦

h·idRW

Γ, q > r ` hx0 = f (x) & q ≥ ri◦

Γ, q ≥ r ` hx0 = f (x) & q ≥ ri◦

Γ ` hx0 = f (x) & q ≥ ri◦

On 3 , we continue by cutting in second premise of lp≥ . This allows us to use h·idR, and
subsequently finish the proof using dI.
∗
.

dI

2

.

q = r ` [x0 = f (x) & q ≥ r]q ≥ r
.

h·idR

.

q = r, x0 = f (x) & q ≥ r ◦ ` hx0 = f (x) & q ≥ ri◦

cut

Γ, q = r ` x0 = f (x)q ≥ r

Observe that lp≥ allows us to pass from reasoning about local progress for q ≥ r to local
.
.
progress for their Lie derivatives q ≥ r whilst accumulating q = r in the antecedent. It is clear,
then, that we can iterate application of the rule from the initial premise until we eventually apply
lp> :
. (k)
. (k)
Γ, q = r, . . . ` q > r
lp>
...
..
.
.
Γ, q = r ` q ≥ r
.
.

.

lp≥
Γ, q = r ` x0 = f (x) & q ≥ r ◦
Γ`q≥r
lp≥
Γ ` hx0 = f (x) & q ≥ ri◦

Gathering the succedents of the open premises above, we can instead directly prove the following
formula from antecedents Γ:
.
.
.
.
. (2)
. (2) 
q ≥r∧ q =r →q ≥r ∧ q =r∧q =r →q ≥r
∧...
.
.
. (k−1)
. (k−1)
. (k)
. (k) 
∧ q = r ∧ q = r ∧ ··· ∧ q
=r
→q >r
def

Working in antecedents Γ = Γr with r = p2k , we may equivalently prove this formula where all
of the Lie derivatives of r are set to 0 instead. Moreover, a sensible choice of k is N − 1, where N
.
. (N −1)
is the order of q. Recall, that if q, q, . . . , q
are simultaneously zero, then all higher derivatives
of q are also 0. This motivates the following definition that summarizes the above intuition:
21

A. Platzer and Y. K. Tan

Differential Equation Axiomatization
. (∗)

Definition 4 (Progress formula). The progress formula q > 0 for a polynomial q with order
N is defined as the following formula, where the Lie derivatives are computed with respect to
x0 = f (x):


def
. (∗)
.
.
. (2)
q > 0 ≡q ≥ 0 ∧ q = 0 → q ≥ 0 ∧ q = 0 ∧ q = 0 → q ≥ 0
∧...

.
. (N −2)
. (N −1)
∧ q = 0 ∧ q = 0 ∧ ··· ∧ q
=0→q
>0
. (−∗)

We write q

> 0 when taking Lie derivatives with respect to x0 = −f (x) instead.
. (∗)

Putting everything together, we have the following derivation where the first cut proves q
from Γ, and the second cut extends Γ to Γr using p = 0:

>0

∗
lp≥ ,lp>
. (∗)

Γ`q
cut

. (∗)

> 0 ` hx0 = f (x) & q ≥ ri◦

. (∗)

> 0 ` hx0 = f (x) & p = 0 ∨ q > 0i◦

Γr , q

cut,h·idRW

Γ, p = 0, q

>0

Γ, p = 0 ` hx0 = f (x) & p = 0 ∨ q > 0i◦

We summarize with the following derived rule:
. (∗)

lp=∨>
6.1.4

Γ`q >0
0
Γ, p = 0 ` hx = f (x) & p = 0 ∨ q > 0i◦

Semialgebraic Case

We now consider the general normal form for semialgebraic P .
Lemma 15 (Semialgebraic local progress). Let P be a semialgebraic formula in normal form (2).
The following rule derives from dL extended with Cont,Uniq.

V
Wm(i) . (∗)
Wn(i) . (∗)
qij > 0
Γ` M
= 0 ∨ j=0
i=0
j=0 pij
lpR
Γ, P ` hx0 = f (x) & P i◦
Proof Summary (See Appendix C). We decompose P using ∧L,&∧. Axiom Uniq is crucially used
in &∧. This yields premises with disjunctive conditions. We prove local progress for these disjuncts using conto ,h·idRI,lp=∨> , and then lift the result to the full disjunction using h·idRW.

6.2

Proving Semialgebraic Invariants

Let semialgebraic P be written in the normal form (2), and let ¬P also be written in the same
normal form:
a(i)
b(i)
N
^
_
_

¬P ≡
ri = 0 ∨
sij > 0
(3)
i=0

j=0

j=0

We summarize our results with the following derived rule.
22

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Theorem 16 (Semialgebraic invariants). For semialgebraic P , with normal forms (2) and (3),
the following rule (with two premises) is sound and derives from the dL calculus extended with
RInd,Cont,Uniq.
m(i)
n(i)
M
^
_ . (∗)
_ . (∗)

P `
pij = 0 ∨
qij > 0
i=0

¬P `
sAI

j=0

N
^

a(i)

i=0

j=0

_

j=0
b(i)

. (−∗)

rij

=0∨

_

. (−∗)

sij


>0

j=0

P ` [x0 = f (x)]P

Proof. Straightforward application of lpR,rInd.

6.3

Completeness for Semialgebraic Invariants

The completeness of the sAI rule was proved in [9]. Their proof makes crucial use of the fact
that solutions to polynomial ODE systems are analytic. Our derivations in this section shows that
the sAI proof rule can be derived in a purely syntactic manner within the dL calculus. This leads
to the following completeness theorem, which applies for all semialgebraic (i.e., first-order real
arithmetic) formulas P , because quantifier elimination [2] allows us to equivalently rewrite P to
normal form with rule R.
Theorem 17 (Semialgebraic invariant completeness). Let P be a semialgebraic formula. The dL
calculus is complete for invariance properties of the form P ` [x0 = f (x)]P .
In Appendix B, we show a more general version of Theorem 17 that also handles semialgebraic evolution domains. This crucially relies on the fact that we can characterize local progress
properties for semialgebraic formulas using Cont,Uniq, see Theorem 28.
It is important to note the difference between Theorem 6 and Theorem 17. In the former, we
may decide [x0 = f (x) & Q]p = 0 from any set of (non-modal) premises Γ. This is not the case for
Theorem 17 (or its generalized version), as the completeness result is limited to conclusions of the
form P ` [x0 = f (x)]P . Therefore, some work still has to be done to find such an invariant P .

7

Related Work

We focus our discussion on work related to deductive verification of hybrid systems. We refer
readers interested in the basic theories of ODEs [21], real analysis [4], and real algebraic geometry [2] to the respective cited texts. Orthogonal to our work is the question of how invariants can be
efficiently generated. We refer readers to the literature [7, 9, 17, 18]. Although these methods are
usually phrased in the language of hybrid automata [1], their core reasoning principles (for ODEs)
may also be expressed as proof rules [8].

23

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Proof Rules for Invariants. An overview of proof rules for invariance of algebraic and semialgebraic sets can be found in [8]. The soundness and completeness theorems for dRI,sAI were first
shown in [7] and [9] respectively. There are numerous other sound, but incomplete, proof rules
for deductive verification along an ODE system [20, 17]. In their original presentation, dRI and
sAI, are algorithmic procedures for checking invariance, requiring e.g., checking ideal membership for all polynomials in the semialgebraic decomposition. This makes them very difficult to
implement soundly as part of a small, trusted axiomatic core, such as the implementation of dL in
KeYmaera X [6]. We instead show that these rules can be derived from a small set of axiomatic
principles. Although we also leverage ideal computations, they are only used as part of derived
rules. With the aid of a theorem prover, derived rules can be implemented as tactics, that crucially
remain outside the soundness-critical axiomatic core.
Deductive Power and Proof Theory. The derivations shown in this paper are fully general,
which is necessary for completeness of the resulting derived rules. However, many simpler classes
of invariants can be proved using simpler derivations. This is where a study of the deductive
power of various sound, but incomplete, proof rules [8] comes into play. If we know that an
invariant of interest is of a simpler class, then we could simply use the proof rule that is complete
for that class. This intuition is echoed in [14], which studies the relative deductive power of
differential invariants (dI) and differential cuts (dC). Our first result shows, in fact, that dL with
dG is already complete for algebraic invariants. Other proof-theoretical studies of dL [13] reveal
surprising correspondences between its hybrid, continuous and discrete aspects in the sense that
each aspect can be axiomatized completely relative to any other aspect. Our Corollary 7 is a step
in this direction.

8

Conclusion and Future Work

The first part of this paper demonstrates the impressive deductive power of differential ghosts: they
prove all algebraic invariants and Darboux inequalities. We leave open the question of whether
their deductive power extends to larger classes of invariants. The second part of this paper introduces extensions to the base dL axiomatization, and shows how they can be used together with the
existing axioms to prove all real arithmetic invariants syntactically. The real induction principle
is crucially used to reduce global invariance properties to local progress properties. In contrast
to local progress, global liveness properties are tricky because solutions of differential equations
may blow up in finite time. Indeed, existing liveness rules [12, 19] require the side assumption
that solutions exist for sufficient duration. An avenue of future work is to investigate calculi for
liveness without the need for these conditions.
It is instructive to examine the mathematical properties of solutions and terms that underlie our
axiomatization. In summary:

24

A. Platzer and Y. K. Tan

Differential Equation Axiomatization
Axiom
dI
dC
dG
Cont
Uniq
RInd

Property
Mean value theorem
Prefix-closure of solutions
Picard-Lindelöf
Existence of solutions
Uniqueness of solutions
Completeness of R

The soundness of our axiomatization, therefore, easily extends to term languages beyond polynomials, e.g., continuously differentiable terms satisfy the above properties. We may, of course, lose
completeness and decidable arithmetic in the extended language, and we leave further exploration
of these issues to future work.

Acknowledgment
This material is based upon work supported by the National Science Foundation under NSF CAREER Award CNS-1054246. The second author was supported by an A*STAR National Science
Scholarship (PhD), Singapore.
Any opinions, findings, and conclusions or recommendations expressed in this publication are
those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

References
[1] Rajeev Alur, Costas Courcoubetis, Thomas A. Henzinger, and Pei-Hsin Ho. Hybrid automata:
An algorithmic approach to the specification and verification of hybrid systems. In Robert L.
Grossman, Anil Nerode, Anders P. Ravn, and Hans Rischel, editors, Hybrid Systems, volume
736 of LNCS, pages 209–229. Springer, 1992. doi:10.1007/3-540-57318-6_30.
[2] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy. Real Algebraic Geometry, volume 36 of A Series of Modern Surveys in Mathematics. Springer, 1998. doi:10.1007/
978-3-662-03718-8.
[3] Brandon Bohrer, Vincent Rahli, Ivana Vukotic, Marcus Völp, and André Platzer. Formally
verified differential dynamic logic. In Yves Bertot and Viktor Vafeiadis, editors, CPP, pages
208–221. ACM, 2017. doi:10.1145/3018610.3018616.
[4] Pete L. Clark. The instructor’s guide to real induction. arXiv preprint arXiv:1208.0973, 2012.
[5] Gaston Darboux. Mémoire sur les équations différentielles algébriques du premier ordre et du
premier degré. Bulletin des Sciences Mathématiques et Astronomiques, 2(1):151–200, 1878.
[6] Nathan Fulton, Stefan Mitsch, Jan-David Quesel, Marcus Völp, and André Platzer. Keymaera X: an axiomatic tactical theorem prover for hybrid systems. In Amy P. Felty and
25

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Aart Middeldorp, editors, CADE, volume 9195 of LNCS, pages 527–538. Springer, 2015.
doi:10.1007/978-3-319-21401-6_36.
[7] Khalil Ghorbal and André Platzer. Characterizing algebraic invariants by differential radical
invariants. In Erika Ábrahám and Klaus Havelund, editors, TACAS, volume 8413 of LNCS,
pages 279–294. Springer, 2014. doi:10.1007/978-3-642-54862-8_19.
[8] Khalil Ghorbal, Andrew Sogokon, and André Platzer. A hierarchy of proof rules for checking
positive invariance of algebraic and semi-algebraic sets. Computer Languages, Systems and
Structures, 47(1):19–43, 2017. doi:10.1016/j.cl.2015.11.003.
[9] Jiang Liu, Naijun Zhan, and Hengjun Zhao. Computing semi-algebraic invariants for polynomial dynamical systems. In Samarjit Chakraborty, Ahmed Jerraya, Sanjoy K. Baruah, and
Sebastian Fischmeister, editors, EMSOFT, pages 97–106. ACM, 2011. doi:10.1145/
2038642.2038659.
[10] Dmitri Novikov and Sergei Yakovenko. Trajectories of polynomial vector fields and ascending chains of polynomial ideals. In ANNALES-INSTITUT FOURIER, volume 49, pages
563–609. Association des annales de l’institut Fourier, 1999.
[11] Susan S. Owicki and David Gries. Verifying properties of parallel programs: An axiomatic
approach. Commun. ACM, 19(5):279–285, 1976. doi:10.1145/360051.360224.
[12] André Platzer. Differential-algebraic dynamic logic for differential-algebraic programs. J.
Log. Comput., 20(1):309–352, 2010. doi:10.1093/logcom/exn070.
[13] André Platzer. The complete proof theory of hybrid systems. In LICS, pages 541–550. IEEE,
2012. doi:10.1109/LICS.2012.64.
[14] André Platzer. The structure of differential invariants and differential cut elimination. Logical
Methods in Computer Science, 8(4):1–38, 2012. doi:10.2168/LMCS-8(4:16)2012.
[15] André Platzer. A complete uniform substitution calculus for differential dynamic logic. J.
Autom. Reas., 59(2):219–265, 2017. doi:10.1007/s10817-016-9385-1.
[16] André Platzer and Yong Kiam Tan. How to prove “all” differential equation properties. Technical Report CMU-CS-17-117, School of Computer Science, Carnegie Mellon University,
Pittsburgh, PA, August 2017.
[17] Stephen Prajna and Ali Jadbabaie. Safety verification of hybrid systems using barrier certificates. In Rajeev Alur and George J. Pappas, editors, HSCC, volume 2993 of LNCS, pages
477–492. Springer, 2004. doi:10.1007/978-3-540-24743-2_32.
[18] Sriram Sankaranarayanan, Henny B. Sipma, and Zohar Manna. Constructing invariants
for hybrid systems. Form. Methods Syst. Des., 32(1):25–55, 2008. doi:10.1007/
s10703-007-0046-1.

26

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

[19] Andrew Sogokon and Paul B. Jackson. Direct formal verification of liveness properties
in continuous and hybrid dynamical systems. In Nikolaj Bjørner and Frank S. de Boer,
editors, FM, volume 9109 of LNCS, pages 514–531. Springer, 2015. doi:10.1007/
978-3-319-19249-9_32.
[20] Ankur Taly and Ashish Tiwari. Deductive verification of continuous dynamical systems.
In Ravi Kannan and K. Narayan Kumar, editors, FSTTCS, volume 4 of LIPIcs, pages 383–
394. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2009. doi:10.4230/LIPIcs.
FSTTCS.2009.2334.
[21] Wolfgang Walter. Ordinary Differential Equations, volume 182 of Graduate Texts in Mathematics. Springer, 1998. doi:10.1007/978-1-4612-0601-9.

27

A. Platzer and Y. K. Tan

A

Differential Equation Axiomatization

Differential Dynamic Logic Axiomatization

We work with the uniform substitution calculus presented in [15]. The calculus is based on the
uniform substitution inference rule:
φ
US
σ(φ)
The uniform substitution calculus requires a few extensions to the syntax and semantics presented
in Section 2. Firstly we extend the term language with differential terms (e)0 and k-ary function
symbols f , where e1 , . . . , ek are terms. The formulas are similarly extended with k-ary predicate
symbols P and predicationals C:
e ::= · · · | (e)0 | f (e1 , . . . , ek )
φ ::= · · · | P (e1 , . . . , ek ) | C(φ)
The grammar of dL programs is as follows (a is a program symbol):
α ::= a | x := e | ?φ | x0 = f (x) & Q | α1 ∪ α2 | α1 ; α2 | α∗
We refer readers to [15] for the complete, extended semantics. Briefly, for each variable x,
there is an associated differential variable x0 , and states map all of these variables (including differential variables) to real values; we write S for the set of all states. The semantics also requires an
interpretation I for the uniform substitution symbols. The term semantics, Iω[[e]], gives the value
of e in state ω and interpretation I. The formula semantics, I[[φ]], is the set of states where φ is true
in interpretation I, and the transition semantics of hybrid programs I[[α]] is given with respect to
interpretation I. The transition semantics for x0 = f (x) requires:
(ω, ν) ∈ [[x0 = f (x) & Q]] iff there is T ≥ 0 and a function
ϕ : [0, T ] → S with ϕ(0) = ω on {x0 }{ , ϕ(T ) = ν, and
I, ϕ |= x0 = f (x) & Q
The I, ϕ |= x0 = f (x) & Q condition checks that ϕ(ζ) ∈ I[[x0 = f (x) ∧ Q]], ϕ(0) = ϕ(ζ) on
(ζ) exists, and is equal to ϕ(ζ)(x0 ) for all
{x, x0 }{ for 0 ≤ ζ ≤ T , and, if T > 0, then dϕ(t)(x)
dt
0 ≤ ζ ≤ T . In other words, ϕ is a solution of the differential equations x0 = f (x) that stays in
the evolution domain constraint. It is also required to hold all variables other than x, x0 constant.
Most importantly, the values of the differential variables x0 is required to match the valuation of
the RHS of the differential equations along the solution. We refer readers to [15, Definition 7] for
further details.
The calculus allows all of the axioms (cf. [15, Figures 2 and 3]) to be stated as concrete instances, which are then instantiated by uniform substitution. In this appendix, we take the same
approach: all of our (new) axioms will be stated as concrete instances as well. We will need to be
slightly more careful, and write down explicit variable dependencies for all the axioms. To make
this paper self-contained, we state all of the axioms used in the paper and the appendix. However,
we only provide justification for derived rules and axioms that are not already justified in [15].
28

A. Platzer and Y. K. Tan

A.1

Differential Equation Axiomatization

Base Axiomatization

The following are the base axioms and proof rules for dL from [15, Figure 2].
Theorem 18 (Base axiomatization [15]). The following are sound axioms and proof rules for dL.
[:=] [x := f ]P (x) ↔ P (f )
[?] [?P ]R ↔ (P → R)
[∪] [a1 ∪ a2 ]P (x) ↔ [a1 ]P (x) ∧ [a2 ]P (x)
[; ] [a1 ; a2 ]P (x) ↔ [a1 ][a2 ]P (x)
[∗ ] [a∗ ]P ↔ P ∧ [a][a∗ ]P
h·i haiP (x) ↔ ¬[a]¬P (x)
K [a](P1 → P2 ) → ([a]P1 → [a]P2 )
I [a∗ ](P → [a]P ) → (P → [a∗ ]P )
G

P (x)
[a]P (x)

In our sequent calculus, we instantiate these axioms using uniform substitution, and then use
congruence reasoning for equivalences (and equalities). All of the substitutions that we require
are admissible [15, Definition 19]. Note that G above is presented as a Hilbert-style rule. In our
sequent calculus formulation, we use it by discarding the context, because if φ is valid, then it must
also be true after running any program α:
G

`φ
Γ ` [α]φ

The [·]∧ axiom derives using G,K. For the “ → ” direction (the case for [α]φ2 in the succedent
is symmetric):
∗
φ1 ∧ φ2 ` φ1
G,→R
` [α](φ1 ∧ φ2 → φ1 )
cut,K
[α](φ1 ∧ φ2 ) ` [α]φ1
In the “ ← ” direction we use K twice:
∗
φ2 , φ1 `
G,→R
`
cut,K
[α]φ2 `
cut,K
[α]φ1 , [α]φ2 `

φ1 ∧ φ2
[α](φ2 → φ1 → φ1 ∧ φ2 )
[α](φ1 → φ1 ∧ φ2 )
[α](φ1 ∧ φ2 )
29

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

The M[·] rule derives using G,K as well. Note that applying K produces two premises.
φ2 ` φ1
Γ ` [α](φ2 → φ1 )
Γ ` [α]φ2
Γ ` [α]φ1

G,→R
K

The following is the familiar loop induction rule.
loop

φ ` [α]φ
φ ` [α∗ ]φ

It derives from the induction axiom I and G.
φ ` [α]φ
G,→R
cut,I

A.2

` [α∗ ](φ → [α]φ)

φ ` [α∗ ]φ

Differential Equation Axiomatization

The following are axioms for differential equations and differentials from [15, Figure 3]. Note
that x is a vector of variables x1 , x2 , . . . , xn , x0 is the corresponding vector of differential variables
x01 , x02 , . . . , x0n , and f (x) is a vector of n-ary function symbols f1 (x), f2 (x), . . . , fn (x).
Theorem 19 (Differential equation axiomatization [15]). The following are sound axioms of dL.
DW [x0 = f (x) & Q(x)]Q(x)
DI=

(Q(x) → [x0 = f (x) & Q(x)](p(x))0 = 0)
→ ([x0 = f (x) & Q(x)]p(x) = 0 ↔ [?Q(x)]p(x) = 0)

DI&

(Q(x) → [x0 = f (x) & Q(x)](p(x))0 ≥ 0)
→ ([x0 = f (x) & Q(x)]p(x) & 0 ↔ [?Q(x)]p(x) & 0)

[x0 = f (x) & Q(x)]P (x, x0 )
DE
↔ [x0 = f (x) & Q(x)][x0 :=f (x)]P (x, x0 )
c0 (f )0 = 0
x0 (x)0 = x0
+0 (f (x) + g(x))0 = (f (x))0 + (g(x))0
·0 (f (x) · g(x))0 = (f (x))0 · (g(x)) + (f (x)) · (g(x))0
Syntactic derivation under differential equations is performed using the DE axiom along with
the axioms for working with differentials c0 ,x0 ,+0 ,·0 [15, Lemmas 36-37], and the assignment axiom [0 :=] for differential variables. We label the exhaustive use of the differential axioms as e0 .
30

A. Platzer and Y. K. Tan

Differential Equation Axiomatization
.

The following derivation is sound for any polynomial term p (where p is the polynomial term for
the Lie derivative of p). We write ∼ for a free choice between = and &:
.

` [x0 = f (x) & Q]p ∼ 0
e0 ,[0 :=],R
` [x0 = f (x) & Q][x0 :=f (x)](p)0 ∼ 0
DE
` [x0 = f (x) & Q](p)0 ∼ 0
The e0 ,[0 :=],R step first performs syntactic Lie derivation on p, and then additionally uses R to
.
rearrange the resulting term into p as required. To see this more concretely, we perform the above
derivation with a polynomial from the running example.
def

Example 2 (Using syntactic derivations). Let pe = v 2 − u2 + 23 , unfolding the Lie derivative, we
have:
∂pe
∂pe
(−v + u(1 − u2 − v 2 )) +
(u + v(1 − u2 − v 2 ))
∂u
∂v
= −2u(−v + u(1 − u2 − v 2 )) + 2v(u + v(1 − u2 − v 2 ))
.
= 4uv + 2(1 − u2 − v 2 )(v 2 − u2 ) = pe

Lαe (pe ) =

Now, we may perform the above derivation:
`
R
`
[0 :=]
`
e0
`
DE
`

.

[αe ]pe ∼ 0
[αe ]2v(u + v(1 − u2 − v 2 )) − 2u(−v + u(1 − u2 − v 2 )) ∼ 0
[αe ][u0 := − v + u(1 − u2 − v 2 )][v 0 :=u + v(1 − u2 − v 2 )]2vv 0 − 2uu0 ∼ 0
[αe ][u0 := − v + u(1 − u2 − v 2 )][v 0 :=u + v(1 − u2 − v 2 )](pe )0 ∼ 0
[αe ](pe )0 ∼ 0

Note that we needed the R step to rearrange the result from syntactically differentiating pe to match
.
the expression pe for the Lie derivative. Since the two notions must coincide under the ODEs, this
rearrangement step is always possible.
We prove generalized versions of axioms from [15]. These are the vectorial differential ghost
axioms (DG and DG∀ )12 which were proved only for the single variable case, and the differential
modus ponens axiom, DMP, which was specialized for differential cuts.
Lemma 20. The following axioms are sound. Note that y is an m-dimensional vector of variables,
y0 is its corresponding vector of differential variables, and a(x) (resp. b(x)) is a m × m matrix
(resp. m-dimensional vector) of function symbols.
[x0 = f (x) & Q(x)]P (x)
DG
↔ ∃y [x0 = f (x), y0 = a(x) · y + b(x) & Q(x)]P (x)
DG∀

[x0 = f (x) & Q(x)]P (x)
↔ ∀y [x0 = f (x), y0 = a(x) · y + b(x) & Q(x)]P (x)

[x0 = f (x) & Q(x)](Q(x) → R(x))
DMP
→ ([x0 = f (x) & R(x)]P (x) → [x0 = f (x) & Q(x)]P (x))
12

We do not actually need DG∀ in this paper. We prove it for completeness, because [15] proves a similar axiom.

31

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Proof. In this proof, we use ω for the initial state, and ν for the state reached at the end of a
continuous evolution. The valuations for matrix and vectorial terms are applied component-wise.
We first prove vectorial DG and DG∀ . Our proof is specialized to the case of linear (inhomogeneous) systems. We only need to prove the “→” direction for DG∀ , because ∀y φ implies ∃y φ over
the reals, and so we get the “→” direction for DG from the “→” direction of DG∀ . Conversely, we
only need to prove the “←” direction for DG, because the “←” direction for DG∀ follows from it.
“→” We need to show the RHS of DG∀ assuming its LHS. Let ωyd be identical to ω except where
the values for y are replaced with any initial values d ∈ Rm . Consider any solution ϕy :
[0, T ] → S where ϕy (0) = ωy on {x0 , y0 }{ , ϕy (T ) = ν, and
I, ϕy |= x0 = f (x), y0 = a(x) · y + b(x) & Q(x)
Define ϕ : [0, T ] → S satisfying:
(
ϕy (t)(z)
def
ϕ(t)(z) =
ω(z)

z ∈ {y, y0 }{
z ∈ {y, y0 }

In other words, ϕ is identical to ϕy except it holds all of y, y0 constant at their initial values
in ω. Observe that by construction, ϕ(0) = ω on {x0 }{ , and moreover, because y is fresh
i.e., not mentioned in Q(x), f (x), by coincidence for terms [15, Lemma 10], we have that:
I, ϕ |= x0 = f (x) & Q(x)
Therefore, ϕ(T ) ∈ I[[P (x)]] from the LHS of DG∀ . Since ϕ(T ) coincides with ϕy (T ) = ν
except on {y, y0 } and y is fresh, by coincidence for formulas [15, Lemma 11] we also have
ν = ϕy (T ) ∈ I[[P (x)]] as required.
“←” We need to show the LHS of DG assuming its RHS. Consider a solution ϕ : [0, T ] →
def
S where ϕ(0) = ω on {x0 }{ , ϕ(T ) = ν, and I, ϕ |= x0 = f (x) & Q(x). Let ϕa (t) =
def
Iϕ(t)[[a(x)]], and ϕb (t) = Iϕ(t)[[b(x)]] be the valuation of a(x), b(x) along ϕ respectively.
Recall that ϕa : [0, T ] → Rm × Rm and ϕb : [0, T ] → Rm .

By [15, Definition 5], ϕa (t) = I(a) I(ϕ(t))(x) , where I(a) is continuous (and similarly
for ϕb (t)). Since ϕ is a continuous function in t, both ϕa (t), ϕb (t) are compositions of continuous functions, and are thus, also continuous functions in t. Consider the m-dimensional
initial value problem:
y0 = ϕa (t)y + ϕb (t), y(0) = ω[[y]]
By [21, Chapter IV, Theorem 14.VI], there exists a unique solution ψ : [0, T ] → Rm for this
system that is defined on the entire interval [0, T ]. Therefore, we may construct the extended
solution ϕy satisfying:

0 {

ϕ(t)(z) z ∈ {y, y }
def
ϕy (t)(z) = ψ(t)(z) z ∈ y

 dψ(t)(w)
z = w 0 ∈ y0
dt
32

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

By definition, ϕy (0) = ω on {x0 , y0 }{ , and by construction and coincidence for formulas [15,
Lemma 11], I, ϕy |= x0 = f (x), y0 = a(x) · y + b(x) & Q(x). Thus, we have ϕy (T ) ∈
I[[P (x)]] from the RHS of DG. Since ϕ(T ) coincides with ϕy (T ) except on y, y0 , again by
coincidence for formulas [15, Lemma 11] we have ν = ϕ(T ) ∈ I[[P (x)]] as required.
We now prove DMP. Consider an initial state ω satisfying both negative premises of DMP, i.e.,
1 ω ∈ I[[[x0 = f (x) & Q(x)](Q(x) → R(x))]], and
2 ω ∈ I[[[x0 = f (x) & R(x)]P (x)]]
We need to show ω ∈ I[[[x0 = f (x) & Q(x)]P (x)]], i.e., for any solution ϕ : [0, T ] → S where
ϕ(0) = ω on {x0 }{ , and I, ϕ |= x0 = f (x) & Q(x), we have ϕ(T ) ∈ I[[P (x)]]. By definition, we
have ϕ(t) ∈ I[[Q(x)]] for t ∈ [0, T ], but by 1 , we also have that ϕ(t) ∈ I[[Q(x) → R(x)]] for
all t ∈ [0, T ]. Therefore, ϕ(t) ∈ I[[R(x)]] for all t ∈ [0, T ], and hence, I, ϕ |= x0 = f (x) & R(x).
Thus, by 2 , we have ϕ(T ) ∈ I[[P (x)]] as required.
Using the axiomatization from Theorem 19 and Lemma 20, we now derive all of the rules
shown in Theorem 1.
Proof of Theorem 1. For each rule, we show a derivation from the dL axioms. The open premises
in these derivations correspond to the open premises for each rule.
dW We apply DMP and obtain two premises corresponding to the two formulas on the left of its
implications. The right premise closes using DW. The left premise uses G, which leaves the
open premise of dW.
Q`P
∗
DW
0
Γ ` [x = f (x) & Q](Q → P )
Γ ` [x0 = f (x) & P ]P
Γ ` [x0 = f (x) & Q]P

G,→R
DMP

dI= This rule follows from the DI= axiom, and also using the equivalence between Lie derivatives
and differentials within the context of the ODEs.
.

Q`p=0
Γ, Q ` p = 0
[?],→R
cut

Γ ` [?Q]p = 0

.

dW,→R

Γ, Q ` [x0 = f (x) & Q]p = 0

DE,e0 ,R

Γ, Q ` [x0 = f (x) & Q](p)0 = 0

cut,DI=

Γ, [?Q]p = 0 ` [x0 = f (x) & Q]p = 0

Γ ` [x0 = f (x) & Q]p = 0

dI& The derivation is similar to the previous case, using DI& instead of DI= .

33

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

dC We cut in a premise with the postcondition Q → (Q ∧ C). We reduce this postcondition to
C by M[·] because C → (Q → (Q ∧ C)) is a valid formula. The right premise after the cut
is abbreviated by 1 .
M[·]
cut

Γ ` [x0 = f (x) & Q]C
1
Γ ` [x0 = f (x) & Q](Q → (Q ∧ C))
0
Γ ` [x = f (x) & Q]P

Continuing on 1 we use DMP to refine the domain constraint, which leaves open the remaining premise of dC:
Γ ` [x0 = f (x) & Q ∧ C]P
DMP
Γ, [x0 = f (x) & Q](Q → (Q ∧ C)) ` [x0 = f (x) & Q]P
dG This follows by rewriting the RHS with (vectorial) DG.
Γ ` ∃y [x0 = f (x), y0 = a(x) · y + b(x) & Q]P
DG
Γ ` [x0 = f (x) & Q]P

We note, additionally, that dI= can be derived directly from DI& , using [·]∧, and the real arithmetic equivalence p = 0 ↔ p ≥ 0 ∧ p ≤ 0. We refer readers to [15, Theorem 38] for a proof
of soundness of DI& , which relies on the mean value theorem. Briefly, consider any solution
def

ϕ : [0, T ] → S, and let ϕp (t) = Iϕ(t)[[p]] be the valuation of p along ϕ. We may, without loss
of generality, assume T > 0, and ϕp (0) & 0. By the assumption on the left of the implication in
DI& , (p(x))0 ≥ 0, which, by the differential lemma [15, Lemma 35], means that dϕdtp (t) (ζ) ≥ 0 for
0 ≤ ζ ≤ T . By the mean value theorem, we have ϕp (T ) = ϕp (0) + dϕdtp (t) (ζ)(T − 0) for some
0 < ζ < T . Since ϕp (0) & 0, T > 0, and dϕdtp (t) (ζ) ≥ 0, we therefore have ϕp (T ) & 0 as required.
We can, conversely, obtain a version of the mean value theorem in dL:
Corollary 21 (Mean Value Theorem). The following analogue of the mean value theorem is a
derived axiom:
MVT p ≥ 0 ∧ hx0 = f (x) & Qip < 0 → hx0 = f (x) & Qi(p)0 < 0
Proof. This follows immediately by taking contrapositives, dualizing with h·i, and then applying
DI& .
∗
DI&
0
0
[?Q]p ≥ 0, [x = f (x) & Q](p) ≥ 0 ` [x0 = f (x) & Q]p ≥ 0
cut,[?]
p ≥ 0, [x0 = f (x) & Q](p)0 ≥ 0 ` [x0 = f (x) & Q]p ≥ 0
¬L,¬R,h·i
p ≥ 0 ∧ hx0 = f (x) & Qip < 0 ` hx0 = f (x) & Qi(p)0 < 0
Intuitively, this version of the mean value theorem asserts that if p changes sign from p ≥ 0
to p < 0 along a solution, then its Lie derivative must have been negative somewhere along the
solution.
34

A. Platzer and Y. K. Tan

A.3

Differential Equation Axiomatization

Extended Axiomatization

We re-state the axioms shown in Section 5 as concrete instances and prove their soundness. Consequently, the axioms of Section 5 follow as uniform substitution instances.
For these proofs, we will often need to take truncations of solutions. Let ϕ : [0, T ] → S be a
solution, we define the truncation of ϕ to a smaller interval as ϕ|t : [0, t] → S, which is identical to
ϕ on the interval [0, t], for 0 ≤ t ≤ T . For any solution ϕ : [0, T ] → S, we write ϕ([a, b]) ∈ I[[P ]]
to mean ϕ(ζ) ∈ I[[P ]] for all a ≤ ζ ≤ b. We use ϕ((a, b)) instead when the interval is open,
and similarly for the half-open cases. For example, if ϕ obeys the evolution domain constraint Q
on the interval [0, T ], we write ϕ([0, T ]) ∈ I[[Q]]. We will only use this notation when [a, b] is a
subinterval of [0, T ].
As we did in Section 5, we assume that the system of differential equations, x0 = f (x), already
contains t0 = 1, which makes t act as a clock that tracks the passage of time.
A.3.1

Existence, Uniqueness, and Continuity

We prove soundness for concrete versions of the axioms in Lemma 8.
Lemma 22 (Existence, Uniqueness and Continuity). The following axioms are sound.
hx0 = f (x) & Q1 (x)iP1 (x) ∧ hx0 = f (x) & Q2 (x)iP2 (x)
Uniq
→ hx0 = f (x) & Q1 (x) ∧ Q2 (x)i(P1 (x) ∨ P2 (x))
Cont t = t0 → (p(x) > 0 → hx0 = f (x) & p(x) > 0it 6= t0 )
Proof. For the ODE system x0 = f (x), the RHSes, when interpreted as functions on x are continuously differentiable. Therefore, by the Picard-Lindelöf theorem [21, §10.VI], from any state ω,
there is an interval [0, τ ), τ > 0 on which there is a unique, continuous solution ϕ : [0, τ ) → S
with ϕ(0) = ω. Moreover, the solution may be uniquely extended in time (to the right), up to its
maximal open interval of existence [21, §10.IX].
We first prove axiom Uniq. Consider an initial state ω, satisfying both conjuncts on the
left of the implication in Uniq. Expanding the definition of the diamond modality, this means
that there exists two solutions from ω, ϕ1 : [0, T1 ] → S, ϕ2 : [0, T2 ] → S where I, ϕ1 |=
x0 = f (x) & Q1 (x), I, ϕ2 |= x0 = f (x) & Q2 (x), with ϕ(T1 ) ∈ I[[P1 ]] and ϕ(T2 ) ∈ I[[P2 (x)]].
Now let us first assume T1 ≤ T2 . Since both ϕ1 , ϕ2 are solutions starting from ω, the uniqueness
of solutions implies that ϕ1 (t) = ϕ2 (t) for t ∈ [0, T1 ]. Therefore, since ϕ2 ([0, T2 ]) ∈ I[[Q2 (x)]] and
T1 ≤ T2 , we have I, ϕ1 |= x0 = f (x) & Q1 (x) ∧ Q2 (x). Since ϕ1 (T ) ∈ I[[P1 (x)]], which implies
ϕ1 (T ) ∈ I[[(P1 (x) ∨ P2 (x))]], we therefore have ω ∈ I[[hx0 = f (x) & Q1 (x) ∧ Q2 (x)i(P1 (x) ∨
P2 (x))]].
The case for T2 < T1 is similar, except now we have ϕ2 (T ) ∈ I[[P2 (x)]]. In either case, we
have the required RHS of Uniq:
ω ∈ I[[hx0 = f (x) & Q1 (x) ∧ Q2 (x)i(P1 (x) ∨ P2 (x))]]
Next, we prove axiom Cont. Consider an arbitrary initial state ω, with ω ∈ [[p(x) > 0]] and
ω ∈ [[t = t0 ]]. In other words, we initially have ω(t) = ω(t0 ).
35

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

By the existence theorem, there is a solution ϕ : [0, τ ) → S, of the system x0 = f (x), with
ϕ(0) = ω except on {x0 }{ and τ > 0. Since t0 = 1 and t0 is held constant in the system of
equations, the valuation of t satisfies ϕ(ζ)(t) = ω(t0 ) + ζ along this solution.
When viewed as a function on x, I[[p(x)]] is a continuous function from Rn → R (recall that x
is shorthand for x1 , . . . , xn ). Moreover, the set I[[p(x) > 0]] is topologically open. Hence, viewing
ω(x) as a point in Rn , there exists  > 0 such that all points d in the open ball, kd − ω(x)k < ,
also satisfy I[[p(d)]] > 0. In terms of states, this implies that all states ν where kν(x) − ω(x)k < 
also satisfy ν ∈ I[[p(x) > 0]].
Moreover, the solution ϕ(ζ) is by definition, differentiable, and hence continuous about ζ = 0
for x1 , . . . , xn , which implies, for a sufficiently small 0 < δ < τ , that kϕ([0, δ])(x)−ϕ(0)(x)k < .
Hence, ϕ([0, δ]) ∈ I[[p(x) > 0]], and so the truncated solution ϕ|δ satisfies:
I, ϕ|δ |= x0 = f (x) & p(x) > 0
Finally, since ϕ|δ (δ)(t) = ω(t0 ) + δ > ω(t0 ) = ϕ|δ (δ)(t0 ), we have ϕ|δ (δ) ∈ I[[t 6= t0 ]], and so
ω ∈ I[[hx0 = f (x) & p(x) > 0it 6= t0 ]] as required.
From the proof for Cont, it is clear that we may also write t > t0 in its postcondition. In fact,
the choice t0 = 1 was made for convenience: we only need some way to encode local progress.
We also have used t0 = −1, or even t0 = c for any constant c 6= 0.
A.3.2

Real Induction

We prove the symmetric real induction principle stated in Proposition 10. Variants of this principle
can be found in [4].
Proof of Proposition 10. In the “⇐=” direction, if S = [a, b], then S is inductive by definition. For
the “=⇒” direction, let S ⊆ [a, b] be inductive, i.e., we have:
1 a∈S
2 If a ≤ x < b and x ∈ S , then [x, x + ] ⊆ S for some 0 < 
3 If a < x ≤ b and x ∈ S { , then [x − , x] ⊆ S { for some 0 < , where we write S { for the
complement [a, b] \ S.
Suppose that S 6= [a, b], so that the set S { is non-empty. Let x be the infimum of S { , and note
that x ∈ [a, b] since [a, b] is left-closed. We consider various cases for x.
1. Case x = a. By properties 1 and 2 , [x, x + ] ⊆ S,  > 0, so x +  is a greater lower bound
of S { than x, contradiction.
2. Case a < x, x ∈ S. If x = b, then S = [a, b], contradiction. Otherwise, a < x < b, then by
2 , [x, x + ] ⊆ S,  > 0, so x +  is a greater lower bound of S { than x, contradiction.
3. Case a < x, x ∈ S { . By 3 , there is [x − , x],  > 0, but then x −  ∈ S { , so x is not a lower
bound of S { , contradiction.
36

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

We now restate and prove a generalized, concrete version of the real induction axiom given in
Lemma 11. This strengthened version includes the evolution domain constraint. We have removed
the syntactic abbreviation in Section 5 for a precise statement here.
Lemma 23. The following real induction axiom is sound.
RInd& [x0 = f (x) & Q(x)]P (x) ↔
0



(Q(x) → P (x)) ∧ [x = f (x) & Q(x)]∀t0 t = t0 →
P (x) ∧ hx0 = f (x) & Q(x)it 6= t0 →

hx0 = f (x) & P (x)it 6= t0 ∧
¬P (x) ∧ hx0 = −f (x) & Q(x)it 6= t0 →

hx0 = −f (x) & ¬P (x)it 6= t0


Proof. We shall label the conjuncts after ∀t0 t = t0 → . . . under the box modality on the RHS
as follows:
P (x) ∧ hx0 = f (x) & Q(x)it 6= t0 → hx0 = f (x) & P (x)it 6= t0
(a)
¬P (x) ∧ hx0 = −f (x) & Q(x)it 6= t0 → hx0 = −f (x) & ¬P (x)it 6= t0

(b)

Consider an initial state ω, we prove both directions of the axiom separately.
“→” Assume that ? ω  [x0 = f (x) & Q(x)]P (x). If ω ∈ I[[Q(x)]], then consider the solution of
duration 0 which stays in Q(x). By assumption ? , this solution is required to satisfy P (x) at
its endpoint, which is identical to ω except on {x0 }{ , and so by coincidence for formulas [15,
Lemma 11], ω ∈ I[[P (x)]]. Thus, ω ∈ I[[Q(x) → P (x)]].
Next, we prove the conjunction ( a ∧ b ) under the box modality. Consider any solution
ϕ : [0, T ] → S starting from ω with I, ϕ |= x0 = f (x) & Q(x). We may also assume
ϕ(T ) ∈ I[[t = t0 ]].
For conjunct b we need to show:
ϕ(T ) ∈ I[[¬P (x) ∧ . . . → . . .]]
However, by assumption ? , we must have ϕ(T ) ∈ I[[P (x)]], and therefore this conjunct is
trivially true.
For the remaining conjunct a , we additionally assume that:
ϕ(T ) ∈ I[[P (x) ∧ hx0 = f (x) & Q(x)it 6= t0 ]]
As we did in the proof of soundness for Cont, we identify t as the clock variable with initial
value t0 . Unfolding the diamond modality, there is another solution ψ : [0, τ ] → S starting
37

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

from ϕ(T ) with ψ(τ ) ∈ I[[t 6= t0 ]]. We also have I, ψ |= x0 = f (x) & Q(x). Note that
ψ(0) = ϕ(T ) exactly rather than just on {x0 }{ , because both of these states must have the
appropriate values for the differential variables.
We now need to show:
ϕ(T ) ∈ I[[hx0 = f (x) & P (x)it 6= t0 ]]
We shall directly show:
I, ψ |= x0 = f (x) & P (x)
In particular, since ψ already satisfies the requisite differential equations and ψ(τ ) ∈ I[[t 6=
t0 ]], it is sufficient to show that it stays in the evolution domain for its entire duration, i.e.,
ψ([0, τ ]) ∈ I[[P (x)]].
Let 0 ≤ ζ ≤ τ and consider the concatenated solution Φ : [0, T + ζ] → S defined by:
(
ϕ(t)
t≤T
def
Φ(t) =
ψ(t − T ) t > T
Since ψ must uniquely extend ϕ [21, §10.IX], the concatenated solution Φ is a solution
starting from ω, it solves the system x0 = f (x), and it stays in Q(x) for its entire duration.
Hence, by ? , Φ(T + ζ) = ψ(ζ) ∈ I[[P (x)]] as required.
“←” Assume that the RHS of the equivalence is true in state ω. If ω ∈
/ I[[Q(x)]] then we are
done, because there are no solutions that stay in Q(x) and so the box modality on the LHS
is trivially satisfied. Otherwise, consider an arbitrary solution ϕ : [0, T ] → S starting from ω
such that I, ϕ |= x0 = f (x) & Q(x). We need to show ϕ([0, T ]) ∈ I[[P (x)]]. We will do this
by showing that the subset {ζ : ϕ(ζ) ∈ I[[P (x)]]} is an inductive subset of [0, T ].
1 We have ω = ϕ(0) except on {x0 }{ and ω ∈ I[[Q(x)]]. By the assumption ω ∈
I[[Q(x) → P (x)]], we have ω ∈ I[[P (x)]]. Thus, ϕ(0) ∈ I[[P (x)]] by coincidence
for formulas [15, Lemma 11].
2 Now, consider 0 ≤ ζ < T , and suppose ϕ(ζ) ∈ I[[P (x)]]. We need to show ϕ([ζ, ζ +
def
]) ∈ I[[P (x)]] for some  > 0. For notational simplicity, let t0 = ϕ(ζ)(t), we instantiate the box modality on the RHS with ϕ|ζ , and the quantifier with t0 . We therefore,
have ϕ(ζ) ∈ I[[ a ]].
Observe that since ζ < T , we may consider the solution that starts from state ϕ(ζ), i.e.,
def
ψ : [0, T − ζ], where ψ(τ ) = ϕ(τ + ζ), and we have I, ψ |= x0 = f (x) & Q(x). We
also have T − ζ > 0, and therefore, ψ(T − ζ) ∈ I[[t 6= t0 ]] by viewing t as the clock
variable. In other words, we have ϕ(ζ) ∈ I[[hx0 = f (x) & Q(x)it 6= t0 ]]. Therefore, we
may discharge the implication in a to obtain:
ϕ(ζ) ∈ I[[hx0 = f (x) & P (x)it 6= t0 ]]
38

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Unfolding the diamond modality, gives us a solution, which by uniqueness, yields a
truncation of ψ, ψ| , for some  > 0 which starts from ϕ(ζ) and satisfies ψ| ([0, ]) ∈
I[[P (x)]].
Now, by definition, ψ| (τ ) is equal to ϕ(τ + ζ) for 0 ≤ τ ≤ , which implies ϕ([ζ, ζ +
]) ∈ I[[P (x)]] as required.
3 In this case, we consider 0 < ζ ≤ T , and suppose ϕ(ζ) ∈ I[[¬P (x)]]. We need to
show ϕ([ζ − , ζ]) ∈ I[[¬P (x)]] for  > 0. This is essentially symmetric to 2 by
the fact that time-reversed solutions of differential equations satisfy the negated system
def
x0 = −f (x). Note that we have t0 = −1 here. We let t0 = ϕ(ζ)(t), and instantiate the
RHS to obtain ϕ(ζ) ∈ I[[ b ]].
Since 0 < ζ, let us consider ψ : [0, ζ], where
(
ϕ(ζ − τ )(z)
z ∈ {x0 }{
def
ψ(τ )(z) =
−ϕ(ζ − τ )(z) z ∈ {x0 }
In other words, ψ is the time-reversed solution starting from ϕ(ζ) and following the
system x0 = −f (x). Note that in the case for z ∈ {x0 }, we have explicitly negated the
signs of the differential variables along ψ. This is needed to ensure that the differential
variables match the RHS of x0 = −f (x). By a similar argument to the previous case, ψ
is a witness for ϕ(ζ) ∈ I[[hx0 = −f (x) & Q(x)it 6= t0 ]], and thus, from the implication
in b we have:
ϕ(ζ) ∈ I[[hx0 = −f (x) & ¬P (x)it 6= t0 ]]
By uniqueness, this gives a truncation ψ| , for some  > 0, which starts (backwards)
from ϕ(ζ) and satisfies ψ| ([0, ]) ∈ I[[¬P (x)]]. This gives us ϕ([ζ − , ζ] ∈ I[[¬P (x)]]
as required.

We shall work with the following derived real induction rule (with two premises). It derives
directly from RInd& using dW. The derived rule rInd follows as a special case, where we ignore
the antecedents involving the evolution domain Q.
t = t0 , Q, hx0 = f (x) & Qi◦, P ` hx0 = f (x) & P i◦
t = t0 , Q, hx0 = −f (x) & Qi◦, ¬P ` hx0 = −f (x) & ¬P i◦
rInd&
P ` [x0 = f (x) & Q]P

A.4

Diamond Modality Rules and Axioms

We derive the rules and axioms from Corollary 9, along with an additional derived rule that is used
in the appendix.

39

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Corollary 24 (Derived diamond modality rules and axioms). In addition to the derived rules and
axioms in Corollary 9, the following derived rule is sound:
Mh·i

Γ ` [α](φ2 → φ1 )
Γ ` hαiφ2
Γ ` hαiφ1

Proof (includes proof of Corollary 9). For each rule, we show a derivation from the dL axioms.
The open premises in these derivations correspond to the open premises for each rule.
h·idR This follows by dualizing with the h·i axiom.
Γ ` [x0 = f (x) & R]Q
Γ, [x0 = f (x) & Q]¬P ` [x0 = f (x) & R]¬P
h·i,¬R,¬L
Γ ` hx0 = f (x) & RiP
Γ, hx0 = f (x) & RiP ` hx0 = f (x) & QiP
cut
0
Γ ` hx = f (x) & QiP
DMP,DW

h·idRW This follows from h·idR by simplifying its left premise with dW.
&∧ This follows from h·idRW for the “→” direction, because Q ∧ R → Q and Q ∧ R → R are
both valid formulas. The “←” direction is an immediate instance of Uniq by setting P1 , P2
to P , and Q1 , Q2 to Q, R respectively.
Mh·i This follows from K by dualizing its inner implication with the h·i axiom.
h·i,K

B

Γ ` [α](φ2 → φ1 )
Γ ` hαiφ2
Γ ` hαiφ1

Completeness for Semialgebraic Invariants and Evolution
Domain Constraints

This section gives the full completeness arguments for dRI and sAI. With the extended axiomatization, we may prove the completeness direction of dRI and (most of) sAI within dL. We take this
syntactic approach here to demonstrate the versatility of the dL calculus. We refer the readers to
other presentations [7, 9] for purely semantical completeness arguments. As usual, we will assume
that x0 = f (x) already contains a clock equation t0 = 1. We will, however, need to make more use
of this specific choice here.
We start with the following definition due to [9], which summarizes the formulas in the premises
of sAI. It lifts the progress and differential radical formulas for single polynomials to the general
case of an arbitrary semialgebraic formula written in normal form.

40

A. Platzer and Y. K. Tan

Differential Equation Axiomatization
. (∗)

Definition 5 (Semialgebraic progress formula). The semialgebraic progress formula P
semialgebraic formula P written in normal form (2) is defined as follows:
m(i)
M
^
_

. (∗) def

≡

P

i=0
. (−∗)

We write P

for a

n(i)
. (∗)
pij

_

=0∨

j=0

. (∗)

qij


>0

j=0

when taking Lie derivatives with respect to x0 = −f (x) instead.

We note that the syntactic form of semialgebraic progress formula for P depends on the choice
. (∗)

of normal form. This choice will always be made clear in the context when we refer P .
We first make the following useful observation on various rearrangements of the progress and
differential radical formulas for polynomials:
Proposition 25. Let N be the order of q. The following are valid equivalences on the progress and
differential radical formulas.
. (∗)

q

.

> 0 ↔q > 0 ∨ (q = 0 ∧ q > 0)
∨ ...
.

. (N −2)

∨ q = 0 ∧ q = 0 ∧ ··· ∧ q
. (∗)

¬(q

. (∗)

¬(q

. (∗)

= 0) ↔q

.

.

> 0) ↔(−q)


>0

(∗)

> 0 ∨ (−q)
(∗)

. (N −1)

=0∧q

>0

. (∗)

>0∨q

=0

Proof. All of these equivalences follow immediately by unfolding the definitions of the progress
and differential radical formulas, applying logical rearrangements and real arithmetic identities.
The latter two equivalences are particularly important, as we show in the next proposition.
Proposition 26. Let P be in normal form:
P ≡

m(i)
M
^
_
i=0

n(i)

pij = 0 ∨

j=0

_


qij > 0

j=0

¬P can be put in a normal form:
¬P ≡

a(i)
N
^
_
i=0

rij = 0 ∨

j=0

b(i)
_
j=0

for which we additionally have the valid equivalence:
. (∗)

¬(P

.

(∗)

) ↔ (¬P )
41


sij > 0

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Proof. We start by applying negating P (in normal form), and applying the arithmetic identities
p 6= 0 ↔ p > 0 ∨ −p > 0 and q ≤ 0 ↔ −q > 0 ∨ q = 0 to obtain the valid formula:
m(i)
n(i)
M
_
^
^

¬P ↔
(pij > 0 ∨ −pij > 0) ∧ (−qij > 0 ∨ q = 0)
i=0

j=0

j=0

|

{z

}

φ

Expanding and negating the progress formula for P , we have the valid equivalence:
¬

m(i)
M
_
^

n(i)
. (∗)
pij

=0∨

m(i)

M
_
^
i=0

qij


>0 ↔

j=0

j=0

i=0

. (∗)

_
n(i)

. (∗)
¬pij

=0∧

j=0

. (∗)

^

¬qij


>0

j=0

The RHS of this equivalence can be rewritten with the latter two equivalences from Proposition 25
to obtain the following formula, which we label as ψ:
M  m(i)
^
def _
i=0

.

. (∗)

ψ≡

(∗)

> 0 ∨ (−pij )

pij


>0 ∧

j=0
n(i)

^

.

(∗)

>0∨

(−qij )

. (∗)
qij


=0

j=0

Observe that φ, ψ have the same disjunctive normal form shape. We distribute the outer disjunction
over the inner conjunctions in φ to obtain the following valid equivalence, whose RHS is a normal
form for ¬P (for some indices N, a(i), b(i) and polynomials rij , sij ):
¬P ↔

a(i)
N
^
_
i=0

rij = 0 ∨

j=0

b(i)
_


sij > 0

j=0

We distribute the disjunction in ψ following the same syntactic steps taken in φ to obtain the
following valid equivalence:
ψ↔

a(i)
N
^
_
i=0

. (∗)
rij

=0∨

b(i)
_

. (∗)

sij


>0

j=0

j=0

By rewriting with the equivalences derived so far, and using the above normal form for ¬P , we
have the required, valid equivalence:
. (∗)

¬(P

.

(∗)

) ↔ (¬P )

42

A. Platzer and Y. K. Tan

B.1

Differential Equation Axiomatization

Algebraic Invariants

We now derive axiom DRI from Theorem 6.
Proof of Theorem 6. In the “←” direction, we use dRI, by setting N to the order of p, so that the
. (∗)
succedent of its left premise is exactly p = 0. The right premise closes by real arithmetic, since
N is the order of p, it must, by definition satisfy the identity (1).
∗
→L

. (∗)

Q→p

∗
. (∗)

= 0, Q ` p

. (∗)

dRI

Q→p

R

=0

. (N )

`p

=

PN −1
i=0

. (i)

gi p

= 0 ` [x0 = f (x) & Q]p = 0

For the “→” direction, we first reduce to the contrapositive statement by logical manipulation.
An application of h·i turns the negated box modality in the succedent to a diamond modality.
Finally, by Proposition 25, we equivalently rewrite the negated differential radical formula in the
antecedents. We refer to the open premise with 1 .
. (∗)

> 0 ∨ (−p) > 0 `
. (∗)
Q, ¬(p = 0) `
. (∗)
Q, ¬(p = 0) `
[x0 = f (x) & Q]p = 0 `

. (∗)

Q, p
R
h·i

hx0 = f (x) & Qip 6= 0
hx0 = f (x) & Qip 6= 0
¬[x0 = f (x) & Q]p = 0
. (∗)
Q→p =0

Since Q characterizes an open, semialgebraic set, by the finiteness theorem [2, Theorem 2.7.2]
for open semialgebraic sets, Q may be written as follows (qij are polynomials):
Q≡

M m(i)
^
_

qij > 0

i=0 j=0

Thus, we have the following derivation. As usual, we have collapsed similar cases (indexed by i)
after the &∧,∧L step. All the premises close using conto .
∗ D
E
W
t = t0 , j=0 qij > 0 ` x0 = f (x) & m(i)
q
>
0
◦
j=0 ij
D
E
V Wm(i)
VM Wm(i)
&∧,∧L
0
t = t0 , M
q
>
0
`
x
=
f
(x)
&
q
>
0
◦
ij
ij
i=0
j=0
i=0
j=0
conto

R

Wm(i)

t = t0 , Q ` hx0 = f (x) & Qi◦

We are now ready to continue from 1 . In the first step, we introduce a clock variable satisfying
t = t0 initially using dG,∃R. Next, using the derivation above, we cut in local progress for Q. We
. (∗)

then use ∨L to case split on the disjunction p

.

(∗)

> 0 ∨ (−p)

43

> 0. The resulting premises are

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

labelled 2 and 3 .
2
∨L

. (∗)

t = t0 , hx0 = f (x) & Qi◦, p

. (∗)

cut

t = t0 , Q, p

. (∗)

dG,∃R

Q∧ p

.

(∗)

> 0 ∨ (−p)
.
.

> 0 ` hx0 = f (x) & Qip 6= 0

(∗)

> 0 ∨ (−p)

> 0 ∨ (−p)

3

(∗)

> 0 ` hx0 = f (x) & Qip 6= 0

> 0 ` hx0 = f (x) & Qip 6= 0

. (∗)

Continuing on 2 , because we already have p > 0 in the antecedents, using lp=∨> , we may cut
hx0 = f (x) & t = t0 ∨ p > 0i◦. Now, by an application of &∧, we combine the two local progress
formulas in the antecedent.
hx0 = f (x) & Q ∧ (t = t0 ∨ p > 0)i◦ ` hx0 = f (x) & Qip 6= 0
hx0 = f (x) & Qi◦, hx0 = f (x) & t = t0 ∨ p > 0i◦ ` hx0 = f (x) & Qip 6= 0
. (∗)
cut,lp=∨>
t = t0 , hx0 = f (x) & Qi◦, p > 0 ` hx0 = f (x) & Qip 6= 0
&∧

R

z
}|
{
Next, because Q ∧ (t = t0 ∨ p > 0) → Q, we use h·idRW to strengthen the evolution domain
constraint in the succedent. This allows us to use Mh·i, whose right premise closes trivially. Removing the syntactic abbreviation for ◦ allows us to close the premise using dW, because we have
t = t0 ∨ p > 0 in the domain constraint R.
∗
R`
dW
`
Mh·i
hx0 = f (x) & Ri◦ `
h·idRW 0
hx = f (x) & Ri◦ `
R

(t 6= t0 → p 6= 0)
[x0 = f (x) & R](t 6= t0 → p 6= 0)
hx0 = f (x) & Rip 6= 0
hx0 = f (x) & Qip 6= 0
.

(∗)

The remaining premise 3 follows similarly, except that the progress formula (−p) > 0 enables the cut hx0 = f (x) & t = t0 ∨ −p > 0i◦. It leads to the same conclusion of p 6= 0 in the
postcondition.
We now prove Corollary 7 using the characterization of algebraic invariants of ODEs from Theorem 6. The test-free fragment of dL programs is generated by the following grammar, where we
have omitted tests, and evolution domain constraints:
α ::= x := e | x0 = f (x) | α1 ∪ α2 | α1 ; α2 | α∗
Proof of Corollary 7. Firstly, since P is algebraic, it is equivalent to a formula p = 0 for some
polynomial p so we may, without loss of generality, assume that it is written in this form.
We proceed by structural induction on the form of test-free α, and show that for some (computable) polynomial q, we can derive the equivalence [α]p = 0 ↔ q = 0 in dL.

44

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

• Case x0 = f (x). By Theorem 6, since the set of all states (i.e., the evolution domain true) is
. (∗)
open, by DRI, we have the derived equivalence [x0 = f (x)]p = 0 ↔ p = 0. Let N be the
V −1 . (i)
. (∗)
def P −1 . (i) 2
order of p so that p = 0 expands to N
= 0. Let q = N
i=0 p
i=0 (p ) so that we have
. (∗)
the valid arithmetic equivalence p = 0 ↔ q = 0. Rewriting with this derives the desired
equivalence, [x0 = f (x)]p = 0 ↔ q = 0.
• Case x := e. By [:=], [x := e]p(x) = 0 ↔ p(e) = 0. As a composition of polynomials, p(e)
is a polynomial.
• Case α1 ∪ α2 . By [∪], [α1 ∪ α2 ]p = 0 ↔ [α1 ]p = 0 ∧ [α2 ]p = 0. By the induction
hypothesis on α1 , α2 , we may derive [α1 ]p = 0 ↔ q1 = 0 and [α2 ]p = 0 ↔ q2 = 0 for some
polynomials q1 , q2 . Moreover, q1 = 0 ∧ q2 = 0 ↔ q12 + q22 = 0 is a valid formula of real
arithmetic. Rewriting with the derived logical equivalences yields the derived equivalence:
[α1 ∪ α2 ]p = 0 ↔ q12 + q22 = 0.
• Case α1 ; α2 . By [; ], [α1 ; α2 ]p = 0 ↔ [α1 ][α2 ]p = 0. By the induction hypothesis on α2 ,
we derive [α2 ]p = 0 ↔ q2 = 0. By rewriting with this equivalence, we derive [α1 ; α2 ]p =
0 ↔ [α1 ]q2 = 0. Now, by the induction hypothesis on α1 , we derive [α1 ]q2 = 0 ↔ q1 = 0
for some q1 . Rewriting with the derived logical equivalences yields the derived equivalence
[α1 ; α2 ]p = 0 ↔ q1 = 0.
• Case α∗ . This case relies on the fact that the polynomial ring R[x] (and Q[x]) over a finite
number of indeterminates x is a Noetherian domain, which implies that every ascending
chain of ideals is finite. We first construct the following sequence of polynomials qi :
def

q0 = p,

def

qi+1 = fi

where fi is the polynomial satisfying the derived equivalence fi ↔ [α]qi = 0 obtained by
applying the induction hypothesis on α with postcondition qi = 0.
Since the ring of polynomials over the (finite set) of variables mentioned in α or p is Noetherian, the following chain of ideals is finite:
(q0 ) ⊂ (q0 , q1 ) ⊂ (q0 , q1 , q2 ) ⊂ . . .
Thus, there is some smallest k such that qk satisfies the following polynomial identity, with
polynomial cofactors gi :
k−1
X
qk =
gi qi
i=0

Vk−1

We claim that i=0 qi = 0 ↔ [α∗ ]p = 0 is derivable. Since we also have the valid
P
Vk−1
equivalence k−1
qi2 = 0 ↔ i=0
qi = 0, this claim yields the derived equivalence
i=0
Pk−1 2
∗
[α ]p = 0 ↔ i=0 qi = 0, as required. We show both directions of the claim separately.

45

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Vk−1
def
“→” We strengthen the postcondition of the box modality to i=0
qi = 0 (recall that q0 = p,
Vk−1
so i=0 qi = 0 → p = 0 is valid), and prove it as a loop invariant. By an application
of [·]∧ followed by ∧R, we may split the postcondition to its constituent conjuncts
(indexed by 0 ≤ i ≤ k − 1). We observe that, by construction, we can equivalently
replace each [α]qi with qi+1 .
Vk−1
i=0 qi = 0 ` qi+1 = 0
Vk−1
i=0 qi = 0 ` [α]qi = 0
V
Vk−1
∧R k−1
i=0 qi = 0 `
i=0 [α]qi = 0
Vk−1
[·]∧ Vk−1
q
=
0
`
[α]
i
i=0
i=0 qi = 0
Vk−1
loopVk−1
∗
i=0 qi = 0 ` [α ]
i=0 qi = 0
V
M[·] k−1
∗
i=0 qi = 0 ` [α ]p = 0
The open premises where 0 ≤ i < k − 1 close trivially because qi = 0 is already in
the antecedent. The final case where i = k − 1 is where we need to show
qk = 0 in
Pk−1
gi qi , the
the succedent. However, because we have the polynomial identity qk = i=0
final premise also closes by a cut and real arithmetic.
∗

∗
RVk−1
i=0 qi
cut

=0`

Pk−1

i=0 gi qi
Vk−1
i=0 qi

=0

R

` qk =

Pk−1
i=0

gi qi

= 0 ` qk = 0

“←” This direction is straightforward using k times the iteration axiom [∗ ] together with [·]∧.
By construction, we may replace the antecedents with qi , which gives us the required
implication.
∗
q0 = 0 ∧ q1 = 0 ∧ q2 = 0 ∧ · · · ∧ qk−1 = 0 `

Vk−1

qi = 0

p = 0 ∧ [α]p = 0 ∧ [α][α]p = 0 ∧ · · · `

Vk−1

qi = 0

∗

Vk−1

qi = 0

∗

p = 0 ∧ [α][α ]p = 0 `

Vk−1

qi = 0

[α∗ ]p = 0 `

Vk−1

qi = 0

[∗ ],[·]∧
[∗ ],[·]∧

i=0

···
p = 0 ∧ [α]p = 0 ∧ [α][α][α ]p = 0 `

[∗ ],[·]∧
[∗ ]

B.2

i=0

i=0

i=0

i=0

Local Progress

Fixing a normal form (2) for P , the following axiom derives from dL extended with Cont,Uniq.
. (∗)

lpR→ t = t0 ∧ P ∧ P

46

→ hx0 = f (x) & P i◦

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

This follows by a direct application of lpR, whose premise closes because the succedent is exactly
. (∗)

P

.

∗
. (∗)

t = t0 ∧ P

`

VM

i=0

lpR

Wm(i)
j=0
. (∗)

. (∗)

pij

=0∨

Wn(i)

. (∗)

j=0 qij


>0

` hx0 = f (x) & P i◦

t = t0 ∧ P ∧ P

Note that we have explicitly included t = t0 here, although it was left implicit in the antecedents
when we derived lpR. We now derive a converse implication.
Lemma 27 (Semialgebraic local progress, converse implication). Let P be a semialgebraic formula in normal form (2). The following axiom derives from dL extended with Cont,Uniq.
. (∗)

lpR← t = t0 ∧ hx0 = f (x) & P i◦ → P
Proof. By Proposition 26, there is a normal form for ¬P , i.e.,
¬P ≡

a(i)
N
^
_
i=0

rij = 0 ∨

j=0

b(i)
_


sij > 0

j=0

where we additionally have the valid equivalence:
. (∗)

¬(P

.

(∗)

) ↔ (¬P )

We first reduce to the contrapositive statement by logical manipulation, and then use the above
normal form to rewrite the negation in the antecedents. We refer to the open premise with 1 .
.

(∗)

t = t0 , (¬P )
. (∗)

R

t = t0 , ¬(P

` ¬hx0 = f (x) & P i◦

) ` ¬hx0 = f (x) & P i◦
. (∗)

t = t0 ∧ hx0 = f (x) & P i◦ ` P

We have the following valid equivalence, where the RHS is a normal form for ¬P ∨ t − t0 = 0. It
is obtained by distributing t − t0 = 0 over the conjunction in ¬P :
¬P ∨ t − t0 = 0 ↔

a(i)
N
^
_
i=0

rij = 0 ∨ t − t0 = 0 ∨

j=0

b(i)
_


sij > 0

j=0

The progress formula for ¬P ∨ t − t0 = 0 in this normal form is:
N  a(i)
^
_
i=0

. (∗)
rij

.

(∗)

= 0 ∨ (t − t0 )

j=0

=0

b(i)
_
j=0

47

. (∗)
sij


>0

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Now, we consider the polynomial t − t0 . Since t0 = 1, the first Lie derivative of t − t0 is 1, which
.

(∗)

gives the valid equivalence (t − t0 )

= 0 ↔ false because the LHS contains an unsatisfiable con.

(∗)

junct 1 = 0. Rewriting with this equivalence yields the valid equivalence (¬P ∨ t − t0 = 0)
.

↔

(∗)

(¬P ) .
We therefore, have the following derivation, whose conclusion we label 2 . In the first cut step,
we use the valid implication t = t0 → ¬P ∨ t − t0 = 0. We then use the equivalence above to
replace the progress formula in the antecedents before closing with lpR→ .
∗
lpR→

.

(∗)

t = t0 , ¬P ∨ t − t0 = 0, (¬P ∨ t − t0 = 0)
.

(∗)

R

t = t0 , ¬P ∨ t − t0 = 0, (¬P )

cut

t = t0 , (¬P )

.

(∗)

` hx0 = f (x) & ¬P ∨ t − t0 = 0i◦
` hx0 = f (x) & ¬P ∨ t − t0 = 0i◦
` hx0 = f (x) & ¬P ∨ t − t0 = 0i◦

We may now complete the derivation from 1 . We first cut in 2 using the derivation above.
Next, we combine the evolution domain constraints using &∧.
hx0 = f (x) & (¬P ∨ t − t0 = 0) ∧ P i◦ ` false
&∧ 0
hx = f (x) & ¬P ∨ t − t0 = 0i◦, hx0 = f (x) & P i◦ ` false
¬R
2
hx0 = f (x) & ¬P ∨ t − t0 = 0i◦ ` ¬hx0 = f (x) & P i◦
.

cut

(∗)

t = t0 , (¬P )

` ¬hx0 = f (x) & P i◦

We continue by dualizing with h·i, and finish the proof with dW and arithmetic.
∗
(¬P ∨ t − t0 = 0) ∧ P ` t = t0
dW
0
` [x = f (x) & (¬P ∨ t − t0 = 0) ∧ P ]t = t0
h·i,¬L
hx0 = f (x) & (¬P ∨ t − t0 = 0) ∧ P i◦ ` false
R

The above proof used the following valid equivalence where P is in normal form, and we
normalize P ∨ t − t0 = 0 by distributing t − t0 over the outer conjunction in P :
.

(∗)

(P ∨ t − t0 = 0)

. (∗)

↔P

(4)

This equivalence allows us to give a complete characterization of local progress for semialgebraic
formulas.
Theorem 28 (Semialgebraic local progress completeness). Let P be a semialgebraic formula in
normal form (2). The following axiom derives from dL extended with Cont,Uniq.
. (∗)

lpR↔ t = t0 → P

↔ hx0 = f (x) & P ∨ t = t0 i◦
48



A. Platzer and Y. K. Tan

Differential Equation Axiomatization

Proof. We derive both directions separately. In both cases, (4) is used crucially. First in the “←”
direction, we use lpR← and (4).
∗
R

.

(∗)

(P ∨ t = t0 )

lpR←

. (∗)

`P

. (∗)

t = t0 , hx0 = f (x) & P ∨ t = t0 i◦ ` P

For the “→” direction, we first use (4) to rewrite the progress formula in the antecedents. However,
since t = t0 , we cut in P ∨ t = t0 , which allows us to complete the proof with lpR→ .
∗
lpR→
cut

.
.

(∗)

t = t0 , (P ∨ t = t0 )
R

. (∗)

t = t0 , P

B.3

(∗)

t = t0 , P ∨ t = t0 , (P ∨ t = t0 )

` hx0 = f (x) & P ∨ t = t0 i◦

` hx0 = f (x) & P ∨ t = t0 i◦

` hx0 = f (x) & P ∨ t = t0 i◦

Proving Semialgebraic Invariants with Semialgebraic Evolution Domain
Constraints

As a consequence of lpR← , we now have the following general version of sAI, which also handles
the evolution domain constraints.
Theorem 29 (Semialgebraic invariants with semialgebraic domains). For semialgebraic Q, P, ¬Q, ¬P ,
all written in normal form, the following rule (with two stacked premises) is sound and derives from
the dL calculus extended with RInd&,Cont,Uniq.
. (∗)

t = t0 , P, Q, Q
. (−∗)

. (∗)

`P
.

(−∗)

t = t0 , ¬P, Q, Q
` (¬P )
sAI&
P ` [x0 = f (x) & Q]P
Proof. This follows directly from rInd&, by rewriting the progress condition in the antecedents of
its premises with lpR← , and proving their succedents using lpR→ .

B.4

Completeness for Semialgebraic Invariants with Semialgebraic Evolution Domain Constraints

We now prove the completeness theorem for sAI&, from which Theorem 17 follows as a special
case. This proof uses a mix of a syntactic derivation, and a minor semantic argument. The semantic part of this argument is straightforward. The essential idea is that solutions of the differential
49

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

equations x0 = f (x) are the reversed solutions of x0 = −f (x) and vice-versa. This property underlies the “there and back again” axiom for dL which equivalently expresses properties of differential
equations with evolution domain constraints in terms of properties of forwards and backwards differential equations without evolution domain constraints [13]. We can also internalize this property
with the differential adjoints axiom, as we do in [16]. Consequently, it is possible to prove a form
of the completeness theorem purely syntactically, however, we omit the additional formal development for this paper.
Theorem 30 (Semialgebraic invariant completeness with semialgebraic domains). Let P, Q be
semialgebraic formulas. The dL calculus is complete for invariance properties of the form:
P ` [x0 = f (x) & Q]P
Proof. We may, without loss of generality, assume that P, Q (and ¬P, ¬Q) are equivalently rewritten into appropriate normal forms when necessary by an application of rule R. To show that the
calculus is complete, we shall prove that the premises of sAI& are necessary, i.e., if there are states
that do not satisfy the premises of sAI&, then the conclusion P ` [x0 = f (x) & Q]P is not valid.
Using the characterization of local progress, we first derive the following valid formula (labelled 1 ):
. (∗)

t = t0 ∧ P ∧ Q ∧ Q

. (∗)

∧ ¬(P

) → hx0 = f (x) & Qi¬P

In the first step, we apply Proposition 26. This is followed by using lpR↔ on ¬P , and lpR→ on Q.
Note that we only use lpR→ on Q and not lpR↔ .
&∧
lpR→
lpR↔

hx0 = f (x) & Q ∧ (¬P ∨ t = t0 )i◦ ` hx0 = f (x) & Qi¬P
hx0 = f (x) & ¬P ∨ t = t0 i◦, hx0 = f (x) & Qi◦ ` hx0 = f (x) & Qi¬P
. (∗)

t = t0 , Q, Q , hx0 = f (x) & ¬P ∨ t = t0 i◦ ` hx0 = f (x) & Qi¬P
. (∗)

.

(∗)

t = t0 , Q, Q , (¬P )
R

. (∗)

. (∗)

t = t0 , P, Q, Q , ¬(P

` hx0 = f (x) & Qi¬P
) ` hx0 = f (x) & Qi¬P

The remainder of the derivation is similar to what we did for algebraic invariants. Since we have the
R
z
}|
{
tautology Q ∧ (¬P ∨ t = t0 ) → Q, we use h·idRW to strengthen the evolution domain constraint
in the succedent. This allows us to use Mh·i, whose right premise closes trivially. Removing the
syntactic abbreviation for ◦ allows us to close the premise using dW, because we have ¬P ∨ t = t0
in the domain constraint R.
∗
R`
dW
`
Mh·i
0
hx = f (x) & Ri◦ `
h·idRW 0
hx = f (x) & Ri◦ `
R

(t 6= t0 → ¬P )
[x0 = f (x) & R](t 6= t0 → ¬P )
hx0 = f (x) & Ri¬P
hx0 = f (x) & Qi¬P
50

A. Platzer and Y. K. Tan

Differential Equation Axiomatization
. (∗)

Now, let ω be a state which falsifies the left premise of sAI&, i.e., ω ∈ I[[t = t0 ∧P ∧Q∧ Q ]],
. (∗)

. (∗)

but ω ∈
/ I[[P ]]. By unfolding the semantics, we have ω ∈ I[[¬(P )]], and therefore, since 1 is
valid in all states, we have ω ∈ I[[hx0 = f (x) & Qi¬P ]]. In other words, ω falsifies the conclusion
of sAI&. Hence, the left premise of sAI& is necessary.
Similarly, let ν be a state which falsifies the right premise of sAI&, i.e., ν ∈ I[[t = t0 ∧ ¬P ∧
. (−∗)

Q∧Q
have:

.

(−∗)

]], but ν ∈
/ I[[(¬P )

]]. By a similar argument with 1 (appropriately instantiated), we
ν ∈ I[[hx0 = −f (x) & QiP ]]

This does not immediately falsify the conclusion of sAI&. Instead, by definition, there is a solution
ϕ : [0, T ] → S, of the system x0 = −f (x), with ϕ(0) = ν except on {x0 }{ , where ϕ(T ) ∈ I[[P ]].
We claim that ϕ(T ) falsifies the conclusion of sAI&. Let us consider the time-reversed solution
ψ:
(
ϕ(T − τ )(z)
z ∈ {x0 }{
def
ψ(τ )(z) =
−ϕ(T − τ )(z) z ∈ {x0 }
Notice that ψ(0) agrees with ϕ(T ) except on {x0 }{ . Moreover, it solves the system x0 = f (x) and
stays in evolution domain Q for its entire duration. Finally, ψ(T ) agrees with ν, except on {x0 }{ ,
which, by coincidence for formulas [15, Lemma 11], implies that ψ(T ) ∈ I[[¬P ]] (recall, that P
only depends on x). Therefore, ψ is a witness for ϕ(T ) ∈ I[[hx0 = f (x) & Qi¬P ]]. Hence, ϕ(T )
falsifies the conclusion of sAI&, and so the right premise is also necessary.

C

Completed Proofs

We give full proofs for all remaining lemmas and theorems that have not already been proved in
previous appendices where we developed the axiomatization (Appendix A) or derived the complete
proof rule for semialgebraic invariants (Appendix B).

C.1

Darboux Inequalities

We derive the dbx& rule. Its proof is similar to the one for dbx.
Proof of Lemma 3. Let 1 denote the use of the premise of dbx&, and 2 abbreviate the right
premise in the following derivation.
p&0, y>0 ` [x0 = f (x), y 0 = −gy & Q ∧ y > 0]py & 0 2
p & 0, y > 0 ` [x0 = f (x), y 0 = −gy & Q](y > 0 ∧ py & 0)
M[·],∃R
p & 0 ` ∃y [x0 = f (x), y 0 = −gy & Q]p & 0
dG
p & 0 ` [x0 = f (x) & Q]p & 0
dC

Note the minor variation in the proof: the last step above uses dC instead of [·]∧, which introduces y > 0 into the evolution domain constraint in the left premise. This sign condition on y is
51

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

crucially used when we apply 1 in the proof for the left premise:
∗
∗
R

cut

.

p ≥ gp, y > 0 ` py − gyp ≥ 0

1

p&0, y>0 ` py & 0

dI

R.
.

Q, y > 0 ` py − gyp ≥ 0

p&0, y>0 ` [x0 = f (x), y 0 = −gy & Q ∧ y > 0]py & 0

The choice of the differential ghost y 0 = −gy is obtained by solving the top condition for y 0 .
The right premise 2 is:
y > 0 ` [x0 = f (x), y 0 = −gy & Q]y > 0
Its proof continues using a second ghost z 0 = g2 z. This allows us to prove yz 2 = 1 invariant, which
implies y > 0 in the postcondition:
∗
Q ` −(gy)z 2 + y(2z( g2 z)) = 0

R
dI

yz 2 = 1 ` [x0 = f (x), y 0 = −gy, z 0 = g2 z & Q]yz 2 = 1

M[·],∃R
dG

C.2

y > 0 ` ∃z [x0 = f (x), y 0 = −gy, z 0 = g2 z & Q]y > 0
y > 0 ` [x0 = f (x), y 0 = −gy & Q]y > 0

Differential Radical Invariants

We derive the dRI proof rule.
Proof of Theorem 5. Let p be a polynomial satisfying both premises of the dRI proof rule, and let


p
 p. (1) 
def 

p=

..


.
. (N −1)

p
def . (i−1)

We have pi = p
for i = 1, 2, . . . , N . If we take the component-wise Lie derivative of p, we
.
. (i)
have: (p)i = Lf (x) (pi ) = p .
We start by setting up for a proof by vdbx. On the left premise after the cut, we used the
V −1 . (i)
arithmetic equivalence N
= 0 ↔ p = 0, to rewrite the succedent to the left premise of
i=0 p
dRI.
V −1 . (i)
p = 0 ` [x0 = f (x) & Q]p = 0
Γ, Q ` N
=0
i=0 p
R
M[·]
Γ, Q ` p = 0
p = 0 ` [x0 = f (x) & Q]p = 0
cut
Γ, Q ` [x0 = f (x) & Q]p = 0
dI
Γ ` [x0 = f (x) & Q]p = 0
52

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

We continue on the right premise by applying vdbx with the following special choice of G,
with 1 on its superdiagonal, and the gi cofactors in the last row:
G

z

0

}|

1

0
...
0
..
..
..

.
.
.
 0 0
.
 . . .
.
Q ` p =  .. ..
..
..
0

 0 0 ...
0
1
g0 g1 . . . gN −2 gN −1
vdbx
p = 0 ` [x0 = f (x) & Q]p = 0

{



p



The succedent of the open premise requires us to prove a component-wise equality on two vectors,
.
i.e., (p)i = (Gp)i for 1 ≤ i ≤ N . For 1 ≤ i < N , explicit matrix multiplication yields:
.

. (i)

(p)i = p

. (i)

=1·p

= 1 · (p)i+1 = (Gp)i

Therefore, all but the final component-wise equality prove trivially by R. The remaining premise
is:
.
Q ` (p)N = (Gp)N
The LHS of this equality simplifies to:
.

. (N )

(p)N = p
The RHS simplifies to:
(Gp)N =

N
X
i=1

gi−1 (p)i =

N
X

. (i−1)

gi−1 p

=

i=1

N
−1
X

. (i)

gi p

i=0

Therefore, by an arithmetic step, we equivalently reduce the remaining open premise to the right
premise of dRI.

C.3

Semialgebraic Case

We prove local progress for the general case where P is a semialgebraic formula in normal
form (2).
Proof of Lemma 15. Throughout this proof, we will collapse similar premises in derivations and
index them by i, j. We first decompose the outermost conjunction in P with ∧L for the antecedents,
and &∧ for the evolution domain constraint. We write Pi for the i-th conjunct of P .
&∧,∧L

Γ, P, Pi ` hx0 = f (x) & Pi i◦
Γ, P ` hx0 = f (x) & P i◦

53

A. Platzer and Y. K. Tan

Differential Equation Axiomatization

W
Wn(i)
Each Pi is a disjunctive formula: m(i)
j=0 pij = 0 ∨
j=0 qij > 0. It will be sufficient for us to show
local progress for just one of these disjuncts, and then use h·idRW to conclude local progress for
Pi .
W
We continue by case splitting on Pi in the antecedent with ∨L. For the case with n(i)
j=0 qij > 0,
W
m(i)
we close using conto . This leaves the j=0 pij = 0 cases abbreviated by 1 .
∗
1
∨L

conto ,h·idRW

Wn(i)

j=0 qij

> 0 ` hx0 = f (x) & Pi i◦

Γ, P, Pi ` hx0 = f (x) & Pi i◦

We continue on 1 by cutting in the corresponding i-th conjunct of the premise of lpR, and then
. (∗)
. (∗)
case splitting on the cut premise. In the pij = 0 cases, we use h·idRI. The cases for qij > 0
are abbreviated with 2 :
∗

2
h·idRI,h·idRW .
(∗)
pij = 0 ` hx0 = f (x) & Pi i◦
∨L W
Wm(i) . (∗)
Wn(i) . (∗)
m(i)
= 0 ∨ j=0
qij > 0 ` hx0 =
j=0 pij
j=0 pij = 0,
cut
Wm(i)
Γ, P, j=0 pij = 0 ` hx0 = f (x) & Pi i◦

f (x) & Pi i◦

Qm(i)
W
Finally, for 2 , we rewrite the antecedents and domain constraint with m(i)
j=0 pij =
j=0 pij = 0 ↔
0 which is a valid real arithmetic equivalence. We then complete the proof with lp=∨> .
∗
lp=∨> Q
h·idRW,R
cut,R

m(i)
j=0

. (∗)
0, qij

pij =
Qm(i)

D

> 0 ` x0 = f (x) &

. (∗)
j=0 pij = 0, qij
Wm(i)
. (∗)
j=0 pij = 0, qij

Qm(i)
j=0

E
pij = 0 ∨ qij > 0 ◦

> 0 ` hx0 = f (x) & Pi i◦
> 0 ` hx0 = f (x) & Pi i◦

54

