This file was generated only in order to help search engines; its contents will display poorly, as the file was obtained by filtering out all symbols.
The file that you really want to look at is the (gzipped) postscript,
or the pdf, version of the one that you are currently looking at.
These files, as well others, with publication information, can be found in
Eduardo Sontag's
Online Papers site.
If the file that you are looking at is named "foo.html", then
the file that you want is (only one of the formats may be
available) foo.ps.gz and/or foo.pdf.
For convenience, here are direct links to those files (the pdf file is in some
cases unavailable):
TeXPS: dvi->PostScript Driver dvitps, Version 3.11 of September 5, 1990 Dvi file name: "siam-fa.dvi". This PostScript file was produced on host "control.rutgers.edu". Pass0: Page 1 Pass0: Page 2 Pass0: Page 3 Pass0: Page 4 Pass0: Page 5 Pass0: Page 6 Pass0: Page 7 Pass0: Page 8 Pass0: Page 9 Pass0: Page 10 Pass0: Page 11 Pass0: Page 12 Pass0: Page 13 Pass0: Page 14 Pass0: Page 15 Pass0: Page 16 Pass0: Page 17 Pass0: Page 18 Pass0: Page 19 Pass0: Page 20 Pass0: Page 21 Pass0: Page 22 Pass0: Page 23 Pass0: Page 24 Pass0: Page 25 Pass0: Page 26 Pass0: Page 27 Dvi file name: "siam-fa.dvi". This PostScript file was produced on host "control.rutgers.edu". Pass1: Page 1 DISCRETE-TIME TRANSITIVITY AND ACCESSIBILITY: ANALYTIC SYSTEMS 1 Francesca Albertini Eduardo D. Sontag SYCON - Rutgers Center for Systems and Control Department of Mathematics, Rutgers University, New Brunswick, NJ 08903 (908) 932-3072, E-mail: albertin@hilbert.rutgers.edu,sontag@hilbert.rutgers.edu ABSTRACT A basic open question for discrete-time nonlinear systems is that of determining when, in analogy with the classical continuous-time "positive form of Chow's Lemma," acces- sibility follows from transitivity of a natural group action. This paper studies the problem, and establishes the desired implication for analytic systems in several cases: (i) compact state space, (ii) under a Poisson stability condition, and (iii) in a generic sense. In addition, the paper studies accessibility properties of the "control sets" recently introduced in the context of dynamical systems studies. Finally, various examples and counterexamples are provided relating the various Lie algebras introduced in past work. 1 Introduction This paper continues the study, initiated in [4], of systems of the type x(t + 1) = f (x(t); u(t)) ; t = 0; 1; 2; : : : ; (1) where x and u take values in manifolds. The smooth mapping f is assumed to be invertible on x for each fixed u, a restriction which models systems that arise when dealing with continuous-time plants under digital control. See [4] for further motivation for the study of such systems, and [9] for general definitions of systems. Given the system (1), one may introduce the reachable or forward-accessible set from a state x 0 , which we will denote by R(x 0 ). This is the set of states to which one may steer x 0 using arbitrary controls. Clearly, reachable sets are one of the central concepts in control theory. A mathematically far easier object to deal with is the orbit or forward-backward accessible set from x 0 , which we will denote by O(x 0 ). This is defined as the set consisting of all states to which x 0 can be steered using both motions of the system and negative time motions: a state z is in the orbit of x 0 if there exists a sequence of states x 0 = x 0 ; x 1 ; : : : ; x k = z 1 This research was supported in part by US Air Force Grant AFOSR-88-0235. Keywords: Discrete-time, nonlinear systems, transitivity, accessibility. AMS(MOS) subject classification: Primary: 93B03,93B05, Secondary: 93C55,93B29 Running head: Discrete-time transitivity and accessibility 1 Pass1: Page 2 such that, for each i = 1; : : : ; k, either x i is reachable from x i\Gamma 1 or x i\Gamma 1 is reachable from x i . Of course, R(x 0 ) is always included in O(x 0 ), but these two sets are in general dif- ferent. Observe that O(x 0 ) is the orbit of x 0 under the group action induced by all the diffeomorphisms f (\Delta ; u), while the main interest in control theory -since negative time motions are in general not physically realizable- is in R(x 0 ), the orbit under the cor- responding semigroup. One reason that orbits are easier to study is that they have a natural structure of submanifold of the state space; this induces a decomposition of the state space into invariant submanifolds which integrate a natural distribution of vector fields (see for instance [8]). One of the central facts in continuous-time controllability is the following property, valid for analytic systems and arbitrary states x 0 : (C) R(x 0 ) has nonempty interior in O(x 0 ). This property follows directly from the orbit theorem, but it can also be established for general smooth systems, under appropriate Lie-algebraic assumptions; it is often known as the "positive form of Chow's Lemma." Thus, for continuous-time, the state space can be partitioned into invariant submanifolds, and inside each submanifold one can reach an open set from each state. In particular, the interior of the reachable set from x 0 is nonempty --one then says that there is forward accessibility from x 0 ,-- if and only if the orbit is open, --i.e., there is transitivity from x 0 . In contrast, Property (C) may fail in discrete-time, even for systems obtained through the time-sampling of one-dimensional analytic continuous-time systems; see the examples in [4]. There are two known cases where (C) does hold: (a) When x 0 is an equilibrium point (and the system is analytic and the control-value set is connected); this is one of the main results in [4]. (b) If the map f is rational on states and controls; see [6]. Both of these properties are quite restrictive; equilibria are in general few, and the ra- tionality assumption is too strong in discrete-time (note that even when sampling very simple --for instance, polynomial,-- continuous-time systems one does not in general obtain rational equations.) In this paper we extend the validity of property (C). For analytic systems, we prove that Property (C) does hold if the orbit from x 0 is compact, or under certain stability hy- potheses related to Hamiltonian dynamics. Another result shows that if there is only one orbit (the system is transitive), then forward accessibility holds from an open dense set of states, assuming the state space to have at most finitely many connected components. Low-dimensional cases are of interest because certain special implications hold in those cases, and as sources of examples and counterexamples. For instance, we show that in dimension one transitivity from a given state x 0 implies either forward accessibility from x 0 or backward accessibility (controllability from some open set to x 0 ), but that this result fails in dimension two. Recently, Colonius and Kliemann introduced the notion of control subsets of the state space of continuous-time systems. These are essentially sets where "almost reachability" 2 Pass1: Page 3 holds. Control sets have proved to be an extremely useful concept; in particular, in [2] these authors established an interesting relationship between such sets and chaotic behavior in subsets of an associated dynamical system. The extension to discrete-time of the results of Colonius and Kliemann depends critically on the better understanding of the forward accessibility properties of control sets, so we devote the last part of this paper to that goal. The reader is referred to the conference paper [1] for a detailed explanation of how the results in [2] can indeed be extended when applying the techniques developed here. 2 Basic Definitions In this paper we will deal with discrete-time nonlinear systems \Sigma of the type (1) where x(t) 2 X and u(t) 2 U . We assume that the state space X is a connected, second countable, Hausdorff, differentiable manifold of dimension n, except in Section 5.1, where we wish to study what happens if the connectedness assumption is dropped. The control-value space U is always assumed to be a subset of IR m which satisfies the assumptions U ` clos int U and 0 2 U . We always assume that U is a connected set, except in Sections 3.1 and 6 where this assumption can be dropped. The system is of class C k , with k = 1 or !, if the manifold X is of class C k and the function f : X \Theta U ! X is of class C k (i.e., there exists a C k extension of f to an open neighbourhood of X \Theta U in X \Theta IR m ). We call systems of class C 1 smooth systems and those of class C ! analytic systems. The most restrictive technical assumption to be made is that the system is invertible; this means that for each u 2 U the map f u = f (\Delta ; u) : X ! X is a global diffeomorphism of X. Invertibility allows the application of the techniques in [4]; the assumption is satisfied when dealing with systems obtained by sampling a continuous time one. We will use f \Gamma 1 u to denote the inverse of the map f u . Unless otherwise stated, from now on we assume that a fixed smooth system \Sigma is given. 2.1 Some Notations If there exists an integer k * 0 and a k-tuple (u k ; : : : ; u 1 ) 2 U k such that f u k ;:::;u 1 (x) = z, we will write: x ; k z : As usual, f u k ;:::;u 1 denotes f u k ffi : : : ffif u 1 . For any fixed state x and any nonnegative integer k define: k;x (u) := f u k ;:::;u 1 (x) 3 Pass1: Page 4 where u = (u k ; : : : ; u 1 ) 2 U k . For each u, let ae k;x (u) be the rank of @ @u k;x [u], and denote _ae k;x := max u2U k ae k;x (u): For each x, let also _ae x := max k*0 _ae k;x ; roughly, this is the largest possible dimension of a manifold reachable from x. Observe that k 0 * k implies _ae k 0 ;x * _ae k;x (2) because if u 2 U k achieves ae k;x (u) = _ae k;x then also ae k 0 ;x (~u) * ae k;x (u) for any ~u 2 U k 0 that extends u. We define the following sets: R k (x) := fz j x ; k zg is the set of states reachable from x in (exactly) k steps, ~ R k (x) := f k;x (u) j u 2 U k ; ae k;x (u) = _ae x g is the set of states that are maximal-rank reachable from x in (exactly) k steps, _ R k (x) := f k;x (u) j u 2 U k ; ae k;x (u) = ng is the set of states that are nonsingularly reachable from x in k steps. Observe that, clearly, _ R k (x) ` ~ R k (x) ` R k (x): We let: R(x) := [ k*0 R k (x) and analogously for ~ R(x) and _ R(x). Recall that \Sigma is said to be forward accessible from x if and only if int R(x) 6= ;. We also define: ( O 0 (x) = x O k (x) = f z j 9z 1 2 O k\Gamma 1 and z 1 ; 1 z or z ; 1 z 1 g and O(x) = [ k*0 O k (x): Thus O(x) is the orbit from x; \Sigma is said to be transitive from x if and only if int O(x) 6= ;. Note that, given any state x, there is a well-defined restriction of the system to the orbit O(x). Hence all results can be in principle applied in each orbit. The only difficulty is that orbits are often not connected, while most results hold only under the blanket assumption that the state space must be connected. In Section 5.1 we make some further comments about this issue. 4 Pass1: Page 5 Certain Lie algebras of vector fields L; L + ; \Gamma ; \Gamma + were introduced in [4], --see also [3] for previous work,-- we repeat their definitions here for the convenience of the reader. First we let X + u and X \Gamma u be the following vector fields: X + u;i (x) = @ @v i fi fi fi fi fi v=0 f \Gamma 1 u ffi f u+v (x); X \Gamma u;i (x) = @ @v i fi fi fi fi fi v=0 f u ffi f \Gamma 1 u+v (x); one for each i = 1; : : : ; m. Given a vector field Y and a control value u, we can define an- other vector field from Y by applying a change of coordinates given by the diffeomorphism f u , (Ad u Y )(x) = (df u (x)) \Gamma 1 Y (f u (x)): Here df u stands for the differential of f u with respect to x. In the same way, but now using the diffeomorphism f \Gamma 1 u , we also define Ad \Gamma 1 u . We let: Ad ffl k \Delta \Delta \Delta ffl 1 u k \Delta \Delta \Delta u 1 Y = Ad ffl 1 u 1 \Delta \Delta \Delta Ad ffl k u k Y: (3) We will use the abbreviated notation Ad k 0 Y for Ad 0\Delta \Delta \Delta 0 Y with u = 0 repeated k-times, if k ? 0, and for Ad \Gamma 1\Delta \Delta \Delta \Gamma 1 0 \Delta \Delta \Delta 0 Y , if k ! 0. Additionally, Ad 0 0 Y = Y . The Lie algebras \Gamma + and \Gamma are now defined as \Gamma + = fAd u k \Delta \Delta \Delta u 1 X + u 0 ;i jk * 0; 1 ^ i ^ m; u 0 ; : : : ; u k 2 U g; \Gamma = fAd ffl k \Delta \Delta \Delta ffl 1 u k \Delta \Delta \Delta u 1 X oe u 0 ;i jk * 0; 1 ^ i ^ m; u 0 ; : : : ; u k 2 U; ffl 1 ; : : : ; ffl k = \Sigma 1; oe = \Sigma g: Finally the Lie algebras L + and L are as follows. L + = Lie fAd k 0 X + u;i j k * 0; 1 ^ i ^ m; u 2 U g; L = Lie f Ad k 0 X + u;i j k 2 ZZ; 1 ^ i ^ m; u 2 U; g: We look at the sets of states in which various rank conditions fail, or forward acces- sibility fails: B + := fx j int R(x) = ;g B + L := fx j dim L + (x) ! ng B + \Gamma := fx j dim \Gamma + (x) ! ng : Although well-defined always, the set B + L will be of interest only when the system is analytic. 5 Pass1: Page 6 2.2 Review of Main Known Facts With these notations, many of the results obtained in [4] can be visualized by the fol- lowing diagram, where an arrow "A ! B" indicates inclusion A ` B, and the inclusions involving B + L are only valid in the analytic case. ~ R(B + ) \Gamma ! B + \Gamma \Gamma ! B + L # # . R(B + ) \Gamma ! B + Note: ffl The inclusion ~ R(B + ) ` B + \Gamma (4) rephrases the result obtained in Corollary 4.4 of [4]. ffl The inclusion B + \Gamma ` B + expresses the result in Theorem 6 part (a) of [4]. ffl The inclusion B + L ` B + represents the result in Theorem 6 part (b) of [4]. 3 Some New General Properties In this section we prove a number of general facts which can be conveniently expressed in terms of the sets just defined. Remark 3.1 If there exists any k 0 such that _ R k 0 (x) is non-empty, then for all k * 0 we have _ R k (x) = ~ R k (x). Indeed, the assumption implies that _ae x = n. Proposition 3.2 For each x 2 X, the following properties are equivalent: (a) int _ R(x) 6= ;. (b) int ~ R(x) 6= ;. (c) int R(x) 6= ;. Proof. Since _ R(x) ` ~ R(x) ` R(x), it is only necessary to show that (c) implies (a). We will show the following two properties: 1. for each k * 0 if int _ R k (x) = ; then _ R k (x) = ;; 2. if _ R k (x) = ; for all k * 0 then int R(x) = ;. Combining (1) and (2) we have that if int _ R(x) = ; then all int _ R k (x) = ; too, so int R(x) = ;, as desired. We first prove (1). Suppose that _ R k (x) 6= ;, so that there exists some sequence _ u for which the rank ae k;x (\Delta ) is equal to n at _u. Since we assume U ae clos int U , there exists also some ~u 2 int U k so that ae k;x (u) = n for each u in some neighbourhood of ~u. By the implicit mapping theorem, ~z = k;x (~u) belongs to int _ R k (x). 6 Pass1: Page 7 We now prove (2). If _ R k (x) = ; for all k * 0 then each u 2 U k is a singular point of the map k;x , for each k. Thus by Sard's Theorem k;x (U k ) has measure zero for all k * 0. It follows that also R(x) = [ k*0 R k (x) = [ k*0 k;x (U k ) has measure zero, and hence int R(x) = ;, as desired. Proposition 3.3 If the system \Sigma is analytic then, for any x 2 X: clos R k (x) = clos ~ R k (x) for all k sufficiently large. Proof. Fix x 2 X, and let k 0 be so that _ae k 0 ;x = _ae x . For all k * k 0 , let A k (x) = fu j ae k;x (u) = _ae x g : We claim that A k (x) is an open dense set of U k . This is because A k (x) 6= ; by (2) and the complement of A k (x) is a set defined by the vanishing of certain analytic functions (suitable determinants) of u. We claim that R k (x) ` clos ~ R k (x) which implies clos R k (x) ` clos ~ R k (x) for each such k. (5) This will establish the result, the other inclusion being obvious. Indeed, pick k * k 0 and take any z 2 R k (x). Then z = k;x (u) for some u = (u k ; : : : ; u 1 ). Since A k (x) is dense, we can find a sequence fu l g such that u l = (u (l) k ; : : : ; u (l) 1 ) ! u = (u k ; : : : ; u 1 ) as n ! 1 and u l 2 A k (x) for each l. Let z l = k;x (u l ) 2 ~ R k (x). By continuity, z l ! z, which proves (5). Remark 3.4 Assume that the system \Sigma is analytic, and that there exists an x 0 2 X and a k 0 * 0 for which _ R k 0 (x 0 ) 6= ;. Then the proof of the previous result together with Remark (3.1) imply that: clos R k (x 0 ) = clos _ R k (x 0 ) for all k * k 0 . Moreover, since @ @u k;x [u] is analytic also with respect to the x-variable, this particular k 0 works also for an open dense set of states x 2 X. Thus, under these assumptions, we have that: clos R k (x) = clos ~ R k (x) = clos _ R k (x) for all k * k 0 and for almost all x 2 X. 7 Pass1: Page 8 3.1 Regular Points We call x a regular point if _ae x is constant in a neighbourhood of x. The following fact will be useful later; it is of course a well-known general fact about smooth mappings. Lemma 3.5 The regular points form an open dense subset of X. Proof. Let _ae = max x2X _ae x : We have _ae 2 f0; : : : ; ng. We will prove our thesis by induction on _ae. If _ae = 0, then each x 2 X is a regular point, thus the statement is true. Let _ae ? 0. Define X 1 := fx 2 X j x is a regular point and _ae x = _aeg ; Y 1 := int fX n X 1 g : Then X 1 and Y 1 are open. Moreover X 1 S Y 1 is dense in X, since its complement is the boundary of X 1 which is a nowhere dense set. If we call _ae 1 = max x2Y 1 _ae x we have _ae 1 ! _ae. Thus, applying the inductive assumption to (_ae 1 ; Y 1 ), we have that the set of regular points in Y 1 , denote it by Y r , is dense in Y 1 . But since the set of regular points of X is given by X 1 S Y r and X 1 S Y 1 is dense in X, then X 1 S Y r is also dense in X. Note that, in the particular case in which the system is analytic, then in the above proof the set X 1 is already dense, because the rank is less then _ae if and only if certain determinants, which are analytic functions of x, vanish and this can happen only in a nowhere dense set. 4 More Results for Analytic Systems In this section we always assume the system \Sigma to be analytic. Lemma 4.1 Suppose that for a fixed x 2 X there exists a sequence of elements fx n k g and some y 2 X so that dim L + (y) = n, such that: 1. x n k 2 R n k (x), with n k ! 1, 2. x n k ! y. Then the system is forward accessible from x (i.e. x 62 B + ). 8 Pass1: Page 9 Proof. Since x n k ! y and dim L + (y) = n there is some integer k 0 * 0 such that dim L + (x n k ) = n for all k * k 0 . But for k sufficiently large we know (by Proposition (3.3)) that x n k 2 clos ~ R n k (x): Thus there exists some z 2 X such that z 2 ~ R n k (x) and dim L + (z) = n. So we can conclude forward accessibility from x by (4). Remarks 4.2 1. The result is also true if the weaker assumption dim \Gamma + (y) = n is made, but we shall apply it in the above form. 2. If x and y are as in the previous Lemma, and U is any open neighbourhood of y then, in particular, we have that R(x) " U is also open. 3. If for a fixed x 2 X there exists a sequence of elements fx n k g such that x n k 2 R n k (x), with n k ! 1 and x n k ! x then, by the previous Lemma, we can conclude that forward accessibility from x is equivalent to dim L + (x) = n. We will see later that in dimension 1 this equivalence is always true, but it can fail in higher dimensions. For each x 2 X, we will denote by y k 0;x the image under k;x (\Delta ) of the zero control; i.e. y k 0;x = k;x (0; : : : ; 0 -- -z "" k\Gamma times ): Lemma 4.3 Suppose that x; y 2 X are so that: 1. the system is transitive from y, (or equivalently, dim L(y) = n,) 2. there exists a sequence fy n k 0;x g with n k ! 1 such that y n k 0;x ! y. Then dim L + (x) = n: Proof. Choose n vector fields v 1 ; : : : ; v n in L such that fv 1 (y); : : : ; v n (y)g is a basis for L(y). As in the proof of Proposition 4.2 in [4], we can assume that the v i 's involve Lie brackets of a finite numbers of vector fields of the form Ad k j 0 X + u j , with k j 2 ZZ. Choose a positive integer k 0 so that k j + k 0 * 0 for all such j. Since the v i 's are linearly independent at y, they are still linearly independent in some neighbourhood U y of y. By assumption (2), there is some n k so that y n k 0;x 2 U y and n k * k 0 . Applying the operator Ad n k 0 to the v i 's, there result n linearly independent vectors in L + (x), as desired. 9 Pass1: Page 10 4.1 Poisson Stability Recall that if Y is a vector field on a manifold M , one says that x 2 M is a positively Poisson stable point for Y if and only if for each neighbourhood V of x and each T * 0 there exists some t ? T such that e tY (x) 2 V , where e tY (\Delta ) represents the flow of Y . Analoguosly, one can define positive Poisson stability in discrete time, as follows: Definition 4.4 Let f : X ! X be a global diffeomorphism. The point x 2 X is positively Poisson stable if and only if for each neighbourhood V of x and each integer N * 0 there exists some integer k ? N such that f k (x) 2 V . Theorem 1 Let x 2 X be a positively Poisson stable point for f 0 = f (\Delta ; 0). Then transitivity from x implies forward accessibility from x. Proof. Positive Poisson stability from x implies the existence of a sequence fy n k 0;x g, with n k ! 1, convergent to x. Thus the result follows immediately combining Lemmas (4.1), (4.3) (applied with y = x). 4.2 Compact State Space For each k * 0 we define the following sets: C k (x) := f y j y ; k xg; i.e. the set of states controllable to x in (exactly) k steps, and C(x) = [ k*0 C k (x): A system is backward accessible from x if and only if int C(x) 6= ;. Theorem 2 Let \Sigma be a discrete time, analytic, invertible system, and assume that the state space X is compact. Then, \Sigma is transitive if and only if it is forward accessible. Proof. By [4], Theorem 3, it will be enough to show that dim L + (x) = n for all x 2 X. Fix any x 2 X, and consider the sequence y l 0;x = l;x (0; : : : ; 0): Then since X is compact (and second countable) there exists a subsequence fy l k 0;x g which converges; let y be so that y l k 0;x ! y. Since \Sigma is transitive, dim L(y) = n, so, by Lemma (4.3), dim L + (x) = n as wanted. Remark 4.5 Clearly, using the same arguments as in Theorem (2), we also have that, if the state space is compact, then transitivity from all x 2 X is equivalent to backward accessibility from all x 2 X. 10 Pass1: Page 11 Recall that for a space Z with a oe-algebra F and a finite measure _, we say that a measurable transformation T : Z ! Z is measure-preserving if for every A 2 F we have _(T \Gamma 1 A) = _(A). The following controllability result is an analogue for discrete-time systems of the result in [5]. The proof is very similar, but it uses the facts just established. Proposition 4.6 Assume that the state space X is a compact Riemannian analytic manifold, and that for all u 2 U the map f u is a measure preserving transformation (for the natural measure in X). Then \Sigma is transitive if and only if \Sigma is controllable. Proof. We need only to prove that transitivity implies controllability. For each u, since f u is a measure preserving map, by the Poincar'e Recurrence Theorem the set of positively Poisson stable points for f u is known to be dense in X. Let x; y 2 X; we need y 2 R(x). By Theorem (2), we know that \Sigma is both forward and backward accessible from x and y. Choose _x 2 int R(x) and _y 2 int C(y); since \Sigma is transitive there exist k, (u k ; : : : ; u 1 ), and (ffl k ; : : : ; ffl 1 ), with each u i 2 U and ffl i = 1 or \Gamma 1, such that: f ffl k u k ffi : : : ffif ffl 1 u 1 (_x) = _y: Let l = number of ffl i = \Gamma 1. We will show by induction on l the following fact: there exist ~x 2 int R(x) and ~y 2 int C(y) such that ~y 2 R(~x). Clearly the previous statement implies our thesis. If l = 0 then the statement holds with ~x = _x and ~y = _y. So let l ? 0 and let i be the first index such that ffl i = \Gamma 1. Define x i = f u i\Gamma 1 ffi : : : ffif u 1 (_x) and y i = f \Gamma 1 u i (x i ) : Since _y 2 int C(y), there exists a neighbourhood V of y i such that f ffl k u k ffi : : : ffif ffl i+1 u i+1 (V ) ` C(y) ; let W = f u i (V ). Since _x 2 int R(x) we can assume (taking V smaller if necessary) that W ` R(x). Choose z i 2 W positively Poisson stable for f u i ; then there exists some n ? 1 such that f n u i (z i ) 2 W and the following properties hold: ffl f n\Gamma 1 u i (z i ) = f \Gamma 1 u i ffif n u i (z i ) 2 V , ffl ^y = f ffl k u k ffi : : : ffif ffl i+1 u i+1 (z i ) 2 int C(y). So we have constructed a trajectory joining z i 2 int R(x) to ^y 2 int C(y) with a number of negative steps strictly less than l; the statement follows by induction. Remark 4.7 The result obtained in the previous Proposition can be applied to any discrete-time system \Sigma that arises through the time-sampling of a continuous-time sys- tem, if the vector fields in the right hand side of the differential equation are conservative. The latter happens for Hamiltonian systems; see for instance [7] for many examples of such Hamiltonian control systems, and the last section of [8] for conditions under which transitivity is preserved under sampling. 11 Pass1: Page 12 5 Accessibility Almost Everywhere We say here that a property holds for "almost all" x 2 X if it holds on an open dense subset of X. Lemma 5.1 Let \Sigma be an n-dimensional, discrete-time, invertible and analytic system. Then the following are equivalent: 1. \Sigma is transitive from almost all x 2 X. 2. dim L(x) = n for almost all x 2 X. 3. \Sigma is forward accessible from almost all x 2 X. 4. dim L + (x) = n for almost all x 2 X. Proof. We will show (1) ! (2) ! (4) ! (3) ! (1). (1) ! (2) This is a consequence of Theorem 4 in [4]. (2) ! (4) Since the system is analytic, and X is connected it will be enough to show that there is at least one x with dim L + (x) = n, because the set where this property holds is either empty or open and dense. To show that there exists such an x we will use the same procedure used in proving Lemma (4.3). Fix any y 2 X for which dim L(y) = n, and let v 1 ; : : : ; v n 2 L be so that fv 1 (y); : : : ; v n (y)g is a basis for L(y). Assume that the v i 's involve vector fields of the form Ad k j 0 X + u j ; with k j 2 ZZ, and choose a positive integer k 0 so that k j + k 0 * 0 for all such j. Applying the operator Ad k 0 0 to the v i 's, there result n linearly independent vectors in L + (x), where x := f \Gamma k 0 0 (y). Thus dim L + (x) = n. (4) ! (3) Again by analyticity, it will be sufficient to find at least one x form which \Sigma is forward accessible. Choose _x regular and let k; u = (u k ; : : : ; u 1 ), and _z be such that: k;_x (u) = _z and ae k;_x (u) = _ae _x : Let W be some neighbourhood of _x so that ae k;x (u) * ae k;_x (u) = _ae _x for each x 2 W . As _x is regular _ae _x = _ae x * ae k;x (u); so there is equality, ae k;x (u) = ae k;_x (u). Define U = f u (W ); 12 Pass1: Page 13 since f u is a diffeomorphism, U is open. Moreover, by maximality of the rank, we have: U ` ~ R k (W ): Since dim L + (x) = n for almost all x, we can choose some z 2 U for which dim L + (z) = n. Let y := f \Gamma 1 u (z) 2 W: Note that then z 2 ~ R k (y) and dim L + (z) = n. We can conclude forward accessibility from y by (4). (3) ! (1) This is clear. Remarks 5.2 (1) Since \Sigma is analytic, in each of the previous statements we can substitute "there exists x 2 X" instead of "for almost all x 2 X." (2) Notice that, in general, the open dense sets in which the previous statements hold are not the same, except for those in parts (1) and (2). In particular, if we denote B := fx j dim L(x) ! ng; we have: ffl B = fx j x is not transitive g, ffl B ` B + L ` B + , and the previous inclusions can be proper. For example, for the system described in example (6.4) below we have: B = ; B + L = f (k; y) j k * 1 ; k 2 ZZ; \Gamma k ^ y ^ k g B + = f (k; y) j k * 0 ; k 2 ZZ; \Gamma k ^ y ^ k g = B + L [ f(0; 0)g: 5.1 Nonconnected Orbits Given any system \Sigma , its state space can be partitioned into invariant submanifolds, the orbits. Since the system restricted to each orbit is transitive, one would like to conclude that relative to each orbit there is forward accessibility from almost every state. Unfortunately, this conclusion is false in general (see example (5.4) below), because orbits are in general not connected. We can prove this fact, however, in the particular case of orbits with at most finitely many connected components, as follows from the next result. Proposition 5.3 Let \Sigma be an n-dimensional, discrete-time, invertible and analytic sys- tem, and assume that the state space X has finitely many connected components. If \Sigma is transitive then it is forward accessible from almost all x 2 X. 13 Pass1: Page 14 Proof. Partition X = S l i=1 X i , into disjoint nonempty open connected subsets. Note that, if x 2 X i and f (x; u) 2 X j , then since X i \Theta U is connected we have that f (X i \Theta U ) ` X j ; (6) by continuity of f . Then for each i there is some j(i) so that: f u (X i ) ` X j(i) i = 1; : : : ; l; for every u 2 U . Fix now any u 2 U . Since f u (X) = X, necessarily S l i=1 X j(i) = X. As f u is a diffeomorphism of X, the X j(i) are all distinct and f u (X i ) = X j(i) . Since \Sigma is transitive, we can conclude that for any p = 1; : : : ; l \Gamma 1, denoting by f p u = f u; : : : ; u -- -z "" p\Gamma times ; the following holds: f p u (X i ) 6= X i 8 i = 1; : : : ; l: (7) If this were not the case and there exists such p and i, then applying (6) p-times we would have: f u 1 ;:::;u p (X i ) = X i for all (u 1 ; : : : ; u p ) 2 U p . Thus the set p\Gamma 1 [ j=0 f j u (X i ) will be an invariant set different from X, which contradicts the assumption that \Sigma is an orbit. Moreover from (7), since l is finite, we can conclude that: f u 1 ;:::;u l (X i ) = X i 8 i: (8) By repeating the arguments used in the proof of the Lemma 5.1 (2 ! 4) we conclude that there exists x 2 X such that dim L + (x) = n. Assume that x 2 X i . Since X i is connected we have: dim L + (y) = n from almost all y 2 X i : Choose _x 2 X i , _x regular and let k; u = (u k ; : : : ; u 1 ), and _z be such that: k;_x (u) = _z and ae k;_x (u) = _ae _x : By inequality (2) we can assume that k is a multiple of l. Thus, by (7), we get that _z 2 X i . Now, we can repeat the arguments used in the proof of the Lemma 5.1 (4 ! 3) and conclude that \Sigma is forward accessible from almost all x 2 X i . To conclude that \Sigma is forward accessible from almost all x 2 X it is enough to notice that, for any j 6= i, (7) implies that there exists p such that: f u 1 ;:::;u p (X j ) = X i : 14 Pass1: Page 15 Example 5.4 Consider the following analytic system, with X = IR 2 , U = IR, and equations: x + = x + 1 y + = y + uh(x) ; where h(x) is any analytic function whose zeros are exactly at the positive integers f1; 2; 3; : : :g. This system is easily seen to be invertible. Let z 0 = (0; 0). Then it is easy to verify that the orbit O(z 0 ) is as follows: O(z 0 ) = [ i2ZZ R i ; R i = f (i; y) j y 2 IR g: If we restrict the system to this orbit, the restricted system is not forward accessible from any the points in R i , for each i = 1; 2; 3; : : :. This is because there it holds that h(x) = 0, so z + and z must have the same y-coordinate. 6 Low-Dimensional Cases In this section we make some remarks about one- and two-dimensional systems. 6.1 Dimension One There we consider systems for which the state space X is of dimension one. The pointwise versions of [4], Theorem 3, hold for these systems as follows. Lemma 6.1 Let \Sigma be as above, and pick x 2 X. Then: 1. if \Sigma is smooth then \Sigma is forward accessible from x if and only if dim \Gamma + (x) = 1, 2. if \Sigma is analytic and U is connected then \Sigma is forward accessible from x if and only if dim L + (x) = 1. Proof. (1) The necessary part follows from part (a) of Theorem 6 in [4], so we will prove sufficiency. If \Sigma is not forward accessible from x then f (x; u) must be independent of u. Moreover if y = f u k ;:::;u 1 (x), since \Sigma is also not forward accessible from y, also f (y; u) = f (f u k ;:::;u 1 (x); u) must be independent of u. Thus: Ad u k ;:::;u 1 X + u 0 (x) = @ @v fi fi fi fi fi v=0 f \Gamma 1 u k ;:::;u 1 ffif \Gamma 1 u 0 ffif u 0 +v ffif u k ;:::;u 1 (x) = 0 15 Pass1: Page 16 which implies dim \Gamma + (x) = 0. (2) The necessary part follows from part (b) of Theorem 6 in [4]. Sufficiency is a consequence of (1), since L + (x) ` \Gamma + (x). Lemma 6.2 Let \Sigma be a one-dimensional, discrete-time, invertible system, and pick any x 2 X so that \Sigma is transitive from x. Then, either \Sigma is forward accessible from x or \Sigma is backward accessible from x. Proof. Suppose that neither conclusion holds. We claim that, for each u 2 U , \Sigma is not forward nor backward accessible from y = f u (x). Since x is not forward accessible, f (x; u) is independent of u. Thus y = f u (x) for all u 2 U , so also f \Gamma 1 u (y) = x for all u 2 U: It follows that C 1 (y) = x, which implies that C k (y) = C k\Gamma 1 (x) for all k * 1: Thus if \Sigma would be backward accessible from y also \Sigma would be backward accessible from x. Clearly, forward accessibility from y would imply forward accessibility from x (in any dimension). So the claim is proved. With the same arguments we can prove that \Sigma is not forward nor backward accessible from z = f \Gamma 1 u (x) for all u 2 U . Now we want to prove that dim \Gamma (x) = 0, which implies that \Sigma in not transitive from x. In order to do that, we will show that: Ad ffl k ;:::;ffl 1 u k ;:::;u 1 X oe u 0 (x) = 0 for all k * 0; (u k ; : : : ; u 1 ); ffl i = 1 or \Gamma 1; oe = 1 or \Gamma 1; and for all x which are neither forward nor backward accessible. We will use induction on k. Take first k = 0. ffl If oe = 1: X + u 0 (x) = @ @v fi fi fi fi fi v=0 f \Gamma 1 u 0 ffif u 0 +v (x) = 0 since f (x; \Delta ) is independent of u (\Sigma is not forward accessible from x). ffl If oe = \Gamma 1: X \Gamma u 0 (x) = @ @v fi fi fi fi fi v=0 f u 0 ffif \Gamma 1 u 0 +v (x) = 0 since f \Gamma 1 (x; \Delta ) is independent of u (\Sigma is not backward accessible from x). Take now any k ? 0 and note that: Ad ffl k ;:::;ffl 1 u k ;:::;u 1 X oe u 0 (x) = (df ffl k u k (x)) \Gamma 1 Ad ffl k\Gamma 1 ;:::;ffl 1 u k\Gamma 1 ;:::;u 1 X oe u 0 (f ffl k u k (x)): From the first part of the proof, we have that \Sigma is also neither forward nor backward accessible from f ffl k u k (x), so, by inductive assumption, this last vector is zero. 16 Pass1: Page 17 Remark 6.3 A consequence of the two previous Lemmas is that, for each x: 1. dim L(x) = 1 if and only if dim L + (x) = 1 or dim L \Gamma (x) = 1. 2. dim \Gamma (x) = 1 if and only if dim \Gamma + (x) = 1 or dim \Gamma \Gamma (x) = 1. The result in Lemma (6.2) is true only pointwise. In fact we can find a one- dimensional, analytic system \Sigma which is transitive but is neither forward nor backward accessible. One example of such a system is as follows. Consider the following system: x + = 1 + x + u 2 g(x) (9) with X = IR, U = [\Gamma 1; 1], and where g(x) is the following function: g(x) = sin(ssx) ssx (10) It is easy to verify that jg 0 (x)j ^ 1 for all x 2 IR. Moreover, g(x) = 0 if and only if x 2 ZZ n f0g. Since jg 0 (x)j ^ 1, this system is invertible. Moreover the following properties hold and are easily verified: 1. \Sigma is transitive, 2. if x = 1; 2; 3; : : : then \Sigma is backward accessible but not forward accessible from x, 3. if x = \Gamma 1; \Gamma 2; \Gamma 3; : : : then \Sigma is forward accessible but not backward accessible from x. 6.2 Dimension Two We now show that both the results in Lemmas (6.1) and (6.2) are false if the dimension of the state space X is greater than one, even if the system is invertible, analytic and with a connected control space U. The following example illustrates these facts. Example 6.4 Consider the discrete-time, analytic system with X = IR 2 ; U = [\Gamma 1; 1] 2 ; and equations: x + = x + 1 + u 2 sin(y)g(x) y + = y + v where g(x) is the function in (10). This system is invertible. In fact the determinant of the Jacobian matrix of the map f u;v (x; y) is given by: 1 + u 2 sin(y)g 0 (x): 17 Pass1: Page 18 Since u 2 [\Gamma 1; 1]; j sin(y)j ^ 1 and jg 0 (x)j ^ 1, j u 2 sin(y)g 0 (x)j ! 1 so the determinant is nonzero for all x, y. Moreover it is easy to verify that for each (u; v) 2 U , the map f u;v (\Delta ; \Delta ) is bijective. We wish to study the behavior of this system when starting from x = 0; y = 0. Let z 0 = (0; 0). We prove the following properties: 1. the system is not forward accessible from z 0 , 2. the system is not backward accessible from z 0 , 3. dim L + (z 0 ) = 2, 4. the system is transitive from z 0 . Proof. (1) This follows from the equality R k (z 0 ) = f (k; y) j \Gamma k ^ y ^ k g which holds for each k * 1 and it is clear from the equations. (2) It will be sufficient to show that: C k (z 0 ) = f (\Gamma k; y) j \Gamma k ^ y ^ k g (11) First note that if (x k ; y k ) 2 C k (z 0 ) then we can write y k + v 1 + : : : + v k = 0 with all jv i j ^ 1, so jy k j ^ k. To prove (11), it is now sufficient to notice the following. For any fixed u 2 [\Gamma 1; 1] and any y 2 IR, the function x h 7\Gamma ! x + 1 + u 2 sin(y)g(x) is invertible. Moreover h \Gamma 1 (\Gamma k + 1) = \Gamma k for all k * 1; independently of u and y. Thus x = \Gamma k is the only solution of h(x) = \Gamma k + 1, for all u; y, and we have proved C k (z 0 ) ` f (\Gamma k; y) j \Gamma k ^ y ^ k g: The other inclusion is obvious. (3) Consider the vector fields X + (u;v);1 (z) = (df (u;v) (z)) \Gamma 1 @ @ffl fi fi fi fi fi ffl=0 f (u+ffl;v) (z) 18 Pass1: Page 19 and X + (u;v);2 (z) = (df (u;v) (z)) \Gamma 1 @ @ffl fi fi fi fi fi ffl=0 f (u;v+ffl) (z) : Fix (u; v) = (0; 0). Then: df (0;0) (z) = 1 0 0 1 ! for all z 2 IR 2 , X + (0;0);1 (z) = sin(y)g(x) 2 0 ! ; and X + (0;0);2 (z) = 0 1 ! : So: h X + (0;0);1 ; X + (0;0);2 i (z) = cos(y)g(x) 2 0 ! : In particular, X + (0;0);2 (z 0 ) = 0 1 ! and h X + (0;0);1 ; X + (0;0);2 i (z 0 ) = 1=2 0 ! ; so dim L + (z 0 ) = 2 as desired. (4) Transitivity at z 0 is a consequence of (3) since dim L + (z 0 ) = 2 implies dim L(z 0 ) = 2. 7 Control Sets The next definition is a precise analogue of that in [2], except that we make the assump- tion of nonempty interior. Definition 7.1 A set D ` X is called a precontrol set if D ` clos R(x) for all x 2 D and int D 6= ;. A precontrol set which is maximal with respect to set inclusion is called a control set . Note that if D is a precontrol set, then in D the system \Sigma is "almost" controllable, in the sense that if x; y 2 D then from x it is possible to reach any neighbourhood of y. 19 Pass1: Page 20 Lemma 7.2 Let D ` X be a control set. Pick any two elements _x; _y in int D. Then, for each sequence (u 0 ; : : : ; u T ) 2 U T +1 such that f u T ffi : : : ffif u 0 (_x) = _y we have that, necessarily, also f u k ffi : : : ffif u 0 (_x) 2 int D for k = 0; : : : ; T \Gamma 1: Proof. Let _x; _y , u 0 ; : : : ; u T be as in the statement and let E be the following set: E := f f u k ffi : : : ffif u 0 (_x) ; k = 0; : : : ; T \Gamma 1 g: We will first prove that E ` D, by showing that D 0 = D S E is again a precontrol set and using that D is maximal. For this, we must prove that: D 0 ` clos R(x) for each x 2 D 0 : Observe that E ` R(_x) ` clos R(_x) and _y 2 R(y) ` clos R(y) for all y 2 E . Thus: ffl E ` clos R(_x) ` clos R(clos R(x)) = clos R(x) 8x 2 D ffl D ` clos R(x) 8x 2 D ffl If y 2 E then D ` clos R(_y) ` clos R(clos R(y)) = clos R(y) and E ` clos R(_x) ` clos R(clos R(_y)) ` clos R(y). Thus: D S E = D 0 ` clos R(x) 8x 2 D 0 . So we have proved that, for any two points _x, _y in int D and any trajectory joining them, all the intermediate states must be in D. We now prove that such intermediate points must be in int D. Pick any _x, _y, u 0 ; : : : ; u T as above. Let k 2 f0; : : : ; T \Gamma 1g and _z = f u k ffi : : : ffif u 0 (_x). By continuity of f \Gamma 1 u 0 ffi : : : ffif \Gamma 1 u k and of f u k+1 ffi : : : ffif u T , there exists some open neighbourhood V of _z such that: f \Gamma 1 u 0 ffi : : : ffif \Gamma 1 u k (V ) ` int D and f u k+1 ffi : : : ffif u T (V ) ` int D: Pick any z 2 V . For such a z, z = f u k ffi : : : ffif u 0 (x) for some x 2 int D and y = f u k+1 ffi : : : ffif u T (z) 2 int D: Thus, applying the first part of the proof to x and y (rather than to _x and _y), it follows that z 2 D: We conclude that V ` D; so _z is in int D; as desired. 20 Pass1: Page 21 Lemma 7.3 Let D ` X be a precontrol set. Then we have: D ` clos F k (int D) for all k = 0; 1; 2; : : : where F k (int D) = [ l*k R l (int D) Proof. We proceed by induction on k. The case k = 0 follows directly from the defintion of control set. So let k * 1 and pick any x 2 D. Choose y 2 int D; y 6= x: By inductive assumption there exists a sequence y n ! y with y n 2 F k (int D): For _n sufficiently large, y _n 2 D (since y 2 int D) and y _n 6= x (since y 6= x), where each y _n is of the form y _n = l;z (u) with z 2 int D; l * k; for some u 2 U l . Pick one such _n. Since x 2 clos R(y _n ), there exist a sequence ft n g and a sequence fz n g so that z n 2 R t n (y _n ) and z n ! x: Since y _n 6= x we can assume t n * 1 for all n. Thus z n 2 R l+t n (z) ` F k+1 (int D); which implies x 2 clos F k+1 (int D). Remark 7.4 The conclusion of the previous lemma can be rephrased by saying that: D ` lim k R k (int D) where for any family of sets E k ; lim k E k = T 1 k=0 S l*k E l : Lemma 7.5 Let D ` X be a control set. Then : clos D = clos int D Proof. Let x 2 D: We only need to prove that for any neighbourhood W of x, W " int D 6= ; Pick any such W and choose any y 2 int D: Since y 2 clos R(x); we can find z = k;x (u) for some k * 0 and some u 2 U k , such that z 2 int D: Let U z be a neighbourhood of z contained in D. Then, by continuity, there exists a neighbourhood U x of x such that for all y 2 U x ; k;y (u) is in U z and so, in particular, in int D. Let W x = U x " W: Choose y 0 2 int D: Since x 2 clos R(y 0 ), we can find k 0 ; u 0 such that _x := k 0 ;y 0 (u 0 ) 2 W x : 21 Pass1: Page 22 Let _u be the concatenation of u 0 and u. Since _x 2 U x ; k;_x (u) 2 int D: Thus k+k 0 ;y 0 ( _ u) 2 int D; so by Lemma (7.2), _x 2 int D. Hence W x " int D 6= ;; so W " int D 6= ; as wanted. Definition 7.6 Let x 2 X and S ` X. We say that x is forward accessible in S (resp. backward accessible in S ) if int (R(x) " S) 6= ; (resp. int (C(x) " S) 6= ;). If we simply say that x is forward (backward) accessible, we mean forward (backward) accessible in X. Lemma 7.7 Let S ` X and define: S f = f x 2 M j x is forward accessible in S g; then S f is open. Proof. If S f = ;, then it is trivially open; thus assume S f 6= ;. Pick any x 2 S f . By assumption there exists W ` S open such that W ` R(x); therefore there exists k such that W " R k (x) has nonzero measure. Let U k W = f u j u 2 U k ; and k;x (u) 2 W g; then U k W is open and the image of k;x j U k W has nonzero measure. It follows, by Sard's Theorem, that there exists u 2 U k such that ae k;x (u) = n. We may assume, without loss of generality, that u 2 int U k . Now pick any neighbourhood V of x such that k;V (u) ` W and still ae k;y (u) = n for all y 2 V . By the implicit mapping theorem, V ` S f ; therefore S f is open. We assume from now on that the system \Sigma to be analytic and transitive. In this case, we can conclude the following important property of precontrol sets. Theorem 3 Let D ` X be a precontrol set. Then every point of D is forward accessible in D. 22 Pass1: Page 23 Proof. Since \Sigma is transitive and analytic, by Lemma 5.1 we have that there exists an open dense set of points for which dim L + (x) = n. If we intersect this set with int D then this intersection, which we denote by W , is open. Pick any x 2 D, and y in W , with x 6= y. Now, we will construct a sequence of elements y n such that y n ! y; y n 2 R k n (x) and k n ! 1 as n ! 1: Then, using Lemma 4.1 and its succesive Remarks, we can conclude that from x it is possible to reach an open set within any neighbourhood of y, i.e. since y 2 int D, x is forward accessible in D, as desired. To construct the y n 's we proceed as follows. Let's denote by W n a neighbourhood of y. Since y 2 clos R(x), we can find y 1 2 W 1 , y 1 6= y, and y 1 2 R k 1 (x) where (since y 6= x) we can assume k 1 * 1. Now we proceed by induction. Suppose that we have found y 1 ; : : : ; y n such that: y i 2 W i ; y i 6= y; y i 2 R k i (x) and k i * i for i = 1; : : : ; n: Since y 2 clos R(y n ) we can find y n+1 2 W n+1 such that y n+1 6= y; y n+1 2 R l (y n ) with l * 1: Since y n 2 R k n (x), y n+1 2 R k n +l (x) and k n+1 = k n + l * n + 1: Thus k n ! 1 as n ! 1; moreover, we can choose the W i 's in such a way that y n ! y. The definition of precontrol set is not reversible in time, so we cannot conclude back- ward accessibility from every point. However, the next result provides backward accessi- bility from a dense subset. Proposition 7.8 Let D ` X be a control set. Then there exists some (necessarily nonempty) open subset E ` D such that: 1. clos E = clos D; 2. if y 2 E then y is backward accessible in D. Proof. Since \Sigma is transitive and analytic, by Lemma 5.1 applied to the "inverse" system x(t + 1) = f \Gamma u (x(t)); we know that there exists an open dense set from which we have backward accessibility. Moreover, there exists some integer k 0 such that the set G of states x 2 X for which int C k 0 (x) 6= ; and clos int C k (x) = clos C k (x) for all k * k 0 is itself open dense (Remark 3.4). Consider first the open set E 0 = int D " G: 23 Pass1: Page 24 We claim that E 0 is open and clos E 0 = clos int D: In order to show this, it is enough to establish that int D ` clos E 0 . So take any x 2 int D. By density of G, there exists some sequence fy n g with y n 2 G for all n, y n ! x. Thus y n 2 int D " G for all large enough n, and this shows that x 2 clos E 0 . Finally, let: E = E 0 " F k 0 (int D) where F k 0 (int D) is defined as in Lemma (7.3). Then E is also open, since F k (int D) is open for any k. Moreover, using the result in Lemma (7.3) (i.e. D ` clos F k 0 (int D)) and the same arguments used before we have clos E = clos E 0 = clos int D: Thus, by Lemma (7.5), clos E = clos D: So E satisfies property (1). We prove next that it also satisfies (2). Pick y 2 E. Since y 2 F k 0 (int D) then there exists x 2 int D so that y 2 R k (x) for some k * k 0 . This means that x 2 C k (y). Since y 2 G, x 2 clos int C k (y): Thus, since x 2 int D, we can find some z 2 int D " int C k (y), which means that y is backward accessible in D. Thus (2) is proved. Lemma 7.9 Let D ` X be a control set and let E be any set as in the conclusion of the previous Proposition. Then E ` R(x) for each x 2 D: Proof. Take any y 2 E and x 2 D. By the previous Proposition, there exists some nonempty open set W ` D " C(y). Choose any z 2 W . Since D is a control set, z 2 clos R(x), so there exists also ~z 2 R(x) " W . Thus ~z 2 R(x) and y 2 R(~z) (since ~z 2 C(y)) imply y 2 R(x). Definition 7.10 For any set S ` X, define: Core (S) := f x 2 int S j x is forward and backward accessible in S g: Using Lemma (7.7) twice (once for \Sigma and another time for the "inverse" system x(t+1) = f \Gamma u (x(t))), we can conclude the following. 24 Pass1: Page 25 Lemma 7.11 For any subset S ` X, Core (S) is open. For a control set D, we proved (see results in Theorem 3 and Proposition (7.8)) that Core (D) ' E for some E ` D such that clos E = clos D. Thus we have: clos Core (D) = clos D for a control set D: (12) Moreover the result in Lemma (7.9) can be rephrased as follows. Proposition 7.12 If D is a control set, and E = Core (D), then E ` R(x) for all x 2 D. If D is a control set, then, by the previous results, Core (D) is a dense subset of D in which we have exact controllability. Note that if \Sigma was a continuous time system then Core (D) would have been equal to int D. However for discrete-time systems there are control sets D for which Core (D) is strictly contained in int D, as it is shown in the next example. Example 7.13 Let us consider the discrete-time, analytic system with X = IR 2 ; U = [\Gamma 1; 1] 2 ; and equations: x + = x + 1 + uy y + = y + v 2 g(x) where g(x) is the function in (10). This system is invertible. In fact the determinant of the Jacobian matrix of the map f u;v (x; y) is given by: 1 \Gamma uv 2 g 0 (x): Since u; v 2 [\Gamma 1; 1]; and jg 0 (x)j ^ 1, j uv 2 g 0 (x)j ^ 1=2 so the determinant is nonzero for all x, y. Moreover it is easy to verify that for each (u; v) 2 U , the map f u;v (\Delta ; \Delta ) is bijective. It is also easy to prove that this system is transitive. For this system we can see that for all k 2 IN with k * 1 the following hold: 1. the points of the type (\Gamma k; 0) are not backward accessible, 2. the points of the type (k; 0) are not forward accessible. Let: B = f (k; 0) j k 2 IN; k * 1 g: Next we want to show that D = IR 2 n B is a control set. 25 Pass1: Page 26 Notice that D is certainly maximal; in fact, no points in B could belong to a control set, since they are not forward accessible. To prove that D satisfies: D ` _ R(,) for all , 2 D (13) we will prove the following: IR 2 n f (k; y) j k 2 ZZ; y 2 IR g ` R(,) (14) which, by taking the closure in both sides, implies (13). Let F = f (k; y) j k 2 ZZ; y 2 IR g. First we notice that, since j sin(ss(x + 1))j = j sin(ssx)j, if we apply to any (x; y) a control sequence of the form: u l = 0; v l = sign (g(x + l \Gamma 1)); (15) then, after k steps, we will reach the point: x k = x + k y k = y + j sin(ssx)j 2ss k\Gamma 1 X l=0 1 jx + lj : Using this fact and the divergence of the series P n 1=n we will prove (14). Fix (_x; _y) 2 D and (~x; ~y) 2 IR 2 n F . Notice that, since (_x; _y) 62 B, it is not restrictive to assume: g(_x) 6= 0 and _y 6= 0: First we choose u l ; v l as in (15). Since g(_x) 6= 0 there exists k such that y k ? 1. Next we apply a control sequence with all v l = 0 so as to reach a state (x 0 ; y 0 ) of the type: x 0 = ~x \Gamma n and y 0 = y k where n is a positive integer that will be chosen later. Notice that we can assume ~y ! y 0 . Now we want to find a sequence of controls (0; v l ) such that we get the state (~x; ~y) in exactly n steps. It is clear that this is possible if and only if: y 0 \Gamma j sin(ss ~x)j 2ss n\Gamma 1 X l=0 1 j~x \Gamma n + lj ^ ~y (16) So we just have to choose n large enough such that (16) is satisfied. This is possible since sin(ss ~x) 6= 0 and: n\Gamma 1 X l=0 1 j~x \Gamma n + lj = n X m=1 1 j~x \Gamma mj is divergent. Thus D is a control set. Notice that, for this control set D, Core (D) is strictly contained in D = int D. In fact, none of the points of the type (\Gamma k; 0) with k a strictly positive integer, belongs to Core (D). 26 Pass1: Page 27 References [1] Albertini, F., and E.D. Sontag, "Some connections between chaotic dynamical sys- tems and control systems," in Proc. European Control Conference, Grenoble, July 1991. (To appear.) [2] Colonius, F., and W. Kliemann, "Some aspects of control systems as dynamical sys- tems," Report No.223, Inst. Math., Univ. Augsburg, 1990. [3] Fliess, M. and D. Normand-Cyrot, "A group-theoretic approach to discrete-time non- linear controllability," Proc. IEEE Conf. Dec. Control, 1981. [4] Jakubczyk, B., and E.D. Sontag, "Controllability of nonlinear discrete-time systems: A Lie-algebraic approach," SIAM J. Control and Opt. 28(1990): 1-33. [5] Lobry, C., "Controllability of nonlinear systems on compact manifolds," SIAM J. Control 12(1974): 1-4. [6] Mokkadem, A., "Orbit theorems for semigroups of regular morphisms and nonlin- ear discrete time systems," Report SYCON-90-01, Rutgers Center for Systems and Control, January 1990, submitted for publication. [7] Nijmeijer, H., and A.V. Van der Schaft, Nonlinear Dynamical Control Systems, Springer-Verlag, New York, 1990. [8] Sontag, E.D., "Integrability of certain distributions associated with actions on mani- folds and applications to control problems," in Nonlinear Controllability and Optimal Control (H.J. Sussmann, ed.), pp. 81-131, Marcel Dekker, NY 1990. [9] Sontag, E.D., Mathematical Control Theory, Deterministic Finite Dimensional Sys- tems, Springer-Verlag, New York, 1990. 27