Approximate common knowledge revisited

Suppose we replace “knowledge” by “belief with probability p” in standard definitions of common knowledge. Very different notions arise depending on the exact definition of common knowledge used in the substitution. This paper demonstrates those differences and identifies which notion is relevant in each of three contexts: equilibrium analysis in incomplete information games, best response dynamics in incomplete information games, and agreeing to disagree/no trade results.     

Reasoning about knowledge of unawareness revisited

In earlier work (Halpern and Rêgo, 2009), we proposed a logic that extends the Logic of General Awareness of Fagin and Halpern (1988) by allowing quantification over primitive propositions. This makes it possible to express the fact that an agent knows that there are some facts of which he is unaware. In that logic, it is not possible to model an agent who is uncertain about whether he is aware of all formulas. To overcome this problem, we keep the syntax of the earlier paper, but allow models where, with each world, a possibly different language is associated. We provide a sound and complete axiomatization for this logic and show that, under natural assumptions, the quantifier-free fragment of the logic is characterized by exactly the same axioms as the logic of Heifetz et al. (2008).     

Common knowledge,communication, and convergence of beliefs

The aim of this paper is to examine the adequacy of the so-called expected utility theory. It is concluded that the theory is inadequate when the decision-maker is decreasingly risk averse and his initial wealth is risky.     

Prosthaphaeresis revisited

The trigonometric identities for the product of two sines and the product of two cosines were first published in 1588. The discovery of the two equations, however, clearly predates that publication. Credit for priority was debated at the end of the last century and tentatively assigned to Paul Wittich of Breslau. But at least some of the conclusions reached at that time were not completely sound, even with respect to the evidence then available; and in the meantime, new evidence has come to light. Reevaluation of the issue now suggests a very questionable role for Wittich in the discovery of either equation. The first one was certainly discovered by Johannes Werner in about 1510, and probably resurrected from his papers by Wittich, while the second one appears to have been discovered from a knowledge of the first by Joost Bürgi in about 1585. But if Wittich loses one aspect of his priority in this reevaluation, he gains in another aspect. For it is now clear that Wittich had developed the method of prosthaphaeresis—the idea of using a product formula to simplify calculations—well before he arrived on Hven in 1580.     

Forcing revisited

The purpose of this paper is to propose and explore a general framework within which a wide variety of model construction techniques from contemporary set theory can be subsumed. Taking our inspiration from presheaf constructions in category theory and Boolean ultrapowers, we will show that generic extensions, ultrapowers, extenders and generic ultrapowers can be construed as examples of a single model construction technique. In particular, we will show that Łoś's theorem can be construed as a specific case of Cohen's truth lemma, and we isolate the weakest conditions a filter must satisfy in order for the truth lemma to work.     

Napoleon revisited

Napoleon's Theorem can be neatly proved using a tessellation of the plane. The theorem can be generalized by using three similar triangles (instead of the three equilateral triangles) erected in different ways on the three sides of the triangle. Various interesting special cases occur.Dedicated to H. S. M. Coxeter on the occasion of his 80th birthday.     

Paracompactness revisited

New proofs of the characterization of paracompact frames as those frames which admit a complete uniformity, and of the existence of the paracompact regular reflection, based on the Samuel type completion, is presented.     

Transitivity revisited

A survey is given of research on transitivity.The debate about the assumption of transitivity turns upon the interpretation of certain real world experiences     

Signsolvability revisited

For a real matrix A, Q(A) denotes the set of all matrices with the same sign pattern as A. A linear system Ax=b is signsolvable if solvability and Q(x) depend only on Q(A) and Q(b). The study of signsolvability can be decomposed into the study of L-matrices and of S-matrices, where A is an L-matrix [S-matrix] if the nullspace of each member of Q(A) is {0} [is a line intersecting the open positive orthant]. The problem of recognizing L-matrices is shown to be NP-complete, even in the [almost square] case. Recognition of square L-matrices was transformed into a graph-theoretic problem by Bassett, Maybee, and Quirk in 1968. The complexity of this problem remains open, but that of some related graph-theoretic problems is determined. The relation between S-matrices and L-matrices is studied, and it is shown that a certain recursive construction yields all S-matrices, thus proving a 1964 conjecture of Gorman.     

Asymptotic phase revisited

We discuss the classical problem on asymptotic phase of periodic orbits of planar systems. The existence of asymptotic phase for non-hyperbolic periodic orbits is completely determined with hypotheses on the derivatives of a Poincaré map and a return-time map. Smoothness of the vector field turns out to be crucial for existence of asymptotic phase. For hyperbolic periodic orbits, a new proof for the existence of invariant foliations is provided.     

Low-density attack revisited

The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density <0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.’s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.      

Light Dialectica revisited

We upgrade the light Dialectica interpretation (Hernest, 2005) [6] by adding two more light universal quantifiers, which are both semi-computational and semi-uniform and complement each other. An illustrative example is presented for the new light quantifiers and a new application is given for the older uniform quantifier. The realizability of new light negative formulations for the Axiom of Choice and for the Independence of Premises is explored in the new setting.     

Hall's theorem revisited

Let 1)$"> be sets. By a simple graph-theoretic argument we show that any set of distinct representatives of can be extended to a set of distinct representatives of in more than ways. This yields a natural induction proof of the well-known theorem of P. Hall.

     

Fractional programming revisited

A new format is proposed for fractional programming problems. This format gives full expression to the fact that the parametric approach to fractional programming problems is rooted in a first-order necessary and sufficient optimality condition. It is thus shown that although traditionally it has not been construed as such, the parametric approach is in fact classical par excellence.     

Modeling conceptions revisited

The previous issue of ZDM raised several fundamental issues on the role of modeling in the school curricula at micro and macro levels. In this paper we complement the approaches described there by discussing some of the issues and the barriers to the implementation of mathematical modeling in school curricula raised there from the perspective of the on going work of the models and modeling research group. In doing so we stress the need for critical literacy as well as the need to initiate a new research agenda based on the fact that we are now living in a fundamentally different world in which reality is characterized by complex systems. This may very well require us to go beyond conventional notions of modeling.     

Isotone relations revisited

We propose a new approach towards proving that the fixed point property for ordered sets is preserved by products. This approach uses a characterization of fixed points in products via isotone relations. First explorations of classes of isotone relations are presented. These first explorations give us hope that this approach could lead to advances on the Product Problem.