ch7.tex

\chapter{Related Work}

\section{Constructivism}
 

Piaget was an evolutionary biologist\cite[p. 26]{piaget1952origins}. He created theory about how human intelligence develops, from the earliest post-natal life, always building upon what was already present, supporting his theory with years of meticulous observations.

%We can think of our store of knowledge growing by accretion.

Piaget and Beth\cite[p. 195]{beth1966mathematical} wrote that ontogenetic construction of evidence of a new domain integrates the former domain as subdomain.

This natural learning process, in which the new is accommodated by means of what has gone before, may be quite relevant to our students'  preference to receive new proof-related ideas not as abstract members of a class being defined, but as concrete entities serving as examples.



\subsection{Social Constructivism}
Given that our interest is fostering intellectual growth in the domain of proof, it makes sense to enquire how most effectively to interact with the construction being carried out by the student.

Vygotsky, in the time immediately after the Russian Revolution, led a school for children whose physical and mental ages were not much correlated, and whose mental ages had to be assessed. Vygotsky observed that, in assessing the mental age of such a student, not only the capability of the student acting alone, but also the capability when the student received a small amount of assistance from peers or an instructor, was very informative. He named the difference between these measures the ``zone of proximal development''.

We take the zone of proximal development(ZPD) to identify those new ideas which the student is well prepared to learn. 

Given that we wish to teach the abstract ideas of mathematical definitions as important for warranting transformation steps in proof, we may reduce that problem to the cultivation of the development of the ZPD, so that it follows a trajectory supporting the material in our course. Of course the ZPD is within the student.

Vygotsky in Language and Thought\cite{vygotsky1962language} said we do as individuals build up thoughts and then as we become socialized with shared language, some accommodation would need to be enforced onto the child. [p.17] \ldots the psychological problem is to become convinced that always, necessarily a given picture has to appear as one of a multiple of possible graphs of the same category (i.e., only as a representative of a class \ldots must be grasped not in a final fixed state but rather \textit{in construction} the point moving).

Vygotsky\cite[p. 49]{vygotsky1978mind} noted that ``one child selected a picture of an onion to recall the word `dinner'. When asked why she chose the picture, she gave the perfectly satisfactory answer, `Because I eat an onion'. However, she was unable to recall the word `dinner' during the experiment. This example shows that the ability to form elementary associations is not sufficient to ensure that the associative relation will fulfill the \textit{instrumental} function necessary to produce recall.''

As instructors attempt to nurture the ZPD, we should remain cognizant that, when students are not passive,  we may be out of coordination with the direction of advanced spontaneously used by the student, and we should take care to provide associations that students can use to recall the new material.

\subsection{Social Constructivism Applied to Mathematics Education}

Archavi et al.\cite[p. 6]{arcavi1998teaching} ``Students' mathematical activity takes place in an inherently social milieu.''

According to Fischbein\cite[p. 47]{fischbein1987intuition}, intuition tends to survive even when contradicted by systematic formal instruction. 

So we should keep track of the desired path of development, but should be aware also that there are mechanisms that can deflect students from our plan.

Fischbein [p.59] ``Inferential affirmatory intuition may have an inductive or deductive structures. After one has found that a certain number of elements (objects, substances, individual, mathematical entities, etc.) have certain properties in common one tends \textit{intuitively} to generalize and to affirm that the \textit{whole} category of elements possesses that property. This is not a mere logical operation. 
The generalization appears more of less suddenly with a feeling of confidence. 
This is a fundamental source of hypotheses in science. 
According to Poincar\'e ``generalization by induction copied, so to speak, from the proedures of experimental sciences'' is one of the basic categories of intuition (Poincar\'e 1920 [p. 20]).\\
\cite[p. 67]{fischbein1987intuition}(check) ``One morning walking on the bluff, the idea came to me with just the same characteristics of brevity, suddenness and immediate certainty that the arithmetical transformation of indeterminate ternary indefinite forms were identical to those of the non-Euclidean geometry Poincar\'e 1913 [p. 388]''\\

So we see that generalization happens apparently spontaneously (i.e., students may do this on their own), and can produce enduring beliefs.

As we have seen students resist learning definitions,
an interest in helping them do so
is informed by their difficulty, 
which includes not making use of
generalization/specialization hierarchies of definitions
\cite[p. 147]{Fischbein} ``For many students the concepts of parallelogram, square and rectangle are not organized hierarchically. They represent classes of quadrilaterals of the same generality''.

Archavi et al.\cite[p. 10]{arcavi1998teaching} ``To be successful, students must know both the appropriate heuristics and the mathematics required to solve the problem.

\cite[p. 214]{Fischbein} concept of intuitive loading --- have to know students first before knowing how to teach them

McGowan and Tall \cite[p. 172]{ (2010 Jour. Math. Behav.)} ``If learning defaults to the goal of learning how, it can be successful. However, if it is accompanied by a lack of conceptual meaning so that mistakes occur, it can become fragile and more likely to fail in the longer term. At this stage the problems may proliferate as the student becomes confused as to which rule to use, where to use it, and how to interpret it.

Tall and Mejia-Ramos \cite[p. 138]{2010, Explanation and Proof in Mathmatics, Springer} ``Here proof develops through generalized arithmetic and algebraic manipulation'',
different kinds of warrants for truth.

Pinto and Tall (1999 and 2002) build on met-befores.
\begin{figure}[tbph]
	\centering
	\includegraphics[width=0.7\linewidth]{chp7p1}
	\caption{How proof develops, Tall Mejia-Ramos}
	\label{fig:chp7p1}
\end{figure}

Harel and Sowder \cite[p. 237]{harel1998students} have observed of teaching proof in mathematics: Rather than gradually refining students' conception of what constitutes evidence and justification in mathematics, we impose on them proof methods and implication rules that in many cases are utterly extraneous to what convinces them. 
Editors Schoenfeld et al.\cite{kaput1998research} describe that Harel and Sowder\cite{harel1998students} ``characterize students' cognitive schemes of proof''.

The subdivisions in the 1998 version of categories of conceptualizations \cite{harel1998students}, specifically intuitive -- axiomatic, structural and axiomatizing,
matter much in computer science, because intuitive -- axiomatic could be thought to be less used in computer science than in math, a program's content could be less intuitive than Euclidean geometry, and more subject to checking by assertion checking or debugger examination.

\cite[p. 268]{harel1998students} contextual proof scheme: --students have learned to work in a context, e.g., $\mathbb{R}^n$, and so, interpret statements that have greater generality as restricted to be in the context they have learned ``he or she has not yet abstracted the concept \ldots beyond this specific context''. %Compare this with Pang's (is it Pong?) observation that for students who know only one language, ``speaking'' and ``speaking that language'' are concepts that are undifferentiated.

\cite[p. 274]{harel1998students} ``An important distinction between the structured proof scheme and the intuitive proof scheme is the ability to separate the abstract statements of mathematics (e.g., $1+1=2$) from their corresponding quantitative observations (e.g., 1 apple + 1 apple = 2 apples) or the axiomatically -- based observations from their corresponding visual phenomena \ldots '', ``axiomatic proof scheme is epistemologically an extension of transformational proof scheme. One might mistakenly think of the axiomatic proof scheme is the ability to reason formally \ldots ''.

Baranchik and Cherkas\cite{baranchik1998supplementary} found three levels of understanding in a population taking algebra exams:
\begin{enumerate}
	\item Early skills --- arithmetic and elementary algebra
	\item Later Skills --- subsequent algebra and a variety of skills involving methematical abstraction, and
	\item Formalism --- either devising a solution strategy or reformulating a problem into a standard form that permits a solution using early or later skills 
\end{enumerate}

Gibson\cite[p. 289]{kaput1998research} ``Students indicated that diagrams helped them understand information by appealing to their natural thinking. They said that diagrams seemed to coincide with the way their `minds work' and that information represented visually seemed easier or clearer than verbal/symbolic representations.''

Gibson\cite[p. 291]{kaput1998research}'``When I read the definitions you can't think about the whole thing at once, but when you have a picture you can''
Gibson\cite[p. 294]{kaput1998research}``Because students did not usually think of their criteria in terms of formal definitions, their ability to decide whether their criteria had been met was hindered when they worked with information represented in only verbal/symbolic form.''
``They could obtain ideas more readily from diagrams than they could from verbal/symbolic representations''
Gibson\cite[p. 297]{kaput1998research} ``Why always keep the picture in your mind when you can have it on the paper, allowing you to focus more on how to get to the end of the proof instead of always having to recall the picture in each individual step?''
Moore\cite[p. 262]{moore1994making} ``The students' ability to use the definitions in the proofs depended on their knowledge of the formal definitions, which in turn depended on their informal concept images. The students often needed to develop their concept images through examples, diagrams, graphs and others means before they could understand the formal verbal or symbolic definitions''.

We checked for internal consistency and reinforcement, and for external compatibility
of our findings with existing educational literature in computer science
and in mathematics. We noted the phenomenological work of Gian-Carlo
Rota \cite{rota1997phenomenology} who has reported that memory for mathematical proof and its elements
is noticeably improved when a proof is deemed to be beautiful. We were encouraged
by the overlap in description among interview participants. In the
literature of mathematics education, we found researchers [?] reporting quite
similar conceptions of proof by mathematical induction in students of mathematics.
In the literature of computer science education we found research \cite{booth1997phenomenography}
on a different topic, but with similar results. Booth reported categories of
conceptions of recursion similar to our categories of conception of proof by
mathematical induction.

The results have bridged papers in computer science education, by Professor Booth\cite{booth1997phenomenography}?\cite{}, and mathematics education, by \cite{}.

The results have been consistent with results of others in mathematics education.
Research on teaching and learning about proof in mathematics education has
produced an extensive literature. Only a small sampling is mentioned below.
Mathematics educators, including Keith Weber[?], Harel and Sowder in
1998[?], and David Tall[?] have studied students' learning of proof in the mathematics
curriculum. Leron, in 1983, [?] has described the structural method
for proof construction, attributing it to recent ideas from computer science.
Lamport, in 1995, [?] in work on proof construction, has given one approach
that computer science students might find compatible with their background.
Velleman, in 2006, has written software and a textbook [?] about proving with
a structured approach. Weber has reported the success of several approaches
to pedagogy [?].
Barnard [?] has commented upon students negating statements with quantifiers.
Edwards and Ward [?, p. 223] have discussed the role of definitions for undergraduate
mathematics courses, stating ``the enculturation of college mathematics
students into the field of mathematics includes their acceptance and
understanding of the role of mathematical definitions''. Bills and Tall [?] have
distinguished student understanding of definitions that is sufficient that the
student can use them in proofs.
Harel and Sowder [?] and Harel and Brown [?] have conducted qualitative
research on mathematics students' conceptualization of proofs. They have developed
three main categories, each with several subcategories. Evidence from
our studies is consistent with the presence of these categories of conceptualizations
in the population of CS(E) students.
Tall[?, ?] has also categorized mathematics students' understanding of proof.
He has studied the development of cognitive abilities used in proof, starting,
as did Piaget,[?] with abilities believed present at birth.
Yang and Lin have modeled reading comprehension.[?]
Leron[?] has written about encouraging students to attend to proof structure
by teaching with generic proofs (proofs that use a generic particular).
Mejia-Ramos et al.[?] have built a model for proof comprehension. They have
observed that students who are assessed on appreciation of structural and
other appropriate features of a proof, rather than on rote reproduction, are
more likely to develop a deeper understanding of proof.
Knipping and Reid[41] have examined proof in mathematics education.
Weber[?, ?, ?, ?, ?, ?, ?, ?, ?] has investigated students' approaches to and difficulties
with proof. When studying student proof attempts in group theory, Weber
has found that some typical students' inabilities to construct proofs arise despite
having adequate factual and procedural knowledge, the ability to apply that
knowledge in a productive manner was lacking. [?] More specifically applying
the knowledge was seen to include selecting among facts, guided by knowledge
of which were important, for those most likely to be useful. [?] Alcock
and Weber,[?] have studied students' understanding of warrants, the support
for the use of a particular inference. Weber has published a framework for describing
the processes that undergraduate students use to construct proofs. [?]
Almstrum[?] has investigated the understanding of undergraduate computer
science students of problems related to logic, compared to problems only
weakly related to logic, and has shown that some students have trouble with
the notion of truth or falsity.
Healy and Hoyles[?] have reported on algebra students' preferences for the
content of convincing arguments, and their distinction between preferences
for ascertaining vs. preferences about what was likely to be well-received on
assessments.
{\.I}mamo{\u g}lu[?, ?] has studied the conceptualizations of proof of students who
were preparing to become mathematics and science teachers, in their freshman
and senior years. 

Bransford et al.\cite[p. 296]{bransford2000designs} attempt to address the problem identified as inert knowledge (in the sense of Whitehead\cite{whitehead1959aims}). They situated class activity in a problem solving environment, and they showed\cite{van1992jasper} that this instruction  had  better results for students' ability to transfer skills to new word problems than traditional instruction.

Lehrer et al. \cite[p. 334]{lehrer2000inter} found that ``at least in some circumstances, giving children models may be less helpful than fostering their propensity to construct, evaluate, and revise models of their own to solve problems that they consider personally meaningful.''

According to Huang et al.\cite{huang2015highest}, a large body of research suggests that an abstract cognitive processing style produces greater creativity. 

According to Gray and Tall \cite[p. 117]{gray1994duality}, Hiebert and Lefevre observed ``a connected web \ldots  a network in which the linking relationships are  as prominent as the discrete pieces of information \ldots a unit of conceptual knowledge cannot be an isolated piece of information;
by definition is it part of conceptual knowledge only if  the holder recognizes its relationship to other pieces of information ``\cite[p. 3-4]{hiebert2013conceptual}.

Gibson\cite{gibson1998students} examined students' use of diagrams in proofs, and found that diagrams helped link students' ideas to mathematization, namely, to representation in symbols, and also to support variation, in the sense of the critical difference between what Harel and Sowder\cite{harel1998students} call perceptual and transformational conceptualizations.

Application of findings about students
of mathematics to students of computer science is fraught by differences
in the preparation and interests related to algorithms. One likely difference is
motivation: students of mathematics know that proof is the principal means
of discourse in their community, but students of computer science might not
be aware of the importance of proof to their work. Not all differences favor
students of mathematics. In particular, the categories internalization and
interiorization of Harel and Sowder’s 1998 model\cite{harel1998students} are apt to be, in students
interested in algorithms, more closely related, than in students of mathematics.
There may be a difference regarding abstraction. Both mathematics and
computer science deal in abstraction, and students in both disciplines struggle
with it. \cite{mason1989mathematical,hazzan2003students}. In mathematics, following Vi\`ete, \cite{viete2006analytic}, single letter variable names
are used. These are thought to support the learning of abstraction, for example, Gray and Tall \cite[p. 121]{gray1994duality} observe ``we want to encompass the growing compressibility of knowledge characteristic of successful mathematicians. Here, not only is a single symbol viewed in a flexible way ''
and
in computer science abstraction, one way to exhibit abstraction is UML diagrams. Because the
``trie'' structure and International Standards Organization ISO standard 11179
are computer science approaches to management of definitions, it could be that
computer science students would be more accessible to noticing the desirability
of concept definitions over concept images (see R\"osken and Rolka, \cite{rosken2007integrating} and
Rasslan and Tall \cite{rasslan2002definitions}). It would be interesting to know whether any of several
approaches reported by Weber [?] could be used, perhaps in modified form, for
instruction of students of computer science. The Action Process Object Schema
approach of Dubinsky \cite{dubinsky2002apos} sounds compatible with computer science students'
interests. An approach due to Leron and Dubinsky uses computer programming
\cite{leron1983structuring}, another \cite{leron1995abstract} is directed more to learning group theory than to learning proof
construction. Also specific to students concerned with algorithms, we may
wish to extend the notion of social constructivism from that of Piaget \cite{piaget1952origins} and
of Vygotsky\cite{vygotsky1978mind,vygotsky1987zone}, where it was necessarily a person with whom the learner was
communicating, and therefore with whom it was necessary to share a basis for
communication, to include a compiler and runtime execution environment, as
students of computing disciplines must also comply with rules (e.g., syntax)
used in these systems. Recalling the work of Papert and Harel\cite{harel1991constructionism}, we might
call this constructivism with constructionism. Constructionism is an approach
to learning in which the person learns through design and programming.

\subsection{Radical Constructivism}


\section{Computer Science Education}
\subsection{Quantifiers}
In 2010 Pillay [44] asserted that ``there has been no research into the actual
learning difficulties experienced by students with the different topics'' in formal
languages and automata theory. Of the pumping lemmas, Pillay states ``A
majority of the students made logical errors when proving that a language
is regular and using the Pumping Lemma to show that a language is nonregular.
These could be attributed to a lack of problem-solving skills and an
understanding of the Pumping Lemma.'' Devlin[18] observes that quantifiers
can appear daunting to the uninitiated, and that statements containing multiple
quantifiers can be difficult to understand.
\subsection{Symbols}
H\"uttel and N{\o}rmark[45] described a successful method for improving both
student activity level in the course and final grades, which combines peer
assessment with creation of notes that can be used during the exam. (``The
incentive was that their answers to text (CHECK) questions would be available for them
to use at the written exam. No other textual aids would be allowed at the
exam.''[p. 4]) The better performance on the exam is welcome; whether it is
due to having notes compared to closed book, or having performed the review
might not be certain.
According to Arnoux and Finkel[46], it is not unusual for students to acquire
mathematical knowledge without attaching meaning to it, and leaving them
unable to solve some problems. They go on to report that Paivio proved
that ``double coding (verbal and visual)'' facilitated remembering. They also
report that different parts of the brain are used to process verbal and visual
information, and therefore more of the brain is involved when both verbal and
pictorial communication is used. They prefer multi-modal representations.
Xing[47] writes about aiding students comprehension of proofs being aided by
graphs. She reports ``students feel that Pumping Lemma(PL) is so abstract to
grasp that using it to prove that a language is non-regular is a daunting task.''
She shows a graphically laid out proof that a given language is not regular. This
graph has the advantage over a traditional proof, i.e., a sequence of statements,
that the dependencies of states on axioms or intermediate results are plainly
shown by graph edges.
Simon et al.[43] ask ``Is it possible that students plug and chug in computing, not
really understanding the concepts as we would like them to?'' and go on to say
``We posit that the need exists for computing instructors to design assessments
more directly targeting understanding, not just doing, computing. And, of
course, to adopt teaching approaches that support student development of
these skills.''
Mazur[25] developed peer instruction to address students' propensity to practice
a plug-and-chug approach to problems. This approach has been applied
to computer science teaching, including theory of computation, by several researchers
including Simon, Zingaro, Porter, Bailey-Lee and others[48, 49, 50,
51, 27].
\subsection{Teaching Pumping Lemmas}
In 2003 Weidmann[39] wrote a dissertation on teaching Automata Theory to
students at the college level. She found that past performance in prerequisite
theory courses was a statistically significant indicator for success in their college
level course. She described a theoretical framework called ``pedagogical
positivism'', a stance between logical positivism and constructivism, allowing
the notion of a teaching method best suited to a group of students to learn Automata
Theory. She interviewed a teacher with ``several'' years of experience
teaching this course (p. 5), who ``admitted that she did not have a better way
to teach abstract thinking other than repeated exposure'' (p. 98).
In chapter 5, Discussion, Conclusions and Implications, of this dissertation[39],
the suggestion ``Instead of simply providing the solution to a problem in class,
or stating the intuitive leap that makes the problem easy to solve, the students
should be exposed to the iterative thought process that lead to the intuition
that created the solution.''(p. 201) appears. One suggestion is ``Learning objectives
should be set to focus on familiarity with formalisms and rigorous
mathematical notations” (p. 224) and another suggestion is “Include programming
projects as part of the required coursework''(p. 224). The combination
of these brings to mind the suggestion of Harel and Papert[40]: ``constructing
personally designed pieces of instructional software'', and the thought that the
students might dwell more effectively on the notion of abstraction as they tried
to teach someone else about it.
\section{Proof by Induction}
Kinnunen and Simon [7] describe an example applying phenomenography to
computing education research, listing several recent examples, and also providing
a detailed description of a mainly data- but also theory-driven refinement
of categories.
Berglund, Eckerdal and Thun\'e [16, 3, 4] have applied phenomenography to
computing education research, obtaining classifications by judicious grouping
of student conceptions derived from interview data. Eckerdal et al. [4] describe
how the results using phenomenography showed additional insights beyond
other methods.
Jones and Herbst [6] considered which theoretical frameworks might be most
useful for studying student teacher interactions in the context of learning about
proofs. Bussey et al. [2] illustrated student teacher interactions in the space of
learning, and the objects of learning, in variation theory, modified from the
model of Rundgren and Tibell [13].
Reid and Petocz [12] used phenomenography to study students' conceptions
of statistics. Their purposes included to ``enable teachers to develop curricula
that focus on enhancing the student learning environment and guiding
student conceptions of statistics.'' They asked students to describe how they
understood statistics and then organised student responses into a hierarchy of
conceptions. They used interviews to understand individual students, and the
group of interviews to show the variations they found. They found the students with the most superficial understanding to be carrying out steps without
knowing their meaning.
Krantz [8] describes proof by induction, giving several examples in this book
of proof techniques for computer science.
\section{Mathematics Education on Proof}
\section{Qualitative Research}
\subsection{Phenomenography and Variation Theory}

Marton and Booth\cite{marton1997learning} have written 

{\aa}kerlind \cite{aakerlind2012variation} has written on how

Runesson\cite{runesson2005beyond} has applied variation theory to math



\subsection{Thematic Analysis}