No description available.

No description available.

No description available.

Given two structures M and N on the same domain, we say that N is a reduct of M if all emptyset-definable relations of N are emptyset-definable in M. In this thesis, the reducts of the generic digraph, the Henson digraphs, the countable vector space over F_2 and of the linear order Q.2 are classified up to first-order interdefinability. These structures are aleph_zero-categorical, so classifying their reducts is equivalent to classifying the closed groups that lie in between the structures’ automorphism groups and the full symmetric group.

The thesis examines two dimensions of constructivity that manifest themselves within foundational systems for Bishop constructive mathematics: intuitionistic logic and predicativity. The latter, in particular, is the main focus of the thesis. The use of intuitionistic logic affects the notion of proof : constructive proofs may be seen as very general algorithms. Predicativity relates instead to the notion of set: predicative sets are viewed as if they were constructed from within and step by step. The first part of the thesis clarifes the algorithmic nature of intuitionistic proofs, and explores the consequences of developing mathematics according to a constructive notion of proof. It also emphasizes intra-mathematical and pragmatic reasons for doing mathematics constructively. The second part of the thesis discusses predicativity. Predicativity expresses a kind of constructivity that has been appealed to both in the classical and in the constructive tradition. The thesis therefore addresses both classical and constructive variants of predicativity. It examines the origins of predicativity, its motives and some of the fundamental logical advances that were induced by the philosophical re ection on predicativity. It also investigates the relation between a number of distinct proposals for predicativity that appeared in the literature: strict predicativity, predicativity given the natural numbers and constructive predicativity. It advances a predicative concept of set as unifying theme that runs across both the classical and the constructive tradition, and identifies it as a forefather of a computational notion of set that is to be found in constructive type theories. Finally, it turns to the question of which portions of scientifically applicable mathematics can be carried out predicatively, invoking recent technical work in mathematical logic.

The present thesis is a contribution to a project that is carried out by Michael Rathjen and Andreas Weiermann to give a general method to study the proof-complexity of Pi_2 sentences. This general method uses the generalised ordinal-analysis that was given by Buchholz, Rueede and Strahm as well as the generalised characterisation of provable-recursive functions of PA with axioms for transfinite induction that was given by Weiermann. The present thesis links these two methods by giving an explicit elementary bound, for the proof-complexity increment that occurs after the transition from the theory that was used by Rueede and Strahm, to PA with axioms for transfinite induction, which was analysed by Weiermann.

The study of set theory (a mathematical theory of infinite collections) has garnered a great deal of philosophical interest since its development. There are several reasons for this, not least because it has a deep foundational role in mathematics; any mathematical statement (with the possible exception of a few controversial examples) can be rendered in set-theoretic terms. However, the fruitfulness of set theory has been tempered by two difficult yet intriguing philosophical problems: (1.) the susceptibility of naive formulations of sets to contradiction, and (2.) the inability of widely accepted set-theoretic axiomatisations to settle many natural questions. Both difficulties have lead scholars to question whether there is a single, maximal Universe of sets in which all set-theoretic statements are determinately true or false (often denoted by ‘V ’). This thesis illuminates this discussion by showing just what is possible on the ‘one Universe’ view. In particular, we show that there are deep relationships between responses to (1.) and the possible tools that can be used in resolving (2.). We argue that an interpretation of extensions of V is desirable for addressing (2.) in a fruitful manner. We then provide critical appraisal of extant philosophical views concerning (1.) and (2.), before motivating a strong mathematical system (known as‘Morse-Kelley’ class theory or ‘MK’). Finally we use MK to provide a coding of discourse involving extensions of V , and argue that it is philosophically virtuous. In more detail, our strategy is as follows: Chapter I (‘Introduction’) outlines some reasons to be interested in set theory from both a philosophical and mathematical perspective. In particular, we describe the current widely accepted conception of set (the ‘Iterative Conception’) on which sets are formed successively in stages, and remark that set-theoretic questions can be resolved on the basis of two dimensions: (i) how ‘high’ V is (i.e. how far we go in forming stages), and (ii) how ‘wide’ V is (i.e. what sets are formed at successor stages). We also provide a very coarse-grained characterisation of the set-theoretic paradoxes and remark that extensions of universes in both height and width are relevant for our understanding of (1.) and (2.). We then present the different motivations for holding either a ‘one Universe’ or ‘many universes’ view of the subject matter of set theory, and argue that there is a stalemate in the dialectic. Instead we advocate filling out each view in its own terms, and adopt the ‘one Universe’ view for the thesis. Chapter II (‘G¨odel’s Programme’) then explains the Universist project for formulating and justifying new axioms concerning V . We argue that extensions of V are relevant to both aspects of G¨odel’s Programme for resolving independence. We also identify a ‘Hilbertian Challenge’ to explain how we should interpret extensions of V , given that we wish to use discourse that makes apparent reference to such nonexistent objects. Chapter III (‘Problematic Principles’) then lends some mathematical precision to the coarse-grained outline of Chapter I, examining mathematical discourse that seems to require talk of extensions of V . Chapter IV (‘Climbing above V ?’), examines some possible interpretations of height extensions of V . We argue that several such accounts are philosophically problematic. However, we point out that these difficulties highlight two constraints on resolution of the Hilbertian Challenge: (i) a Foundational Constraint that we do not appeal to entities not representable using sets from V , and (ii) an Ontological Constraint to interpret extensions of V in such a way that they are clearly different from ordinary sets. 5 Chapter V (‘Broadening V ’s Horizons?’), considers interpretations of width extensions. Again, we argue that many of the extant methods for interpreting this kind of extension face difficulties. Again, however, we point out that a constraint is highlighted; a Methodological Constraint to interpret extensions of V in a manner that makes sense of our naive thinking concerning extensions, and links this thought to truth in V . We also note that there is an apparent tension between the three constraints. Chapter VI (‘A Theory of Classes’) changes tack, and provides a positive characterisation of apparently problematic ‘proper classes’ through the use of plural quantification. It is argued that such a characterisation of proper class discourse performs well with respect to the three constraints, and motivates the use of a relatively strong class theory (namely MK). Chapter VII (‘V -logic and Resolution’) then puts MK to work in interpreting extensions of V . We first expand our logical resources to a system called V -logic, and show how discourse concerning extensions can be thereby represented. We then show how to code the required amount of V -logic usingMK. Finally, we argue that such an interpretation performs well with respect to the three constraints. Chapter VIII (‘Conclusions’) reviews the thesis and makes some points regarding the exact dialectical situation. We argue that there are many different philosophical lessons that one might take from the thesis, and are clear that we do not commit ourselves to any one such conclusion. We finally provide some open questions and indicate directions for future research, remarking that the thesis opens the way for new and exciting philosophical and mathematical discussion.

This thesis explores the effect of different types of underlying network structure on the dynamical behaviour of a competitive population - a situation encountered in many real-world complex systems. In the first part of the thesis, I focus on generic, but abstract, multi-agent systems. I start by presenting analytic and numerical results for a population of heterogeneous, decision-making agents competing for some limited global resource, in which connections arise unintentionally between agents as a by-product of their strategy choices. I show that accounting for the resulting groups of strongly-correlated agents - in particular, the crowds and so-called 'anticrowds' - yields an accurate analytic description of the systems dynamics. I then introduce a local communication network between the agents, enabling them to intentionally share information among themselves. Such an interaction network leads to highly non-trivial dynamics, forcing a trade-off between individual and global success. Introducing corruption into the information being exchanged between agents, gives rise to a novel phase transition. I then provide a quantitative analytic theory of these various numerical results by generalizing the Crowd-Anticrowd formalism to include such local interactions. In the second part of the thesis, I consider a real-world system which also features competitive populations and networks - a cancer tumour, which contains cancerous cells competing for space and nutrients in the presence of an underlying vasculature structure. To simplify the analysis and comparison to real clinical data, the model chosen is far simpler than that discussed in the first part of the thesis - however despite its simplicity, the model is shown to yield remarkably good agreement with empirical findings. In addition, the model shows how different treatment methods can lead to a wide variety of unexpected re-growth behaviours of the tumour.

The expeditious development of technology in the past decades resulted in the introduction of concurrent systems that incorporate both ubiquitous and pervasive computing, the ambient systems. These systems are named after their ability to be completely embedded in the environment in which they operate and interact with the users, in a silent and non distracting way, facilitating the completion of their tasks. Hence, there is a growing need to introduce and develop formal techniques for computational models capable of faithfully modelling the behaviour of these systems. One way of capturing the intricate behaviours of the ambient systems is to use Petri nets, which are a modelling language that is used for the representation and analysis of concurrent systems. Within the domain of rigorous system design, verification of systems effectively checks and guarantees the correctness of the examined models with respect to the specification. This work investigates the modelling and the analysis of ambient systems using Petri nets. To examine the modelling of these systems, their taxonomy into Ambient Guidance Systems and Ambient Information Systems is carried out and a case study is used for the modelling of each category. To model ambient systems, the step-modelling approach and a variant class of Coloured Petri Nets, the Ambient Petri Nets (APNs), are introduced. Step modelling approach focuses on the interaction between the system and the user and Ambient Petri Nets is a class of nets with colour-sensitive inhibitor arcs that is used especially for the structural and behavioural representation of ambient systems. For the modelling of general ambient systems, the compositionality of the Ambient Petri Nets is used. To verify the correctness of the produced Ambient Petri Nets models, the introduction of the Transformed Ambient Petri Nets class that has no colour-sensitive inhibitor arcs is required since Charlie and generally most of the existing verification tools do not support the analysis of inhibitor nets. To address this problem, a construction is defined to translate the Ambient Petri Nets into Transformed Ambient Petri Nets. Afterwards, the Step Transition Systems are used to prove the behavioural equivalence of the nets that are associated through the construction. Subsequently, the Transformed Ambient Petri Nets models of the chosen case studies are verified against model checking and qualitative properties. For the first category, Computation Tree Logic (CTL) is used to check the models against important properties of the ambient systems that are related to their features and their general functioning. Finally, qualitative properties consider fundamental structural and behavioural properties of Petri nets that provide useful outcome about the systems under consideration.

Political, environmental, and commercial needs for information on the Earths surface and atmosphere drive the development of improved satellite data products. At visible and thermal wavelengths the quality of these products is dependent on our ability to distinguish between clouds and the underlying surface. Unlike oceans, land surfaces are highly heterogeneous, containing a wide range of materials, some of which exhibit similar spectral properties to cloud, and hence it is much harder to distinguish between the two. ~ This research project, supported by the Along-Track Scanning Radiometer (ATSR) science team at the Rutherford Appleton Laboratory (RAL), addresses the need for improved cloud detection over land surfaces through the development of an unsupervised cloud detection system for global ATSR-2 scenes over land surfaces. The thesis details the development of the first successful un-supervised near-global cloud detection scheme for ATSR-2 scenes over land surfaces. The scheme developed operates on ATSR-2 data using a fuzzy set methodology. The level of membership of the fuzzy sets is determined using aggregated Gaussian distribution functions defined in a knowledge base that has been developed from the International Satellite Cloud Climatology Project (ISCCP) data sets. This is the first cloud detection algorithm that is uniquely customisable to its end users needs. Specifically, this is achieved through the use of fuzzy set theory and set membership grades. This elegant solution to the problem achieves cloud detection as oppose to cloud clearing, and its final output retains all the information computed on possible classifications of image pixels, thus providing the end user with a true representation of the imprecision inherent in the real-world data. A comprehensive quantitative evaluation and inter-comparison of cloud clearing schemes is presented. This showed that with respect to other algorithms (in literature and currently under development at RAL) F-CLOUD is one of the frontrunners in a new generation of cloud detection algorithms over land surfaces. The scheme is highly accurate and has immediate potential applications within the development programme of future ATSR-2/AATSR products at RAL. Using confusion matricies to analyse hardened results yielded a mean classification accuracy of 92.3% (for a total of forty-five scenes analysed against neph-analysis derived cloud masks).