矩阵对策鞍点定理的归纳法证明

Many proofs have been published for the minimax theorem, and all the published inductive proofs have been indirect ones. It has been pointed out that a direct inductive proof is needed, especially for instructional purposes, since indirect proofs are more or less implicit in nature. Such a direct proof is given in [4]. Now the minimax theorem can be stated equivalently in terms of saddle point; And it is the object of the present paper to give a direct inductive proof for the saddle point version of this theorem.     

Concurrency of the altitudes of a triangle

Of all the traditional (or Greek) centers of a triangle, the orthocenter (i.e., the point of concurrence of the altitudes) is probably the one that attracted the most of attention. This may be due to the fact that it is the only one that has no exact analogue for arbitrary higher dimensional simplices, for spherical and hyperbolic triangles, or for triangles in normed planes. But it possibly has to do also with the non-existence of any explicit treatment of this center in the Greek works that have come down to us. In this paper we present different proofs of the fact that the altitudes of a triangle are concurrent. These include the first extant proof, in the works of al-Kūhī, Newton’s proof, Gauss’s proof, and other interesting proofs.     

On quantitative versions of theorems due to F.E. Browder and R. Wittmann

This paper is another case study in the program of logically analyzing proofs to extract new (typically effective) information (‘proof mining’). We extract explicit uniform rates of metastability (in the sense of T. Tao) from two ineffective proofs of a classical theorem of F.E. Browder on the convergence of approximants to fixed points of nonexpansive mappings as well as from a proof of a theorem of R. Wittmann which can be viewed as a nonlinear extension of the mean ergodic theorem. The first rate is extracted from Browder's original proof that is based on an application of weak sequential compactness (in addition to a projection argument). Wittmann's proof follows a similar line of reasoning and we adapt our analysis of Browder's proof to get a quantitative version of Wittmann's theorem as well. In both cases one also obtains totally elementary proofs (even for the strengthened quantitative forms) of these theorems that neither use weak compactness nor the existence of projections anymore. In this way, the present article also discusses general features of extracting effective information from proofs based on weak compactness. We then extract another rate of metastability (of similar nature) from an alternative proof of Browder's theorem essentially due to Halpern that already avoids any use of weak compactness. The paper is concluded by general remarks concerning the logical analysis of proofs based on weak compactness as well as a quantitative form of the so-called demiclosedness principle. In a subsequent paper these results will be utilized in a quantitative analysis of Baillon's nonlinear ergodic theorem.     

Simplified existence for solutions to stochastic differential equations

Nonstandard methods are used to give a simple construction of a solution to SDEs of the form , where are required only to be measurable, with, bounded. By working with an internal Brownian motion the proof avoids the complicated lifting and approximation arguments needed in previous existence proofs.     

Integrating algebra and proof in high school mathematics: An exploratory study

Frequently, in the US students’ work with proofs is largely concentrated to the domain of high school geometry, thus providing students with a distorted image of what proof entails, which is at odds with the central role that proof plays in mathematics. Despite the centrality of proof in mathematics, there is a lack of studies addressing how to integrate proof into other mathematical domains. In this paper, we discuss a teaching experiment designed to integrate algebra and proof in the high school curriculum. Algebraic proof was envisioned as the vehicle that would provide high school students the opportunity to learn not only about proof in a context other than geometry, but also about aspects of algebra. Results from the experiment indicate that students meaningfully learned about aspects of both algebra and proof in that they produced algebraic proofs involving multiple variables, based on conjectures they themselves generated.     

Randomized proofs in arithmetic

A randomized proof system for arithmetic is introduced. A proof of an arithmetical formula is defined as its derivation from the axioms of arithmetic by the standard rules of inference of arithmetic and also one more rule which we call the random substitution rule. Such proofs can be regarded as a special kind of interactive proof and, more exactly, as a special kind of the Arthur-Merlin proofs. The main result of the paper shows that a proof in arithmetic with the random substitution rule can be considerably shorter than an arithmetical proof of the same formula. Namely, there exists a set of formulas such that (i) these formulas are provable in arithmetic but, unless PSPACE=NP, do not have polynomially long proofs; (ii) these proofs have polynomially long proofs in arithmetic with random substitution (whatever random numbers appear) and the probability of error of these proofs is exponentially small. Bibliography: 10 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 49–71. Translated by E. Ya. Dantsin.     

Tactics for Hierarchical Proof

There is something of a discontinuity at the heart of popular tactical theorem provers. Low-level, fully-checked mechanical proofs are large trees consisting of primitive logical inferences. Meanwhile, high-level human inputs are lexically structured formal texts which include tactics describing search procedures. The proof checking process maps from the high-level to low-level, but after that, explicit connections are usually lost. The lack of connection can make it difficult to understand the proof trees produced by successful tactic proofs, and difficult to debug faulty tactic proofs. We propose the use of hierarchical proofs, also known as hiproofs, to help bridge these levels. Hiproofs superimpose a labelled hierarchical nesting on an ordinary proof tree, abstracting from the underlying logic. The labels and nesting are used to describe the organisation of the proof, typically relating to its construction process. In this paper we introduce a foundational tactic language Hitac which constructs hiproofs in a generic setting. Hitac programs can be evaluated using a big-step or a small-step operational semantics. The big-step semantics captures the intended meaning, whereas the small-step semantics is closer to possible implementations and provides a unified notion of proof state. We prove that the semantics are equivalent and construct valid proofs. We also explain how to detect terms which are stuck in the small-step semantics, and how these suggest interaction points with debugging tools. Finally we show some typical examples of tactics, constructed using tactical combinators, in our language.     

Reflections on the security proofs of Boneh-Franklin identity-based encryption scheme

In this paper, we first review the existing proofs of the Boneh-Franklin identity-based encryption scheme (BF-IBE for short), and show how to admit a new proof by slightly modifying the specifications of the hash functions of the original BF-IBE. Compared with prior proofs, our new proof provides a tighter security reduction and minimizes the use of random oracles, thus indicates BF-IBE has better provable security with our new choices of hash functions. The techniques developed in our proof can also be applied to improving security analysis of some other IBE schemes. As an independent technical contribution, we also give a rigorous proof of the Fujisaki-Okamoto (FO) transformation in the case of CPA-to-CCA, which demonstrates the efficiency of the FO-transformation (CPA-to-CCA), in terms of the tightness of security reduction, has long been underestimated. This result can remarkably benefit the security proofs of encryption schemes using the FO-transformation for CPA-to-CCA enhancement.     

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.     

A formalization of Sambins's normalization for GL

Sambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut-free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B45.     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

A graph-theoretic proof of the non-existence of self-orthogonal Latin squares of order 6

The non-existence of a pair of mutually orthogonal Latin squares of order six is a well-known result in the theory of combinatorial designs. It was conjectured by Euler in 1782 and was first proved by Tarry in 1900 by means of an exhaustive enumeration of equivalence classes of Latin squares of order six. Various further proofs have since been given, but these proofs generally require extensive prior subject knowledge in order to follow them, or are ‘blind’ proofs in the sense that most of the work is done by computer or by exhaustive enumeration. In this paper we present a graph-theoretic proof of a somewhat weaker result, namely the non-existence of self-orthogonal Latin squares of order six, by introducing the concept of a self-orthogonal Latin square graph. The advantage of this proof is that it is easily verifiable and accessible to discrete mathematicians not intimately familiar with the theory of combinatorial designs. The proof also does not require any significant prior knowledge of graph theory.     

Proof validation and modification in secondary school geometry

Proof validation is important in school mathematics because it can provide a basis upon which to critique mathematical arguments. While there has been some previous research on proof validation, the need for studies with school students is pressing. For this paper, we focus on proof validation and modification during secondary school geometry. For that purpose, we employ Lakatos’ notion of local counterexample that rejects a specific step in a proof. By using Toulmin’s framework to analyze data from a task-based questionnaire completed by 32 ninth-grade students in a class in Japan, we identify what attempts the students made in producing local counterexamples to their proofs and modifying their proofs to deal with local counterexamples. We found that student difficulties related to producing diagrams that satisfied the condition of the set proof problem and to generating acceptable warrants for claims. The classroom use of tasks that entail student discovery of local counterexamples may help to improve students’ learning of proof and proving.     

A General Zero-Knowledge Scheme

There is a great similarity between the zero-knowledge proof of quadratic residuocity presented by Goldwasser-Micali-Rackoff and the graph isomorphism proof presented by Goldreich-Micali-Wigderson. There is also a resemblance between the zero-knowledge proofs of Fiat-Shamir, Chaum-Evertse-van de Graaf, Beth and Guillou-Quisquater. A similar observation holds for zero-knowledge proofs based on encryption: the 3-colourability proofs and the Hamiltonian-circuit proofs of Blum and Goldreich-Micali-Wigderson, and the Brassard-Chaum-Crepeau proof for SAT. Feige, Fiat and Shamir introduced the concept of zero-knowledge proofs of knowledge. In this paper we present a general zero-knowledge scheme which unifies all these Arthur-Merlin proofs.     

Kharitonov 定理的若干讨论

Kharitonov 在区间多项式稳定性研究中的开创性工作,给鲁棒控制领域带来了新的希望.Kharitonov 定理断言,几个特殊多项式的稳定性即可保证某一族(无穷多个)多项式的稳定性.近年来,这一领域的研究引起了控制界的极大关注,出现了许多有意义的结果.在这些工作中,对 Kharitonov 定理本身也有一定的探讨.由于原始的定理证明不够直观明了,一些学者试图对定理的证明进行简化,得到了一些简单证明.本     

Integrating Algebra and Proof in High School: Students' Work with Multiple Variables and a Single Parameter in a Proof Context

In the United States, researchers argue that proof is largely concentrated in the domain of high school geometry, thus providing students a distorted image of what proof entails, which is at odds with the central role that proof plays in mathematics. Despite the centrality of proof, there is a lack of studies addressing how to integrate proof into other mathematical domains. In this article, we discuss a teaching experiment designed to integrate algebra and proof in the high school curriculum. Algebraic proof was envisioned as the vehicle that would provide high school students the opportunity to learn not only about proof in a context other than geometry but also about aspects of algebra. Results from the experiment indicate that students meaningfully learned about aspects of both algebra and proof in that they produced algebraic proofs involving multiple variables and a single parameter, based on conjectures they themselves generated.     

Bieberbach’s conjecture, the de Branges and Weinstein functions and the Askey-Gasper inequality

The Bieberbach conjecture about the coefficients of univalent functions of the unit disk was formulated by Ludwig Bieberbach in 1916 [4]. The conjecture states that the coefficients of univalent functions are majorized by those of the Koebe function which maps the unit disk onto a radially slit plane. The Bieberbach conjecture was quite a difficult problem, and it was surprisingly proved by Louis de Branges in 1984 [5] when some experts were rather trying to disprove it. It turned out that an inequality of Askey and Gasper [2] about certain hypergeometric functions played a crucial role in de Branges’ proof. In this article I describe the historical development of the conjecture and the main ideas that led to the proof. The proof of Lenard Weinstein (1991) [72] follows, and it is shown how the two proofs are interrelated. Both proofs depend on polynomial systems that are directly related with the Koebe function. At this point algorithms of computer algebra come into the play, and computer demonstrations are given that show how important parts of the proofs can be automated. This article is dedicated to Dick Askey on occasion of his seventieth birthday. 2000 Mathematics Subject Classification Primary—30C50, 30C35, 30C45, 30C80, 33C20, 33C45, 33F10, 68W30     

A Teacher's Conception of Communication in Geometry Proofs

Mathematical proof has many purposes, one of which is communication of the reasoning behind a mathematical insight. Research on teachers' views of the role that proof plays as mathematical communication has been limited. This study describes how one teacher conceptualized proof communication during two units on proof (coordinate geometry proofs and Euclidean proofs). Based on classroom observations, the teacher's conceptualization of communication in written proofs is recorded in four categories: audience, clarity, organization, and structure. The results indicate differences within all four categories in the way the idea of communication is discussed by the teacher. Implications for future studies include attention to teachers' beliefs about learning mathematics in the process of understanding teachers' conceptions of proof as a means of mathematical communication.