ch6.tex

\chapter{Interpretation/Discussion}

In this chapter we consider the results summarized in the previous chapter. We consider alternate dimensions of variation, comparing them with the chosen. 
We consider alternate critical factors, both along alternate dimensions of variation, but also along the proposed dimensions of variation.

Critical factors are ideas that are necessary for a better conceptualization\cite{marton and pang?}. 
We conjecture that not all points along a dimension of variation are equally valuable.
Some ideas encounter more resistance from students than others. (Is a cite needed for this?)
Those ideas that are less readily adopted by students might be preferable as critical factors, in that these enable the helping role of teachers.

\section{Interpretation}

\subsubsection{Interpretation of What Students Think Proofs Are}
Students know that proofs are about truth, and are about demonstrating that something is true. Students know that such demonstrations involve logic, and make use of mathematical notation. Students know that there are forms or patterns that can be used, such as proof by mathematical induction.

However, the lack of importance that students assign to definitions, and the lack of facility with representation in mathematical formulation hinders students, especially in the construction of proofs.

Students know that proofs contain sequences of logical statements.
There is a diversity of concepts for what a logical statement is.
Some students know that proofs use logical statements when warranted.




\subsubsection{Interpretation of How Students Attempt to Understand Proofs}

Students do not always attempt to understand proofs they are shown.
"people have trouble with they see a proof, they see it, that's a theorem, that's a proof, that's true, i believe it, they don't look to see how is it a proof, everyone understands when you're staring at the screen, my recursion should work, my mathematical reduction works, but it's the steps in between that no one has an idea about, it's like a bridge, you start at a, you get to c, but b is the journey, and everyone skips that, they understand a, c but they don't"

 "while knowing what they can and can't do through proofs is of course important i just keep saying it gets a bit confusing in this class, nebulous sometimes"
 
  "the biggest thing that changed in my proof writing in the math side i didn't really have a good understanding of logical statements, like an if and only if"

When students attempt to understand proofs, they sometimes get stuck.  
They reported preferring a representation in code, which they could exercise in a development system. They did not know of a similar system that would help them tinker with or otherwise examine a proof.

If construction by students attempted without an appreciation of the role of definitions (students zone out during definitions, students prefer examples), is formulaic, i.e., by learned steps but not also problem solving (as can happen when proof by mathematic induction is selected as a technique because it is a known technique, rather than some sense of its appropriateness is signaled by the problem), that would be consistent with comprehension not involving warrants.




\subsubsection{Interpretation of Reasons for Teaching Proof}

Some students do not know why proofs appear in the curriculum.
Though we might expect this to be remediated upon the student seeing proofs used in subsequent classes, sometimes students don't recognize proofs when they see them.

Some students know that proofs are used for justifying claims about the correctness and resource consumption of algorithms. No student was found who considered provability to be a guide for algorithm construction.

Some students' conceptions of what proofs are for are at a lower level of detail than others. For example, a student reported that proof by counterexample is for proving something is not true.

Other students connect learning proof by induction with explaining why algorithms work: "yes, of course, the first thing i thought of when i saw induction, was recursion"

\subsubsection{Interpretation of How Students Attempt to Apply Proofs (When not assigned)}

We can also look at how students attempt to apply proofs when assigned.
What are conceptualizations of application of proofs?
They need to use proofs, like pumping lemma, to solve problems posed to them, such as "Can we say this language is not regular?".
Rather than understanding what the proof says about features a regular language must possess, (Scouts must be thrifty, brave, clean and reverent.) and inverting the statement to find that a language not having these features cannot  be regular (If a person is not thrifty or not brave or not clean or not reverent, that person cannot be a scout.), students seem to prefer to learn a procedure. Such a procedure would include, test for all possible segmentations, show for any such segmentation, it is not the case that segment $y$, when replicated any natural number of times, contributes to a string that is present in the language. Some students stumble in the application of the procedure, especially if the procedure is described using a mathematical formulation. Some students try to memorize and reproduce  the mathematical formulation without understanding it.

Quantifiers introduce additional complexity and challenge for students.

There is insufficient evidence of students applying proofs when not assigned.

\subsubsection{Interpretation of Whether students exhibit consequences of inability (such as avoiding recursion)}

Students claim to be unsure of when certain algorithmic approaches, such as recursion, are appropriate, and do not think of proof as helpful in a determination.

\subsubsection{Interpretation of How familiar and/or comfortable are students with different (specific) proof techniques: induction, construction, contradiction?}

Students are familiar, in the sense of name recognition, with proof by mathematical induction, contrapositive, contradiction and cases.
Students see these as patterns for proof construction, i.e., steps that can be carried out. 
Students are aware that, but are not always possessed of intrinsic conviction that the patterns achieve the desired result.
Thus the students do not always achieve confidence in what Carnap\cite[p. 21-22]{carnap1958introduction} calls "the psychological content (the totality of associations)" of the consequence of the logical deductions.
When some proof is subsequently viewed in a context where it is intended to be explanatory, its power over the students' conceptions is correspondingly diminished.

\subsubsection{Interpretation of Whether students notice structural elements in proofs}



\subsubsection{Interpretation of What do students think it takes to make an argument valid?}
\subsubsection{Interpretation of Whether students incorporate structural elements in proofs}

When students consider whether a rule of inference is applicable to, and helpful for the transformation of logical representation they are attempting to accomplish, we might ask whether there are two levels of abstraction. One for the rule of inference in isolation, and another for that same rule of inference when in use in the specific proof.


Here I want to put the ideas about definitions and abstraction. Without abstraction
definitions are more cumbersome to remember and operate with. This
discourages use of the axiomatic proof conceptions, because they are based on
definitions.
What about Valiant? His establishing of definitions in circuits in the mind by
conjunctions, and by disjunctions, of ideas. Without abstraction for definitions,
this is more cumbersome.

Is intuition helping or opposing our educational objectives? Can we get help from it?

\subsection{Productive and Counterproductive Beliefs}
What do they ``know'', and what do they ``know that isn't so''.
Some will be conscious, some will be unconscious.
\subsection{Productive and Counterproductive Momentum}
What are they trying to learn? Is it aligned with the departmental curriculum? the course goals?
\subsection{Published papers}
Three papers in this area were published:
\begin{itemize}

\item CCSCNE: Categorizing the School Experience of Entering Computing
Students \cite{smith2013categorizing}
\item FIE: Mathematization in Teaching Pumping Lemmas \cite{smith2013mathematization}
\item Koli Calling: Computer Science Students’ Concepts of Proof by Induction\cite{smith2014computer}
 
\end{itemize}
\paragraph{Categories of Experience of Entering Students}
Undergraduate students beginning study of the computing disciplines present
various degrees of preparedness\cite{smith2013categorizing}. Some had no experience, some had had
informal experience, and some had had formal classes. The formal classes
extended from using applications to building applications. Informal experience
ranged from editing configuration files, such as background colors, to full time
jobs extended over multiple summers.
After publishing this paper, we encountered more related information. For
example, consistent with the work of Almstrum\cite{almstrum1996investigating}, we found that, about implications,
some students, who do know that any statement must and can, be
either true or false, thought implications must be true. Some interview participants
enjoyed a modified Moore method\cite{cohen1982modified} geometry class in middle school,
and relished opportunities to create proofs (not yet published). Other students
were not so well prepared.

 

 
\paragraph{Representation/Symbolization in Pumping Lemmas}
We found that some students may lack facility in notation. For example, in the
application of the pumping lemma, students are expected to understand the
role of $i$, in the context that a string $s$, having component substrings $x$, $y$ and $z$,
can be used to generate other strings, of the form $xy^iz$, where $i$ gives the number
of copies of the substring $y$. Moreover, students are expected to understand that
the subdivision of a string of length $p$, $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance
of a natural number, but a representation of a domain. An excerpt of the errors found on tests is shown in Table . Trigueros et
al. \cite[ p. 3]{jacobs2008developing} have observed that ``students are often unclear about the different
ways letters are used in mathematics''.  We have seen this
lack of understanding in a situation in which it was proposed as evidence that
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified
statement.
Some of our results were consistent with the framework described by Harel
and Sowder in 1998\cite{harel1998students}. We found students holding conceptualizations that
Harel and Sowder's 1998 model calls symbolization. Harel and Sowder have
identified another category of conceptualization, that correctly applied transformation
and axiomatic arguments. Some students expressed enthusiasm for
the power that inheres to building arguments with carefully specified component
ideas, in particular how the absence of ambiguity permitted arguments to
extend to great length while remaining valid. Not all of the students had developed
axiomatic conceptualizations of proof. About definitions, we collected
preliminary data on students' conceptualizations of definitions used in proofs.
Some students thought definitions were boring. Some students thought that
they could infer definitions from a few examples. Concerning executive function,
we found that some students do not state the premises clearly, and some
students did not keep track of their goal. About rules of inference, we found
Figure 5.3.1: Some categories / conceptualizations found among students of
introduction to the theory of computing, and published at FIE.
that some students apply invalid approaches to inference.

We have found students holding conceptualizations
that Harel and Sowder's 1998 model\cite{harel1998students} calls symbolization: We have found
that some students may lack facility in notation. For example, in the application
of the pumping lemma, students are expected to understand the role of $i$,
in the context that a string $s$, having component substrings $x$, $y$ and $z$, can be
used to generate other strings, of the form $xy^iz$, where $i$ gives the number of
copies of the substring $y$. Moreover, students are expected to understand that
the subdivision of a string of length $p$, expressed as $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance
of a natural number, but a representation of a domain.
Trigueros et al.\cite[p. 3]{jacobs2008developing} have observed that ``students are often unclear about the different way letters are used in mathematics.''
 We saw this
lack of understanding in a situation in which it was proposed as evidence that
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified
statement. An excerpt of the errors found on tests is shown in Table .

Table : Some example errors\\
Let x be empty\\
$|xy| \leq p, so xy = 0^p$\\
$|xy| \leq p; let x = 0^{p+r}, y = 0^{p+r}, 0 < r < p$\\
Let’s choose $|xy| = p$\\
$0^{p+1}0^b1^p \neq 0^{p+1}1^p \therefore xy^2z \not\in \mathcal{L}$\\
where $\mathcal{L} = \{0^i1^j, i \neq j\}$\\
we choose $s = 0^{p+1}1^p$ within $|xy|$\\
thus $\neq 0^p1^{p+1}$\\
Let $x = 0^a, y = 0^b1^a$\\
$x = 0^{p-h}, y = 0^h$\\
$x = 0^i, y = 0^i, z = 0^i1^j$\\
Figure 5.3.3: Some categories / conceptualizations found among students of
introduction to the theory of computing, and published at FIE.

Some of our results were consistent with the framework described by Harel
and Sowder in 1998[?]. We found students holding conceptualizations that
Harel and Sowder's 1998 model calls symbolization. Harel and Sowder have
identified another category of conceptualization, that correctly applied transformation
and axiomatic arguments. Some students expressed enthusiasm for
the power that inheres to building arguments with carefully specified component
ideas, in particular how the absence of ambiguity permitted arguments to
extend to great length while remaining valid. Not all of the students had developed
axiomatic conceptualizations of proof. About definitions, we collected
preliminary data on students' conceptualizations of definitions used in proofs.
Some students thought definitions were boring. Some students thought that
they could infer definitions from a few examples. Concerning executive function, we found that some students do not state the premises clearly, and some
students did not keep track of their goal. About rules of inference, we found
that some students apply invalid approaches to inference.
\paragraph{Abstract Model for Proof by Mathematical Induction and Recursion}
Far from finding agreement that (a) theorems are true as a consequence of
the definitions and the premise, and that (b) proofs serve to show how the
consequence is demonstrated from the premise, axioms and application of
rules of inference, instead we found a variety of notions about proof, including
the well-known procedural interpretation \cite{tall2008transition,weber2004traditional,tall2001symbols}, and the well-known empirical
misconception \cite{harel1998students}. The conceptualization that definitions are not necessarily
of interest compared with the procedures seemed different in kind from the
concept image / concept definition discoveries of R\"osken et al. \cite{rosken2007integrating}.
Interviews with students revealed that some students saw generation of a proof
by mathematic induction as a procedure to be followed, in which they should
produce a base case, and prove it, and should produce an induction step, and
prove that. This was consistent with Weber [?, p. 4-426] who has stated ``in
the studies that I conducted, it was more often the case that undergraduates
applied procedures that were not meaningful to them.'' He went on to give a
quotation from a participant [?, p. 4-426] ``And I prove something and I look at
it, and I thought, well, you know, it's been proved, but I still don't know that I
even agree with it [laughs]. I'm not convinced by my own proof!'' Some of the
students interviewed did not know why this procedure generated a convincing
argument. Polya[?] has written a problem involving all girls being blue-eyed;
a similar problem appears in Sipser \cite{sipser2012introduction} about all horses being the same color.
The purpose of this exercise is to make students aware that the truth of the
inductive step must apply when the base case appears as the premise. In some
cases, this point was not clear to the students.
Students' conceptualizations of proof by mathematical induction can support
their choice to apply recursive algorithms. One student reported success at
both mathematical induction and recursive algorithm application without ever
noticing any connection. This student opined that having learned recursion
with figures, and proof by mathematical induction without figures, that no
occasion for the information to spontaneously connect occurred. Students reporting
ability to implement assigned problems recursively, but not the ability
to understand proof by mathematical induction also reported that ability to
write recursive programs did not result in recognition of when recursive solutions
might be applicable in general. Students reporting ability to implement
assigned problems recursively, and also the ability to prove using mathematical
induction also reported preferring to implement recursive solutions in
problems as they arose.

 (Say something about how this is consistent with the procedural conceptualization, bifurcation in Tall's writing.) 
Our work on students' choices of algorithmic approaches was consistent with
work by other researchers in computer science education\cite{booth1997phenomenography} on conceptualizations
of algorithms. Our work served to unify that of mathematician educators
with computer science educators, by providing a plausible explanation why
the conceptualizations of recursive algorithms that were found, might exist.
\begin{figure}
\centering
%\includegraphics[width=0.7\linewidth]{./}
\caption{Categories of Student Conceptualizations of Proof by Induction
that Recursion Works}
\end{figure}

Figure 5.3.2: 
\begin{table}[h]
\caption{The Outcome Space for Proofs by Induction}
\begin{tabular}{|p{.2cm}|p{6cm}|p{6cm}|}
\hline  & Category &  Description \\ 
\hline 1 & Following procedure & The method is learned, without understanding \\ 
\hline 2 & Understands base case &  The idea that a base case is proved by an existence
proof, often with a specific example\\ 
\hline 3 & Understands implication  &  The idea that an implication is proved by
assuming the premise is not used\\ 
\hline 4 & Does not understand connection & Sees the implication and proves it well, but
does not anchor the succession to a base
case \\ 
\hline 5 & Does understand the argument & Understands the argument \\ 
\hline 6 & Knows why recursion works & Can tailor the argument to explain recursive
algorithms \\ 
\hline 7 & Appreciates data structures supporting recursion & Can see the benefit to algorithm from recursive data structure \\ 
\hline 
\end{tabular} 
\end{table}
 


\subsection{Helping Students Discern Abstraction}
Recall that variation theory holds that students cannot discern a thing unless
contrast is provided. Pang has pointed out that [], for persons aware of only
one language, ``speaking'' and ``speaking their language'' are conflated. Only
when the existence of a second language is known, does the idea of speaking
become separated from the idea of speaking a specific language.
(Here is a specialization (Hofstadter), formation of a new conjunct (Valiant), see Besold 2015)
Abstraction is important in computer science, and is worthy of investigation.
Inquiry into students' conceptualizations of formalization using symbols, symbolization,
has shown similar results among students of mathematics and of
computer science [?, ?]. Student populations contain the conceptualization that
proofs ought to be expressed using symbols, and some proof attempts show
that not all students are able to formalize meaningfully. Mathematics and computer
science pedagogies differ on the recommended style of variable names in
symbolization. In mathematics, there is a preference for single letter variable
names, and in computer science it is recognized that longer variable names assist
readers in understanding. In mathematics the use of single variable names
is preferred because it is thought to contribute to cultivating students' ability
to learn abstraction. If, in computer science education, we apply variation
Table 5.3.5: The Outcome Space for Proofs by Induction\\
Category Description\\
 1 Following procedure The method is learned, without understanding\\
  2 Understands base case The idea that a base case is proved by an existence
proof, often with a specific example\\
3 Understands implication The idea that an implication is proved by
assuming the premise is not used\\
4 Does not understand connection
Sees the implication and proves it well, but
does not anchor the succession to a base
case\\
5 Does understand the argument
Understands the argument\\
6 Knows why recursion
works\\
Can tailor the argument to explain recursive
algorithms\\
7 Appreciates data structures
supporting recursion\\
Can see the benefit to algorithm from recursive
data structure\\
theory, we gain confidence in the idea that students may discern the process
of abstraction as we vary the names of the variables. We could imagine deriving
code from a requirement about a specific class, and using corresponding
variable names, and we could show the process of promoting the code into a
more general class in the inheritance hierarchy, changing the variable names to
correspond to the more general domain of objects. Thus we can borrow from
the approach used by mathematics education, but make it more explicit, taking
advantage of computer science's explicit treatment of inheritance hierarchies in
object oriented code. Seeking evidence of students' conception of abstraction,
we could examine overridden methods to see whether variable names in more
and less general implementations bear that relation to one another.
 
\subsection {Algebra}
In middle or high school algebra students became familiar with the use of letters in equations,
and solving equations which resulted in individual values, or no value, being attached to the letters.

Ideally the ability to understand expressions, to formulate pre- and post conditions would be acquired.
As we have seen that this occurs sometimes, but does not always occur,
there may be benefit to some students to review this idea.
We might choose to emphasize abstraction in this process.

\subsection{Geometry}
In high school geometry, formal proofs of geometric properties are covered.
Students are exposed to a form for argument, and are given examples of use of rules of inference to perform logical deduction.
We have seen that sometimes this process is appreciated in enough generality to be recognized
as an example of argumentation.
We have seen as well, that some students found this process entirely specific to geometry,
doubting that it had broader application.

\subsection{Seeing a Broader Context}

It may be that some students do not see a separation between the activity of formalization on the one hand,
and the application area of finding solutions to equations on the other.
It may be that some students do not see a separation between the activity of deducing using logic on the one hand, and the application area of learning geometric facts on the other.
It seems consistent with neglecting opportunities for abstraction, that these separations are not always seen,
Speciation, an idea which uses abstraction, providing a hierarchy of properties animals and plants might have, was not recognized early or universally. So, it is
not surprising that abstraction, which involves choice about which details to defer, and which to regard as significant, is not always obvious.
In the machine learning perspective, features can be learned.
What do I want to say, it takes some effort to recognize features?
There might be a way to formulate choice of features such that some better efficiency is gained by thinking of the features in that order vs. another order.
(Such as, we never have to think about some features for some parts of the tree.)
If we think about knowledge being organized in neural networks, such that abstraction has a physical manifestation, we can see that ideas between which there is little distance (by some measure, neurons, glia?) in the tree will more frequently elicit one another by linkages at the metabolic level.
At the neural level, modifications for efficiency are constantly taking place (Do we have this from Kandel and Squire?).
We might wish to exploit this in the way we teach, to exhibit the abstraction deliberately, to minimize the amount of neural connection remodeling that would occur in the process of providing an efficient neural connection remodeling that would occur in the process of providing an efficient neural representation.
Being able to learn by analogy testifies to the utility of having a neural representation that corresponds to abstraction.
Students who are working without hierarchical organization of concepts are at a disadvantage.
\subsection{Mathematics tests in high school that involve proving}
What can we learn from students of computer science who excelled in reasoning to this level?


%\chapter{Discussion}

\section{Discussion}

The idea of representation appears to be extremely important.
       Depending upon how subject matter is represented, students may or may not achieve the mental connections instructors intend.
 Students might not recognize that a heap is a graph.
 Students might not recognize that a tree, being a recursive data structure, enables the use of recursive algorithms, that are in turn provable using mathematical induction.
 
 
 \subsection{Importance}
Importance goes here, rather than in analysis\\

Programmers/developers who produce and/or verify software that is used in safety critical applications, such as medical equipment, self-driving cars, and defense-related equipment should be able to know that their software functions correctly.

Programmers/developers who produce and/or verify software that is expected to perform work, such as search, efficiently, should be able to know that their algorithms are efficient.

Computer science is the expected background preparation for people working in these careers.
Proof is the method that is used to ascertain, and to convince, that these goals have been achieved.
\subsection{Interpretation of Results}
As in mathematics, some students learn as procedure that which we would prefer that they understand.
Some procedural learning is insufficiently accompanied by an understanding as to which contexts to which it applies, and has become in some cases what Whitehead calls "inert knowledge".

\subsection{More Discussion}
\paragraph{Helping Students Discern Abstraction}
Recall that variation theory holds that students cannot discern a thing unless
contrast is provided. Pang has pointed out that [], for persons aware of only
one language, ``speaking'' and ``speaking their language'' are conflated. Only
when the existence of a second language is known, does the idea of speaking
become separated from the idea of speaking a specific language.
(Here is a specialization (Hofstadter), formation of a new conjunct (Valiant), see Besold 2015)
Abstraction is important in computer science, and is worthy of investigation.
Inquiry into students' conceptualizations of formalization using symbols, symbolization,
has shown similar results among students of mathematics and of
computer science [?, ?]. Student populations contain the conceptualization that
proofs ought to be expressed using symbols, and some proof attempts show
that not all students are able to formalize meaningfully. Mathematics and computer
science pedagogies differ on the recommended style of variable names in
symbolization. In mathematics, there is a preference for single letter variable
names, and in computer science it is recognized that longer variable names assist
readers in understanding. In mathematics the use of single variable names
is preferred because it is thought to contribute to cultivating students' ability
to learn abstraction. If, in computer science education, we apply variation
Table 5.3.5: The Outcome Space for Proofs by Induction\\
Category Description\\
 1 Following procedure The method is learned, without understanding\\
  2 Understands base case The idea that a base case is proved by an existence
proof, often with a specific example\\
3 Understands implication The idea that an implication is proved by
assuming the premise is not used\\
4 Does not understand connection
Sees the implication and proves it well, but
does not anchor the succession to a base
case\\
5 Does understand the argument
Understands the argument\\
6 Knows why recursion
works\\
Can tailor the argument to explain recursive
algorithms\\
7 Appreciates data structures
supporting recursion\\
Can see the benefit to algorithm from recursive
data structure\\
theory, we gain confidence in the idea that students may discern the process
of abstraction as we vary the names of the variables. We could imagine deriving
code from a requirement about a specific class, and using corresponding
variable names, and we could show the process of promoting the code into a
more general class in the inheritance hierarchy, changing the variable names to
correspond to the more general domain of objects. Thus we can borrow from
the approach used by mathematics education, but make it more explicit, taking
advantage of computer science's explicit treatment of inheritance hierarchies in
object oriented code. Seeking evidence of students' conception of abstraction,
we could examine overridden methods to see whether variable names in more
and less general implementations bear that relation to one another.
\paragraph{Helping Students Discern Abstraction}
\paragraph {Algebra}
In middle or high school algebra students became familiar with the use of letters in equations,
and solving equations which resulted in individual values, or no value, being attached to the letters.

Ideally the ability to understand expressions, to formulate pre- and post conditions would be acquired.
As we have seen that this occurs sometimes, but does not always occur,
there may be benefit to some students to review this idea.
We might choose to emphasize abstraction in this process.

\paragraph{Geometry}
In high school geometry, formal proofs of geometric properties are covered.
Students are exposed to a form for argument, and are given examples of use of rules of inference to perform logical deduction.
We have seen that sometimes this process is appreciated in enough generality to be recognized
as an example of argumentation.
We have seen as well, that some students found this process entirely specific to geometry,
doubting that it had broader application.

\paragraph{Seeing a Broader Context}

It may be that some students do not see a separation between the activity of formalization on the one hand,
and the application area of finding solutions to equations on the other.
It may be that some students do not see a separation between the activity of deducing using logic on the one hand, and the application area of learning geometric facts on the other.
It seems consistent with neglecting opportunities for abstraction, that these separations are not always seen,
Speciation, an idea which uses abstraction, providing a hierarchy of properties animals and plants might have, was not recognized early or universally. So, it is
not surprising that abstraction, which involves choice about which details to defer, and which to regard as significant, is not always obvious.
In the machine learning perspective, features can be learned.
What do I want to say, it takes some effort to recognize features?
There might be a way to formulate choice of features such that some better efficiency is gained by thinking of the features in that order vs. another order.
(Such as, we never have to think about some features for some parts of the tree.)
If we think about knowledge being organized in neural networks, such that abstraction has a physical manifestation, we can see that ideas between which there is little distance (by some measure, neurons, glia?) in the tree will more frequently elicit one another by linkages at the metabolic level.
At the neural level, modifications for efficiency are constantly taking place (Do we have this from Kandel and Squire?).
We might wish to exploit this in the way we teach, to exhibit the abstraction deliberately, to minimize the amount of neural connection remodeling that would occur in the process of providing an efficient neural connection remodeling that would occur in the process of providing an efficient neural representation.
Being able to learn by analogy testifies to the utility of having a neural representation that corresponds to abstraction.
Students who are working without hierarchical organization of concepts are at a disadvantage.
\paragraph{Mathematics tests in high school that involve proving}
What can we learn from students of computer science who excelled in reasoning to this level?


\section{Previously Published Work}

Three papers in this area have been published to date:
\begin{itemize}

\item CCSCNE: Categorizing the School Experience of Entering Computing
Students
\item FIE: Mathematization in Teaching Pumping Lemmas
\item Koli Calling: Computer Science Students' Concepts of Proof by Induction
 
\end{itemize}
\subsection{Categories of Experience of Entering Students}
Undergraduate students beginning study of the computing disciplines present
a various degrees of preparedness.\cite{reilly2014examination} Some interview participants enjoyed
a modified Moore method\cite{cohen1982modified} geometry class in middle school, and relished
opportunities to create proofs (not yet published). Other students are not so
well prepared.
After publishing this paper, more information relating to its topic has been
encountered. For example, consistent with the work of Almstrum \cite{almstrum1996investigating}, we have
found that, about implications, some students, who do know that any statement
must and can, be either true or false, think implications must be true.
\subsection{Categories of Experience of Entering Students}
Undergraduate students beginning study of the computing disciplines present
various degrees of preparedness\cite{smith2013categorizing}. Some had no experience, some had had
informal experience, and some had had formal classes. The formal classes
extended from using applications to building applications. Informal experience
ranged from editing configuration files, such as background colors, to full time
jobs extended over multiple summers.
After publishing this paper, we encountered more related information. For
example, consistent with the work of Almstrum\cite{almstrum1996investigating}, we found that, about implications,
some students, who do know that any statement must and can, be
either true or false, thought implications must be true. Some interview participants
enjoyed a modified Moore method\cite{cohen1982modified} geometry class in middle school,
and relished opportunities to create proofs (not yet published). Other students
were not so well prepared.
\subsection{Representation/Symbolization in Pumping Lemmas}
Some of our results to date are consistent with the framework described by
Harel and Sowder in 1998\cite{harel1998students}. We have found students holding conceptualizations
that Harel and Sowder's 1998 model\cite{harel1998students} calls symbolization: We have found
that some students may lack facility in notation. For example, in the application
of the pumping lemma, students are expected to understand the role of $i$,
in the context that a string $s$, having component substrings $x$, $y$ and $z$, can be
used to generate other strings, of the form $xy^iz$, where $i$ gives the number of
copies of the substring $y$. Moreover, students are expected to understand that
the subdivision of a string of length $p$, expressed as $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance
of a natural number, but a representation of a domain. We have seen this
lack of understanding in a situation in which it was proposed as evidence that
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified
statement. An excerpt of the errors found on tests is shown in Table .

Table : Some example errors\\
Let x be empty\\
$|xy| \leq p, so xy = 0^p$\\
$|xy| \leq p; let x = 0^{p+r}, y = 0^{p+r}, 0 < r < p$\\
Let's choose $|xy| = p$\\
$0^{p+1}0^b1^p \neq 0^{p+1}1^p \therefore xy^2z \not\in \mathcal{L}$\\
where $\mathcal{L} = \{0^i1^j, i \neq j\}$\\
we choose $s = 0^{p+1}1^p$ within $|xy|$\\
thus $\neq 0^p1^{p+1}$\\
Let $x = 0^a, y = 0^b1^a$\\
$x = 0^{p-h}, y = 0^h$\\
$x = 0^i, y = 0^i, z = 0^i1^j$

Figure: Some categories / conceptualizations found among students of
introduction to the theory of computing, and published at FIE.

Harel and Sowder identified a category of conceptualization that correctly
applied transformation and axiomatic arguments. Some students expressed
enthusiasm for the power that inheres to building arguments with carefully
specified component ideas, in particular how the absence of ambiguity permitted
arguments to extend to great length while remaining valid. Not all of the
students had developed axiomatic conceptualizations of proof. About definitions,
we have collected preliminary data on students' conceptualizations of
definitions used in proofs. Some students think definitions are boring. Some
students think that they can infer definitions from a few examples. Concerning
executive function, we have found that some students do not state the
premises clearly, and some students do not keep track of their goal. About
rules of inference, we have found that some students apply invalid approaches
to inference.
\subsection{Representation/Symbolization in Pumping Lemmas}
We found that some students may lack facility in notation. For example, in the
application of the pumping lemma, students are expected to understand the
role of $i$, in the context that a string $s$, having component substrings $x$, $y$ and $z$,
can be used to generate other strings, of the form $xy^iz$, where $i$ gives the number
of copies of the substring $y$. Moreover, students are expected to understand that
the subdivision of a string of length $p$, $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance
of a natural number, but a representation of a domain. An excerpt of the errors found on tests is shown in Table . Trigueros et
al. \cite[ p. 3]{jacobs2008developing} have observed that ``students are often unclear about the different
ways letters are used in mathematics''.  We have seen this
lack of understanding in a situation in which it was proposed as evidence that
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified
statement.
Some of our results were consistent with the framework described by Harel
and Sowder in 1998\cite{harel1998students}. We found students holding conceptualizations that
Harel and Sowder's 1998 model calls symbolization. Harel and Sowder have
identified another category of conceptualization, that correctly applied transformation
and axiomatic arguments. Some students expressed enthusiasm for
the power that inheres to building arguments with carefully specified component
ideas, in particular how the absence of ambiguity permitted arguments to
extend to great length while remaining valid. Not all of the students had developed
axiomatic conceptualizations of proof. About definitions, we collected
preliminary data on students' conceptualizations of definitions used in proofs.
Some students thought definitions were boring. Some students thought that
they could infer definitions from a few examples. Concerning executive function,
we found that some students do not state the premises clearly, and some
students did not keep track of their goal. About rules of inference, we found
Figure 5.3.1: Some categories / conceptualizations found among students of
introduction to the theory of computing, and published at FIE.
that some students apply invalid approaches to inference.
\subsection{Abstract Model for Proof by Mathematical Induction and Recursion}
Far from finding agreement that (a) theorems are true as a consequence of
the definitions and the premise, and that (b) proofs serve to show how the
consequence is demonstrated from the premise, axioms and application of
rules of inference, instead we found a variety of notions about proof, including
the well-known procedural interpretation \cite{tall2008transition,weber2004traditional,tall2001symbols}, and the well-known empirical
misconception \cite{harel1998students}. The conceptualization that definitions are not necessarily
of interest compared with the procedures seemed different in kind from the
concept image / concept definition discoveries of R\"osken et al. \cite{rosken2007integrating}.
Interviews with students revealed that some students saw generation of a proof
by mathematic induction as a procedure to be followed, in which they should
produce a base case, and prove it, and should produce an induction step, and
prove that. This was consistent with Weber [?, p. 4-426] who has stated ``in
the studies that I conducted, it was more often the case that undergraduates
applied procedures that were not meaningful to them.'' He went on to give a
quotation from a participant [?, p. 4-426] ``And I prove something and I look at
it, and I thought, well, you know, it's been proved, but I still don't know that I
even agree with it [laughs]. I'm not convinced by my own proof!'' Some of the
students interviewed did not know why this procedure generated a convincing
argument. Polya[?] has written a problem involving all girls being blue-eyed;
a similar problem appears in Sipse \cite{sipser2012introduction} about all horses being the same color.
The purpose of this exercise is to make students aware that the truth of the
inductive step must apply when the base case appears as the premise. In some
cases, this point was not clear to the students.
Students' conceptualizations of proof by mathematical induction can support
their choice to apply recursive algorithms. One student reported success at
both mathematical induction and recursive algorithm application without ever
noticing any connection. This student opined that having learned recursion
with figures, and proof by mathematical induction without figures, that no
occasion for the information to spontaneously connect occurred. Students reporting
ability to implement assigned problems recursively, but not the ability
to understand proof by mathematical induction also reported that ability to
write recursive programs did not result in recognition of when recursive solutions
might be applicable in general. Students reporting ability to implement
assigned problems recursively, and also the ability to prove using mathematical
induction also reported preferring to implement recursive solutions in
problems as they arose.
Our work on students' choices of algorithmic approaches was consistent with
work by other researchers in computer science education\cite{booth1997phenomenography} on conceptualizations
of algorithms. Our work served to unify that of mathematician educators
with computer science educators, by providing a plausible explanation why
the conceptualizations of recursive algorithms that were found, might exist.
\subsection{Proofs by Induction}
Table 5.3.3: The Outcome Space for Proofs by Induction
Category Description
1Following procedure The method is learned, without understanding
2Understands base case The idea that a base case is proved by an existence
proof, often with a specific example
3Understands implication The idea that an implication is proved by
assuming the premise is not used
4Does not understand connection
Sees the implication and proves it well, but
does not anchor the succession to a base
case
5Does understand the argument
Understands the argument
6Knows why recursion
works
Can tailor the argument to explain recursive
algorithms
7Appreciates data structures
supporting recursion
Can see the benefit to algorithm from recursive
data structure
\subsection{Abstract Model for Proof by Mathematical Induction and Recursion}
Interviews with students revealed that some students see generation of a proof
by mathematic induction as a procedure to be followed, in which they produce
a base case, and prove it, and produce an induction step, and prove that. Some
of the students interviewed did not know why this procedure generated a
convincing argument. Moore, as reported in Polya[] noted that some students
of mathematics formed the same conceptualization, that there is a procedure,
but it does not necessarily produce a convincing argument. Polya[] wrote
a problem involving all girls being blue-eyed; a similar problem appears in
Sipser\cite{sipser2012introduction} about all horses being the same color. The purpose of this exercise is
to make students aware that the truth of the inductive step must apply when
the base case appears as the premise. In some cases, this point was not clear to
the students.
Students' conceptualizations of proof by mathematical induction can support
their choosing to apply recursive algorithms. One student reported success at
both mathematical induction and recursive algorithm application without ever
noticing any connection. This student opined that having learned recursion
with figures, and proof by mathematical induction without figures, that no
occasion for the information to spontaneously connect occurred. Students reporting
ability to implement assigned problems recursively, but not the ability
to understand proof by mathematical induction also reported that ability to
write recursive programs did not result in recognition of when recursive solutions
might be applicable in general. Students reporting ability to implement
assigned problems recursively, and also the ability to prove using mathematical
induction also reported preferring to implement recursive solutions in
problems as they arose.
Our work on students' choices of algorithmic approaches is consistent with
work by other researchers in computer science education\cite{} on conceptualizations
of algorithms. Our work served to unify that of mathematician educators
with that of computer science educators, by providing a plausible explanation why
the conceptualizations of recursive algorithms that were found, might exist.

Figure 4.0.2: Conceptualizations of proof by induction and recursion, published
in Koli Calling

Index Element of Model
\begin{enumerate}

\item Some students begin learning proof by mathematical induction as if it were
a procedure.
\item Some students learn two parts of this proof technique without seeing any
connection between the two.
\item Some students do not find the procedure to be a convincing argument.
\item Some students would not employ proof by mathematical induction to explore
whether a recursive algorithm would apply to a given problem.
\item Some students understand both proof by mathematical induction and also
recursion and had never noticed any similarity.
 
\end{enumerate}

\subsection{Pumping Lemmas}
TABLE III. CATEGORIES\\
understand inequality\\
formulate correctly\\
distinguish between particular and generic particular\\
correctly apply universal quantifier\\
recognize string as member of language set


\section{Results of Combined Investigations}
There are some categories that are shared among the several contexts.
\section{Categories}
Categories found in one or more investigations

Categories\\
Definition of proof as convincing (to mathematicians) argument is not
always understood\\
Definitions in general are not always recognized as significant building
blocks in arguments\\
The idea of a false statement sometimes becomes troublesome when
negation is being learned.\\
In particular, accepting that an implication may be false, can be troublesome.
Notation is sometimes difficult.\\
Ideas presented relying on notation are not always connected with
ideas presented relying on figures.\\
Warrants are not always recognized.\\
Students do not always traverse levels of abstraction effectively.\\
The applicability of valid argument forms to contexts of interest is not
always appreciated.
\section{Critical Factors}
To determine critical factors, we can convert negative categories into achievement
levels.
\begin{longtable}{|p{7cm}|p{8.5cm}|}\hline
 
 \endfirsthead
 
 \multicolumn{2}{c}%
 {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\
 \hline \multicolumn{1}{|c|}{\textbf{Category}} &
 \multicolumn{1}{c|}{\textbf{Achievement Levels}}  \\ \hline 
 \endhead
 
 \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline
 \endfoot
 
 \hline \hline
 \endlastfoot
%\begin{tabular}{p{6cm}p{8cm}}
Categories & Achievement Levels\\
The idea of a false statement
sometimes becomes troublesome
when negation is being
learned.&\\
&True and false make sense, and
we can make arguments using
them.\\
Definition of proof as convincing
argument is not always understood&\\
Warrants are not always recognized.&\\
&Proof can sometimes be obtained
through a series of warranted assertions.\\
Definitions in general are not always
recognized as significant
building blocks in arguments&\\
&Using agreed definitions and
valid rules of inference we can
sometimes explore the consequences
of definitions.\\
Notation is sometimes difficult.&\\
&Notation helps.\\
Ideas presented relying on notation
are not always connected
with ideas presented relying on
figures.&\\
&We might wish to help students
traverse multiple rendering of
ideas.\\
Students do not always traverse
levels of abstraction effectively.&\\
&We might wish to help students
traverse multiple levels of abstraction.\\
The applicability of valid argument
forms to contexts of interest
is not always appreciated.&\\
&We might wish to give exercise
with authentic (career related)
examples\\
 
%\end{tabular}
\end{longtable}

Using the achievement levels we can infer critical factors.
\begin{longtable}{|p{7cm}|p{8.5cm}|}\hline
 
 \endfirsthead
 
 \multicolumn{2}{c}%
 {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\
 \hline \multicolumn{1}{|c|}{\textbf{Achievement Levels}} &
 \multicolumn{1}{c|}{\textbf{Critical Factors}}  \\ \hline 
 \endhead
 
 \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline
 \endfoot
 
 \hline \hline
 \endlastfoot
%\begin{tabular}{p{3cm}p{3cm}}
Achievement Levels& Critical Factors\\
True and false make sense, and
we can make arguments using
them.&\\
& True and false apply to assertions.\\
Proof can sometimes be obtained
through a series of warranted assertions.
& Proof is exploration and discovery.\\
Using agreed definitions and
valid rules of inference we can
sometimes explore the consequences
of definitions.&\\
& Efficiency but also abstraction
are aided by notation.\\
Notation helps.&\\
& Notation is one representation
and there are others. Ideas appear
in multiple guises.\\
We might wish to help students
traverse multiple rendering of
ideas.&\\
& When notation allows for multiple
interpretations, abstraction
above those multiple interpretations
has been achieved.\\
We might wish to help students
traverse multiple levels of abstraction.&\\
&Multiple levels of abstraction are
relevant at the same time.\\
We might wish to give exercise
with authentic (career related)
examples.&\\
& Authentic applications show the
use of this knowledge.\\
%\end{tabular}
\end{longtable}


\subsection{Abstraction}
Literature reports \cite{} students of CS have trouble with abstraction.
Taking abstraction to be the ability to select some details to ignore,
and thereby find a simpler model of an entity, we can transform the ideal
knowledge transfer experience into on disabled by a lack of ability to see this dimension.
The multiple-inheritance hierarchy that could be used to organize
definitions and relationships of ideas is less able. More entities will be
grouped together than effective use of the multiple inheritance hierarchy
would consider equivalent.
Another useful concept that students have been seen to underappreciate is the significance of careful definitions.
Abstraction hierarchies allow for efficiency in definitions.
A new entity can be defined as a specialization of an existing entity, and its differences
make up the new definition material.
In the absence of this multiple inheritance hierarchy, every definition in its full length
is attached to its entity.
Tie in with Mazur. For students holding the same granularity of refinement of 
concepts, conversations would be easier, because there would be fewer disconnects as one participant expressed a thought on one degree of refinement far from that of another student.
If the ideas implying the refinement of the definition inheritance graph, being different from one
discussant to the next, are rare, and/or the meaning of the sentence does not depend upon it, these exchanges are not too disruptive or distressing.
On the other hand when two sets of refinement are very different,
and the meaning of the exchange depends upon the refinement in the speaker, that the  hearer does not have,
then some degree of failure of communication will ensue.
Absence of abstraction converts tree of topics into sequence of topics.
Tree of proof examples (say of application of proof technique) into sequence of examples.
Might detract from recognizing what is a related example.
Would detract from plausible inference technique of ``related problem seen before''.
We have a goal for student programming that they should strive for segments of programs
(e.g., method implementations) to be small. One way of accomplishing this is to use abstraction,
such as combining instructions into a method, and calling the method.
If students have difficulty with abstraction, they might
have difficulty with choosing groups of instructions to represent a method.
Correspondingly, if they practice grouping instruction into methods, and using those methods, they would 
be gaining practice relevant to using abstraction.
One way to cultivate abstraction is to pose a question of which one of several examples is different.
When several things are examples of one abstract idea and one is not, identifying the one that is different involves noticing the abstraction.
These questions could be instantiated using blocks of code.

\subsection{Definitions}
Without abstraction the burdensomeness of definition is increased. This could contribute to the reluctance of students to embrace definitions.
\subsection{Symbolization}
Use of symbols is a kind of abstraction.
Symbolization is the syntax for simple, clear definitions as Gries\cite[p.205]{gries2012science}(Science of Programming) recommends for construction of programs.
Students will be hindered at this program derivation/development style if symbolization is a not-yet-acquired skill.
Program development/derivation should begin with a formulation of the requirements.
Students may arrive with some programming experience that is of a more intuitive, less
mathematically disciplined sort.
We have to ask how we desire to cultivate the abilities of such students. 
Vygotsky discussed language acquisition by children, in which some children will have begun to invent
some terms for items in their environment, and will need to be guided to abandon neologisms for the naming generally agreed in their environment.
Kuhn discussed the reluctance of scientists who have been rewarded for operating in one
perspective on nature to adopt a different perspective.
Instructor may encounter a similar reluctance on the part of students
to adapt a scientifically/mathematically disciplined approach to programming,
especially if the students have experienced some success in their earlier work.
To win over such students,
demonstration of superior outcomes on problems, especially on problems that seem insoluble otherwise,
are more frequently convincing.
Happily, Professor Gries has provided such examples.
By showing superior relative efficacy of these approaches in an activity the students recognize as 
desirable, instructors could motivate the students to learn symbolization.
\subsection{Structure}
sequence vs. sequence that has come about from combining parts. Refer to Leslie Lamport's structure for proofs. Combine with Gries' proofs for deriving code. The purpose for getting through Goguen and Malcolm is that it applies to imperative programs.





The results of a phenomenographic study comprise a set of categories of description of ways of experiencing (or capability for experiencing [p. 126]) a phenomenon, and relations among those categories.

Marton and Booth\cite[p. 125]{marton1997learning} give criteria for the quality of a set of descriptive categories.
The collective experience, over all participants in the study should be included.
The individual categories should each stand in clear relation to the phenomenon of the investigation so that each category tells us something distinct about a particular way of experiencing the phenomenon.
The categories have to stand in a logical relationship with one another, a relationship that is frequently hierarchical.
Finally the systems should be parsimonious, which is to say that as few categories should be explicated as is feasible and reasonable, for capturing the critical variation in the data.

late stages of analysis able to see aspects/facets of research object, 
see how they fit together like jigsaw pieces,
see it against background, and communicate it to others.

There are results for each of the research questions, and some combined results.

While mainly we are discussing proof in general, it can help to think about one proof at a time. Applying the analytical framework of Marton and Booth\cite[p.43]{marton1997learning}
\begin{table}[placement]
\caption{Outcome space for what is proof, with temporal facet}
\begin{tabular}{|p{4cm}|p{4cm}|p{4cm}|}\hline
Acquiring & Knowing & Making Use of\\\hline\hline
see the steps & remembering the steps & write it out\\\hline
understand the steps & remembering the meaning & produce the meaning\\\hline
understand steps and warrants & understanding the meaning & be able to apply the proof to simple examples\\\hline
analyzed the structure, determine the warrants & understand the relevance & be able to apply the proof in general, know its context of applicability\\\hline
\end{tabular}
 
\end{table}
Our goal might be in the lower right, and for some students who do not arrive that far, they might arrive at any of its three neighbors in the chart.

We are looking for ways of experiencing, for example, one way is, proofs only apply to number facts, vs. proof techniques are separable from number facts and can be used on other domains.




\section{What do students think a proof is?}

One participant opined "Some students think proof is a magical incantation."

Some students do not recognize a proof when they are looking at one. When asked "Were we doing proofs today?", such a student said "No." When asked, "Did we not show that certain things must always be the case when certain contextual requirements were met?", the answer was "Yes, oh, I guess that's a proof." When asked, "Why didn't it appear to be a proof?", the answer was "It didn't start by saying 'Proof:', and it didn't end by saying 'QED', or that box."

Some students say that a proof is a sequence of statements, starting with one distinguished statement, called a premise and ending with a distinguished statement, what we wanted to prove.

Some students say "What's a lemma?". Some students cannot, when asked for credit, identify the use of structure, such as a lemma, in a proof.

Some students know that proof ought to be a convincing argument. Some of these are not convinced by a proof by induction. When assured that they would enjoy a certain proof in introduction to the theory of computation, because it was a proof by induction, voices in a class claimed, "We never 'got' that".

Some students, when asked what they think a proof is, will report that they think it is a list of true mathematically formulated statements, demonstrating the truth of a mathematically formulated statement. Some students report that a proof has a goal, a statement to be proved true.
Some students know that the identified goal does not have to be known to be true in advance of the first proof.

Sometimes, though, students have the idea that the proof is an exhibit of their ability to connect known facts, including the goal as a known fact.



Some students, for example some taking philosophy, understand a proof more generally as not having a requirement for a mathematical formulation. Some of these have expressed dislike of such less precisely articulated statements.

Some students, when prompted, will acknowledge that warrants for these statements are required. Axioms and agreed facts do not require warrants. 
Some students, but not all, recognize that premises do not require warrants.
Some students, but not all, recognize that suppositions, as premises, do not require warrants.
Some students, but not all, recognize that cases, as suppositions, do not require warrants.
Some students, but not all, know that progress from one statement to the next, a transformation of a statement, requires a warrant.

Some of the optional syntactic ornamentation of a proof, such as literal text "Proof:", and "QED" or $\qed$, are used by some students as proxies for the proof. As in the research by Harel and Sowder\cite{harel1998students}, which they describe as "ritual proof", we find in our research that some students claim to recognize a proof when they see these artifacts, and claim they have not seen a proof when they do not see these artifacts.

Some students are aware that proof, as encountered in class, ought to be a convincing argument.
These students feel that something is wrong when they are not convinced by the proof technique they have learned to execute in a procedural fashion.

Some students know that proof is convincing others, and also ascertaining for oneself. Of these, some find that proof is convincing for some facts they regard as mathematical, yet do not think proof is applicable to programs as large as those with which they plan to be involved.
Some of these students have not yet acquired the perspective that proving theorems about the number of instruction executions, and/or memory locations needed are both numerical and also applicable to and relevant for software development.


\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{/home/theresesmith/Documents/2015Fall/Research/Thesis/whatThemes}
\caption{Conceptualizations found for what a proof is}
\label{fig:whatThemes}
\end{figure}
\begin{table}
 \caption{Critical factors for what a proof is}
\begin{tabular}{|c|c|c|}
\hline Lesser Conceptualization & Better Conceptualization & Critical Factor\\ \hline
\hline List of Known Facts & List of Warranted Facts & Warrants\\ 
\hline List of Warranted Facts & Means of Discovery & Tool rather than\\  & & demonstration to teachers\\ \hline
\end{tabular}
 \end{table}

\newpage
\section{How do students approach understanding a proof?}
Those students who felt they understood some proofs approached them by checking whether they felt each line of a proof was true.
Some of these mentioned that a statement should be warranted by previous statements.

{Some students report that a dynamic quality, such as the transformations of data they see in algorithms and in coding, helps them understand, compared to a static quality, that they associate with a proof (as well as with a theorem).}

\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{/home/theresesmith/Documents/2015Fall/Research/Thesis/howThemes}
\caption{Conceptualizations of how to comprehend a proof}
\label{fig:howThemes}
\end{figure}
\begin{table}
 \caption{Critical factors for what a proof is}
\begin{tabular}{|c|c|c|}
\hline Lesser Conceptualization & Better Conceptualization & Critical Factor\\ \hline
\hline List of Known Facts & List of Warranted Facts & Warrants\\ 
\hline List of Warranted Facts & Means of Discovery & Tool rather than\\  & & demonstration to teachers\\ \hline
\end{tabular}
 \end{table}

\newpage
\section{What do students think  a proof is for?}

{
It goes together that students who don't generalize/abstract well might not notice any application of proof to what they care about, (presuming they have an idea already, what they care about).  
I.e., when there is a problem with abstraction, we can expect that some students will not know what is the point, in terms of interest to them.
They will not find structural relevance on their own.
Moreover, when we operate at an abstract level, we should remember that some students will not see any connection between that abstraction and a specific example (say, on a test) to which they are supposed to apply it. More generally, they may not be able to see to what context the abstraction applies.
If they don't have an idea of a suitable context for use, they might not use.
}
Some students think that proofs are not applicable to what they do. They think they do not need to know it. Because they do not need to know it, they logically conclude that learning to produce a "proof" procedurally is enough, because, it earns full credit.

Some students combine the learning about proof with the subject matter that is used to exercise proof techniques; they think proof is for demonstrating facts about numbers.

Some students claim that they never produce proofs unless assigned to do so in class.

Let us call the statement to be proved, the target, so as to more clearly articulate the variety of student thinking, by escaping the connotations of "statement to be proved".

Perhaps not surprisingly in light of the teaching of proof, some students think the purpose of proof is to demonstrate that they can construct a sequence of statements that connects the truth of the premises to the truth of the target. Some of these students regard the truth of the target to be known beforehand. As the purpose of the proof is to exhibit their ability to produce an argument, it is not surprising that students say they never construct proofs unless they are assigned to do so. It is not surprising in this context, that students opt for a procedural approach, learning the parts, for example, of a proof by induction, learning to provide a proof for a base case, and learning to take a premise as a given and a conclusion of an implication to be proved. Some students do not understand why this procedure constructs a proof. Some express an unease -- they wish for the proof procedure to be convincing, to themselves. They are glad when they learn why the procedure does produce a convincing argument.

Some students recognize proof being used in class, for example in algorithms class and in introduction to the theory of computing.




Some students felt that proof was for finding out that a mathematical expression was true, or false. Some students knew that some statements could be proved undecidable.

\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{/home/theresesmith/Documents/2015Fall/Research/Thesis/whyThemes}
\caption{Conceptualizations about why to study proofs}
\label{fig:whyThemes}
\end{figure}
\begin{table}
 \caption{Critical factors for what a proof is}
\begin{tabular}{|c|c|c|}
\hline Lesser Conceptualization & Better Conceptualization & Critical Factor\\ \hline
\hline List of Known Facts & List of Warranted Facts & Warrants\\ 
\hline List of Warranted Facts & Means of Discovery & Tool rather than\\  & & demonstration to teachers\\ \hline
\end{tabular}
 \end{table}

\newpage
\section{What do students use proof for, when not assigned?}
Some students claim they never use proofs when not assigned.

It is not the case that any student, even when prompted, said they chose to carry out a proof without being directed to do so.
This could easily be due to a misunderstanding of the definition of proof.

\newpage
\section{Do students exhibit any consequence of inability in proof?}
Some students said that they knew how to craft recursive procedures, and enjoyed doing so when assigned problems designated as suitable for recursive implementations.
Some students said they did not employ recursive procedures in situations without a designation that recursive procedures were appropriate. They claimed not to be able to tell when recursive procedures were applicable.

\newpage
\section{What kind of structure do students notice in proofs?}
Some students think proofs are lists of statements without hierarchical structure.
Some students have asked what lemma means.
Some students knew that lemmas were built for use in larger proofs.
Some students were interested to hear about Dr. Lamport's structure in proofs.

\subsection{Abstraction/Generalization Relating to Proofs}
Students recognize a difference between programs and algorithms.
This recognition is more subtle than a distinction between expression in pseudocode and expression in a specific language.
Students recognize that a program might be solving a single version of a problem: values bound to parameters can be expected to change (Single assignments to parameters constitute an instance of a problem.), and conditional execution can differ based on the parameters, but there is a sense in which one problem is being solved.
Algorithms, by contrast, are thought to address a wider domain of problems. Moreover, they are considered material to be reused, either in whole or in part, for more problems as people have insight.

We can compare this study of and reuse of at least parts of with learning to play chess. Students of chess attend to previous games as instructive, as having relevance to future games, as sources of inspiration. 

Taking this attitude toward algorithms and chess games as one, which we might call a pro-synthesis attitude, we can contrast it with an attitude that some students have expressed about proof. Proof is said to be once-only, over as soon as the theorem has been demonstrated.

One thing we might infer from this attitude is that there are some students who are not internally motivated to learn to fashion mathematical arguments. Is it a foregone conclusion that if they wanted to learn to develop such arguments, they would not regard proofs they have been shown to be over?

Some students observe that mathematics includes a language that aids in thought. They also say that this language is infrequently used (by them); some say they find the language of algorithms is sufficient for their purposes.

Perhaps the wealth of defined terms in mathematics is so much larger than the number of keywords in any particular programming language, or in pseudocode, that students perceive a barrier to fluency in even a subset of mathematical discourse.

It may be significant that in programs or algorithms we don't need warrants to justify writing a next statement. It is only the case that the variables on the right hand side should be declared and preferably initialized, and the operations invoked should have those data types in its domain.

\newpage
\section{What do students think it takes to make an argument valid?}
Some students, when prompted about rules of inference, felt that when all statement transformations were warranted, an argument was valid.
Some students stated that, when the target of the proof was true, the proof was valid, converse error.

Some students express an interest in the nature of the feedback on their proof attempts.




We organize our overview of results beginning from an ideal Hilbert-axiomatic style of proof approach, and moving through approximations as they become greater departures from it.
\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{/home/theresesmith/Documents/2015Fall/Research/Thesis/valid}
\caption{Conceptualizations about validity of proofs}
\label{fig:validityThemes}
\end{figure}
\begin{table}
 \caption{Critical factors for what a (valid) proof is}
\begin{tabular}{|c|c|c|}
\hline Lesser Conceptualization & Better Conceptualization & Critical Factor\\ \hline
\hline No Warrants & Some Warrants & Warrants\\ 
\hline Some Appropriate Warrants & Fully Warranted & thoroughness\\    \hline
\end{tabular}
 \end{table}

\paragraph{Definition based reasoning}
Some students, and some teaching assistants in their teaching, are not organizing the approach to proof around definitions.
Instead some students and some teaching assistants are focusing on an intuitive approach, involving examples.
Some students use examples to infer definitions.
Some students use single examples as proof.

Some students are not aware that proofs are illustrated with facts of, for the purposes of the class, less significance than the proof techniques. 
Some students are not aware of the relevance of proof to their intended career.
These students do not see any point to learning more than a procedural approach to the proof material, as they believe it to be of no lasting significance to them.

\paragraph{Generalization and transformation based reasoning}
Some students, and some instructors, do not emphasize that a single presentation can be seen as a representative of a group. For example, Mathematical  Association of America\cite{} publishes a proof of the Pythagorean Theorem that uses rectangles to illustrate that, when they are square, the Pythagorean Theorem is being shown to be true, though of course, the rectangles need not always be square. The proof, having been established, does not rely upon the rectangles remaining in a square condition.

 





\section{Combined Description}

The interviews show a dimensions of variation over several capabilities we might wish students to develop, so as to have sufficient achievement levels at proof.

We wish students to be able to recognize when proofs are being given, to comprehend the proofs well enough both to achieve intrinsic conviction from reading them,  and to find them explanatory when the curriculum is using proofs to explain. We wish them to be able to avail themselves of proof synthesis   sufficiently to ascertain whether algorithms they might compose are suitable for a problem they are addressing, and to persuade others, if they wish to publish algorithms or applications thereof.

\subsection{Abstraction}

To recognize a mathematically formulated proof, the student needs to understand the properties of a proof.  Some students claim they have not seen proofs, after taking discrete math and while taking introduction to the theory of computation. We have encountered conceptualizations similar to the "ritual proof" category described by Harel and Sowder\cite{harel1998students}. In our students, lack of practice with abstraction offers a partial explanation.

\input{Abstraction.tex}

\subsection{Structural Relevance}

Among those students who know that proofs are being taught, there are some students who are not sure why the curriculum includes a course on proofs.
The opportunity to motivate the study of proof techniques by reference to their expected use has been lost for these students.
Besides motivation, there is the scaffolding offered by concepts about other parts of the curriculum, that could be employed, if students discerned the relevance of proof.

\input{Memos.tex}

\subsection{Logical Deduction}

In order for students to comprehend the argument exhibited in those mathematical proofs they will encounter in the curriculum, it is important that they recognize logical deduction. We know from Almstrum\cite{almstrum1996investigating} that high school students taking the educational testing service's advanced placement exam in computer science have more difficulty with problems involving logic than with those problems that do not. 

The combination of finding something, such as logical deduction, difficult and not being aware it is relevant can be expected, for students whose time is thoroughly committed, to result in avoidance.
 
\input{logic.tex}

\subsection{Comparing and Contrasting Synthesis of Algorithms and Programs, vs. Proofs}

\input{proofvsAlg.tex}

\subsection{Generalization meets  preference for examples over definitions}
Harel and Sowder\cite{harel}, and also Polya\cite{polya} have described a category of conceptualization in which students work with examples,   concrete examples, in preference for definitions. An axiomatic, Hilbert-style approach is not appreciated in this conceptualization.
When dealing with this conceptualization, 

definitions vs examples, examples are easier, value of definitions not necessarily appreciated.

Use of examples implies hope that generalization will occur.

Recognition that generalization is difficult.

When deferring the axiomatic approach until generalization is easier, we should do this consciously, and plan to support generalization.
Though we hope generalization will occur spontaneously, some students have expressed, while taking introduction to the theory of computing, CSE3502, that they do not understand logical reasoning unless it is  carried out with concrete instances. 
This poses difficulties in CSE2502. 

We can imagine a trajectory which begins in concrete examples, generalizes, accompanied by developing an appreciation of careful definitions. Also we can imagine building in structural relevance, so that a relationship between the generalized knowledge and the intended use of it, in computer science and engineering, is facilitated. During assessment we wish for the existence of a path from otherwise inert knowledge to application. Some problem-solving activity begins with the problem statement, which might well be concrete, and the generalization ability gets exercised, to recognize and example of a principle that should be known, and the knowledge, that should not be inert, should be activated and brought to bear on the problem. Because practicing taking quizzes exercises these latter capabilities, whose exercise is probably useful for test taking, we find a compatibility with existing knowledge on the utility of test preparation by taking quizzes.\cite{marcell2008effectiveness}

There are a couple of ways students work with exercises in proof, that are incomplete.

Some students reason well with concrete entities, yet are confused with abstractions. These students are not appreciating the value of careful definitions, because they do not use them as tools, or the basis for reasoning. They are more comfortable with examples, because they are operating in a concrete world.

Some students do not connect the world of concrete objects with the abstract, symbolic representation, but are making use of symbols. Some operations transforming symbolic expressions are performed correctly, but not all. The lack of understanding of the symbols combined with a procedural approach to producing a proof artifact, leaves these students personally unconvinced, and unmotivated to make use of proof when it would be helpful to them.

Some students do understand application of facts, axioms and rules of inference, and are at home with careful definitions and symbolic concision. Some of these students also study math.

\subsection{Recognize problem solutions, comprehend problem solutions, create problem solutions}

Some students know they have seem demonstrations of working code. 
Some students can mimic using supplied code, and by producing variations on it, and can comprehend how supplied code works.
While for some, a list of statements lacks properties that emerge from the collection, for others the relations and combinations are noticed.
Synthesis of problem solutions can be a difficulty for some students, including for some of those who appreciate these interactions.

This difficulty is reported  in synthesis both of logical arguments and  of solutions to problems posed in data structures and in algorithms courses.

Hunter/gatherer vs. farmer, for solutions to problems. What about the Freudian sublimation process of creation of solutions to problems? 

Schoenfeld\cite{schoenfeld1998reflections} problem solving class. Is it that, only those motivated to solve problems sign up?

Some students have motivation to solve problems that existed when they wanted to solve networking problems and configuation editing problems to support playing multiplayer games.
Some students have found gratification in problem solving in general.
Some students have a concern for earning the grades in the class.
Some of those who feel rewarded by and/or have become successful at problem solving will choose to solve problems themselves, even if looking up solutions is easier than creating them.
Others have not developed this preference for problem solving might be tempted to look up solutions.

Some of synthesis is retrieval of a learned technique in response to a problem setting that might be novel.
Some synthesis requires combination of multiple learned techniques in response to a problem setting.
Some synthesis requires analysis of the problem setting, so that divide and conquer can be applied.
Maybe we need more exercise of retrieval and problem analysis, and of synthesis.


\newpage
\section{Diagram of Conceptualizations}

\begin{figure}[h]
\centering
\includegraphics[width=0.95\linewidth]{./themes}
\caption{Themes from interview data}
\label{fig:themes}
\end{figure}
\newpage
\section{Outcome Space}
The outcomes were not arranged in a single progression. Rather, there were several means, listed below, by which students were able to construct the proof artifact required by the class. The students did not always find the artifact convincing.

\begin{enumerate}
\item Concrete to Abstract -- generalize the argument, then the entities
\item Hilbert-style axiomatic/definitional proof
\item Abstract operations  -- symbols rather than entities, structure of argument
\end{enumerate}

The concrete to abstract path enabled students to reason with specific cases whose logic made sense to them, then make the step that the logical process itself was an entity that could be reused. The idea that other concrete entities could bear the same relationships, and be subject to the same reasoning constituted a step. The idea that analogies were being made, and that generalization was possible was another step.

The reasoning by axioms and rules of inference path was known to some students. These students mentioned their appreciation of math, and in some cases their discomfort with philosophy, in connection with symbolization and application of rules of inference.

One path was operation at the level of symbols, using procedures. This path is distinguished from that involving definitions, because some students, using definitions, were clear about appropriate operations to transform symbolic expressions, but students also sometimes were unsure about denotation and about appropriate operations.

\section{Critical Factors}
On the path from concrete to structured proofs, called herein "generalize the argument, then the entities", one critical factor is that an argument about one set of concrete entities can be used on another set, having analogous relationships.

Another critical factor is that, when an argument can be reused, sets of entities that stand in analogous relationships, the relationship can be generalized. When the relationship is generalized, the entities standing in that relationship can be given symbols.

On the path that starts with symbols, students have not generalized from concrete to abstract entities, rather, they have entered the fray at the level of abstraction of symbols. Thus, a critical factor is to understand the operations appropriate to the symbols, which imbues application of the rules of inference with significance. Another critical factor is that these symbols can represent entities of interest.





 






\section{More Discussion}
\paragraph{Helping Students Discern Abstraction}
Recall that variation theory holds that students cannot discern a thing unless
contrast is provided. Pang has pointed out that [], for persons aware of only
one language, ``speaking'' and ``speaking their language'' are conflated. Only
when the existence of a second language is known, does the idea of speaking
become separated from the idea of speaking a specific language.
(Here is a specialization (Hofstadter), formation of a new conjunct (Valiant), see Besold 2015)
Abstraction is important in computer science, and is worthy of investigation.
Inquiry into students' conceptualizations of formalization using symbols, symbolization,
has shown similar results among students of mathematics and of
computer science [?, ?]. Student populations contain the conceptualization that
proofs ought to be expressed using symbols, and some proof attempts show
that not all students are able to formalize meaningfully. Mathematics and computer
science pedagogies differ on the recommended style of variable names in
symbolization. In mathematics, there is a preference for single letter variable
names, and in computer science it is recognized that longer variable names assist
readers in understanding. In mathematics the use of single variable names
is preferred because it is thought to contribute to cultivating students' ability
to learn abstraction. If, in computer science education, we apply variation
Table 5.3.5: The Outcome Space for Proofs by Induction\\
Category Description\\
 1 Following procedure The method is learned, without understanding\\
  2 Understands base case The idea that a base case is proved by an existence
proof, often with a specific example\\
3 Understands implication The idea that an implication is proved by
assuming the premise is not used\\
4 Does not understand connection
Sees the implication and proves it well, but
does not anchor the succession to a base
case\\
5 Does understand the argument
Understands the argument\\
6 Knows why recursion
works\\
Can tailor the argument to explain recursive
algorithms\\
7 Appreciates data structures
supporting recursion\\
Can see the benefit to algorithm from recursive
data structure\\
theory, we gain confidence in the idea that students may discern the process
of abstraction as we vary the names of the variables. We could imagine deriving
code from a requirement about a specific class, and using corresponding
variable names, and we could show the process of promoting the code into a
more general class in the inheritance hierarchy, changing the variable names to
correspond to the more general domain of objects. Thus we can borrow from
the approach used by mathematics education, but make it more explicit, taking
advantage of computer science's explicit treatment of inheritance hierarchies in
object oriented code. Seeking evidence of students' conception of abstraction,
we could examine overridden methods to see whether variable names in more
and less general implementations bear that relation to one another.
\paragraph{Helping Students Discern Abstraction}
\paragraph {Algebra}
In middle or high school algebra students became familiar with the use of letters in equations,
and solving equations which resulted in individual values, or no value, being attached to the letters.

Ideally the ability to understand expressions, to formulate pre- and post conditions would be acquired.
As we have seen that this occurs sometimes, but does not always occur,
there may be benefit to some students to review this idea.
We might choose to emphasize abstraction in this process.

\paragraph{Geometry}
In high school geometry, formal proofs of geometric properties are covered.
Students are exposed to a form for argument, and are given examples of use of rules of inference to perform logical deduction.
We have seen that sometimes this process is appreciated in enough generality to be recognized
as an example of argumentation.
We have seen as well, that some students found this process entirely specific to geometry,
doubting that it had broader application.

\paragraph{Seeing a Broader Context}

It may be that some students do not see a separation between the activity of formalization on the one hand,
and the application area of finding solutions to equations on the other.
It may be that some students do not see a separation between the activity of deducing using logic on the one hand, and the application area of learning geometric facts on the other.
It seems consistent with neglecting opportunities for abstraction, that these separations are not always seen,
Speciation, an idea which uses abstraction, providing a hierarchy of properties animals and plants might have, was not recognized early or universally. So, it is
not surprising that abstraction, which involves choice about which details to defer, and which to regard as significant, is not always obvious.
In the machine learning perspective, features can be learned.
What do I want to say, it takes some effort to recognize features?
There might be a way to formulate choice of features such that some better efficiency is gained by thinking of the features in that order vs. another order.
(Such as, we never have to think about some features for some parts of the tree.)
If we think about knowledge being organized in neural networks, such that abstraction has a physical manifestation, we can see that ideas between which there is little distance (by some measure, neurons, glia?) in the tree will more frequently elicit one another by linkages at the metabolic level.
At the neural level, modifications for efficiency are constantly taking place (Do we have this from Kandel and Squire?).
We might wish to exploit this in the way we teach, to exhibit the abstraction deliberately, to minimize the amount of neural connection remodeling that would occur in the process of providing an efficient neural connection remodeling that would occur in the process of providing an efficient neural representation.
Being able to learn by analogy testifies to the utility of having a neural representation that corresponds to abstraction.
Students who are working without hierarchical organization of concepts are at a disadvantage.
\paragraph{Mathematics tests in high school that involve proving}
What can we learn from students of computer science who excelled in reasoning to this level?