2
$\begingroup$

I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:

Problem 4. If a set, $A$, is finite, then $|A| < 2^{|A|} = |\cal P(A)|$, and so there is no surjection from set $A$ to its powerset. Show that this is still true if $A$ is infinite. Hint: Remember Russell's paradox and consider $\{x \in A \mid x \notin f(x)\}$ where $f$ is such a surjection.

My question is: am I expected to prove these math theorems and should I focus on my proving skills (because they are proving to be quite difficult for me at the moment)? Do they make me a better problem solver in later courses such as Data Structures and Algorithms?

$\endgroup$

closed as primarily opinion-based by Raphael Sep 27 '17 at 16:53

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ All your theory coursework will involve proofs. $\endgroup$ – Yuval Filmus Sep 26 '17 at 22:17
  • $\begingroup$ Computer scientists know their program is correct via proofs. Hobbyist coders guess their program is correct via trial-and-error. $\endgroup$ – Billiska Sep 26 '17 at 22:26
  • 1
    $\begingroup$ @Billiska And professional programmers almost never prove their programs correct. $\endgroup$ – Derek Elkins Sep 26 '17 at 22:44
  • 1
    $\begingroup$ @Xuan Proving when a loop ends is typically far harder than proving Russel's paradox. $\endgroup$ – Derek Elkins Sep 26 '17 at 22:48
  • 1
    $\begingroup$ All (good enough) computer science students should be able to prove such theorems; what these proofs involve is exactly proof techniques (and basic discrete math concepts essential for CS). If you don't have proof skills to tackle such problems, when you go into a theoretical CS textbook, e.g., Sipser, CLRS, TaPL, you'll get lost in the exercises very soon. $\endgroup$ – xuq01 Sep 27 '17 at 5:14
2
$\begingroup$

There are several different ways to answer your question.

First, in the particular course you are taking now, part of the material is mathematical proofs. In order to succeed in this course, you need to be able to prove mathematical theorems. There are several reasons for this requirement:

  • Some more advanced classes also involve proving theorems.
  • The concept of proof and mathematical validity is important even if you don't expect to actively prove theorems. You need to understand the difference between a heuristic algorithm and an algorithm which is guaranteed to always work efficiently.
  • Programming is an abstract pursue, and requires a certain way of thought. Mathematics is one way to develop this way of thought, since it forces you to think in abstract terms.

Second, while more advance proofs do involve a lot of problem solving, in this particular problem you are handed out the solution, and your task is to convert the hint into a formal proof (in the sense of your class). At this stage of your class, you are not required to be able to create completely new proofs. Rather, the emphasis is on you understanding what is a mathematical proof and how it is written. Later on you might be given more creative tasks.

Third, the course you're taking will also teach you basic mathematical concepts that might be useful for you in the future. For example, one of the topics you are taught is propositional logic. You could encounter propositional logic in database theory, verification, and elsewhere. The only way to understand such an abstract concept is to play with it, and the way we play with concepts in mathematics is by proving simple statements.

Fourth, you mention that proving theorems is hard for you at the moment. This is why you're taking this class. One goal of the course is to teach you how to prove theorems. You might find it hard, but if the course goes slowly enough, you will eventually find it easy, and will have gained an invaluable skill. In a similar vein, you might have encountered the jump in difficulty level from high school to undergraduate studies. It requires some adjustment, but eventually you will gain the relevant studying skills.

$\endgroup$
2
$\begingroup$

Writing computer programs that work is a theorem proving activity. Full stop.

$\endgroup$
  • $\begingroup$ I would say that's not a common point of view. It's like saying that writing computer programs is a creative artistic activity, so painting and art appreciation are important for computer science. I feel cheated now that I never took an art history class. $\endgroup$ – Yuval Filmus Sep 27 '17 at 10:10
  • $\begingroup$ While my point of view is similar due to Curry-Howard-Lambek correspondence, I think the way you phrased it leaves holes --- a statement maybe true despite there being no known proof. In the same way, a program may work without writer knowing why. $\endgroup$ – Billiska Sep 27 '17 at 10:26
  • $\begingroup$ @YuvalFilmus: you are forgetting one thing: the correctness of a program is an objective property. The theorem to be proven is "this programs fulfills its specification". For instance "this program computes the square root of all naturals less than 2^31", which is a mathematical fact. Nothing to do with "how elegant!" $\endgroup$ – Yves Daoust Sep 27 '17 at 10:47
  • $\begingroup$ @Billiska: this writer must be fired. You don't use programs that work by accident. (With one exception: you can use a program for the input values that are known to work, by testing, even if you don't know why. This is because the test proved it correct for the given input.) $\endgroup$ – Yves Daoust Sep 27 '17 at 10:52
  • $\begingroup$ @YvesDaoust In practice the first obstacle is getting a specification that is sufficiently precise to enable any kind of proof. There are very few pieces of nontrivial software that have such a specification. $\endgroup$ – adrianN Sep 27 '17 at 11:00
2
$\begingroup$

Computer Science as it's taught in universities has a large overlap with applied maths. If you want to succeed in your coursework you have to be able to prove mathematical theorems. A strong foundation in maths is required to do original research (or even understand existing results!) in many fields of computer science. Universities traditionally prepare their students for research.

This is very different from working as a software engineer, where mathematical skills are almost completely unnecessary. You can write great, useful software without understanding basic proof techniques. Almost all software is incredibly mundane when viewed from a science point of view. The hard part in software engineering usually is taming complexity and understanding user requirements.

$\endgroup$
  • $\begingroup$ Very much agree from first line. $\endgroup$ – Complexity Sep 27 '17 at 12:08
  • $\begingroup$ "You can write great, useful software without understanding basic proof techniques." -- I find that the mindset that has come with being trained in TCS helps a lot with understanding and creating complex systems. $\endgroup$ – Raphael Sep 27 '17 at 20:00
0
$\begingroup$

A (probably incomplete but too long for a comment) thought of a student:

I never understood the bad blood between students and the proofs. To me, they are the real essence behind the theorems: a theorem is just a claim, the proof is the reason why that claim is considered a theorem.

Every time I see a proof, I try to understand how the author thinks about that particular topic. Of course, sometimes often it can be hard, but the more time you spend on studying proofs the more you learn.

Long story short: the proofs are the difference between science and magic.


To answer your question: yes, you will see theorems (and their proofs) everywhere during your courses (mathematical sciences are built up theorem by theorem), and yes, they will teach you how to reason, and hence you will become a better problem solver.


Ironically, the major current challenge in computer science is really about proof: informally, it asks whether proving something is more difficult than checking the correctness of a proof. Since the answer is believed to be yes, this teach us an important thing: don't just check the proof step-by-step (which is easier) but really try to understand what is going on.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.