ch4.tex

 \chapter{Phenomenographic Analysis}
 
 
 
 
 
 
 
 
 \subsection{Application of Phenomenographic Analysis in this Study}
 
 We applied phenomenographic analysis, 
 
 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
 
  \subsubsection{Phenomenographic Analysis of What Students Think Proofs Are}
  
  \begin{quote}
  Mathematics, as it is currently practiced, is a delicate interplay between monastic contemplation and blowing stuff up with dynamite. (Ellenberg)\cite[page 223]{ellenberg2014not}
  
  Probably I don't want to keep this, but it's fun at the moment.
  \end{quote}
  
  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 the 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. They were dual majors in math.
  
  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". 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".
  
  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.
  

  

  
  
  % % %comprehension
  
 \subsubsection{Phenomenographic Analysis of How Students Attempt to Understand Proofs}
 Some students are attempting to understand proofs while not recognizing that they are studying a proof.
 "Were we studying proofs today?" "No" "Were we discussing certain contexts, and why certain ideas will always be true in those contexts?" "Yes" "Doesn't that seem like proof, then?" "Yes"\\
 "So, you're taking introduction to the theory of computing this semester. Do you seen any use of proofs in that course?" "No"\\
 
 
 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. 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.
 
 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 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 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[that pin dropping probability problem]{ellenberg2014not}
 
 % % % structural relevance
 
 \subsubsection{Phenomenographic Analysis of Reasons for Teaching Proof}
 
 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.
 
 \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline
 
 \endfirsthead
 
 \multicolumn{2}{c}%
 {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\
 \hline \multicolumn{1}{|c|}{\textbf{Category}} &
 \multicolumn{1}{c|}{\textbf{Representative}}  \\ \hline 
 \endhead
 
 \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline
 \endfoot
 
 \hline \hline
 \endlastfoot
 
% \begin{tabular}{|p{7cm}|p{8.5cm}|}\hline
 Category & Representative\\\hline\hline
 
  
  some students do not see any point to proof&
 They teach it to us because they were mathematicians and they like it.\\
 
 
 & we didn't see ok why do i really have to know the proof of the theorem to do that right? We didn't see the point, because no one taught us the point, so, that's a very important part that was missing.\\\hline

  some students think that it satisfies the curriculum goals, to be able to reproduce a previously taught proof, or follow a procedure to generate a proof, without being personally convinced&
 I was able to get a full score, but I don't understand why a proof by induction is convincing\\\hline
 
 Some students do not see a relationship between a problem and approach&
 When I have to prove anything, I always start with proof by mathematic induction, that was the one they taught the most.\\\hline
 
  Some students are surprised to discover that there is a relation between proof by induction and recursion&
 I never noticed that before, but now that you mention it, I see that they are isomorphic.\\\hline
 
  Some students see the relationship but do not use it&
  Professor (redacted) would be really proud of me that I learned to understand proof by induction quite well. \ldots I understand how recursion matches induction, there's a base case, there's a way of proceeding. \ldots I just couldn't figure out how to program the merge-sort algorithm.\\\hline
 
  some students think the only reason for studying proof is to understand proofs of, for example, resource utilization of known algorithms&
  I would never consider writing a proof except on an assignment.\\
  
  & I understand the proof of the lower bound on comparison sort. \ldots I understand the proof of the upper bound on searching in a binary search tree. \ldots If I had to prove something about termination on a search tree, I don't know how I would do that.\\
  
 
 & I know that recursion has the same structure as proof by mathematical induction. \ldots If I had an algorithm with a recursive data structure like a tree, and I had to prove something like termination about it, I'm not sure what approach I would use, it would depend.\\\hline
 
 Some students see that they could employ proof to explore whether an algorithm can be expected to solve a problem in a given context that includes bounds upon resources that are available for consumption. & mostly design the algorithm first, we had some expectation of what that complexity results would be and then we try to find an approach to prove.
%\end{tabular}
 \end{longtable}
 
 

 
 
 % % %application
 
\subsubsection{Phenomenographic Analysis of How Students Attempt to Apply Proofs (When not assigned)}

Some students claimed they never constructed proofs when not assigned.


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

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.

% % %analysis

  \subsubsection{Phenomenographic Analysis of How familiar and/or comfortable are students with different (specific) proof techniques: induction, construction, contradiction?}
  
  When asked about specific proof techniques, some students mentioned proof by mathematical induction "When faced with a proof I start with induction, they taught us that one the most."
  
  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.
  

  \subsubsection{Phenomenographic Analysis of Whether students notice structural elements in proofs}
  
  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. "What's a lemma?"
  
  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. "What good does that do, doesn't the proof become longer?"
  
  Some students describe proofs as a sequence of statements, not commenting on any structure.
  
  \subsubsection{Phenomenographic Analysis of What do students think it takes to make an argument valid?}
  
  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.

% % %synthesis
   
\subsubsection{Phenomenographic Analysis of Whether students incorporate structural elements in proofs}

Students have asked whether, when using categorization into cases, they must apply the same proof technique in each of the cases.
 
 Probably needs additional interviews.
 


% %evaluation
 
  % \section{Interview}
       Some students remembered taking proofs in high school in geometry.
       Some students were taking proofs contemporaneously in philosophy.
       Some of the students studying proof in philosophy found them disturbing, expressing a preference for geometrical proofs.
       Some students remembered having to furnish proofs of geometrical facts, also facts about prime numbers and sets.
       Some students knew that CSE2500 treated proofs because they would be used in later courses. Students did not know why proofs would be used later, and were generally happy to hear some example uses.
       Though students were asked whether they made use of proofs spontaneously, none of those interviewed gave an example.
       Some students preferred to articulate with code, and some (who were dual computer science / math) sometimes preferred mathematical symbols, depending upon the context.
       Some students do wish to convince themselves of things, such as tractable execution times, and correctness. Though students were asked whether they made use of proofs for this purpose, none of those interviewed claimed to do so, rather they mentioned going carefully over their algorithm construction, and considering cases.
       
       In interviews, the students almost all chose to discuss proofs by mathematical induction.
       
       \subsubsection{Themes / Categories}
       \begin{itemize}
       \item Definitions\\
       Students divided into (1)those who found definitions boring, difficult to pay attention to, and undesirable compared to examples, from which they preferred to induce their own definitions, and (2) those who had caught on to the idea that definitions were the carefully crafted building blocks of reasoning.
       \item Procedures
       Students sometimes learned what was desired in a proof, but learned to produce it by procedure, and were not themselves convinced.
       \item Context
       Students asked whether the topics for examples and exercises, such as prime numbers, had relevance to programming, with which they had experience, but not unrelated to the topics.
       Students did not know the context in which the proofs, or procedure version of proof, was applicable, so, for example, did not apply proof by mathematic induction to recursive algorithms, and did not know how to tell whether recursive algorithms would be applicable.
       \item Concrete vs. Abstract
       Some students felt quite comfortable with the application of rules of inference to concrete items, but had difficulty transferring application of those rules to mathematical symbols.
       \item Symbolization
       consistent with Harel and Sowder's 1998 categorization of concepts, we found students who would attempt to write in symbols, but not understand what was denoted, and consequently were uncertain about appropriate operations. Some of these students were glad to see a progression from pseudocode with long variable names to pseudocode with short variable names to mathematical symbolization (formula translation (FORTRAN) in reverse).
       \item Applicability of single examples
       Some students believed that a few examples constituted a proof. These examples were not generic particular, nor were they transformational, in the sense of Harel and Sowder's 1998 model.
       \item Substructure
       Students familiar with methods, in the sense of object-oriented programming, and with construction of programs involving multiple method calls, did not always recognize that proofs could be built from multiple lemmas, although they did understand that axioms could be applied.
       \item Proofs are used, in computer science, to show resource consumption (complexity class), properties of models of computation, and computability/decidability. No occasion was identified, other than assignment, when undergraduate students recognized they were undertaking proofs. 
       \item Among graduate students, proofs were undertaken in the context of preparing manuscripts for publication. These were scheduled to be approached after algorithm design, though retroactive adjustment of algorithms did occur for simplifying the proof.
       
       \end{itemize}
       \subsubsection{Relationships}
       
       \subsection{Analysis of Homework and Tests}
       \subsubsection{Proofs}
       Proofs submitted on homework and tests were analyzed in several respects. 
       The overall approach should be valid. For example, students who undertook to prove that the converse was true did not use a valid approach.
       The individual statements should each be warranted. 
       Use of structure, such as lemmas, and care that cases form a partition of the relevant set are gladly noticed.
       Proof attempts that lose track of the goal, and proof attempts that assert with insufficient justification, the goal are noted.
       \subsubsection{Pumping Lemmas}
       We wrote descriptions for each error. Some example descriptions
       are in Table II.
       
        
       Table : Some example errors
       Let x be empty
       $|xy| \leq p, so xy = 0^p$\\
       $|xy| \leq p; let \; x = 0^{p+r}, y = 0^{p+r}, 0 < r < p$\\
       Let’s choose $|xy| = p$\\
       $0^{p+1}0^b1^p \neq 0^{p+1}1^p \therefore xy^2z \not\in \mathcal{L}$
       where $\mathcal{L} = \{0^i1^j, i \neq j\}$\\
       we choose $s = 0^{p+1}1^p$ within $|xy|$\\
       thus $\neq 0^p1^{p+1}$\\
       Let $x = 0^a, y = 0^b1^a$\\
       $x = 0^{p-h}, y = 0^h$\\
       $x = 0^i, y = 0^i, z = 0^i1^j$
       
       A handful of students did exhibit their reasoning that for
       all segmentations there would exist at least one value of $i$ that
       would generate a string outside the language.
       We categorized the errors as misunderstandings of one or
       more of:
       
  \cite[get some page reference]{sipser2012introduction} 
       1) ∣𝑥𝑦∣ ≤ 𝑝 permits ∣𝑥𝑦∣ < 𝑝\\
       2) 𝑥 is the part of the string prior to the cycle\\
       3) 𝑦 is the part of the string which returns the state of
       the automaton to a previously visited state\\
       4) 𝑧 is the part of the string after the (last) cycle up to
       acceptance\\
       5) 𝑝 − 1 characters is the maximum size of a string
       that need not contain a cycle, (strings of length 𝑝
       or greater must reuse a state)\\
       6) 𝑖 is the number of executions of 𝑦\\
       7) There must be no segmentation for which pumping
       is possible, if pumping cannot occur.\\
       8) A language is a set of strings.\\
       9) A language class is a set of languages.\\
       Categories are shown in the chapter on results (labelled table iii).\\