ch5.tex

\chapter{Interpretation/Discussion}

In this chapter we discuss the results obtained in the analysis.
First we discuss and interpret the results for the individual questions.
Then we combine the data from the individual questions, to discuss what the data seems to suggest as a collection.

When we write an algorithm or program in which we handle special cases, the amount of code for the more frequent cases may be much less than the amount of code for the unusual cases. So, too, here, the amount of discussion should not be thought to match the relative frequencies with which ideas are held by students. Conceptualizations are deemed to be held by populations of students, and qualitative research avoids quantitative ideas such as relative frequency.

In a phenomenographic study, the results include categories of conceptualizations found in the collection of students.
These were shown in Chapter four.
Much as a detective assembles clues to arrive at a coherent explanation of events, we assemble phrases to infer categories of conceptualization from the data produced by the participants. A description of each category is part of the  result, and also pairwise relationships between some pairs of categories are part of the result. 

One expectation in a phenomenographic study is that
one or more dimensions of variation will be discovered\cite{marton1997learning}.
Arranging the categories as suggested by these relationships helps exhibit a dimension of variation. 
The dimension of variation in turn may suggest distinguished points, called critical factors (also critical aspects\footnote{The phrases critical factors and critical aspects are both used. We prefer critical factors, as aspects might seem more specific to a component hierarchy of a learning objective, compared with critical factor which may admit more readily to a generalization/specialization hierarchy.}). 
Points along the dimension of variation are concepts, awareness of which is thought to be especially beneficial to students\cite{marton2006some}.

As we discuss the results, it can make sense to consider  alternate dimensions of variation, comparing them with the chosen. 
This is a process step thought to contribute to validation\cite{norman2005sage}.
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{marton2006some}. 
We conjecture that not all points along a dimension of variation are equally valuable.
Some ideas encounter more resistance from students than others \cite{puchner2014using}.
While students resist ideas, they are less likely to adopt them on their own\cite{puchner2014using}.
Those ideas that are less readily adopted by students might be preferable as critical factors, in that these exercise the helping role of teachers.

For discussion, we arrange the research questions in an order inspired by the early version of Bloom's Taxonomy of the Cognitive Domain\cite{BBloom1984}.
We attempt to trace development of student's conceptualizations, looking especially for stages at which some students seem to miss some components of the material we wish them to acquire. 
Bloom begins with recognition.

 % % %recognition
% from chap 3
  %Using Marton's overriding categorization of task and objective, we can consider that some students do not know, at least when they are studying CSE2500, that they need to be able to understand some proofs, to be good developers. Therefore, they can logically approach the study of proof in CSE2500 as a task, having some facts that they must memorize. Other students, including those with dual majors in math, wish to improve themselves by improving their ability to couch arguments in mathematical terms and both ascertain facts for themselves and convince others. Students who are aware that there are computer-science related purposes for proof, for example, in the study of algorithms they will be using proofs to understand resource consumption, will recognize the study as having the objective to improve themselves vis-a-vis dealing with proof.
       
       
       %Because the relationships are expected to form a partial order, corresponding to set inclusion of subsets of the complete (with respect to the objective of teaching) understanding of the information being taught, we can say relationships \textit{between} categories.
       
       %The set inclusion relationship can be that a deeper understanding includes a more superficial understanding.
       %It may also be that a deeper understanding qualifies a more superficial understanding, such as being applicable in a restricted domain. Thus, understanding of a liquid as being divisible to any degree can be qualified as to scale such as macroscopic, microscopic and so on.
       
       %In a phenomenographic study, this partial order is referred to as a hierarchical order.
       
       %The objective of teaching, as will be in some parts of this study, the components of proof, may have many parts, called, in phenomenology, internal structure. The granularity of the subdivision of the objective of teaching results in the number of parts in the internal structure. If we let $n$ denote the number of parts obtained with a specific granularity, we see that the number of subsets will be $2^n$, which will be inconveniently large unless the granularity is sufficiently coarse. Thus, we choose a granularity resulting in approximately 4 elements of internal structure.
       
       %Thus, when the teaching objective is, what is a proof, we may limit the granularity, such that the internal structure of a proof is, for example, 
     %  \begin{enumerate}
       %\item that particular statement which is to be proved
       %\item axioms, premises, suppositions, cases
       %\item other statements
       %\item warrants (rules of inference)
       %\end{enumerate} 
       
       %We might choose to pursue finer granularity in some cases, for example, we might pursue ``What is a statement?'', because instructors have found that not all students arriving in CSE3502 have the same depth of understanding of statement, and some do not have sufficiently deep understanding of ``statement'' to be able to comprehend a proof.
       
       
       %Marton and Booth\cite[p. 22]{marton1997learning} call our attention to learners directing their attention to the sign vs. to the signified. With proofs, Polya \cite{} has mentioned a procedural approach to executing a proof, without understanding, as have Harel and Sowder \cite{harel1998students}, and Tall\cite{tall2001symbols}. Weber and Alcock\cite{weber2004semantic} have observed and described students omitting understanding of warrants in proofs. In each of these cases, the sign is provided, but the signified is at best incompletely understood.
       
       %Analysis can usefully illuminate learning processes, taking note of the temporal domain\cite{marton1997learning}. This has been used by Booth in her analysis of how students understand the process of programming\cite{marton1997learning}.
       
       %[p. 136]\cite{marton1997learning} important to be looking whether conceptualizations appear in a certain case, in a certain period of time (such as, when see proofs again in 3500, 3502, are they recognized as proofs, some no some yes, are they helpful as proofs, or troublesome, some helpful, some not, ``never did get that'').
       
       %also moved from chapter 3
        %The idea that a variable used in the pumping lemma could take on only one value, as if it were a single root of linear equation, rather than representing the domain of values possible for strings in a language, was proposed by a student in a help session. The context was a student proposition that examples were sufficient for proofs of universal statements, because the the variable in the pumping lemma could take on only a single value.
              
          %    some students, who do know that any statement must and can, be
            %  either true or false, thought implications must be true.
 
\section{Interpretation of What Students Think Proof Is}

Here we interpret the results from section \ref{aWhatIs}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that argumentation is the activity, that a specialized language exists to support it, that some sequences of statements in this language are useful in the synthesis of proof, that some sequences of statements in this language express reasoning and carry out warranted transformations, and that the result of an argument so formulated is to convince members of the intellectual community of the statement to be proved.


It may be that students find unfamiliar that circumstance in which argumentation rather than, for example, relative personal achievement, provides the figure of merit for persuasion.
Students who are accustomed to learn from those who have earned an authoritative position might not immediately notice that in the domain of mathematical proof, only the argument controls belief.

Once students' conceptualization includes the idea of formulating an argument, previous experience writing programs may appear relevant.
Here, students are familiar with writing such lines of code as a compiler recognizes.
Moreover, students may be very familiar with the use of example programs.
These are compatible with the constructivist paradigm.
Students may gain satisfaction building with and upon examples.
Recognizing sequences of mathematical statements, that perform a function, such as proof by mathematic induction, as process steps, is easy.
The opportunity to reflect upon how the process steps accomplish what they do is taken to some degree.
Some students do not find a satisfactory explanation.
They feel uneasy, because they are not convinced, even when they can earn a full score.
They  would not gain a sense of surety in applying such a proof on their own behalf, and they do not.

Students who find that working code is sufficient for the purposes addressed by proofs could be thinking about proofs of existential statements.
Proving (not disproving) universal statements might not be of much interest for these students.
They might not be involved in making proofs of safety, for example.

Even when guided by the notion of transformation steps, students might not have a sense of direction, or of an appropriate step size.
It may be that some students are not so comfortable with mathematic formulation that, as they search through the space of possible transformations to find helpful transformations, they are guided by a sense of distance between where they are and their goal.

Some students do not have a sense of the size of a step vs. a leap, and, searching for a justification for a leap, overlook steps they could justify.

Moreover students may not know how to distinguish which steps they may take.
The importance (or rather lack thereof) that some students assign to definitions, and the lack of facility with representation in mathematical formulation, hinder some students in the construction of proofs. 
Remembering that proofs involving semantics show us the consequences of the definitions, and that definitions supply the justification for transformation steps, we can see that discounting the importance of definitions will have a strong effect on students' ability to create proofs.

This is not to say that all students linger at this conceptualization.
Some students discover the power of well-crafted definitions to support arguments of universal statements, and some students greatly enjoy the progress of their ability to create proofs over time. Some of these students have become dual majors, adding mathematics, due to their enjoyment of it.


%We have seen students learning why certain consequences are attained unequivocally as a result of certain contexts,
%without identifying the reasoning process as a proof.
%When asked about this, a student claimed to recognize proof by the tokens ``Proof'' and ``Qed''. 
%So, we see evidence in our students of what Harel and Sowder\cite{harel1998students} called ``ritual proof''.
%Another form of evidence that some students are confused about recognizing
%a proof is that students' suggestion that experimental evidence can increase one's confidence in the conclusion of a proof.
%That a proof is an argument sufficient to convince the mathematical community seems absent in these students,
%who are from opposite ends of the   grade point average spectrum.

%A deductive method of analysis would set out to compare the idea ``a process for ascertaining and convincing of the truth of one statement premised upon some statements'' with the meaningful phrases of participants.

%An inductive process, by contrast, gathers and assembles clues without comparing to any particular conceptualization.

%Some students say that proofs are about truth, and are about demonstrating that something is true.
%There is a difference of opinion as to whether the proof generates new knowledge vs. clarifying an inherent truth.
%Those hoping for the former may not feel they have learned the intended objective.

%The degree of refinement that distinguishes a derivation from a proof was not evident in the interviews. 
%Some students say that such demonstrations involve logic, and make use of mathematical notation. 
%Some students ascribe more importance to the theorems being proved than to learning the process of proving.
%``These have been proved before.'', ``You prove it, it's done, finished.'' ``Do programmers have to know these number facts?'' ``I prefer to use code.''

%There are students who say proofs should be convincing.
%Some of these have expressed concern when they do not understand why a particular
%argument should be convincing.
%There are students who don't understand that a proof is unequivocal.
%These are two different ways of arriving at a conceptualization that lacks
%understanding of who it is that proof achieves its credibility.






%Some students say that proofs contain sequences of logical statements.
%There is a diversity of concepts for what a logical statement is.
%Some students know that the use of a logical statement at a point within a sequence must be warranted by what has been established prior to that point.

%Some students say that there are forms or patterns that can be used, such as proof by mathematical induction.
%Some students have expressed a preference, for occasions in which they are producing proof, for proofs whose construction is guided by what these students perceive as a procedure. It appears that these proofs involve less creativity or less searching for next statements. Some students characterize these proofs as having steps that can be followed. Some students refer to proofs that seem to lack guiding steps as ``logic proofs''.





%We could propose an analogy between finding a desired destination along roads by ``dead reckoning'' vs. following the instructions from a source such as a list of directions or a GPS-enabled map software. In ``dead reckoning'', the driver has some notion of the relative placement of the present location and the goal, has a sense of direction, and can estimate the value of a road as it is discovered, according to its width, its proclaimed direction and sometimes the presence of a list of supported destinations. A person following directions can do so without this sense of relative placement.

%Polya\cite{polya1954mathematics} and Schoenfeld\cite{schoenfeld1993learning}  have things to say about problem solving and proving.

%Some students have observed that they began by trying every allowed transformation, to see what resulted, and that after spending hours doing this they developed some ability to predict what the result of a transformation would be.
%Some students have remarked that they expect they would do better with more practice. 

%In summary, we can consider plausible the implication ``If students did not appreciate the role of definitions, or if they did not have facility with abstracting from a specific situation to a mathematical formulation, they would have trouble developing a succession of warranted transformations.'' We have some student claims that they do not consider definitions to be valuable. We have also student claims that even when they can reason about concrete situations (instances with people and things), they cannot perform the same reasoning steps with symbols. These appear to be sufficient sources of difficulty.

%\subsection{Alternate Dimensions of Variation}
%Does the idea about direction, step size go here?

%It seems that a clear understanding of what a proof is -- a (thoroughly) convincing argument -- will help students do better in all topics related to proof. 
%Emphasis that convincing, unequivocally, is the goal.
%Argumentation by logical deduction is the preferred technique for convincing.
%Warranting, either by use of syntax rules of inference and semantics via definitions, is the linkage that allows a list of statements to furnish this confidence about a universal statement.

%The proposed dimension of variation is depth of understanding of the role of definitions, especially a generalization/specialization hierarchy of defined terms, vs. process steps, in proofs.
%One alternative is that students are fully appreciative of the role of definitions, but lack some degree of facility using mathematical formulation. 
%If this alternative were the case, students would be able to be articulate in their verbal descriptions of the relationships of ideas, while being unable to render these ideas in mathematical expressions.
%Another alternative is that students are fully appreciative of the role of definitions, but lack some degree of ability to work with abstractions.
%Another alternative is that students are fully appreciative of the role of definitions, but lack some degree of appreciation of the role of warrants that contribute to the formation of an argument from the succession of statements.

%A lack of understanding of the warranted nature of a sequence of statements transforming the premise into the conclusion seems to offer an explanation of how it can be that otherwise capable students might think that experimentation is not redundant in the presence of proof. This might offer an explanation of how it can be that some students can believe that the argument proceeding from the assumption of the premise could establish that premise as true.

%The proposed explanation that the student is not using words according to their definitions, and intended to say that the argument supports the claim, rather than saying an argument supports a premise.

%\subsection{Alternate Critical Factors}

%If we accept depth of appreciation of the role of definitions as the dimension of variation, we might ask where along this axis might the critical factors be.
%We have seen student conceptualizations including that definitions are uninteresting, or can be inferred from a collection of examples. We have also seen, from students also majoring in math, a strong understanding of the role of definition in argumentation.

%As an alternative critical factor we might choose the source of a warrant. We could consider that some conceptualizations include that warrants are based upon definitions and some conceptualizations do not know where warrants may arise.



% % % comprehension
\section{Interpretation of How Students Attempt to Understand Proofs}

Bloom\cite{BBloom1984} arranges comprehension after recognition.

Here we interpret the results from section \ref{aHowU}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that
they attempt to generalize from an instance to a pattern, and they attempt to visualize a process.

We have seen that there is a  conceptualization of a proof as the result of carrying out process steps (``Produce a base case, prove the base case, produce an induction step, prove the induction step'').

We can readily imagine that as a student attempts to understand an instance of proof, an attempt to categorize the instance as one of the student's collection of known types could occur.

A more insightful picture of the process of attempting to match an instance to a known type is gained by examining the ability of students to generalize and specialize.

We consider the implication: ``If students could generalize from a specific problem involving unadorned (explicitly no context, which students see as ``number facts'', facts about prime numbers, about numbers modulo $n$) natural numbers to a general argument involving natural numbers, (i.e., whether or not there may be context, such as a push down stack or depth of tree) and could specialize from natural numbers in general to natural numbers characterizing a (different) specific problem, then students would be able to transfer their understanding of one proof by mathematical induction using unadorned natural numbers to another proof by mathematical induction using natural numbers characterizing a different specific problem. We consider this implication to be believable. Then using student claims as evidence, we would have to conclude that either students have difficulty generalizing or students have difficulty specializing. (Given knowledge of the ease of learning specialization (a form of association in which two existing ideas are combined)\cite{quiroga2015concept,reddy2015learning}, and knowledge of the utility of good REM sleep in generalizing\cite{czeisler}, we increase the confidence with which we regard generalization as the greater problem.)

Further insight into the process of recognizing an instance of a proof as being of a category of proof types comes from consideration of modes of expression, such as mathematical formulation, diagrams, and code.

Some students do not understand that the structure / semantics of recursive programming is the same as the structure / semantics of proof by mathematic induction. Some students come to appreciate the correspondence as they discuss it in an interview. Some students saw this subject explained with mathematical notation but not figures in the case of mathematic induction and with figures but not mathematical notation in the case of recursion. The difference between these two representations was given by the students as the reason they did not recognize the structure / semantics of these as being the same. Discussing these together allowed some of these students to generalize from the disparate representations to the common idea. This suggests that the thinking about  proof by mathematic induction can be superficial. Student interviews suggest that the depth of understanding is sometimes insufficient to convince the student of the argument.

It is as if students may not obtain the benefit of seeing entities interrelated by generalization/specialization or by structure. Without this benefit, a collection of isolated entities exists, with a larger demand on memory.

Students tell us this attempted categorizaton is what they do, and for instances that do not match known construction processes, visualization is attempted next.
It seems as if the students are drawing on their experience with programming.
A program carries out activities; these may be visualized at some level.
The transformations carried out by proof steps may be subject to visualization.
Attempt at visualization is a very interesting critical factor because it fits in well with the work of Harel and Sowder\cite{harel1998students} who distinguished the categories perceptual and transformational. 
There is a choice about what is being transformed. The situation being transformed in the work of Harel and Sowder is not necessarily what is being visualized by our students. That our students are open to insights gained through visualization suggests we might wish to exploit transformations of the helpful kind.
%It is not necessarily clear that visualization is helpful.

It seems that students do not have many resources to bring to bear in their efforts to understand proofs.
It also seems that the chief resource, attempts to match instances to types, is hindered by difficulty in generalization and specialization.




%If construction by students is 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.



%When students are trying to understand a proposed proof, they sometimes wonder how the author knows that a statement is justified. 
%We might prefer that students always ask themselves this question.
%Is it not the case that a statement is warranted , either by syntax alone or by the semantics (by the definitions of the terms being represented) of the expression?



%Could it be that the students' declared preference for proofs they can supply by following a procedure, such as proof by mathematic induction, derives from their ability to provide a proof without involving the depth of understanding necessary when they must thoughtfully navigate the space of allowable transformations?

%A student may manipulate expressions composed of symbols, numbers and operators, and an aware student might recognize this manipulation is useful for understanding the depth of the stack in a pushdown automaton.
%We would like the student to read a so-called word problem, extract the idea, express it in mathematical formulation, be about to apply transformations of the mathematical expression to reveal implicit truths in this context.


%\subsection{Alternate Dimensions of Variation}
%The proposed dimension of variation is degree of pattern matching and reduction of generalization.
%Student conceptualizations include that comprehension of a proof can be obtained by finding the explanation for the corresponding proof text among class notes, by recognizing that a proof follows a pattern that has been explained in class. 
%Students also try to understand proofs by considering specific elements of the domain to which the proof applies.
%Students reach for understanding of an unfamiliar line of reasoning by trying to find an analogy in a more familiar specific domain. A proof may invoke that a relationship is transitive, and a student may try to appreciate the reasoning by considering a family tree.

%An alternate dimension of variation is facility with mathematical formulation.
%Generalization occurs when mathematical formulation is used, so these separate ideas may behave in similar ways.
%We would like to distinguish between a dimension of variation for mathematical formulation alone, that does not include generalization, and the dimension of generalization, that includes mathematical formulation.
%One tool is the effectiveness of reasoning by analogy.
%What is intended here by reasoning by analogy is that we can help a student see a relationship, $R$, among entities if a relationship with the same structure is already known for some other entities. 
%This process offers the opportunity to use generalization.
%When the known entities and their relationship is discussed, it can happen that the relationship can be seen separately from the whole.
%The relationship, seen separately, is now a more general idea, from which, with changed entities, another example can be specialized.
%Discussion with some students has shown that some students can separate out relationships from a specific case into a more general idea.
%On the other hand, some students, even when presented with two concrete sets of entities enjoying a similar relationship, do not readily separate the relationship from its realization with entities.
%In the use of mathematical formulation, we have seen conceptualizations that attach to the notion of variable, that is can be used to refer to a subset of a domain, as a free variable does. We have also encountered conceptualizations that a variable may not refer to a locus or other set of points, rather it must necessarily represent a single point, that may, by manipulation, be discovered, thus there exists a dimension of variation of conceptualization of generalization, even within the domain of mathematical formulation.


%\subsection{Alternate Critical Factors}

%Our students are thinking of a proof that carries out a process, to which idea we can readily, but not necessarily correctly, associate the idea of transformation of a representation.
%An alternate critical factor could be analysis into parts.  These parts could be stages in time, but they might also be static components, lemmas.

 % % % applications
\section{Interpretation of What Students Think Proof is For}

Here we interpret the results from section \ref{aWhat4}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that there are some general reasons for proof, such as demonstrating claims, and some computer science related reasons for proof, namely providing assurance of algorithm properties such as resource utilization, providing guidance as to whether an algorithm provably meets its requirements, and some deep reasons, also not related to computer science.

Some students do not know why proofs appear in the computer science curriculum, at the time they are studying them.
We expect this to be remediated upon the student seeing proofs used in subsequent classes, and sometimes it is, but sometimes students don't recognize proofs when they see them in subsequent classes.

Students have trouble generalizing, so even when they have seen a proof by mathematical induction with natural numbers in Discrete Structures, they do not necessarily transfer that knowledge when they see a proof by mathematic induction on the depth of a stack. Those who see that what has been thought of as a pattern can be used in such a way that its meaning is important may choose at this time to request explanation of this proof technique.

The interpretation is that there is a very broad distribution of conceptualizations, and that continued study improves the least informed conceptualizations. Continued study, such as Introduction to the Theory of Computation can be hampered by operating with the less informed conceptualizations. Students might benefit from an optional supplementary course, possibly over winter or summer break.
The Mathematics department might be a resource.

%Because proof is the means of discourse in the Introduction to the Theory of Computation, students who are not yet facile with proof can fall behind.
%Worse yet, students who have not grasped that proof is establishing truth through logical deduction, through argumentation, are not convinced by such arguments as reductions from known undecidable problems.

There is a gap between obtaining bounds on resource consumption and deriving mathematical formulation of intuitive ideas.
The effects of aspects of algorithms on the resulting complexity class might be a valuable stepping stone in between.

%Some students are thought not to know why proofs are taught, because they propose such reasons as ``The professors were math majors, and feel we should know some math.''

%Some students are thought not to recognize that proof is about coming to be aware of the truth value of an expression, given the awareness of a related expression. 

%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''

%Some students were asked whether they ever employed proof for any reason other than having been assigned. No student said they employed proof for any purpose other than responding to an assignment to provide a proof. When students said they never used recursion because they never knew whether a situation warranted the use of recursion, the interviewer suggested that proof might be a useful tool for understanding the situation. Students acquiesced. Given the difficulty with transfer, it appears that students do not choose to exercise this transfer.
%\subsection{Alternate Dimensions of Variation}
%The proposed dimension of variation is degree of specificity of purpose, with initial ideas being vague but more advanced ideas appreciating some particular applications of proof.

%An alternative dimension of variation could be to provide deeper understanding of the nature of computation. Engaging in proof gives students the opportunity to contemplate the operations they carry out in algorithm construction with respect to how the complexity of an algorithm may change as aspects of the computation change, as from 2-SAT to 3-SAT.
%\subsection{Alternate Critical Factors}


% % % more application
\section{Interpretation of How Students Attempt to Apply Proofs (When Assigned)}

Here we interpret the results from section \ref{aWhat4}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that students copy proofs seen in class, modify proofs seen in class, attempt to make use of transformation steps, and, when they can make correct proofs, sometimes strive for efficient transformations.

Though these steps may seem easy, the students have trouble with them.
Students have trouble with negation, even of statements with a single quantifier. 
We might ask: ``What if students are not thinking of universals?''

Some student remember a process in which some expression A is negated, logical deductions are made and a contradiction reached.
Based on this contradiction, something is deduced to be true.
However, some students produce proof-attempts in which it is something other than A which is subsequently claimed to have been shown true.
This could be because the steps of proof by contradiction have been learned in the absence of understanding of how it works.
(This process is not accepted by all mathematicians as sufficient, but it is accepted by many, and taught.)
There are\cite{marton1997discontinuities} cultural differences about the order in which a process to be understood is learned.
In some situations the process is expected to be learned by rote, with understanding following and in others understanding
is expected first making the procedure easy to remember.
Uncertainty about the appropriate time to ask questions
can result.
Some students have reported that their cultural background
discourages asking questions at all; 
combined with uncertainty about timeliness,
this discouragement could overwhelm the desire to get help for understanding.
\section{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.
%\subsection{Alternate Dimensions of Variation}
%We don't have enough information about this.

%\subsection{Alternate Critical Factors}
%We don't have enough information about this.
% % % yet more application
\section{Interpretation of Whether Students Exhibit Consequences of Inability With Proof (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.
%\subsection{Alternate Dimensions of Variation}
We do know that students say they eschew making use of algorithmic techniques they know, for want of recognizing when these are applicable.
Some students say their approach to choosing among algorithms they know includes consulting their relatives and friends.
We could postulate a dimension of variation about the relative value of the methods students use when they reason about the applicability of algorithms to situations.

%\subsection{Alternate Critical Factors}
We could arrange algorithms according to some guidance about how generally useful they are, and discuss variations in situations that make algorithms more or less useful. 

\section{Interpretation of Student Familiarity with Specific Proof Techniques}
Some students are familiar, in the sense of name recognition, with proof by mathematical induction, contrapositive, contradiction and cases.
Some students see these as patterns for proof construction, i.e., steps that can be carried out. 
Some students are aware that, but are not always possessed of intrinsic conviction that the patterns achieve the desired result.
Thus some 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.

%\subsection{Alternate Dimensions of Variation}
The proposed dimension of variation is that comfort derives from degree of similarity to a process, as in, students are more comfortable with proof by induction because there is a process that they have learned for producing its parts. Students have somewhat less comfort with proof by contradiction, which also has a process, but also has a scope within which a premise obtains, and an outer scope in which it does not. Students have even less comfort with proofs for which ``application of logic'' is the only guidance they perceive.

An alternate dimension of variation is that comfort derives from the frequency with which they have practiced a certain kind of proof. Students have remarked that they begin a proof by selecting the technique they have practiced most often, without regard for the problem statement.

%\subsection{Alternate Critical Factors}
We could emphasize the kinds of transformations that are made.
An applicable rule of inference allows us to make a transformation.
We might raise the students' comfort level by increasing their ``sense of direction'', their sense of how distant the presently known representation is from the desired representation, and developing a sense of whether application of any given rule can move the representation in the desired direction.
% % % synthesis
\section{Interpretation of How Students Use Structure in Proof}

Here we interpret the results from section \ref{aStruct}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that proofs are like programs, being composed of statements, that the statements carry out process steps, that certain patterns of process steps exist (such as proof by mathematic induction) , that patterns are not adequate for everything, some proofs must be created as a problem or puzzle  being solved, and lastly the most comprehensive conceptualization covers the idea of solving a problem in parts.

It seems clear that students are using their backgrounds from programming in discerning structure in proof.
Mention of cases, which appear in the programming construct  switch-case,  and in proofs were sadly lacking. Mention of dichotomies, as in the programming construct if-else and in proof by contradiction were missed as well. The situation with proof by mathematic induction and recursion may be useful here. Could it be that the representation of the switch-case construction is sufficiently different that students do not on their own translate from the code representation to the mathematical formulation? The OR-elimination rule from Huth and Ryan\cite{huth2004logic} , for example, might not be taught in Discrete Structures.


From Huth and Ryan\cite{huth2004logic} we see ``How did we come up with the proof above? Parts of it are \emph{determined} by the structure of the formulas we have, while other parts require us to be \emph{creative}.''

It would help students to be able to recognize and exploit structure of the statement to be proved. They could be guided by the structure of what they are to prove, in choosing some parts of the proof they are to construct. Therefore it is of interest to know whether they notice structure within example proofs they are shown.

Because some students do not recognize structures, such as implication introduction, in proofs, and do not correlate these with the structure of statements to be proved (``When I need to do a proof I try proof by mathematical induction because we practiced that most often.'') it lends more confidence to the conjecture that certain approaches to proofs are memorized as monolithic processes, as might occur when learning is scaffolded by learning a proof as a single algorithm, rather than understood as arguments, with parts that can be assembled, where the parts, being smaller arguments, might be thought of as smaller algorithms.
There is some significance to the assembly of the smaller parts.
Some part of it may be pattern matching\cite{huth2004logic}, but there may be a requirement for reasoning, for creating an argument.

Students were familiar with the idea of proof by contradiction, though when it was described as preparing a context in which an additional premise was available, and therefore similar to introduction of special cases, which also introduce contexts with additional premises, students did not find this to be a familiar idea.

One interpretation of this is that some students are comfortable with the idea of proofs having structure, beyond the practiced structure of proof by mathematic induction and proof by contradiction. 

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{Alternate Dimensions of Variation}


%\subsection{Alternate Critical Factors}

% % % analysis
\section{Interpretation of What Students Think Makes a Proof Valid}

Here we interpret the results from section \ref{aValid}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that students should know what's true and why (from memory), should reuse proof patterns (such as proof by mathematic induction)  and should stick to valid rules of inference.

These conceptualizations seem to suggest that students are not comfortable with their ability to take on logical deductions of unspecified nature. Rather, the conceptualizations seem to convey restrictions.
%For students who shun definitions restriction is probably helpful.
The first conceptualization seems daunting in its magnitude, when scaled beyond the specific examples taught in one semester of Discrete Structures, to the mathematical domain of interest to computer science.

The third conceptualization reminds us how limiting the reluctance to use definitions to recognize warranted transformations is.
%There is the conceptualization that many theorems exist and they can be invoked, in combination.
%There is the conceptualization that established patterns of proof, such as proof by mathematical induction, and proof by contradiction, and proof by modus ponens exist.
%There is the conceptualization that later statements must be justified by earlier statements, without clarity as to how this justification is achieved.
%There is the conceptualization of subsequent statements being warranted on the basis of the definitions of the terms being transformed.


%\subsection{Alternate Dimensions of Variation}

%The proposed dimension of variation is extent of what students understand to confer validity. 
%An alternate dimension of variation is the degree of judgment about how large a transformation step may be attempted with complete confidence.
%\subsection{Alternate Critical Factors}
%The granularity of a transformation could be chosen according to what theorem provers use, or invariants applied to algorithms.

 
 
\section{Interpretation of Combined Data}

Here we interpret the results from section \ref{aCombine}.
For the convenience of the reader, these were that the  conceptualizations build from earliest, that did not yet recognize that argumentation by logical deduction is the subject when learning how to prove, followed by the more comprehensive conceptualization that includes the idea of reasoning, but prominently encapsulated within processes that can be reused without necessarily understanding; followed by a more comprehensive conceptualization in which proofs can be constructed outside of patterns, but the process of warranting is not soundly understood; followed at last by understanding justification of steps and valuing efficiency.

It seems worthy of note that  some students do not see, at least not right away, that argumentation is being taught.

Some students do not pay attention evenly to the material presented in lecture.
Some students choose to pay more attention to examples, and even ignore definitions.
It can easily be problematic for students if they choose naively the material to which they attend most.

\subsection{Argumentation}

One interpretation, consistent with the data, is that students don't pay as much attention to the nature of a proof as an argument as they pay attention to the apparent similarity to programs.

When a proof has a form that students can memorize, such as proof by mathematical induction, they can memorize the form and write proofs as sequences of steps, as they describe. When a proof does not have this form, they know they need to use logic, but have been inarticulate about how they use logic. They do not speak of warrants, and they do not mention finding structure, either in proofs they are trying to understand or in statements they are trying to prove, and none related the structure of the statement they were trying to prove to the structure of the proof they were constructing.

By feeling uncomfortable with logic, not paying attention to definitions, and not noticing structure, and not having the purpose of constructing an argument, they are at a disadvantage in creating proofs.

It could be that students are scaffolding their learning of proof with their knowledge of programming.
Though the Curry-Howard isomorphism provides strong support for scaffolding learning of proof by studying how compilers and/or interpreters transform programs from source code into more platform-specific expressions, this is not generally the approach to this scaffolding that students are taking.
Instead, we find some students observing that some proofs, for example, proofs by mathematic induction, seem to proceed according to a process. We have seen the student conception ``logic proofs'', placed in contrast with proofs that seem like processes.
One significant difference is the creativity called for by the so-called logic proofs, compared with the process-like proofs.
Another difference is that a proof constructed by following a process might appear successful in an assessment even though unconvincing to its writer.

Some students report beginning with a premise and trying every transformation provided by every available rule of inference. This impractical approach, when tried, suggests that some students might not, early in their practice, understand the syntax of the logical formulations with which they are working. This would be consistent with the work of Almstrum\cite{almstrum1996investigating}, and observations by Sheehy (reported herein).

When we ponder a preference for examples over definitions, 
in the context of scaffolding learning of proof with learning of programming, the 
utility of examples in learning programming is of interest.
Examples, such as ``Hello, world'' are commonly used in learning programming.

It may be useful to consider an approach to definitions from examples described by Carnap\cite[page 137?]{carnap1958introduction}. He describes starting with the idea of parallel lines in a fixed plane. From the idea of parallel lines, equivalence classes of parallel lines can be obtained. From the idea of differing equivalence classes, the idea of direction can be abstracted. 

This furnishes an example of a dimension of variation. By noticing that direction can vary, the concept of the direction of a parallel line is made distinct from the concept of parallel lines. If every parallel line had the same direction, no distinction between lines being parallel and lines having the direction would occur.

If we were to build upon the preference of some students to work with examples, or even to appreciate the task they take upon themselves when they attempt to proceed in this way, we might wish to explore the nature of learning about proofs through examples.

To introduce proof techniques, we use domains such as natural numbers, integers, and graphs. This is deliberate, so that time need not be spent acquainting students with the domain from which examples are chosen. We use these domains in instruction and assessment.

In later courses we employ these proof techniques with other domains, such as grammars and state machines.

\subsection{Generalization / Specialization}

By ``students know'' we mean students are able to exhibit what they know .
If student $s$ could understand example $x$ of principle $p$ in domain $d1$, and could generalize principle $p$ to apply to      more domains, and could specialize principle $p$ to apply it to domain $d2$, then, student $s$ would be able to exhibit the application of principle $p$ to domain $d2$.

Is this not what transfer is?\\
Transfer, due to difficulty students have with it, is a useful measure of a proposed educational intervention.\cite{rutten2012learning}\\
If transfer were thought to be the combination of a generalization and a specialization, can we tell whether both of these are, or one of these is and if so, which one of these is difficult?
When students learn proof by induction it is often the case that the domain of discourse is natural numbers.
They may be told that this domain can generalize to a domain of things that can be put in correspondence with natural numbers.
They may see an example of proof by mathematical induction about the depth of a stack, which is characterized by a natural number. 
They may discover with such an example, that they don't understand proof by mathematic induction.
Some students prefer, among the proof approaches they study, proofs that follow a pattern. 
These prefer proof by mathematic induction because they can learn that pattern. 
They learn that there is a step, called establishing a base case, that must be proved.
They learn that there is a step, called establishing the inductive hypothesis.
They learn that an inductive hypothesis must be formulated and proved.
Not all students find the combination of these to be a convincing argument.
The existence of Polya's supposed proof that all girls are blue-eyed blondes, which reappears in Professor Sipser's book as all horses are of the same color is directed at the missing idea in this conception.
Some students do not see why following this process to produce a proof artifact generates a convincing argument, as they are not themselves convinced by it.
Proof by contradiction has also bee exposited as a process.
In this process, an item is negated, an absurd conclusion is drawn and the claim is proven. 
However, some students do not see that contexts are being established used and closed.
They do not see that a context is reserved, and that inside this context a premise, namely the negation of the conclusion of the claim, is made available for deduction.
Some students do not see why any contradiction will do for the purpose of disqualifying the premise in the context from the realm of the possible.
Some students are not so comfortable with the law of the excluded middle that they are confident about using it.
From some students, the amount of conviction they gain from an argument form is different depending upon whether the form is occupied by concrete or abstract entities.
They also could be explained by a difficulty in generalization.

Summarily, a difficulty with generalization exists.
A difficulty with generalization would explain problems with mathematical formulation.
A difficulty with generalization would explain problems with transfer.
A difficulty with generalization of representation would explain problems with data structures.

To the question ``If they cannot generalize, how is it that they do so well?'', we might wonder whether in part it is because they learn to perform proofs as process. We are not talking about all students here, only some of those who do not understand.

If we want to test the idea of generalization as preference for a particular representation.

Difficulty knowing how to translate
discussion with figures
such as drawings of binary search trees into code.

Learning to manipulate within a notation.
Are these syntactical manipulations only?

Semantics of a notation has more of something that syntax.
Sometimes this which semantics adds to syntax is called meaning.
Can we say that syntax can be used to denote, but relations in predicate calculus have meaning?

Is there a relation between meaning and generalization?
Generalization is dropping some details that are (for some reason) less significant while paying attention to features/properties that enable grouping into a class of some entities that have these properties in common.

We may say some properties are meaningful while other are not, so meaning and generalization seem to be related ideas.



There is an amount of attention that students give to their coursework.
That level of attention is not necessarily even.
That level of attention could be influenced in multiple ways.
A student may pay attention in one way when having just heard that something will be on a quiz.
A student may pay attention in another way, when having just heard that something will not be on a quiz.
While a relatively relaxed, attentive, reflective mode might be deemed appropriate by an instructor, as a response to hearing that something will not be on a quiz,
and while some students respond that way, it can also happen that a student's response is to think beyond the class, such as wonder about missed telephone calls.
While it may seem obvious to an instructor that anything discussed in class deserves attention, interview results have shown that some students are not aware that anything to which class time is devoted should be regarded as worthy of attention.

Their prior experience could easily have trained students to think that instructors attach points towards a grade to important learning objectives.
There should be no surprise when students operate as if points imply importance.
Students can easily err, supposing that no points implies unimportant.

Instructors provide scaffolding to assist the development of student concepts.
Some students take advantage of such scaffolding.
That students sometimes take advantage of scaffolding implies that they can.
It is probably true that students will use the ability to take advantage of scaffolding, even using material that might not have been intended for scaffolding.
Some students learning about proof scaffold this new material with what they know about programming.
The graceful transition from mathematical proof to programming language semantics illustrated by structural operational semantics (see, e.g., H\"uttel \cite{huttel2010transitions}) shows that scaffolding proof learning in computer science and engineering by programming can have good results.
At the point in the curriculum at which proof is being taught, it could be that some students do not yet have the maturity of understanding of programming languages to afford this benefit on their own.
It might be that explicit scaffolding of proof with programming language examples would improve the results.

\subsubsection{On generalization}
We want students to be able to think at multiple levels of abstraction and to traverse these to find the most appropriate one or ones to be using for any particular activity.
Because we ant student to have this capability, we can reasonably ask where in the curriculum is this addressed.
We can also ask, for any activity in the curriculum, what projections fo the learning activities have, onto the skill of traversing the levels of abstraction, i.e., what use of this skill do the learning activities exercise.
For the curriculum should address building the skill earlier than the curriculum should rely on the skill.
Mathematical formulation, i.e., representing some elements of a problem of interest in mathematical form, or syntax, is an example of abstraction.
Expressing the transformation of data from available input into a desired output is an abstraction,too, so the students do this to some degree as they program.

Abstract is not only an adjective, it is also a verb. 
In the sense of the verb, we may ask, over what range we are exercising the ability of the students to abstract.

If we, consciously or not, work in a domain of abstraction levels with one level, the students might not get a lot of exercise performing abstraction, i.e., looking at a problem through the lens of multiple levels of abstraction.
Let us briefly consider arithmetic problems. 
Students learn some transformation manipulations with numbers.
Then, the opportunity to exercise this skill in a domain wider than strictly numbers, namely ``word problems''. 
Word problems offer the opportunity for students to notice that the domain of the word problem can be generalized to the more abstract level of reasoning that has been addressed with the numeric calculations. 
It is well known that being able to do word problems is an achievement level that is not masted by all students, at least by the time they are assessed.

Perhaps another example of the same phenomenon is the sift in perspective from working with specific program goals, such as extracting item $a$ from database $b$ and using it to choose a property setting on user interface widget $c$.
The more abstract perspective that there are programs, there are data storage mechanisms, and the arrangement of data facilitates, to some degree, the resource consumption of the algorithm.

Programming has a representation for levels of abstraction.
One is UML\textsuperscript{\textregistered} diagrams.
In the introduction to object oriented programming, multiple levels of abstraction are used.
Yet students have asked why we spend so much time on UML\textsuperscript{\textregistered} diagrams.
They do not see a purpose for this, which perhaps should concern us.

Lovato\cite{was it professor Sheehy? with powerpoint definitions/examples} has pointed out students preference for examples over definition-governed consequences.
Tree from general idea though levels of specialization to examples.
We prefer to teach in a top down manner because we realize the inefficiency
of building the abstraction upwards to the definition.
The reason for which students prefer a bottom-up, examples-based approach might be because there is less need for scaffolding in a bottom up construction.
If we could scaffold our general definition and its specialization with ideas bearing similar relationships, i.e., with an analogy, the preference for building up might be ameliorated.

%Are CS students' conceptualizations more like Harel and Sowder, or more like Tall?
%Are the several schemes (Pirie Kieren, etc. complementary? reconcilable? Is one more likely than another based on cognitive neuroscience of language? (proofs are in a language after all))


 

We know some students have trouble with generalization. 
Some students can reason about relationships among concrete entities, but have trouble
expressing the same relationship in mathematical formulation.
For students who have trouble generalizing, so that they do not necessarily abstract away the particular domain, the idea of moving from one example, to the idea of member of a domain, to the idea of different member of the same domain can be an initial challenge. Some students have articulated that this is the maximum level of difficulty of homework that they expect. Changing domains, as from natural numbers devoid of context, to, for example, depth of a stack (which is of course a natural number), as occurs in Sipser\cite{sipser2012introduction} in a proof about the language of pushdown automata and context free grammars, has caused some students difficulty.

The amount of generalization needed to appreciate that the recursive programming technique, which solves problems of a larger size in terms of problems of the same form of smaller size, is similar to proof by mathematical induction, in which the truth value of a statement indexed by a larger natural number is implied by the truth value of a statement of the same form indexed by a smaller natural number does not occur spontaneously in some students. This amount of generalization has occurred during interviews with some students.

Czeisler\cite{czeisler} reports how students improve on performance over several days, when a good night's sleep occurs in between each day.
Stickgold and Walker\cite{stickgold2013sleep, hasselmo1999neuromodulation} report that rapid eye movement (REM) sleep, which occurs in the latter part of a good night's sleep, is used for the generalization process.
When one considers that some students start their homework just before it is due, and frequently do not provide themselves with a good night's sleep, it is not very surprising that generalization would be difficult.
%It might also be worthy of note that the type of long-term memory that is formed in a condition of fear is of a different nature than one formed without fear\cite{richter2015emotional}, and that long term memories formed in fear contain much irrelevant detail. %It might be that fear impacts the ability to generalize.

Students who choose to discount the importance of definitions and instead engage to learn from examples might depend upon their ability to generalize on their own, which in turn, might not help them sufficiently.

Attempts to explicitly support generalization, by rendering concepts found in a chapter as UML\textsuperscript{\textregistered} class symbols, and arranging these symbols in an inheritance hierarchy were not appreciated by some students. Some (better) students have asked why we spend time teaching them with UML\textsuperscript{\textregistered} diagrams. It would appear that conscious, as well as unconscious, generalization, is not easily used by some students.

Without generalization, without the efficiency in representing concepts obtained by use of mathematical formulation, students can be hindered in their efforts. These efforts include creating transformations of formulation as is needed in proofs that involve un-choreographed logical steps.

One example of difficulty students might have in generalizing could be, that the specific occupants of places in a logical sentence cannot be generalized.
For example ``My father was born in Ecuador, of Ecuadorian parents, so I know that he cannot be elected president of the United States.''
One step in generalization would be: ``Person a was born in Ecuador, of Ecuadorian parents, so I know that he or she cannot be elected president of the United States.''
A student has reported that this step is believable, but requires concentration, because the idea `a' is not fixed. (Perhaps it is that bound variables are ok, but free variables are troublesome.)
Likewise, ``Person a was born outside of the US in country b, of parents neither of whom were US citizens, so I know that he or she cannot be elected president of the United States.'', requires further concentration. (Two free variables are more disturbing than one.) However, this topic is currently in the news, so it is understandable.
Sentences about things not in the news, having two free variables, are confusing.

Even when the construction is first offered with bindings to concrete entities, and a second construction is offered with free variables, the confusion persists:
First construction:\\
Time travel is not possible.\\
A deLorean (commercially available) car plus a Mr. Fusion can perform time travel.\\
Because we cannot have time travel, something in the construction deLorean\textsuperscript{\textregistered} and Mr. Fusion is bogus.\\
The deLorean\textsuperscript{\textregistered} is commercially available.\\
The Mr. Fusion must be unattainable.\\
The first construction is thought to be understood.

$A_{TM}$ is not possible.\\
A simple program construction and $E_{TM}$ gives $A_{TM}$.\\
The simple program construction is clearly ok.\\
$E_{TM}$ must be unattainable.\\
The second construction is found to be elusive.

\subsection{Generalization vs. Argumentation}

One interpretation might be that generalization is difficult. Another interpretation is that the sense making of the first instance is that, yes, the reader knows that Mr. Fusion is unattainable, but it is not the argument that has convinced the reader  of this.
It may be that the argument is not noticed. A student volunteered: ``Well, everybody already knows that one can't have a Mr. Fusion, because if we could, we wouldn't be driving with gas.'' 

The argument ``If we had Mr. Fusion, we would drive with it, and we don't drive with Mr. Fusion, so we don't have it.'' is by contradiction. It seems worthy of note that some students will volunteer reasoning by contradiction, without being aware they are using the form, and that these same students also have trouble learning the form. It is as if some students can argue without being conscious of constructing an argument. Maybe this is like pitching a ball well, without being conscious of how it is done.


\subsection{Interiorization vs. Internalization}

I expect to find a model similar to that of Harel and Sowder\cite{harel1998students}, but
modified because of the different emphases on material in computer science
compared to mathematics. First, students of computer science should be very
familiar with the idea of consciously constructing, examining and evaluating a
process, from their study of algorithms. Because of this, the category internalization
might be subsumed by the category interiorization.
From empirical data, we know that there are students of computer science
who think that proofs might be irrelevant to their career; it would be hard to
imagine a mathematics student who thought so. CS students who do not think
proof is part of their career might be relatively content with conceptualizations
corresponding to outside sources of conviction. We found computer science
students whose conception of proof includes that a single example is sufficient
for proving a universally quantified statement. We found computer science
students whose conception of proof is that definitions are barely interesting,
and who find demonstrations based on definitions unconvincing. Because our
findings were not quantitative, we could not compare the population of categories.
Nevertheless, the relationships between categories, and the resulting
critical factors, might be different, especially in the area of Harel and Sowder's\cite{harel1998students}
internalization and interiorization.
Because the scope is broader, involving proof for deciding whether or not an
algorithm is suitable for a problem, I expect we will find more categories,
related to algorithms and their applicability.
The product of a phenomenographical investigation is categories of conceptualization
and critical aspects that distinguish one category from the previous.
One hopes that by identifying critical aspects, suggestions about what to emphasize
when teaching, and what to seek in assessments are also clarified. This
investigation is intended to develop insight into students understandings of
proofs, that are the meanings they have fashioned for themselves, based on how
they have interpreted what they have heard or read. 

\subsection{Representation}
\subsection{Structure}
\subsection{Steps, Leaps and Direction}

\section{Report: Navigating Through Space of Conceptualization of Proof}\label{thickNrich}

In  the Methodology section \ref{conjectures}, the process used to generate this report was described. In summary:
\begin{itemize}
\item A `What if?' question, the main part of which is a conjecture, is evoked when the researcher is examining the data.
\item A conjecture is used to imagine a perspective.
\item A perspective is used to predict student productions (e.g., utterances, responses to assignments).
\item The predictions are used to estimate the degree of confidence with which we might hold the conjecture.
\item With those conjectures about which we have sufficient confidence, the report is constructed.
\end{itemize}

The report is used for member checking, one activity related to validity.
A good report furnishes a thick and rich description of the sending context, so that the reader may judge whether the material can usefully be transferred to the reader's context.

\subsection{Context}
We describe the context, and then describe our students' conceptualizations.

At a large university in the northeastern United States, in the computer science and engineering department, there are approximately (how many??) undergraduate students. There are over one hundred graduate students. The undergraduates are mostly domestic (check it) and the graduate students are mostly international (check it). Among the undergraduates, women are quite noticeably in the minority. The computer laboratories are open, staffed with monitors, until midnight during the semester, and is generally lightly occupied at night, but rarely crowded. Around the times exams or projects are due, the population in the lab increases.
The students have many clubs and activities, and can be seen using the building's public spaces for extracurricular as well as curricular activities in the evenings.
Most of the students live on campus, rather than commuting, and the campus, even after midnight, will have many students walking about, though not nearly as many as in the daytime.
Some computer science students form friendships that assist in the formation of teams for group projects.
The number of students who are overseen by the Center for Students with Disabilities, for having being located on autism spectrum, seems to be increasing.
The economic welfare of the students seems generally to be adequate or better,
though the rate of loan accumulation is a source of concern among most students.
Many students attempt to study without purchasing or even renting textbooks.
While apparently, generally not deprived of food, shelter or clothing, it can often be the case that students deprive themselves of sleep.
The number of all-nighters per week is a statistic that is commonly esteemed.
Most students seem enthusiastic about their studies.
Shared passions for the material accompanies gentle competition.
Students help each other prepare for interviews.
Students ask others, who are seen to excel in class, for help, and help is generally given.
The level of friendly mutual support is similar to that in the mathematics department, and noticeably higher in computer science and mathematics than in physiology and neurobiology, for example.
The faculty are friendly and accessible, maintaining open office doors most of the day.
Some students have been seen to help each other more than university policy permits.
Students often share information, such as their grades, with each other.

\subsection{Conjectures and Conceptualizations}

There is a conceptualization, related to learning proof, that argumentation is not key to proof (see section \ref{combined}).

\subsubsection{What if students are trying to learn ``what'', but not asking ``why''?}
\begin{itemize}
\item They would not be thinking in terms of arguments addressing ``why''.
\item They would be non-plussed about arguments for things they ``know''.
item They would not be on the lookout for arguments about ``why'', and might have trouble seeing them.
\end{itemize}

There is a conceptualization, related to learning proof, that a sequence of statements does not require justification (see section \ref{combined}).

\subsubsection{What if students had a foundation in process/algorithms and did not have much experience thinking about justifications for specific reasoning steps?}
\begin{itemize}
\item They might favor proofs that look like process steps and feel wary about ``logic proofs''.
\item They might attempt proofs that have some but not all of the process steps from correct proofs. 
\item They might fail to understand when these process steps are application vs. when they are not.
\end{itemize}

There is a conceptualization that ``a proof'' can be constructed without benefit of careful definitions (see section \ref{combined}).

\subsubsection{What if students were not sufficiently patient with themselves to notice careful distinctions?}
 (e.g., $\exists n  \in \mathcal{N}: \forall m \in \mathcal{N} n \leq m.$)
\begin{itemize}
\item They might not notice the role of ``no bigger than'' in the phrase there exists a natural number that is no bigger than any other natural number. Instead they might seize on bigger than, and respond that 
there is no largest natural number.
\end{itemize}

There is a conceptualization that precise definitions are not important, or that they can be inferred by the student from examples, and need not be checked.

\subsubsection{What if students do not listen with equal attentiveness to all that is said?} (By
their own testimony about not paying attention to definitions and engaging only when examples are given.)
\begin{itemize}
\item  It might be that they also do not pay attention equally to all parts of a written sentence.
\item Attending insufficiently to definitions combined with not placing enough importance upon
warrants for next statements in proofs would generate difficulties in the composition of proofs.
\end{itemize}

There is a conceptualization that proof assignments should not be difficult.

\subsubsection{What if students didn't realize that the work they see is a polished product?}
(What if they didn't know others make many changes on the way to the end?)

\begin{itemize}
\item Students are able to comprehend programs written by others, and
students notice that in the composition of their own programs,
editing may occur.
\item Early in their programming efforts,
they might worry whether their difficulties signal a poor career choice.
\end{itemize}

There is a conceptualization that the sequence of statements in a proof can be constructed successfully without reasoning, by following a pattern.

\subsubsection{What if students hoped that process-step proofs would be sufficient?}
\begin{itemize}
\item Students might not realize that proving also can involve
choices among possible transformation steps, and that
false starts and subsequent attempts are normal in the community.
\end{itemize}

There is a conceptualization that clarity, such as can be achieved with mathematical formulation, is not always necessary, even in proof.

\subsubsection{What if students were not finding a clarity benefit to mathematical formulation?}
\begin{itemize}
\item Chicken and egg / boot strapping synergy between clear thought and
mathematical formulation.
Attention to positioning students onto this self-reinforcing thought pattern.
brackets,
right associative
practice
structure
\end{itemize}

There is a conceptualization that extracting the structure during comprehension, or developing a structure, during synthesis, is not necessarily beneficial.

\subsubsection{What if students did not notice structure in proofs?}
(By students' own testimony, some are not noticing structure in proofs.)

\begin{itemize}
\item Though students notice structure in code, and it
seems to make sense they would notice structure in proofs,
some do not.
\end{itemize}

The conceptualization that generalization from a representation, and re-expression of an idea so generalized in another representation is a useful exercise seems to be absent.

\subsubsection{What if students did not easily generalize from one representation and specialize an idea into another representation?}
\begin{itemize}
\item
We have investigated, a little, students' and others' facility with switching
representations, and given that some very capable students find representation switching to 
be challenging, it is not that surprising that some students do not immediately
see structure in proofs even when they do see and employ structure in code.
\end{itemize}

There is a conceptualization that negation cannot really be sufficiently difficult to be worthy of much attention.

\subsubsection{What if students really did have trouble with negation?}
\begin{itemize}
\item
Some students have trouble with negation, even of statements with only a single quantifier.
We might ask, what if students are not thinking in terms of universals.
Students who find that working code is sufficient for the purposes addressed by proofs
could be thinking about proofs of existential statements.
Proving (not disproving) universal statements might not be of much interest
to these students. They are not involved in making proofs of safety.
\end{itemize}

\subsection{Report}

%Earliest:
When students first take up proof at university, there are some who are
not so sure what the main message is.
They might react to arguments about concrete entities that they would have known, with confidence, that conclusion without argument.
To some, it is not clear that it is the argument, to which they are trying to direct their attention.
Some students use argument forms ``It must be $x$, because if it were not $x$ some contradiction would occur.''
We can infer from their reactions to the teaching of proof, that
it is not the proof technique that claims their attention.
(``Do programmers have to know these prime number facts?'')
Students have a difficulty moving from the stage of an argument 
reasoning about
concrete entities,
to the stage of an argument reasoning about abstract entities.
It could be generalization from the concrete to the more abstract,
but it could also be, not paying attention or resisting paying attention, or not making the effort to pay attention, to the argument.

Even for students who are conscious that the subject is an argument, they are not so clear how
to make one, especially if it is not one of those for which
there are process steps (``Logic proofs'').
Some students are also not clear on why the product of the process steps
forms a convincing argument.

Moreover, not all students are clear that a proof shows
unequivocally, suggesting that the proof could be ``backed up by experimental data''.

Also, some students say they do not know what they would use a proof for.


If it were not unequivocal, then what benefit would it have over code?
Another insight contributing to this view is that students offer alternative activities to proof, that produce examples. When a statement to be shown is an existential statement, an example is fine.
For disproving a universal statement, a counterexample is fine.
For proving a universal statement, unless it is a generic particular, the example is not adequate.
This casts doubt over whether students are really understanding universal quantifiers.
There is other evidence that students have trouble with quantifiers, as some students do not succeed in negating statements with quantifiers.

Student have been disappointed that all the applications of proofs that they saw were about
things (theorems) that were already known (by someone) to be true.
Some students, at least early in their careers as students, think proofs are supposed to show some new fact, and
are disappointed to see that the product is (``only'') a different 
representation of an implied fact.
Students seem not to appreciate what benefit a new representation
can have.

Also, students do not necessarily see the connections between multiple
representations.
When data structures are taught with tree diagrams for binary search trees, some students do not know how to represent the same
idea in code.

Some students also do not see any connection between the tree diagram
and recursive definitions and proof by mathematical induction.

Some students do not see any benefit in spending time on UML\textsuperscript{\textregistered} diagrams,
either class hierarchy, components or sequence diagrams.

Some student learn how to manipulate mathematical formulation without
knowing how to apply mathematical formulation to problems they may
encounter (such as discovering whether a context supports the use
of an algorithm).

Maybe students are not noticing that proofs for universal statements
are possible, as well as proofs for existential statements (``Think code
is perfectly satisfactory for the purposes for which we have seen
proofs applied.'')

Some students are not aware that proof can be used to determine
whether a situation is suitable for the application of an algorithm
they have learned.
One consequence of this is that they make less use of
these algorithms they have learned than they otherwise might.

The students who were dual majors in math knew that proofs were 
arguments by logical deduction, that careful definitions enabled
the construction of arguments, and that the results of proof were
unequivocal.

One graduate student, whose undergraduate education was elsewhere,
how was not a mathematics major, used proofs in papers, because
it was required in that publishing venue.
She said she did not use proofs at any other time.
She developed algorithms without using proofs,
and in the process of publishing the algorithms,
furnished proofs, adjusting the algorithm if the proof seemed
as if it would be too long.




%\begin{itemize}
%\item Why is argument the appropriate means, when convincing is the end?
%\begin{itemize}
%\item democracy and ancient Greece, probably fostered argument and proof
%\item what about non-Western tradition? We know that Chinese history includes algorithmic descriptions that incorporate proof-explanations. This is a use, but not a necessity.\\
%We might need to make more discernable that we believe proof is mecessary in some situations, because even at high achieving students, may believe that proof is made unnecessary by using algorithsm, maybe $\exists$ vs. $\forall$.
%\begin{itemize}
%\item beginners not believing proof is necessary to establish confidence in conclusion of arguments that we give as examples. because they can have confidence in the conclusions, without the argument (``Duh, I knew that.'')
%\item having difficulty discerning that it is the argument, and not the ``grist for the mill'' that we are demonstrating (``Do programmers really need to know these prime number facts?'')
%\item having difficulty associating argument idea with proof ``Did we do any proofs today?''`` No.''
%\end{itemize}
%\item Once we know that argumentation is appropriate means, in some contexts, how do we argue? (Here we are addressing how to achieve valid arguments, and how to structure arguments.)
%\begin{itemize}
%\item Does it matter that the premise is true? Derivations do not need premise to be true. Thus proof by contradiction takes a premise we choose. That's why we can close the context after a contradiction is reached and carry on knowing that premise we used is now shown to be false.
%\item There are these several forms that we learn. Though they seem like processes with steps, it is important to know how these steps are warranted.
%\item Any warranted step can be taken.
%\item The form of the statement we are trying to transform into, and the froms available to us as starting points, both offer clues as to which transformation steps can be employed
%\end{itemize}
%\end{itemize}
%\end{itemize}

%\begin{itemize}
%\item Transfer\\
%Proofs as taught may look as if they are for number theory and/or graph theory, but in compilers/programming languages/OS/algorithms/theory we see that they get applied (at least by the instructors) to the subject matter
%\item Purpose\\
%Do students ever do proofs when they are not assigned? None of the undergraduate students we asked. Graduate student: Proofs applied in papers that present new algorithms, because there are claims made about the algorithm, of a universal nature, and such claims must be shown to be universally true.
%\item Exploration\\
%consequences of assumptions/definitions checking to see whether an algorithm that has been taught is applicable in a situation that presents itself. This is generalization, used in transfer from one example to another. This could be specialization, if general principle were known and instance were recognized.\\
%``Word problems'' are specialization. Students in earlier grades have trouble with these.\\
%Traversing levels of abstraction
%\end{itemize}

%\begin{itemize}
%\item making arguments
%\item making arguments showing one known thing from another known thing
%\item (ditto) that we can generalize, and subsequently specialize to things like other algorithms, other contexts
%\item (ditto) that we want to use when we want to support universal claims
%\item (ditto) wich we do find occasion to do, because we are building
%secure, safe
%\end{itemize}

%Do we ever show the student an application in which we need them to be sure about safety? reliability? timeliness? memory constraints? power constraints? any universal properties?



%\subsection{Alternate Dimensions of Variation}

%\subsection{Alternate Critical Factors}