Skip to content
Permalink
master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

tpsApril11/ch4.tex

Go to file
 
 
Cannot retrieve contributors at this time
executable file 1245 lines (875 sloc) 91.8 KB
Raw Blame
Open in GitHub Desktop
\chapter{Phenomenographic Analysis}
%\section{Application of Phenomenographic Analysis in this Study}
We applied phenomenographic analysis to transcripts, field notes and documents. We addressed several research questions. The analyses are organized herein by the question addressed.
After each of the research questions' data are analyzed, then the data are combined and analyzed as a single collection.
The analysis for the research question ``What do students think proof is for?'', which was approached as ``Why do you think we teach proof?'' exemplifies a phenomenographic approach. One aspect of the phenomenon of proof is its utility. We selected student verbal productions related to the use of proof. We considered them in the context of their own interview, and we compared them to data from other interviews on the same theme.
The questions are ordered guided by the 1956 version of Bloom's Taxonomy, namely, recognition, comprehension, application, analysis, synthesis, evaluation.\cite{bloom1956taxonomy}
% % %recognition
\section{Phenomenographic Analysis of What Students Think Proof Is} \label{aWhatIs}
This section is organized into Categories, Illustrative Quotes for Categories, Relationships, Critical Factors, Dimension of Variation and Validation.
\subsection{Categories}
The categories developed in the traditional phenomenographic analysis are listed in Table \ref{proofR} and depicted in Figure \ref{fig:WhatProof}.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./CatsWhat}
\caption{Outcome space from What Proof Is}
\label{fig:WhatProof}
\end{figure}
We also used data from homework in Discrete Structures.
Here we categorized incorrect proof attempts.
These showed that students' conceptualizations included that mathematically formulated statements be written in a sequence. However, difficulties were encountered in formulating such statements, and in creating sequences that formed a logical argument.
We then organized these data according to completeness and depth of undertanding.
We used Carnap's description as a basis for comparison.
We formed categories for our data (see Table \ref{proofR}), and we inferred relationships between categories (see Table \ref{proofRrelation}).
\begin{table}
\caption{Categories for Student Conceptualizations of What Proof Is}
\label{proofR}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Make claims obviously correct & That arguments can convince is recognized \\\hline
Arguments in support of an idea or claim & That argumentation is, or can be, expressed, is recognized. \\\hline
Combinations of Standard Argument Forms & The existence and identity of patterns in this language are recognized. \\\hline
Composed of Mathematical Statements & Productions of this grammar are considered.\\\hline
Contain Certain Syntactic Elements & The existence of a specialized language and grammar for the discourse is recognized.\\\hline
Element of Domain of Mental Constructs & Abstract nature of discourse is recognized.\\\hline
\end{tabular}
\end{table}
\subsection{Illustrative Quotations for Categories}
% We asked students in interviews to tell what they thought proof was, and we analyzed the interview data.
% The data supporting the standard argument form idea were also seen as lecture notes from a previous class while substitute-teaching.
% Some representative units of meaning are given in Table \ref{dataWhat}.
Illustrative quotations for the categories are shown in Table \ref{dataWhat}.
\begin{table}
\caption{Illustrative Quotations for Student Conceptualizations of What Proof Is}
\label{dataWhat}
\begin{tabular}{|p{2.3cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Make claims obviously correct
& a logical method for determining whether something is true or not\\ \cline{2-2}
& like everything, uh, like everything that there is to prove, it already exists. So proof is just like a way to get there.\\\hline
\multirow{2}{2.3cm}{Arguments in support of an idea or claim}
&like my (debating) points need to be clear and concise and they need to be connected one to the next. it is very much related to proofs\\ \cline{2-2}
& Q: Were we studying proofs today? A: No. Q: Were we discussing certain contexts, and why certain ideas will always be true in those contexts? A: Yes. Q: Doesn't that seem like proof, then? A: Yes\\\hline
\multirow{3}{2.3cm}{Combinations of Standard Argument Forms}
& Logical deductions\\\cline{2-2}
& There are the ones that use process steps, and logic proofs, that use rules of inference.\\\cline{2-2}
& Q: what made it difficult? A: probably not sufficiently understanding how the logic worked i guess, for certain techniques of proofs\\\hline
\multirow{6}{2.3cm}{Composed of Mathematical Statements}
& set of statements that shows us whether the hypothesis is true\\\cline{2-2}
& My favorite one is proof by mathematic induction. It has a base case and an induction step.\\\cline{2-2}
& list of statements\\\cline{2-2}
& i get that a lot in straight programming, a lot of people have this mathematical explanations, and then in code it all of a sudden makes sense I think part of it has to do with the uh it has to do with the procedural nature of programming we're in state a, we move to state b, state c, state d and in the end we get an answer but equation is like an absolute constant total truth.\\\cline{2-2}
& i'm not too fond of induction, for whatever reason, i don't know why i think that one made the least sense when i was learning you could just say there's a base case i increment once and i guess abstracting from that, and it's true for everything it seems i don't know, it seems kind of weird, sometimes when you think about it\\\cline{2-2}
& I prefer to use code.\\\hline
\multirow{2}{2.3cm}{Contain Certain Syntactic Elements}
& Q: So, you're taking introduction to the theory of computing this semester. Do you seen any use of proofs in that course? A: No\\\cline{2-2}
& begins with Proof: and ends with QED or $\qed$\\\hline
Element of Domain of Mental Constructs
% & you can't expect it to be totally rigorous in decidability.\\
& I can understand it when it is about concrete entities like people I know, or models of cars, but when it is about variables, whether the names are long or short, I don't understand.\\
\hline
%
% ``These have been proved before.''\\\hline
% ``You prove it, it's done, finished.'' \\\hline
% ``Do programmers have to know these number facts?''\\\hline
\end{tabular}
\end{table}
\subsection{Relations}
The relations are shown in Table \ref{proofRrelation}.
Following the traditional phenomenographic method, we examine pairs of categories. We choose categories that appear to be adjacent in the space of features with which categories are distinguished from one another. This calls attention to features whose values differ. These differing values are candidates for critical aspects. We can consider whether a particular difference in feature value is important in distinguishing one category of conceptualization from another. The confidence with which we hold that difference in feature value to be important is the confidence with which we feel that difference is a critical aspect.
For example, there is a conceptualization found in the cohort of students that in a spoken proof attempt, will produce the phrase ``You know what I mean.'' The aspect of argumentation that certain forms, such as mathematical formulation, can be suitable for proof, and other forms, such as ``You know what I mean.'' are not suitable, seems very important. We propose that ``express ideas with logical statements, including mathematical formulation'' is a critical aspect differentiating the category ``Domain of Mental Constructs'' from ``Composed of Statements''.
We used the relations to estimate critical factors (see Table \ref{tab:critWhatIs}).
\begin{table}
\caption{Relationships for Student Conceptualizations of What Proof Is}
\label{proofRrelation}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relationship\\\hline\hline
Make Claims Obviously Correct & \\\hline
Arguments in Support of an Idea or Claim & Combinations of statements are transforming one expression into another.\\\hline
Arguments in Support of an Idea or Claim & \\\hline
Combinations of Standard Argument Forms & Combinations of statements are for legitimate reasons.\\\hline
Combinations of Standard Argument Forms & \\\hline
Composed of Mathematical Statements & Statements work together.\\\hline
Composed of Mathematical Statements & \\\hline
Contain Certain Syntactic Elements & Not all parts of the standard form are equally meaningful or useful for establishing proof.\\\hline
Contain Certain Syntactic Elements & \\\hline
Element of Domain of Mental Constructs & A mental construct can get expressed in an appropriate form.\\\hline
\end{tabular}
%\begin{tabular}{|p{4cm}|p{11cm}|}\hline
%Idea & Description\\\hline\hline
%Consequence of Definitions & Universal statements warranted by definition.\\\hline
%Relationship to Examples & Existential statements proved by example.
% \\\hline
% Relative Value vs. Experiment & we do not expect students to say that proofs wouldn't entirely replace experimentation, but would back up experiment. We prefer students would know that proof is sufficient on its own.\\\hline
%\end{tabular}
\end{table}
\subsection{Critical Factors}
Considering the categories ``Composed of Statements'' and ``Combination of Standard Argument Forms'', the aspect of relationships between statements, specifically that later statements must be justified by what has gone before, seems critical.
Hindering the understanding of warranting of statements is the low level of appreciation for definitions. Note the data showing that when asked what proof is, some students respond with examples rather than attempt a definition.
Considering the categories ``Combination of Standard Argument Forms'' and ``Argument in Support of an Idea or Claim'', the proposed critical aspect is that guidance about the development of the argument comes from the goal claim. There is evidence of students setting out to create an argument, but getting lost, such as forgetting that a scope has been set in which a statement is temporarily held to be false, and forgetting to exit that scope.
Considering the categories ``Argument in Support of Idea or Claim'' and ``Makes a Claim Obviously Correct'', we propose that the rendering obvious, of the claim, by the argument, is the most important distinguishing feature.
Critical aspects are listed in Table \ref{tab:critWhatIs}.
\begin{table}[ht]
\caption{Critical Factors for What Proof Is}
\label{tab:critWhatIs}
\begin{tabular}{|p{8cm}|}\hline
Critical Factor\\ \hline\hline
Express ideas with logical statements, including mathematical formulation.\\ \hline
Later statements must be justified by what has gone before.\\ \hline
A guiding principle in the development of the argument is to reach the state in which the desired claim has been made obviously true, or false.\\ \hline
One criterion for evaluating an argument is that it renders the claim obviously true or false.\\ \hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
Carnap writes eloquently on logical deduction:
\begin{quote}
The essential character of logical deduction, i.e. concluding from a sentence $\mathfrak{S}_i$ a sentence $\mathfrak{S}_j$ that is L-implied by it, consists in the fact that the content of $\mathfrak{S}_j$ is contained in the content of $\mathfrak{S}_i$ (because the range of $\mathfrak{S}_i$ is contained in that of $\mathfrak{S}_j$). We see thereby that logical deduction can never provide us with new knowledge about the world. In every deduction the range either enlarges or remains the same, which is to say the content either diminishes or remains the case \textit{Content can never be increased by a purely logical procedure.}
To gain factual knowledge, therefore, a non-logical procedure is always necessary. \ldots Though logic cannot lead us to anything new in the logical sense, it may well lead to something new in the psychological sense. Because of limitations on man's psychological abilities, the discovery of a sentence that is L-true or of a relation of L-implication is often an important cognition.
But this cognition is not a factual one, and is not an insight into the state of the world; rather it is a clarification of logical relations subsisting between concepts., i.e. a clarification of relations between meanings. Suppose someone knows $\mathfrak{S}_i$ to begin with; and suppose that thereafter, by a laborious logical procedure, he finds that $\mathfrak{S}_j$ is L-implied by $\mathfrak{S}_i$. Our subject may now regard $\mathfrak{S}_j$ as known, but he may not count it as logically new: for the content of $\mathfrak{S}_j$, even though initially concealed, was from the beginning part of the content of $\mathfrak{S}_i$. Thus logical procedure, by disclosing $\mathfrak{S}_j$ and making it known, enables practical activities to be based on $\mathfrak{S}_j$. Again, two L-equivalent sentences have the same range and hence the same content; consequently they are different formulations of this common logical content. However, the psychological content (the totality of associations) of one of these sentences may be entirely different from that of the other. Carnap, \cite[p. 21-22]{carnap1958introduction}
\end{quote}
We take this understanding of proof as complete, for the purpose of comparison with student conceptualizations, which we expect, from Marton\cite{marton1997learning}, to be partial rather than complete, and superficial, rather than deeply appreciative of the relations among the parts.
Some students exhibit an understanding of proof at the ``black box'' level, i.e., there is understanding of the role of proof, without considering any internal structure. When a proof exists, we can know that the thing the proof proves is true, in the context that applies. We can ``use that theorem''. Other students, though, do not have this idea consolidated yet. For example, if we consider proof by exhaustion applied to a finite set of cardinality one, we can associate to it, the idea of a test. Students, assigned to test an algorithm for approximating the sine function, knew to invoke their implementation with the value to be tested, but did not check their result, either against the range of the sine function, or by comparison with the provided sine implementation, presenting values over 480 million.
Moving to the ``white box'' level, we find a spectrum of variation in student understanding.
The most opaque end of this spectrum has been called ``magic incantation''. In this conceptualization we find those ideas of statements that are not clear, and use of mathematical symbols that is not understood.
Ellenberg\cite[page 409]{ellenberg2014not} reports that some mathematicians regard axioms as strings of symbols without meaning, and that this quite formal conceptualization can be contrasted with another conceptualization that axioms are true statements about logical facts. He talks of these conceptualizations being taken by the same individual at different times.
Our participants seemed to regard axioms as strings of symbols that do mean something, though that meaning the participant ascribed might not be correct (especially as participants did not always know definitions of the entities being related), or the participant might feel unable to ascribe any meaning. We did find participants who appreciated the significance of definitions. Those we found were dual majors in math.
The source of such sequences served as a dimension of variation among the concepts we found in our students. Some students stressed the role of a procedure in synthesizing proofs. Proof by mathematic induction was considered preferable; a synthesis by procedure property was assigned to it. By contrast, proofs involving sequences of statements warranted by rules of inference, but otherwise unconstrained as to form, were considered less desirable.
Some students do not see the sequence of statements as carrying out a transformation process on a representation.
Another waystation on this dimension of variation is ``sequence of statements''. A more elaborate idea is ``sequence of statements where each next statement is justified by what when before''.
Absence of attention to warrants has been reported by Alcock and Weber \cite{alcock2005proof}. Some of our students have noted this difficulty .
Another example of not finding the ``connective tissue'' between statements in a proof, and not noticing how a pair of statements warrants a conclusion, and not being convinced by the sequence of statements.
By contrast, some students clearly appreciate warrants.
Some students recognized patterns in sequences of statements. Contrapositive, contradiction, categorization into cases, proof by mathematic induction have been seen as patterns, consisting of steps that can be followed. These are contrasted with what were called ``logic proofs''.
It could be difficult to distinguish between a correct succession of logical steps from the premise(s) to the desired consequence(s) that ``reaches a psychologically useful revised formulation'' from ``carries out a pattern''. Indeed, the objectives of the course teaching proof may be met, while the preparation for the course using proof to explain the nature of, say, complexity classes, might not.
A yet more complete concept is ``finite sequence of statements, starting with the premise and ending with what we want to prove, and justified in each step.'' A more profound conceptualization was found ``finite sequence of statements, starting with axioms and premises, proceeding by logical deduction using (valid) rules of inference to what we wanted to prove, that shows us a consequence of the definitions with which we began, an exploration in which we discover the truth value of what we wanted to show, serving after its creation as an explanation of why the theorem is true''.
Some students have a concept of the exploration purpose of proof.
A few categories, such as those above, serve to identify a dimension of variation. When our purposes include discovering which points we may want to emphasize, we can examine the categories seeking to identify how they are related and how they differ.
It can certainly be that having more categories provides more critical aspects. For example, Harel and Sowder\cite{harel1998students} offered extrinsic vs. intrinsic conviction, empirical proof schemes and their most advanced deductive proof schemes as broader categories, and seven useful subcategories of these, yielding six critical aspects that suggest what teachers could usefully vary, to help learners discern items that would advance their knowledge.
\subsection{Validation}
In this study we applied triangulation in several ways.
We interviewed faculty teaching the courses involving proofs. We interviewed TAs assisting in the courses involving proofs. The students in these courses are from our same population. To get an idea of the background preparation of our students, we substitute taught geometry and algebra II classes in a high school. The high school population was quite similar to our university population, but differed by consisting almost entirely of domestic students, studying in their first language, and by having a larger percentage of women students, and of declared transgender students. Though the community served by this high school is diverse over socio-economic status, this component of diversity is probably greater in our university population.
Consistency with the work of other researchers is a check on the validity of an analysis.
In this study we compared our results with those achieved by some other researchers in computer science education and also by some researchers in the mathematics education community.
Checking possible interpretations is a technique that is thought to increase confidence in validity (see Chapter 6).
We prepared a list of questions that was addressed by several faculty and several students, that began an examination of the role of specific representation styles (mathematical notation, figures and pseudocode) for proof related problem statements.
We used member checking of the summary report to contribute to validity.
%The arrangement of the categories follows that of the table, and is shown in Figure \ref{fig:WhatProof}.
% % %comprehension
\newpage
\section{Phenomenographic Analysis of How Students Attempt to Understand Proofs} \label{aHowU}
\subsection{Categories}
The categories developed in the traditional phenomenographic analysis are shown in Table \ref{under}.
\begin{table}
\caption{Categories for Student Conceptualizations of How to Understand Proofs}
\label{under}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Look up the definitions and use them (Math major) & adopt (warranted) logical deduction based on definitions\\\hline
Use a diagram, visualization (different representation)& comprehend idea in a different representation\\\hline
Go over all the logical elements from Class, related axioms and theorems & infer from the examples, build on examples\\\hline
Apply the Proof Pattern from Class & seen mathematic induction most often, so try that\\\hline
Just Like the Examples from Class & superficial, pattern matching\\\hline
Emotional rather than intellectual response & \\\hline
\end{tabular}
\end{table}
The arrangement of the categories follows that of the table, and is shown in Figure \ref{fig:HowApproach}.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./CatsHow}
\caption{Outcome space from How Students Approach Comprehending Proof}
\label{fig:HowApproach}
\end{figure}
The first category of approach to comprehending a proof is to check whether it is one they have already examined in class.
The next category is to check whether the proof follows a pattern that has been treated in class. The most important difference seems to be that generalization from an instance to a pattern occurs.
The next category after a pattern that has been discussed in class seems to be to engage the visual domain. It is not clear that students view the argument as a process by which one representation of a truth gets transformed into another representation, that renders the claim obvious. Thus, it is not clear what the students are attempting to visualize.
Ideas that would have been welcome but did not appear include transformation of statements, lemmas, the question `Does problem statement suggest anything over which we might induct?'.
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataHow}.
It could be that some students are not attempting to understand proofs.
Students can experience anxiety about mathematical notation.
Some students are attempting to understand proofs while not recognizing that they are studying a proof.
Some students read proofs.
Some students look up the definitions of terms used in the proofs and some do not.
Some students think (or hope) they can solve problems involving producing proofs, without knowing the definitions of the terms used to pose the problem.
Some students are aware that definitions are given, but ``zone out'' until examples are given.
Some students think that the reading of proofs is normally conducted at the same speed as other reading, such as informal sources of information.
Of students who read proofs attentively, some try to determine what rule of inference was used in moving from one statement to the next, and some do not.
Some students experience transient understanding of proof techniques:
Some students notice that lemmas can be proved and then used as building blocks in a larger argument, and some do not.
Some students can identify the forms of proof learned in discrete systems, when they see them employed in proofs, such as the combination of arguing by contrapositive and modus ponens. Some cannot.
Some students can identify these forms in an argument if the argument is made about concrete objects, such as cars or specific people. Some of these students have difficulty transferring this ability with concrete objects to application to abstract entities such as sets, algorithms or symbols.
Some students who achieve with difficulty the ability to recognize the application of rules of inference in one argument about abstract entities, become quicker at recognizing arguments of similar form about other abstract entities, and some continue to achieve with difficulty, as if learning the first argument did not facilitate learning the second argument of the same form.
Students would attend to diagrammatic representation of proofs, such as a block digram depicting machine descriptions packaged as input for yet other machines to process, but were not observed to employ such diagrams.
Students have been seen to employ decision tree diagrams.
Students would attend to algorithm representation of proofs, such as a recursive process that determines a prime factorization, but were not observed to employ such algorithmic descriptions.
Students do not always attempt to understand proofs they are shown.
For those who do try, some students do not succeed.
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, such as ProofGeneral\cite{aspinall2000proof} that would help them tinker with or otherwise examine a proof.
It appears that, as students attempt to understand specific proofs, they try to find an example in which the symbols refer to concrete objects. In a proof about primes, some students will substitute specific primes to ``check the idea''.
Some students have had trouble transferring their understanding of proof patterns applied in one domain to proof patterns applied in a similar domain. In particular, some students who had studied proof by mathematic induction with natural numbers in one semester, when faced with understanding a proof by mathematic induction with natural numbers designating the level of a pushdown stack in a subsequent semester, claimed not to have understood proof by mathematic induction.
The yet more general idea of structural induction, implicit in tree data structures, might elude them in the data structures course.
These students did not detect the problem with the traditional ``all women are blue-eyed blondes'' argument.
Students answering a list of questions, representing computer science ideas mathematically, in algorithms and in figures found the questions ``interesting'', ``fun'', ``different'' and ``non-trivial''.
Except when assigned to do so, students were not observed to attempt to solve simpler problems, such as by imposing partitioning into cases. Except when assigned to do so, students were not observed to attempt to solve more general problems, as is sometimes helpful\cite {ellenberg2014not}.
When examples are given, the students attempt to infer definitions themselves. Some students will compare the definitions they infer with the mathematical community's definitions. Some students do not, continuing to use what they have constructed.
\begin{longtable} {|p{2.2cm}|p{11cm}|}
\caption{Illustrative Quotations for How Students Approach Comprehending Proof} \label{dataHow} \\
%\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
\hline \multicolumn{1}{|c|}{\textbf{Category}} & \multicolumn {1}{c|} {\textbf{Unit of Meaning}}
\endfirsthead
%Category & Unit of Meaning & \\\hline\hline
\multicolumn{2}{c}
{{\bfseries \tablename \thetable{} -- continued from previous page}}\\
\hline \multicolumn{1}{|c|}{\textbf{Category}} &
\multicolumn{1}{c|}{\textbf{Unit of Meaning}}\\ \hline
%\multicolumn{1}{c|}{\textbf{Other feasible triples}} \\ hline
\endhead
\hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline
\endfoot
\hline \hline
\endlastfoot
\hline
\multirow{2}{2.2cm}{ Look up the definitions and use them (Math major) }
& you have to understand all the things that are being accepted as true if the proof relies on them, then logically follow the proof; you have to accept all the rules that the writer of the proof has accepted\\ cline{2-2}
& i think the thing a lot of people hadn't really had to deal with before was just the level of abstraction that comes with proof writing, which is inherent with computer science, but a lot of time when we talked about problems it's always through analogies, i mean the traveling salesman problem is about cities and moving but that's not really what it's about, it's about graphs and paths \\\hline
\multirow{7}{2.2cm}{ Use a diagram, visualization (different representation) }
& a lot of it has to do with fluency, because we don't speak math \ldots we don't actually use the math language to accomplish anything, whereas the code actually accomplishes something \ldots the difference is that a proof is something you only use once. \ldots Recursion you can use, you can apply the principle to many different algorithms, but proof, it's absolute and true and you accept it and move on. \\\cline{2-2}
& visual proofs were just always easier even to this day, i find that things that i can visualize i tend to do a lot better with. So, you know i had very, very little trouble with graph algorithms, because graphs for me personally were very, very easy to visualize, but heaps for example don't have like heaps are not distinguished by their visual element, as a result i actually struggled with heaps a little bit when i was learning. Now I understand them, for me, being able to viuslaize precisely what happens and sort of replay it back in my head is the final level of understanding something, so once i can do that i can probably do the proof so the visual aspect made it a lot easier. I understand how visual proofs are not complete, \ldots a visual explanation only shows one particular situation you know whereas in proofs you have to go for all of them but you know sort of visualizing it has always made it easier at least for me\\\cline{2-2}
& Q:I wonder whether if proofs like mathematical formulations, could be rewritten as algorithms would the computer science students find them more readily understood.
A: absolutely \\\cline{2-2}
& that makes a little more sense than some of the assertions, the equalities, an algorithm you can trace through, you can write it out, things like that, it's very beneficial \\\cline{2-2}
& 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 \\ \cline{2-2}
& eventually definitely in CSE2500 I remember we could do the same thing, continuity, he would draw it out on the board saying well this is how it is and people would draw examples trying to disprove it, make it smaller or whatever, I think being able to visualize it is definitely a key for me and for other people as well, so I don't know how you could truly understand that ort of thing without, it's an abstraction, man this is really hard to say\\ \cline{2-2}
& in pseudocode or in a formula, i would like it's more of an algorithm, you can actually go through and run it in your head at least, uh, so you have a method for obtaining results, and it's i think i feel like in first it's more like you know the general um it's like an atmosphere of how the proof can go, i guess that's true, not really a good explanation, it's it seems it seems more general and out there and not a step by step hm process, more of a way to usually eliminate things that are wrong i guess\\\hline
\multirow{4}{2.2cm}{ Go over all the logical elements from Class, related axioms and theorems}
& you just have to go through a variety of proofs a variety of contexts \\
& \\\cline{2-2}
& 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 \\
& \\\hline
\multirow{2}{2.2cm}{Apply the Proof Pattern from Class}
& considering it's algorithms, it's usually a certain type of proof that youcan recognize so it's fine\\ \cline{2-2}
& aha moment have always been proofs written for induction, despite the fact that I've done them multiple times, they go over my head and I have to relearn proofs by induction. \\\hline
\multirow{3}{2.2cm}{Just Like the Examples from Class}
& leaving it at the formal definition is kind of aaahh, I kind of work backwards with those, like I get an example, then ok this relates to this step that's what this means. \\\cline{2-2}
& she'll read through the formal definition, half the class will kind of zone out, which is fine, everybody has to understand there's a formal definition but going over it personally I would use a lot of examples, i love examples \\\cline{2-2}
& after understanding a proof, I try a few examples to check the idea \\\hline
\multirow{4}{2.2cm}{Emotional rather than intellectual response}
& part of that is that there are kids in computer science who don't really want to be in CS, do the bare minimum or whatever, so i think that's part of the problem, not going to get kids who want to do proofs in cs, if they don't really want to do cs \\\cline{2-2}
& i will pay attention where most kids will zone out \\\cline{2-2}
& the second I see a summation, I'm like oh god this is some really long thing, or my professor's going to ask me to put in you know ask me to find the equation for this summation and it's just 'cause we did a I think it was calc2 um they had us do they gave us sequences and series and summations and they're like write the equation for this and they were awful, just and summations are just weird because you're writing out this really long thing, used them in uh, some of the stuff we used in like 2500 for one of them we had to write out the actual summation i don't know but when you look at that little squiggly (profanity)$*6$. \\\cline{2-2}
& 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\\\hline
%\end{tabular}
\end{longtable}
\subsection{Relations}
The relations are shown in Table \ref{HowRelations}.
\begin{table}
\caption{Relationships for Student Conceptualizations of How to Understand Proofs}
\label{HowRelations}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relation\\\hline\hline
Look up the definitions and use them (Math major) & Recognize that definitions warrant transformations.\\\hline
Use a diagram, visualization & \\\hline
Use a diagram, visualization & Seek for useful transformation.\\\hline
Go over all the logical elements from class, related axioms and theorems & \\\hline
Go over all the logical elements from class, related axioms and theorems & Consider varying a pattern with other elements from class.\\\hline
Apply the Proof Pattern from class & \\\hline
Apply the Proof Pattern from class & Move from passive to active.\\\hline
Just Like the Examples from class & \\\hline
\end{tabular}
% \begin{tabular}{|p{6cm}|}\hline
%Idea \\\hline\hline
% Category & Relationship\\\hline\hline
%Consider what might be deduced from the premises that might be closer to the desired outcome \\\hline
% Notice the premises \\\hline
%Notice the desired outcome \\\hline
%\end{tabular}
\end{table}
\subsection{Critical Factors}
The critical factors are shown in Table \ref{tab:critApproach}.
\begin{table}[ht]
\caption{Critical Factors for How Do Students Approach Comprehending Proof?}
\label{tab:critApproach}
\begin{tabular}{|p{8cm}|}\hline
Critical Factor\\ \hline\hline
Invoke definitions\\\hline
Attempt at visualization of transformation \\ \hline
Generalization from instance to pattern \\ \hline
\end{tabular}
\end{table}
% % % structural relevance
\subsection{Dimensions of Variation}
The dimension of variation found is that component parts of proof, such as process steps in a proof pattern, are used to anchor the effort at understanding. First, the instance is examined to check whether it is an example of a known pattern. Second modifications of known patterns are tried to see whether the instance can be so constructed. Failing to match such a pattern is followed by switching from categorization to investigation of behavior. Visualization of a transformation is attempted. Some relatively sophisticated students will avail themselves of definitions, to examine whether transformation steps appear warranted.
\subsection{Validation}
Consistency with existing literature is helpful here, as there are adjacent categories in Harel and Sowder's\cite{harel1998students} categorization, namely internalization and interiorization, that are useful in the pattern matching part, and another pair of adjacent categories in the same source, perceptual and transformational, that can be similar (depending upon what students are visualizing) for the attempts at visualization.
\newpage
\section{Phenomenographic Analysis of What Students Think Proof is For} \label{aWhat4}
\subsection{Categories}
%What is proof for? What subset of `what proof is for' gives us reason for teaching it?
The categories developed in the traditional phenomenographic analysis are shown in Table \ref{Reasons}.
Groups of categories are shown in Table \ref{aSCat4}.
\begin{table}
\caption{Categories for Student Conceptualizations of Reasons for Teaching Proof}
\label{Reasons}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Effective Communication of Mathematical Thoughts & \\\hline
Understand the consequences of definition & \\\hline
Derive mathematical formulation of intuitive ideas & \\\hline \hline
Derive algorithms for efficiency & \\\hline
Tailor an algorithm so that its properties can be proven & \\\hline \hline
Show that an algorithm meets requirements & \\\hline
Establish bounds on resource utilization & \\\hline
Understanding Algorithms and Their Properties & \\\hline
Ensuring we know why an algorithm works & \\\hline \hline
Demonstrate claims (conclusively) & appreciates proof of existential and possibly universal statements\\\hline
Distinguish the possible from the impossible & partial truth \\\hline
Obtain more knowledge & psychological vs. inherent\\ \hline \hline
Find out whether hypothesis is false & confusion about terms, claim vs. hypothesis or confusion about nature of deduction\\\hline
Increase confidence in experimental results & confusion about universal unequivocal nature of argument\\\hline
Do not know why & ``we do not accomplish anything''\\\hline
Nothing desirable & insufficient structural relevance\\\hline
Nothing of relevance & don't see the general nature of results for numbers, graphs\\\hline
\end{tabular}
\end{table}
The arrangement of the categories follows that of the table, and is shown in Figure \ref{fig:ForWhat}.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./ForWhat}
\caption{Initial Categories from What do students think a proof is for}
\label{fig:ForWhy1}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./CatsWhy}
\caption{Outcome space from What do students think a proof is for}
\label{fig:ForWhy2}
\end{figure}
\begin{table}
\caption{Grouped Categories for Student Conceptualizations of Reasons for Teaching Proof}
\label{aSCat4}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Grouped Category & Description\\\hline\hline
General and Deep Reasons & non-specific to computer science\\\hline
Guidance on Algorithm Design & Proof is for tailoring our algorithm creation.\\\hline
Algorithm Properties & Proof is for knowing our algorithm properties assuredly.\\\hline
General and Superficial Reasons & non-specific to computer science\\\hline
Incorrect Reasons & \\\hline
\end{tabular}
\end{table}
% Ideas that would have been welcome but did not appear:
Because there is an unusually large number of categories in response to this research question, the categories have been grouped.
The least sophisticated group of categories includes misunderstandings, not just incomplete, but containing misinformation. The critical aspect differentiating this group of categories from the next group is the idea that proof establishes, unequivocally, the truth value of the claim. The context of assumptions in which the claim is made is included in the understanding of the claim, in so far as that context has supplied warrants for the argument.
The next group of categories are true conceptualizations that are not very detailed, such as, a proof demonstrates that a claim is true.
%The group of categories beyond that
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataReasons}.
Students offered many reasons why proof is taught, and it seemed interesting to capture the variety. However, the large amount of data made it seem helpful to take two steps in grouping. We called the first step finding categories, but then we dealt with groupings of these categories.
The lowest level of conceptualization contains no reason why proofs are taught, because students propose such reasons as ``The professors were math majors, and feel we should know some math.''
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, although one was found who was required to use proof in publication, and consequently used proof to know when she was finished with her algorithms.
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.
\begin{table}
\caption{Illustrative Quotations for What Students Think Proof is For}
\label{dataReasons}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
\multirow{2}{2.2cm}{General and Deep Reasons}
& making sure you understand the principles \\\cline{2-2}
& seeing why things are the way they are, and showing indisputably that something is the case\\\hline
Guidance on Algorithm Design
& If the proof of part of the algorithm is too long or hard, I can change the algorithm to make the proof easier. \\\hline
\multirow{4}{2.2cm}{Algorithm Properties}
& you can prove that the algorithm's correct \\\cline{2-2}
& using proof to as a way to explain the algorithm and prove its validity\\\cline{2-2}
& now that we \ldots I have a better idea i think it's because when we're deciding how to make programs efficient, make them do what we want, proofs could help us figure out if we're going to reach the truth using thoe programs\\\cline{2-2}
& Q: Did you know if you want to prove a program that is a recursive program, you can prove it with a proof by mathematic induction? A: I never knew that.\\\cline{2-2}
& yes, of course, the first thing I thought of when I saw induction was recursion\\\hline
General and Superficial Reasons
& It is a required part of a paper for the conferences at which I try to publish. \\\hline
\multirow{3}{2.2cm}{Incorrect Reasons }
& if the hypothesis somehow incorrect a proof would be a great way to find that out\\\cline{2-2}
& proof would be a tool to prove that your hypothesis is correct, it wouldn't entirely replace experimenttaion, but it would certainly back up your experiment \\\cline{2-2}
& The professors were math majors, and feel we should know some math. \\\hline
\end{tabular}
\end{table}
\subsection{Relations}
The relations are shown in Table \ref{aSCat4R}.
\begin{table}
\caption{Relationships for Student Conceptualizations of Reasons for Teaching Proof}
\label{aSCat4R}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Grouped Category & Relation\\\hline\hline
General and Deep Reasons & No relation is proposed.\\\hline
Guidance on Algorithm Design & \\\hline
Guidance on Algorithm Design & As the algorithm confers the properties, the provability of the desired properties indicate whether the algorithm suffices.\\\hline
Algorithm Properties & \\\hline
Algorithm Properties & Mathematical statements can be made about algorithm properties.\\\hline
General and Superficial Reasons & \\\hline
General and Superficial Reasons & Demonstrating the truth value of claims.\\\hline
Incorrect Reasons & \\\hline
\end{tabular}
% \begin{tabular}{|p{12cm}|}\hline
%Idea \\\hline\hline
% Category & Relationship\\\hline\hline
%Reasoning carefully about algorithms \\\hline
%These reasons include being certain about algorithm properties \\\hline
%There are good and relevant reasons for teaching proof in the computer science curriculum \\\hline
%\end{tabular}
\end{table}
\subsection{Critical Factors}
The critical factors are shown in Table \ref{tab:forWhat}.
\begin{table}[ht]
\caption{Critical Factors for What do Students Think Proof is For?}
\label{tab:forWhat}
\begin{tabular}{|p{8cm}|}\hline
Critical Factor\\ \hline\hline
As the algorithm confers the properties, the provability of the desired properties indicate whether the algorithm suffices.\\\hline
Mathematical statements can be made about algorithm properties.\\\hline
Demonstrating the truth value of claims.\\\hline
% Discuss in detail occasions in which constructing proofs serves the creation of algorithms, such as pre-conditions, post-conditions, Gries-like construction \\\hline
%Sketch in more detail the domain of CSE in which students can expect to encounter proofs, also opportunities they might experience, to construct proofs \\ \hline
% Explain purpose of proof, including starting from given, including irrefutable, demonstrate the truth value of what is to be shown, with examples from CSE \\ \hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
Students' conceptualizations build on a superficial and general understanding of what proof is for, deepening in understanding as they study examples of proofs applied to algorithms. In particular, they see proofs applied to algorithms in the Algorithms class. Here properties of algorithms such as resource utilization are shown with proofs.
Students report not having to synthesize these proofs, rather, to understand them.
Later, in the Introduction to the Theory of Computing, proofs are seen by students to be used on abstract classes of algorithms.
Here students report more trouble understanding and applying proofs.
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{Validation}
Here validation is by internal consistency.
Excerpts of student transcripts were selected on the basis of being related to this question. A dimension of variation emerged from the data, such that the excerpts seemed readily organized along this dimension.
% % %application
\newpage
\section{Phenomenographic Analysis of How Students Attempt to Apply Proofs (When Assigned)}
\subsection{Categories}
The categories are shown in Table \ref{aCatAssign}.
\begin{table}
\caption{Categories for How Students Attempt to Apply Proofs (When Assigned)}
\label{aCatAssign}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Improve Efficiency & develop a sense of which transformations are helpful in the circumstances\\\hline
Attempt Transformations & consider different representations\\\hline
Adapt Known Proofs & start with class notes and modify\\\hline
Use Known Proofs & copy from class notes\\\hline
\end{tabular}
\end{table}
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataAssigned}.
This data comes from analysis of tests and interviews of students and teaching assistants.
Students claim to apply proof by mathematic induction without reference to the problem statement, citing reasons including ``They taught us that the most.'' and ``I know I can carry out that process, it sort of checks itself.''
Teaching assistants state that proofs from class notes are provided as answers even when they do not match the problem that is posed.
Students sometimes attempt to adapt a pattern, but in an incorrect fashion. For example, a proof by contrapositive is blended with the notion of proof by contradiction, and some property is assumed for the inverse of an implication, resulting in an attempt to derive a conclusion from a proof of an inverse.
Students who succeed in proving report that over time they improve their proof attempts, and sometimes find their older proofs amusing for their wandering nature.
\begin{table}
\caption{Illustrative Quotations for How Students Attempt to Apply Proofs (When Assigned)}
\label{dataAssigned}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Improve Efficiency
& \\\hline
Attempt Transformations
& \\\hline
Adapt Known Proofs
& a proof by contrapositive is blended with the notion of proof by contradiction, and some property is assumed for the inverse of an implication, resulting in an attempt to derive a conclusion from a proof of an inverse.\\\hline
\multirow{2}{2.2cm}{Use Known Proofs}
& They taught us that (induction) the most.\\ \cline{2-2}
& I know I can carry out that process, it sort of checks itself. \\ \hline
\end{tabular}
\end{table}
\subsection{Relations}
The relations are shown in Table \ref{aCatAssignR}.
\begin{table}
\caption{Relations for How Students Attempt to Apply Proofs (When Assigned)}
\label{aCatAssignR}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relation\\\hline\hline
Improve Efficiency & \\\hline
Improve Efficiency & View the transformations as a trajectory that can be more direct.\\\hline
Attempt Transformations & \\\hline
Attempt Transformations & Step away from patterns.\\\hline
Adapt Known Proofs & \\\hline
Adapt Known Proofs & Create a modification.\\\hline
Use Known Proofs & \\\hline
\end{tabular}
\end{table}
\subsection{Critical Factors}
The critical factors are shown in Table \ref{aCatAssigncrit}.
\begin{table}
\caption{Critical Factors for How Students Attempt to Apply Proofs (When Assigned)}
\label{aCatAssigncrit}
\begin{tabular}{|p{12cm}|}\hline
Critical Factor\\\hline\hline
View the transformations as a trajectory that can be more direct.\\\hline
Step away from patterns.\\\hline
Create a modification.\\\hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
The dimension of variation begins with the student reiterating what has been shown in class. Deepening understanding is shown by evidence of modification of what has been shown, as far as a variation on a pattern that has been shown. Further understanding of the logic of transformation is demonstrated by correct (warranted) application of rules of inference. The most advanced conceptualization found includes that students can judge their proof attempts as to length, and seek improvements with more efficient transformations.
\subsection{Validation}
This analysis is supported by commentary from multiple teaching assistants.
\section{Phenomenographic Analysis of How Students Attempt to Apply Proofs (When Not Assigned)}
\subsection{Categories}
There is only one category for student responses to this question. They do not attempt proofs when not assigned.
\subsection{Illustrative Quotations for Categories}
Some students claimed they never constructed proofs when not assigned.
Illustrative quotations for the categories are shown in Table \ref{dataNotAssigned}.
\begin{table}
\caption{Illustrative Quotations for How Students Attempt to Apply Proofs (When Not Assigned)}
\label{dataNotAssigned}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Don't seriously apply proofs outside of assignments
& Q: do you ever decide on your own that you want to do a proof?
A: no, I just tend I tend to just write code, it's always been proof enough for me\\\cline{2-2}
& Q: Do you ever find yourself doing proofs? associated with computer science? that haven't been assigned?
A: That have not been assigned?
Q: Right, for fun, or because you want to know something?
A: um, he-he, well, i did find myself doing proofs, they were silly proofs, just like things about like things stuff up, yeah since i didn't have very solve it base, it was just like statements, not really just proof, just where you want to get to, so like the end result that you want to get to \\\hline
\end{tabular}
\end{table}
\newpage
\section{Phenomenographic Analysis of Whether Students Exhibit Consequences of Inability With Proof (such as avoiding recursion)}
\subsection{Categories}
There is only one category from the traditional phenomenographic method: Students do not have confidence enough to know when they can apply recursion. They felt they were asked to produce recursive algorithms in situations in which it applied, and that they could. They felt that such situations did not occur subsequently. Some asked their employed friends who echoed this opinion.
\subsection{Illustrative Quotations for Categories}
Some students claimed to know how to write recursive algorithms but said they never used them because they did not know when they were applicable.
Students have asked whether, when using categorization into cases, they must apply the same proof technique in each of the cases.
about contexts, as for contradiction or special cases:
\begin{table}
\caption{Illustrative Quotations for Whether Students Exhibit Consequences of Inability With Proof (such as avoiding recursion)}
\label{dataConsequences}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Non-use of recursion
& and then you split, what do i have to do to get to that point, so you have to actually find what are the required pieces for you to solve the problem so and every single piece, then you have to prove by itself, so that can i get to the second step, can i get to the third step, because if i lose the first proof, i will never get to the second, because i already established that my second piece depends upon my first piece, so i cannot move forward so i have to divide into small pieces and try to prove them.\\ \hline
\multirow{2}{2.2cm}{ Lack of confidence}
& I still feel very shaky with proofs, sometimes, still getting the hang of it, it hasn't become second nature to me\\ \cline{2-2}
& it's like I kind of understand like I can see why this would take how long it is but I don't feel it very solid\\\hline
\end{tabular}
\end{table}
\subsection{Relations}
There are no relations, as there is only one category.
\subsection{Critical Factors}
There are no critical factors, as there is only one category.
\subsection{Dimensions of Variation}
There is no dimension of variation, as there is only one category.
\subsection{Validation}
Every participant agreed. Some students contributed commentary from relatives and friends at work, including an uncle working at Microsoft.
% % %analysis
\newpage
\section{Phenomenographic Analysis of Student Familiarity with Specific Proof Techniques }
\subsection{Categories}
The data present us with a basic category, ``Mathematical Induction vs. Everything Else''.
Disconcertingly, students refer to what is not mathematical induction as ``logic proofs''.
With but a single category, we cannot infer relationships or dimensions of variation.
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataFamiliarity}.
This data collected for this question was not diverse enough to be pursued with the traditional phenomenographic method. The data include:
\begin{table}
\caption{Illustrative Quotations for Student Familiarity with Specific Proof Techniques}
\label{dataFamiliarity}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Contradiction
& we're trying to prove that the opposite is incorrect\\ \hline
Contrapositive
& you just flip it around and then it's all better \\ \hline
\multirow{13}{2.2cm}{Mathematical induction vs. the rest}
& I'm not particularly fond of them \ldots there are different ways of strong and weak induction a whole procedure and try and so yeah there's a lot of details that go into it \\ \cline{2-2}
& i'm probably not going to go home and do mathematical induction practice for fun\\ \cline{2-2}
& when it's more of a weird problem I guess it's harder to be like oh i guess I can just induct here somehow \\ \cline{2-2}
& proofs that are not by mathematical induction are ``logic proofs'' \\\cline{2-2}
& i think like mathematical induction um uh because they verify themselves, like you use them to check your answer, and you know if you've arrived at the expected answer most likely did it right. I generally like to do any kind of proof that has either like a given like set of steps like mathematical induction has a set of steps where you have your eventual condition, you verify your um you verify and then you do the inductive step and then you can conclude\\ \cline{2-2}
& I'm a fan of like having like a set of steps to do something with, rather than so i know like what to do next\\ \cline{2-2}
& because i think the thing that draws people to coding is problem solving, the feeling of achievement when something works, i mean, and so why couldn't the same thing be a part of proofs, I guess, I can see it in that way \\ \cline{2-2}
& it's always good too because if you're even it's really reassuring when you're expecting to find something and then you find that and find out why in the process, so you have like you know what you're looking for so it's almost like working backwards, i know what i'm looking for and i know where i'm starting but if i can work both ways i can find the path pretty easily\\ \cline{2-2}
& when I start to create a proof, most commonly mathematical induction because this method of proof seems most straightforward to me, and most of these assignments we did mathematical induction, so that's what goes through my mind first.\\ \cline{2-2}
& the thing that that induction is there are steps to it, you prove for this case, you prove for that case, plus one, I can go through those steps and by going through the steps I'm sure it's correct, because it's the right steps but in my mind it's a little shaky \\ \cline{2-2}
& this feeling of well, I did it, but I'm not necessarily convinced; yes, that's precisely the feeling I've had\\ \cline{2-2}
& laws of logic proofs, they're a little more difficult it's almost like a puzzle, i'll sometimes work forwards and backwards at the same time, i'll start at the bottom and kind of modify that \ldots start thinking from both ends\\ \cline{2-2}
& even if it's almost like in straight programming, there's a few ways to choose from, you know how to solve a certain problem, if you can choose between like one or two or three you know different steps that's fine to but when it's kind of like solve this problem here's the formal definition go for it i'm like whoa\\ \hline
Other
&analyzing every possible manipulation \\\hline
\end{tabular}
\end{table}
When asked about specific proof techniques, some students mentioned proof by mathematical induction
Students claimed to prefer proofs by mathematical induction on the basis that they were formulaic; supposedly, a procedure could be used to synthesize them.
When asked for specific proof techniques other than proof by mathematical induction, students knew the words contradiction and contrapositive, but sometimes could not distinguish between them.
When asked about proof by construction, some students thought this referred to construction of any proof.
Some students thought proof by contradiction referred to proving the opposite of something, rather than disproving the opposite of something.
\subsection{Proposed Next Step}
The reasons given for the strong preference for proof by mathematic induction over other proof techniques include that they had a lot of practice with it, and it can be learned as a procedure.
Perhaps the preference for techniques having similarity to a procedure could be used to practice with scopes, as are used in proof by contradiction and proof by cases.
Perhaps familiarity with the logic of if-then-else constructs and switch-case constructs could be used to ease the learning of the logic underlying proof by contradiction.
\newpage
\section{Phenomenographic Analysis of How Students Use Structure in Proof} \label{aStruct}
\subsection{Categories}
The categories developed in the traditional phenomenographic analysis are shown in Table \ref{struct}.
\begin{table}
\caption{Categories for Student Conceptualizations of What Structural Elements are Found in Proofs}
\label{struct}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Components & Proofs can be built from components\\\hline
Puzzle & creating a proof has some commonality with solving a puzzle\\\hline
Pattern(s) & proofs can follow patterns, such as in contradiction \\\hline
Process Steps, State Transitions & proofs can be generated by following a process\\\hline
Like Programs & similarity to programs in that sequence of statements\\\hline
\end{tabular}
\end{table}
The arrangement of the categories follows that of the table, and is shown in Figure \ref{fig:WhatStructure}.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./CatsStructure}
\caption{Outcome space from What Structural Elements Students Find in Proof}
\label{fig:WhatStructure}
\end{figure}
Ideas that would have been welcome but did not appear include use of lemmas, use of cases, nested assumptions.
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataStructure}.
Some students, in the context of hearing a presentation in an algorithms course, of a proof with a lemma, do not know, by name, what a lemma is.
\begin{table}
\caption{Illustrative Quotations for How Students Use Structure in Proof}
\label{dataStructure}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
\multirow{5}{2.2cm}{Components}
& what i had to start doing with my physics problems was breaking them down into i have this chunk, i have this chunk, i have this chunk, i'm going to label and use this chunk, i'm going to label and use this chunk and then i'm going to see how they all fit together\\ \cline{2-2}
& once it's established that something is true or not, you can build other proofs based on the conclusions you made\\\cline{2-2}
& I think it's crucial to have structure to proofs, it makes tem easier to read, just like code\\ \cline{2-2}
& What's a lemma?\\\cline{2-2}
& very much the same logical sense, um, like with programming there's no ambiguity, everything is very structured, like proofs are structured in much the same way i enjoy programming more than regular proofs, particularly why, maybe because it's more fun to see results, when you program something. \\ \hline
Puzzle
& you have to be careful you do not jump to conclusions that are not logical, \\\hline
\multirow{2}{2.2cm}{Patterns}
& there are patterns you can use, a list of patterns, to identify if proofs are logical \\\cline{2-2}
& What good does that do, doesn't the proof become longer?\\\hline
Process Steps, State Transitions
& \\\hline
Like Programs
& sequence of statements \\\hline
\end{tabular}
\end{table}
Some students describe proofs as a sequence of statements, not commenting on any structure.
Some students, in the context of planning to construct a proof, do not choose to divide and conquer the problem, breaking it into component parts, such as cases.
Some students appreciate structure.
\subsection{Relations}
The relations are shown in Table \ref{structR}.
\begin{table}
\caption{Relationships for Student Conceptualizations of What Structural Elements Students Find in Proof}
\label{structR}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relation\\\hline\hline
Components & Puzzles can often be solved using components.\\\hline
Puzzle & \\\hline
Puzzle & Creative thought can extend and combine known patterns.\\\hline
Pattern(s) & \\\hline
Pattern(s) & It is helpful to know patterns of process steps, because the steps can be applied as a group.\\\hline
Process Steps, State Transitions & \\\hline
Process Steps, State Transitions & There are organizing principles for these sequences of statements.\\\hline
Like Programs & \\\hline
\end{tabular}
% \begin{tabular}{|p{6cm}|p{6cm}|}\hline
% Idea & Description\\\hline\hline
% Scoping Like Lexical Scoping & assumptions can be made within scopes\\\hline
% Good sentence structure &not all sequences of mathematical symbols are meaningful \\\hline
%\end{tabular}
\end{table}
\subsection{Critical Factors}
Critical aspects are listed in Table \ref{tab:critWhatStruct}.
\begin{table}[ht]
\caption{Critical Factors for What structure do students notice in proofs?}
\label{tab:critWhatStruct}
\begin{tabular}{|p{8cm}|}\hline
Critical Factor\\ \hline\hline
%The parts of proofs include statements, warrants, and lemmas. The idea of scope, as in proof by contradiction in which we make the temporary assumption that the consequence of an implication to be proved is false, is worth mentioning.\\ \hline
%Statements can be put in sequence. Some sequences are better than others. In particular, only sequences in which the later statements are justified by the former statements, or axioms or premises, are acceptable.\\ \hline
Building blocks used in a proof can be custom created for that particular proof.\\\hline
Patterns can be assembled using logical thinking; they are not a substitute for reasoning.\\\hline
Certain transformations have been captured in patterns, which continue to be logical deduction.\\\hline
Sequences of statements are performing a transformation of a mathematical expression, often to make the expression reveal a desired aspect.\\\hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
The most basic conceptualization students exhibit for structure is the individual line, similar to the line of code. The next more inclusive conceptualization recognizes groups of lines that show transitions or steps of transformation. The next more inclusive conceptualization captures that such groups of lines can form a pattern, as for reuse on multiple occasions. The next more inclusive conceptualization encompasses more freedom in the choice of sequences of lines. More significantly, the focus moves from preconsidered solutions to the problem. The most inclusive conceptualization admits the idea of solving the problem in component parts.
\subsection{Validation}
These data are internally consistent with how students construct a proof when assigned. They are also compatible with the material on recursion and proof by mathematic induction.
\newpage
\section{Phenomenographic Analysis of What Students Think Makes a Proof Valid} \label{aValid}
\subsection{Categories}
The categories developed in the traditional phenomenographic analysis are shown in Table \ref{valid}.
\begin{table}
\caption{Categories from What Students Think Makes a Proof Valid}
\label{valid}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
Stick to valid rules of inference & rules of inference tell us some valid transformation we can do\\\hline
Re-use proof patterns & can be apply patterns without understanding justification\\\hline
Know what's true and why & this is not about new arguments, is about memory\\\hline
\end{tabular}
\end{table}
The arrangement of the categories follows that of the table, and is shown in Figure \ref{fig:Valid}.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{./CatsValid}
\caption{Outcome space from What Students Think Makes a Proof Valid}
\label{fig:Valid}
\end{figure}
Ideas that would have been welcome but did not appear warrants based upon definitions, preconditions, postconditions.
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataValid}.
Some students are not sure how to construct an argument.
\begin{table}
\caption{Illustrative Quotations for What Students Think Makes a Proof Valid}
\label{dataValid}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Stick to valid rules of inference
& \\\hline
Reuse Proof Patterns
& when we hit 2100 and it was no longer like write this method, write this statement, you would then have to do this, do this, it was just a paragraph, write a stock trader that will handle this input and output this output, i panicked, i had no idea, i didn't even know, we learned how to code, but we didn't learn, we learned how to write code but we didn't learn how to code, the same we learned proofs, but we didn't learn how to write proofs, the only place we saw that was 2500 it helped close a gap for me that i, i'm still not perfect at it, it definitely helped to bring me along which was good\\\cline{2-2}
& that's where you'll find most of your problems understanding proofs, that's the first really the first class where you get it, where it's not just you know, this is the proof, take it on faith, that's what they tell you to do, but that's where you should really see why this works, let's see how this is proven, understand this as a whole, once you get it, that's where the gap is where everyone kind of loses it.\\\hline
Know what's true and why
&\\\hline
\end{tabular}
\end{table}
Some students do not understand that statements should be warranted. Without an appreciation of definitions, understanding warrants can be expected to be fraught with difficulty.
Some students do not recognize a good argument when they are looking at one.
Some students used confused/incorrect forms of rules of inference.
Some students do not notice that the imposition of a subdivision into cases creates more premises.
Some students do not notice that proof by contradiction introduces (for purposes of contradiction) a premise.
Instructors do tell students about valid forms of arguments. There are some students who can recite the names of valid forms, but cannot produce arguments using them.
Students do reiterate valid proofs from class. If the assigned example matches the proof from lecture sufficiently, false positive results for understanding can occur.
\subsection{Relations}
The relations are shown in Table \ref{validR}.
\begin{table}
\caption{Relationships from What Students Think Makes a Proof Valid}
\label{validR}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relationship\\\hline\hline
Stick to valid rules of inference & Even in the absence of a known pattern, one may apply rules of inference that match the present expression. Warrants are important.\\\hline
Re-use proof patterns & \\\hline
Re-use proof patterns & Besides using memory, one can match certain situations with applicable patterns, and explore whether transformation by that pattern would be helpful. \\\hline
Know what's true and why & \\\hline
%Idea & Description\\\hline\hline
%Take note of the difference between the idea in the hypothesis, and the consequence, and consider what warranted transformations might bring the representation of the hypothesis closer to that of the consequence & Categorizing the problem statement before choosing a solution is an advance over always choosing proof by mathematic induction.\\\hline
\end{tabular}
\end{table}
\subsection{Critical Factors}
Critical factors are listed in Table \ref{tab:critValid}.
\begin{table}[ht]
\caption{Critical Factors from What Students Think Makes a Proof Valid}
\label{tab:critValid}
\begin{tabular}{|p{12cm}|}\hline
Critical Factor\\ \hline\hline
Logical deduction is always relevant.\\\hline
Whether a transformation step is warranted, i.e., permitted by circumstances should be considered. Warrants can depend upon definitions.\\\hline
Patterns are sequences of logical deduction.\\\hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
The dimension of variation that most strongly suggests itself is appreciation of definitions as warrants for the logical transformation steps that are to be carried out. Students' conceptualizations show a low appreciation for definitions, including a reluctance to learn them.
Once students are aware of the power of a carefully crafted definition, which we do see in our subpopulation of students who are dual majors in mathematics, the enthusiasm for building collections of related concepts and reasoning about them appears.
Appreciation of definitions as precision tools, and appreciation for reasoning seem to be mutually reinforcing concepts.
More practice distinguishing valid arguments from invalid ones, and more practice writing arguments in valid forms might help.
Students need to pay attention to how the context of definitions and the item to be proved relate to the progression of statements that demonstrates what is to be shown. Practice explicitly providing warrants might help.
\subsection{Validation}
Alcock and Weber\cite{alcock2002definitions} in mathematics education observe the role of appreciation of definitions in warranting.
% % %synthesis
% %evaluation
\newpage
\section{Phenomenographic Analysis of Combined Data} \label{aCombine}
\subsection{Categories}
The categories are shown in Table \ref{combined}.
\begin{table}
\caption{Categories for Combined Data}
\label{combined}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Description\\\hline\hline
``Have the idea, need practice'' & This conceptualization recognizes that improvement should and probably can take place. This idea that practice might help is included.\\\hline
``Uncertain about justification'' & The conceptualization knows that reasoning is to be carried out. It does not contain a complete understanding of how any needed reasoning might be supported.\\\hline
``Maybe the needed argumentation can be provided without performing much reasoning'' & This conceptualization recognizes that reasoning is being used. It does not understand how to reason.\\\hline
``Maybe it isn't argumentation'' & This conceptualization does not notice that argumentation is the activity. It recognizes concrete conclusions by other means, and is lost when abstract entities are discussed.\\\hline
\end{tabular}
\end{table}
The most basic category, ``Maybe it isn't argumentation'', includes that examples are preferred over definitions.
This category also includes that code implementations serve as well as proofs (which might suggest that not all students are remembering some universal statements can be proved).
This category misses the point that argumentation, (which can be greatly facilitated by mathematical notation) can be based upon definitions. It misses that, with definitions, some universal statements can be shown to be true beyond any doubt. Some students' belief that proofs of theorems in Discrete Structures is about the theorems rather than being about the proofs could be evidence of this category. Some students' response of ``Duh'' to arguments about concrete entities could be explained by this conceptualization. The difficulties some students have generalizing from arguments about concrete entities to abstract entities could be explained by this conceptualization.
The next most basic category, ``Maybe the needed argumentation can be provided without performing much reasoning'', includes the applicaton of arguments realized as a sequence of process steps. While the first category misses argumentation save by use of example, the second category seeks to provide argumentation without engaging in much reasoning. Note that the behavior of choosing proof by mathematic induction as a solution because it was most frequently taught or is remembered best as opposed to because the nature of the problem seemed matched to it is evidence of this. Confusion between proof by contrapositive and an admixture of proof by contradiction and use of inverse of an implicaton are evidence of this category of conceptualization. The variety of incorrect reasons students propose, for why proof is taught in the computer science curriculum, is consistent with this conceptualization.
The next category ``Uncertain about justification'' includes the use of steps presumably seen in instructional materials, but in situations in which they are not justified, such as the assertion that all integers can be represented as $2k+1$, for $k$ an integer, because ``all integers are odd''. The absence of the idea, that the collection of mathematical definitions is a resource, has consequences. One consequence is that students with this conceptualization aren't necessarily able to draw on their knowledge of definitions, even to suggesting what they must know is false.
The next category ``Have the idea, need practice'' includes reasoning by application of warranted rules of inference. Students who reported spending hours trying out possible inferences, and developing a sense of which transformations represented progress give evidence for this category.
\subsection{Illustrative Quotations for Categories}
Illustrative quotations for the categories are shown in Table \ref{dataCombined}.
The data are the whole dataset collected for any of the research questions.
\begin{table}
\caption{Illustrative Quotations for Combined Data}
\label{dataCombined}
\begin{tabular}{|p{2.2cm}|p{11cm}|}\hline
Category & Unit of Meaning \\\hline\hline
Have the idea, need practice & \\\hline
Uncertain about justification & \\\hline
Maybe the needed argumentation can be provided without performing much reasoning &\\\hline
Maybe it isn't argumentation & \\\hline
\end{tabular}
\end{table}
In the data of three of the research questions the idea of patterns appears. The ideas of process steps and of visualization also feature prominently. Some students seem to be attempting to understand the structure and validity of proofs by using their knowledge of patterns, process steps and visualization.
The approach of building up process steps for proof construction differs from the axiom and definition based approach of Hilbert\cite{}, which we might hope our students would learn.
Particularly of value are the data that students discount definitions in favor of examples, that students find examples are easier, that students do not necessarily appreciate the value of definitions, and that students think they can adequately reconstruct the definitions from examples. Some students don't realize how time consuming that reconstruction would be.
\subsubsection{Maybe it isn't argumentation}
Student interview, student help session, test data and faculty interview combined on the subject of some students have trouble moving from reasoning about concrete entities to reasoning about abstract entities.
This difficulty was initially thought to stem from an inability to think with abstractions. Written logic was carefully populated with concrete entities and then abstract entities in a completely parallel construction (in the sense of English grammar). The reasoning was found to be clear in the case with concrete entities and obscure in the case with abstract entities. Even when abstractions were ``approached'' by contracting the names of the concrete entities, the sense of being convinced of the conclusion was lost immediately in the contraction. In this manner it was discovered no use was being made of the argument, rather an appeal to already established knowledge (``Maserati is expensive. Duh'') was being made, and the reasoning steps were being ignored. As soon as contraction invalidated the established knowledge, use of the reasoning steps was all that remained.
\subsubsection{Generalization}
The abovementioned test, in which parallel construction was used, to populate one argument in turn with first concrete entities and second abstract entities, received student thanks, as a helpful teaching intervention. Certainly the suspicion that it would be helpful drove the creation of the exercise. Student confirmation that the argument is somehow more readily appreciated with concrete elements, and can then be seen on its own, and applied to abstract entities.
\subsubsection{Generalization vs. Argumentation}
By these two data we see an example where multiple causes can manifest in the same outcomes of student confusion.
\subsubsection{Interiorization vs. Internalization}
Prior work by Harel and Sowder\cite{harel1998students} among students of mathematics revealed the distinction between interiorization and internalization. It seemed to make sense that students of computer science in comparison with students of mathematics, given the emphasis on programming and the meaning of processes, that students of computer science would advance to the more comprehensive conceptualization rapidly, leaving the less comprehensive unpopulated. This raised consciousness of the topic was brought to interviews, but resulted in the unexpected outcome that some students of computer science can learn to carry out a process without being able to speak articulately about what the process is and how it works.
\subsubsection{Representation}
This topic was brought to the forefront in an interview with a student. The original subject of the interview was proof techniques, and proof by mathematic induction was being discussed. Recursion was also being discussed. This student, who had performed well in courses in which these were taught, had never noticed any similarity between the two until during the interview. Because he commented upon this during the interview, the follow up question, ``Why not?'' occurred. The answer was that mathematic induction was taught in mathematical formulation and recursion was taught using diagrams. No thought connecting the two occurred because the representations were different.
This impermability of representation domains occasioned further thought about generalization. Why should thoughts learned in one representation remain trapped there, rather than being generalized, and possibly reexpressed in a different representation?
This question was pursued with the list of questions found in appendix \ref{qlist}. The questions were administered to several volunteers, both faculty and students. The results were that changing representations was challenging, and in some cases fun.
\subsubsection{Structure}
These data are mainly those mentioned in section \ref{aStruct}.
\subsubsection{Steps, Leaps and Direction}
This topic was discussed with students who are dual majors in computer science and mathematics. Such students found that a sense of direction for transformations in proof is acquired through practice. They reflected upon older proof attempts they had made, and newer, and found the earlier attempts rather laughable due to their circumnambulating nature.
\subsection{Relations}
The relations are shown in Table \ref{combinedR}.
\begin{table}
\caption{Relationships for Combined Data}
\label{combinedR}
\begin{tabular}{|p{6cm}|p{6cm}|}\hline
Category & Relationship\\\hline\hline
``Have the idea, need practice'' & The idea of what justifications are \\\hline
``Uncertain about justification'' & \\\hline
``Uncertain about justification'' & The recognition that reasoning should be exercised\\\hline
``Maybe the needed argumentation can be provided without performing much reasoning'' & \\\hline
``Maybe the needed argumentation can be provided without performing much reasoning'' & The idea that reasoning is the main activity\\\hline
``Maybe it isn't argumentation'' & \\\hline
\end{tabular}
\end{table}
\subsection{Critical Factors}
Critical factors are listed in Table \ref{tab:critComb}.
\begin{table}[ht]
\caption{Critical Factors from Combined Data}
\label{tab:critComb}
\begin{tabular}{|p{12cm}|}\hline
Critical Factor\\ \hline\hline
Justifications, warrants, though not always explicit, are at least implicit. \\\hline
Reasoning must be carried out in the construction of the proof; process steps applied without exercising the reasoning associated with them are unsatisfying.\\\hline
The principle activity is reasoning, logical deduction. Appealing to existing theorems might seem like invoking prior authority, but it is actually invoking the reasoning supporting them.\\\hline
\end{tabular}
\end{table}
\subsection{Dimensions of Variation}
There is a dimension of variation that extends from the idea that the student is being called upon to synthesize arguments, through the means of expression of mathematical ideas, through the often creative construction of a sequence of warranted transformations. The idea that a warrant can be the consequence of a definition, and that therefore definitions are critical for reasoning is developed in support of transformations. The idea that reasoning based on definitions can support the proof of universal and not just existential statements then informs those students who had hoped that finding examples would be a sufficient substitute.
\subsection{Validation}
That examples loom vastly more important in the minds of students than definitions has been observed by Lovato\cite{}.
%This work includes two methods of analysis of combined data, the first being influenced by the traditional phenomenographic approach, so, we take each research question in turn, we take text fragments relevant to the individual research question, we obtain categories, and arrange them and infer critical aspects. Then with the arrangements and critical aspects we look for insights spanning the multiple questions. In the second method, the text fragments are not segregated by research question. Categories emerge from the whole collection of text fragments, and relationships between categories are examined using axial coding, as found in Strauss's version of grounded theory \cite{walker2006grounded}.
This suggests that explicit use of patterns, process steps and visualization, comparing and contrasting these existing ideas with ideas from proof will help students learn the new ideas.
%Some relevant conjectures are:
%Use of examples implies hope that generalization will occur.
%Recognition that generalization is difficult.