Explication as a lens for the formalization of mathematical theory through guided reinvention

Realistic Mathematics Education supports students’ formalization of their mathematical activity through guided reinvention. To operationalize “formalization” in a proof-oriented instructional context, I adapt Sjogren's (2010) claim that formal proof explicates (Carnap, 1950) informal proof. Explication means replacing unscientific or informal concepts with scientific ones. I use Carnap's criteria for successful explication – similarity, exactness, and fruitfulness – to demonstrate how the elements of mathematical theory – definitions, axioms, theorems, proofs – can each explicate their less formal correlates. This lens supports an express goal of the instructional project, which is to help students coordinate semantic (informal) and syntactic (formal) mathematical activity. I demonstrate the analytical value of the explication lens by applying it to examples of students’ mathematical activity drawn from a design experiment in undergraduate, neutral axiomatic geometry. I analyze the chains of meanings (Thompson, 2013) that emerged when formal elements were presented readymade alongside those emerging from guided reinvention.     

Validating proofs and counterexamples across content domains: Practices of importance for mathematics majors

Validating proofs and counterexamples across content domains is considered vital practices for undergraduate students to advance their mathematical reasoning and knowledge. To date, not enough is known about the ways mathematics majors determine the validity of arguments in the domains of algebra, analysis, geometry, and number theory—the domains that are central to many mathematics courses. This study reported how 16 mathematics majors, including eight specializing in secondary mathematics education, who had completed more proof-based courses than transition-to-proof classes evaluated various arguments. The results suggest that the students use one of the following strategies in proof and counterexample validation: (1) examination of the argument's structure and (2) line-by-line checking with informal deductive reasoning, example-based reasoning, experience-based reasoning, and informal deductive and example-based reasoning. Most students tended to examine all steps of the argument with informal deductive reasoning across various tasks, suggesting that this approach might be problem dependent. Even though all participating students had taken more proof-related mathematics courses, it is surprising that many of them did not recognize global-structure or line-by-line content-based flaws presented in the argument.     

Are You Convinced? Middle‐Grade Students' Evaluations of Mathematical Arguments

Students learn norms of proving by observing teachers generating proofs, engaging in proving, and generalizing features of proofs deemed convincing by an authority, such as a textbook. Students at all grade levels have difficulties generating valid proof; however, little research exists on students' understandings about what makes a mathematical argument convincing prior to more formal instruction in methods of proof. This study investigated middle‐school students' (ages 12–14) evaluations of arguments for a statement in number theory. Students evaluated both an empirical and a general argument in an interview setting. The results show that students tend to prefer empirical arguments because examples enhance an argument's power to show that the statement is true. However, interview responses also reveal that a significant number of students find arguments to be most convincing when examples are supported with an explanation that “tells why” the statement is true. The analysis also examined the alignment of students' reasons for choosing arguments as more convincing along with the strategies they employ to make arguments more convincing. Overall, the findings show middle‐school students' conceptions about what makes arguments convincing are more sophisticated than their performance in generating arguments suggests.     

Mathematics Majors' Perceptions of Conviction,Validity, and Proof

In this paper, 28 mathematics majors who completed a transition-to-proof course were given 10 mathematical arguments. For each argument, they were asked to judge how convincing they found the argument and whether they thought the argument constituted a mathematical proof. The key findings from this data were (a) most participants did not find the empirical argument in the study to be convincing or to meet the standards of proof, (b) the majority of participants found a diagrammatic argument to be both convincing and a proof, (c) participants evaluated deductive arguments not by their form but by their content, but (d) participants often judged invalid deductive arguments to be convincing proofs because they did not recognize their logical flaws. These findings suggest improving undergraduates' comprehension of mathematical arguments does not depend on making undergraduates aware of the limitations of empirical arguments but instead on improving the ways in which they process the arguments that they read.     

On the different ways that mathematicians use diagrams in proof construction

The processes by which individuals can construct proofs based on visual arguments are poorly understood. We investigated this issue by presenting eight mathematicians with a task that invited the construction of a diagram, and examined how they used this diagram to produce a formal proof. The main findings were that participants varied in the extent of their diagram usage, it was not trivial for participants to translate an intuitive argument into a formal proof, and participants’ reasons for using diagrams included noticing mathematical properties, verifying logical deductions, representing ideas or assertions, and suggesting proof approaches.     

Designing and proving correct a convex hull algorithm with hypermaps in Coq

This article presents the formal design of a functional algorithm which computes the convex hull of a finite set of points incrementally. This algorithm, specified in Coq, is then automatically extracted into an OCaml program which can be plugged into an interface for data input (point selection) and graphical visualization of the output. A formal proof of total correctness, relying on structural induction, is also carried out. This requires to study many topologic and geometric properties. We use a combinatorial structure, namely hypermaps, to model planar subdivisions of the plane. Formal specifications and proofs are carried out in the Calculus of Inductive Constructions and its implementation: the Coq system.     

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.     

Prototype Proofs in Type Theory

The proofs of universally quantified statements, in mathematics, are given as “schemata” or as “prototypes” which may be applied to each specific instance of the quantified variable. Type Theory allows to turn into a rigorous notion this informal intuition described by many, including Herbrand. In this constructive approach where propositions are types, proofs are viewed as terms of λ‐calculus and act as “proof‐schemata”, as for universally quantified types. We examine here the critical case of Impredicative Type Theory, i. e. Girard's system F, where type‐quantification ranges over all types. Coherence and decidability properties are proved for prototype proofs in this impredicative context.     

A Combinatorial Proof of Bass's Evaluations of the Ihara-Selberg Zeta Function for Graphs

We derive combinatorial proofs of the main two evaluations of the Ihara-Selberg zeta function associated with a graph. We give three proofs of the first evaluation all based on the algebra of Lyndon words. In the third proof it is shown that the first evaluation is an immediate consequence of Amitsur's identity on the characteristic polynomial of a sum of matrices. The second evaluation of the Ihara-Selberg zeta function is first derived by means of a sign-changing involution technique. Our second approach makes use of a short matrix-algebra argument.

     

A general rapid network design,line planning and fleet investment integrated model

We study four proofs that the Gittins index priority rule is optimal for alternative bandit processes. These include Gittins’ original exchange argument, Weber’s prevailing charge argument, Whittle’s Lagrangian dual approach, and Bertsimas and Niño-Mora’s proof based on the achievable region approach and generalized conservation laws. We extend the achievable region proof to infinite countable state spaces, by using infinite dimensional linear programming theory.     

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.     

Other Proofs of Old Results

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.     

On constructivity and the Rosser property: a closer look at some Gödelean proofs

The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences.     

Raney and Catalan

Raney’s lemma is often used in a counting argument to prove the formula for (generalized) Catalan numbers. It ensures the existence of “good” cyclic shifts of certain sequences, i.e. cyclic shifts for which all partial sums are positive.We introduce a simple algorithm that finds these cyclic shifts and also those with a slightly weaker property. Moreover it provides simple proofs of lemma’s of Raney type.A similar clustering procedure is also used in a simple proof of a theorem on probabilities of which many well-known results (e.g. on lattice paths and on generalized Catalan numbers) can be derived as corollaries. The theorem generalizes generalized Catalan numbers. In the end it turns out to be equivalent to a formula of Raney.     

On the uniqueness of the solution of the two‐dimensional Navier–Stokes equation with a Dirac mass as initial vorticity

We propose two different proofs of the fact that Oseen's vortex is the unique solution of the two‐dimensional Navier–Stokes equation with a Dirac mass as initial vorticity. The first argument, due to C. E. Wayne and the second named author, is based on an entropy estimate for the vorticity equation in self‐similar variables. The second proof is new and relies on symmetrization techniques for parabolic equations. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new proof of Fitzgerald's characterization of primitive polynomials

We give a new proof of Fitzgerald's criterion for primitive polynomials over a finite field. Existing proofs essentially use the theory of linear recurrences over finite fields. Here, we give a much shorter and self-contained proof which does not use the theory of linear recurrences.     

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.