Bilattice logic of epistemic actions and knowledge

Baltag, Moss, and Solecki proposed an expansion of classical modal logic, called logic of epistemic actions and knowledge (EAK), in which one can reason about knowledge and change of knowledge. Kurz and Palmigiano showed how duality theory provides a flexible framework for modeling such epistemic changes, allowing one to develop dynamic epistemic logics on a weaker propositional basis than classical logic (for example an intuitionistic basis). In this paper we show how the techniques of Kurz and Palmigiano can be further extended to define and axiomatize a bilattice logic of epistemic actions and knowledge (BEAK). Our propositional basis is a modal expansion of the well-known four-valued logic of Belnap and Dunn, which is a system designed for handling inconsistent as well as potentially conflicting information. These features, we believe, make our framework particularly promising from a computer science perspective.     

Measuring the effects of knowledge in military campaigns

A particularly difficult problem in command and control is that of identifying the relationship between intelligence, decision and combat outcome. The problem centres on three things: (1) an adequate representation of the situation confronting the commander on the battlefield; (2) an adequate measure of combat outcome; and (3) an appropriate metric linking knowledge of the first to the second. In this paper, we focus on the third of these by developing a measure of the knowledge possessed by the commander at the time he takes his decision and by relating this to combat outcomes. Combat outcomes are represented using traditional attrition-based metrics and the combat situation is simply the size, location and identity of enemy units. Therefore, the possible number of identified enemy units arrayed against the friendly commander constitutes the set of hypotheses on alternative situations. Surveillance assets provide the commander with evidence that is used to update the probability distribution. Knowledge if then represented as the product of two components: residual knowledge, the knowledge gained from the updated probability distribution, and detection knowledge, the knowledge from the detection itself. Information entropy was used to develop a metric that reflects the degree to which the commander understands the situation confronting him. The metric was applied in a UK Ministry of Defence study of a proposed Airborne STand-Off Radar (ASTOR) to measure the effects of improved surveillance on combat outcomes.     

Embeddings of {\mathbb{C}^*}-surfaces into weighted projective spaces

Let V be a normal affine surface which admits ${\mathbb{C}^*}$ - and ${\mathbb{C}_+}$ -actions. Such surfaces were classified e.g., in: Flenner and Zaidenberg (Osaka J Math 40:981–1009, 2003; 42:931–974), see also the references therein. In this note we show that in many cases V can be embedded as a principal Zariski open subset into a hypersurface of a weighted projective space. In particular, we recover a result of D. Daigle and P. Russell, see Theorem A in: Daigle and Russell (Can J Math 56:1145–1189, 2004)     

To be or not to be constructive,that is not the question

In the early twentieth century, L.E.J. Brouwer pioneered a new philosophy of mathematics, called intuitionism. Intuitionism was revolutionary in many respects but stands out – mathematically speaking – for its challenge of Hilbert’s formalist philosophy of mathematics and rejection of the law of excluded middle from the ‘classical’ logic used in mainstream mathematics. Out of intuitionism grew intuitionistic logic and the associated Brouwer–Heyting–Kolmogorov interpretation by which ‘there exists $x$’ intuitively means ‘an algorithm to compute $x$ is given’. A number of schools of constructive mathematics were developed, inspired by Brouwer’s intuitionism and invariably based on intuitionistic logic, but with varying interpretations of what constitutes an algorithm. This paper deals with the dichotomy between constructive and non-constructive mathematics, or rather the absence of such an ‘excluded middle’. In particular, we challenge the ‘binary’ view that mathematics is either constructive or not. To this end, we identify a part of classical mathematics, namely classical Nonstandard Analysis, and show it inhabits the twilight-zone between the constructive and non-constructive. Intuitively, the predicate ‘$x$ is standard’ typical of Nonstandard Analysis can be interpreted as ‘$x$ is computable’, giving rise to computable (and sometimes constructive) mathematics obtained directly from classical Nonstandard Analysis. Our results formalise Osswald’s longstanding conjecture that classical Nonstandard Analysis is locally constructive. Finally, an alternative explanation of our results is provided by Brouwer’s thesis that logic depends upon mathematics.     

O-minimal Hauptvermutung for polyhedra I

Milnor discovered two compact polyhedra which are homeomorphic but not PL homeomorphic (a counterexample to the Hauptvermutung). He constructed the homeomorphism by a finite procedure repeated infinitely often. Informally, we call a procedure constructive if it consists of an explicit procedure that is repeated only finitely many times. In this sense, Milnor did not give a constructive procedure to define the homeomorphism between the two polyhedra. In the case where the homeomorphism is semialgebraic, the author and Yokoi proved that the polyhedra in R ⁿ are PL homeomorphic. In that article, the required PL homeomorphism was not constructively defined from the given homeomorphism. In the present paper we obtain the PL homeomorphism by a constructive procedure starting from the homeomorphism. We prove in fact that for any ordered field R equipped with any o-minimal structure, two definably homeomorphic compact polyhedra in R ⁿ are PL homeomorphic (the o-minimal Hauptvermutung theorem 1.1). Together with the fact that any compact definable set is definably homeomorphic to a compact polyhedron we can say that o-minimal topology is “tame”.     

Planar Crossing Numbers of Graphs of Bounded Genus

Pach and Tóth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c ^g dn, for a constant c>1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.     

Proofs as bearers of mathematical knowledge

Yehuda Rav’s inspiring paper “Why do we prove theorems?” published in Philosophia Mathematica (1999, 7, pp. 5–41) has interesting implications for mathematics education. We examine Rav’s central ideas on proof—that proofs convey important elements of mathematics such as strategies and methods, that it is “proofs rather than theorems that are the bearers of mathematical knowledge”and thus that proofs should be the primary focus of mathematical interest—and then discuss their significance for mathematics education in general and for the teaching of proof in particular.     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

A constructive proof of Ky Fan's generalization of Tucker's lemma

We present a proof of Ky Fan's combinatorial lemma on labellings of triangulated spheres that differs from earlier proofs in that it is constructive. We slightly generalize the hypotheses of Fan's lemma to allow for triangulations of Sⁿ that contain a flag of hemispheres. As a consequence, we can obtain a constructive proof of Tucker's lemma that holds for a more general class of triangulations than the usual version.     

Specker sequences revisited

Specker sequences are constructive, increasing, bounded sequences of rationals that do not converge to any constructive real. A sequence is said to be a strong Specker sequence if it is Specker and eventually bounded away from every constructive real. Within Bishop's constructive mathematics we investigate non‐decreasing, bounded sequences of rationals that eventually avoid sets that are unions of (countable) sequences of intervals with rational endpoints. This yields surprisingly straightforward proofs of certain basic results fromconstructive mathematics. Within Russian constructivism, we show how to use this general method to generate Specker sequences. Furthermore, we show that any nonvoid subset of the constructive reals that has no isolated points contains a strictly increasing sequence that is eventually bounded away from every constructive real. If every neighborhood of every point in the subset contains a rational number different from that point, the subset contains a strong Specker sequence. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Priori and A Posteriori: A Bootstrapping Relationship

The distinction between a priori and a posteriori knowledge has been the subject of an enormous amount of discussion, but the literature is biased against recognizing the intimate relationship between these forms of knowledge. For instance, it seems to be almost impossible to find a sample of pure a priori or a posteriori knowledge. In this paper, it will be suggested that distinguishing between a priori and a posteriori is more problematic than is often suggested, and that a priori and a posteriori resources are in fact used in parallel. We will define this relationship between a priori and a posteriori knowledge as the bootstrapping relationship. As we will see, this relationship gives us reasons to seek for an altogether novel definition of a priori and a posteriori knowledge. Specifically, we will have to analyse the relationship between a priori knowledge and a priori reasoning, and it will be suggested that the latter serves as a more promising starting point for the analysis of aprioricity. We will also analyse a number of examples from the natural sciences and consider the role of a priori reasoning in these examples. The focus of this paper is the analysis of the concepts of a priori and a posteriori knowledge rather than the epistemic domain of a posteriori and a priori justification.     

Properties of solutions of cooperative games with transferable utilities

We understand a solution of a cooperative TU-game as the α-prenucleoli set, α ∈ R, which is a generalization of the notion of the [0, 1]-prenucleolus. We show that the set of all α-nucleoli takes into account the constructive power with the weight α and the blocking power with the weight (1 ? α) for all possible values of the parameter α. The further generalization of the solution by introducing two independent parameters makes no sense. We prove that the set of all α-prenucleoli satisfies properties of duality and independence with respect to the excess arrangement. For the considered solution we extend the covariance propertywith respect to strategically equivalent transformations.     

A constructive proof of Tucker's combinatorial lemma

Tucker's combinatorial lemma is concerned with certain labellings of the vertices of a triangulation of the n-ball. It can be used as a basis for the proof of antipodal-point theorems in the same way that Sperner's lemma yields Brouwer's theorem. Here we give a constructive proof, which thereby yields algorithms for antipodal-point problems. Our method is based on an algorithm of Reiser.     

Decision Making and Optimization in Changeable Spaces, a New Paradigm

This paper proposes a new decision making/optimization paradigm, the decision making/optimization in changeable spaces (DM/OCS). The unique feature of DM/OCS is that it incorporates human psychology and its dynamics as part of the decision making process and allows the restructuring of the decision parameters. DM/OCS is based on Habitual Domain theory, the decision parameters, the concept of competence set, and the mental operators 7-8-9 principles of deep knowledge. The covering and discovering processes are formulated as DM/OCS problems. Some illustrative examples of challenging problems that cannot be solved by traditional decision making/optimization techniques are formulated as DM/OCS problems and solved. In addition, some directions of research related to innovation dynamics, management, artificial intelligence, artificial and e-economics, scientific discovery, and knowledge extraction are provided in the conclusion.     

K 6-Minors in Triangulations on the Nonorientable Surface of Genus 3

In this paper, we shall give a constructive characterization of triangulations on the nonorientable surface of genus 3 without K ₆-minors. Our characterization implies that every 5-connected triangulation and every 4-representative triangulation on the surface has a K ₆-minor.     

Logic as a Science and Logic as a Theory: Remarks on Frege, Russell and the Logocentric Predicament

Since its publication in 1967, van Heijenoort??s paper, ??Logic as Calculus and Logic as Language?? has become a classic in the historiography of modern logic. According to van Heijenoort, the contrast between the two conceptions of logic provides the key to many philosophical issues underlying the entire classical period of modern logic, the period from Frege??s Begriffsschrift (1879) to the work of Herbrand, G?del and Tarski in the late 1920s and early 1930s. The present paper is a critical reflection on some aspects of van Heijenoort??s thesis. I concentrate on the case of Frege and Russell and the claim that their philosophies of logic are marked through and through by acceptance of the universalist conception of logic, which is an integral part of the view of logic as language. Using the so-called ??Logocentric Predicament?? (Henry M. Sheffer) as an illustration, I shall argue that the universalist conception does not have the consequences drawn from it by the van Heijenoort tradition. The crucial element here is that we draw a distinction between logic as a universal science and logic as a theory. According to both Frege and Russell, logic is first and foremost a universal science, which is concerned with the principles governing inferential transitions between propositions; but this in no way excludes the possibility of studying logic also as a theory, i.e., as an explicit formulation of (some) of these principles. Some aspects of this distinction will be discussed.     

Modelling as a way of organising knowledge

The paper is motivated by the need of to address a new the old topic of operational research and hard (but also soft) systems science: what is the role of mathematical modelling, how does it relate to knowledge, to creativity, to human concerns? Such a need arises because of the great change observed today, of informational revolution, of transition towards knowledge-based economy, towards networked organization of our social and economic life. During last 50 years operational research, mathematical modelling and computerised techniques of model analysis and optimisation contributed essentially to the change of perception of contemporary world, characteristic for the current informational revolution indicating the change of civilisation eras. These contributions have been noted during these years inside operational research, but analysed mostly from so-called soft systems thinking perspective. Main contributions to the actual formation of the new era, however, came from the hard systems research, in particular, as we shall show, from mathematical modelling in applications to the development of technological systems.     

Unitary groups of nondegenerate Hermitian forms and the homotopy groups of pseudospheres

The Witt Extension Theorem states that the unitary group of a finite-dimensional vector space V equipped with a nondegenerate hermitian form acts transitively on the pseudosphere induced by the form. We provide a new, constructive proof of this result for finite-dimensional vector spaces V over R, C, or H. This constructive proof is then used to prove a similar result for the unitary group of a finitely generated free right module over an abelian AW^∗-algebra. The topology of these unitary groups is examined and as an application we determine the homotopy groups π₁ and π₂ of the induced real, complex, and quaternionic pseudospheres.     

A Local Refinement Strategy for Constructive Quantization of Scalar SDEs

We present a fully constructive method for quantization of the solution X of a scalar SDE in the path space L _p [0,1] or C[0,1]. The construction relies on a refinement strategy which takes into account the local regularity of X and uses Brownian motion (bridge) quantization as a building block. Our algorithm is easy to implement, its computational cost is close to the size of the quantization, and it achieves strong asymptotic optimality provided this property holds for the Brownian motion (bridge) quantization.