Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: mathematics

Topic: Fantastic Proofs and How to Make Them

Jacob Zelko (Apr 01 2023 at 02:04):

Hi folks,

I am in the process of gearing up to go to graduate school for applied mathematics! Although my training in engineering and informatics assisted me to learn a lot about mathematical structures that we commonly use in various domain applications, one thing I have never rigorously studied until now are proofs. For example, here is an example problem that I am working on from Introduction to Graph Theory by Trudeau:

If $v$ is an integer greater than or equal to $2$, the path graph on $v$ vertices, denoted, "$P_{v}$", is the graph having vertex set $\{1,2,3,\dots,v\}$ and edge set $\{\{1,2\},\{2.3\},\{3,4\},\dots,\{v,v-1\}\}$. Draw the first five path graphs. Then, find and prove a formula for the number of edges of $P_{v}$.

So, how I attempted to do this was draw the first five path graphs. I quickly picked up on the formula being $e_{v} = v - 1$ where $e_{v}$ is the number of edges for a given number of vertices, $v$. Now, to go about proving this, I tried to make two conjectures (observations) being:

1) $e_{v} = v - 1$

2) $e_{v} = |V_{v - 1}|$ (where $V_{v}$ is the vertex set for a given number of vertices)

Then my idea for proving this formula was taking these two conjectures and setting them equal to each other: $|V_{v-1}| = v - 1$ and seeing that they are in fact equal for any $v$ that I choose to use.

But this doesn't seem quite right and as I am getting a lay for the land of proofs, I am struggling to find where to learn more about proofs in general and how to go about approaching them. I am picking up Algebra: Chapter 0 by Aluffi per several suggestions but I am not sure if that is where I would learn about proofs like this. Could I have some direction on thinking about proofs and how to go about learning more about them as someone who really has not ever written proofs before?

John Baez (Apr 01 2023 at 02:17):

Everything you guessed is true, so you should tell me what "doesn't seem quite right".

John Baez (Apr 01 2023 at 02:20):

Of course, correctly guessing things is quite different from proving things. Generally speaking you have to first guess what's true, and then prove it. But to prove something you need to know 1) what you are allowed to take for granted and 2) what rules of proof you are allowed to use. This depends on context.

For example, if I were writing a paper in a journal it would be fine for me to consider $e_v = v - 1$ as being so obvious that it doesn't require proof. Basically it's saying that if you have a thing like this:

$\bullet - \bullet - \bullet$

there's one fewer line segment than there are dots!

But since this is a textbook, you're probably not supposed to just say it's obvious.
I'd have to read the book to see what tools they're giving you. For example, maybe they want you to prove this by induction, or by defining a bijection.

In practice mathematicians get a sense of what kind of proof is expected in what kind of context by writing literally hundreds of proofs and getting feedback on them.

John Baez (Apr 01 2023 at 02:23):

So get started now, since by the time you hit grad school they will probably assume you know this stuff. Most "pure" undergrad math students I know take a course called "Introduction to Proof" followed by a bunch of courses where they prove stuff.

John Baez (Apr 01 2023 at 02:26):

If you type introduction to proofs into the all-knowing Google, you'll see a bunch of good material. Dive in!

For example you'll see a short MIT course called Introduction to Proofs with homework and answers to the homework.

John Baez (Apr 01 2023 at 02:33):

If you go to Amazon you'll see there are a lot of books that try to be an introduction to proofs. Grab a few of those too, and start proving stuff!

David Egolf (Apr 01 2023 at 02:33):

By the way, it can be quite nice to work from a book that provides solutions to its problems. That can be helpful for getting insights on proof patterns!

John Baez (Apr 01 2023 at 02:34):

Yes, you'll need lots of feedback.

Jacob Zelko (Apr 01 2023 at 02:35):

Hey @John Baez, bullseye in your comment, "Of course, correctly guessing things is quite different from proving things.," as to what I felt was off. In this case, my approach felt too ad hoc in me writing some scratch math, seeing a potential pattern arise, making some conjectures and then saying based on these two conjectures I made a proof. This doesn't feel like a proof and am at a point where, to paraphrase both Rumsfeld, "I don't know what I don't know."

Thanks for the pointers on getting started with any bespoke "Introduction to Proofs" course! I frankly didn't know what requisites there were to learning them and I'll just dive in!

John Baez (Apr 01 2023 at 02:35):

I think you should start by proving some things that are less obvious.

John Baez (Apr 01 2023 at 02:36):

It can be very hard to prove things that are as obvious as the thing you mentioned, because it forces you to understand more of the technicalities of what axioms you are allowed to start from, and what rules you're allowed to use.

John Baez (Apr 01 2023 at 02:37):

Like if I asked you to prove 2+3 = 5 you'd be completely stuck unless I said "use Peano arithmetic and define 2, 3 and 5 as follows..."

David Egolf (Apr 01 2023 at 02:39):

On the topic of proving simple things, I recently had a lot of fun proving some things using Lean. It's amazing how many little steps can be involved to prove something that looks very simple in excruciating detail. But - as far as I know - it is unusual to spell everything out so completely in practice.

John Baez (Apr 01 2023 at 02:39):

As you may know, Russell and Whitehead's Principia Mathematica is sort of infamous for proving 1+1 = 2 somewhere around page 300.

John Baez (Apr 01 2023 at 02:41):

The writing of this preface delayed the publication of the second volume of PM, as Whitehead and Russell struggled over the complications it raised. The difficulties arise from the typical ambiguity of terms and formulas of the theory of types. Every constant, such as those for the numbers 0,1,…,$\aleph_0$ will have a definition relative to each type. Without assuming the Axiom of Infinity for individuals, there is no guarantee that a given constant designates a non-empty class in a given type. The preface introduces the notion of “formal numbers”, which are to be interpreted as belonging to a type that makes them not identical with the ∅ for that type. Volume II begins with Part III, “Cardinal Arithmetic”. The notions of cardinal numbers are developed in full generality, extending to infinite cardinals. Consequently the theory of natural numbers, which are called “Inductive Cardinals” in PM, is introduced with a series of definitions of special cases of notions that are first introduced in a general form applying to any numbers or classes. For example, addition of natural numbers, as in the famous proof that 1+1=2 in ∗110·04 is proved for the special case of the addition of classes that applies to cardinal numbers....

John Baez (Apr 01 2023 at 02:42):

(∗110·04 is some sort of theorem number.)

John Baez (Apr 01 2023 at 02:42):

So anyway, a good introduction to proof will have you prove things that are less obvious, where it's easier to decide what counts as a good proof.

Jacob Zelko (Apr 01 2023 at 02:43):

I agree with you. The above example that I mentioned was in a way, "too easy" and rather obvious. In your experience, are there any proofs that would be good to build towards? Like not too obvious but what an undergrad in mathematics should come out of proofs being, ideally, ready to prove? Would the proof for why a null set is a subset of every set be one sufficient target? Obviously, it'll take much practice regardless but was curious if any came to mind quickly.

Jacob Zelko (Apr 01 2023 at 02:44):

John Baez said:

As you may know, Russell and Whitehead's Principia Mathematica is sort of infamous for proving 1+1 = 2 somewhere around page 300.

Haha, when you mentioned Peano arithmetic, this actually came to mind!

John Baez (Apr 01 2023 at 02:49):

Jacob Zelko said:

I agree with you. The above example that I mentioned was in a way, "too easy" and rather obvious. In your experience, are there any proofs that would be good to build towards? Like not too obvious but what an undergrad in mathematics should come out of proofs being, ideally, ready to prove? Would the proof for why a null set is a subset of every set be one sufficient target?

One version of that proof goes like this:

$X \subseteq Y$ is true if and only if $x \in X$ implies $x \in Y$. Suppose $X = \emptyset$. Then $x \in X$ is always false. A false statement implies anything, so in this case $x \in X$ implies $x \in Y$ for any set $Y$. Thus $\emptyset \subseteq Y$ for any set $Y$.

John Baez (Apr 01 2023 at 02:49):

So, I guess you should look at this crap I just wrote and think about whether you could rattle it off - and if not, why not.

John Baez (Apr 01 2023 at 02:51):

Like, maybe you need to learn the rules of classical logic, or the rules of set theory.

John Baez (Apr 01 2023 at 02:52):

But instead of thinking about some single proof that you should build toward, I think you should prove dozens and dozens of things of various kinds, and get lots of feedback.

It's sort of like playing guitar: to get good, you have to practice and practice a lot.

John Baez (Apr 01 2023 at 02:53):

And I forgot this: read tons of books with proofs in them, so you can see what proofs are supposed to look like in various different contexts.

Jacob Zelko (Apr 01 2023 at 03:00):

Ah! The good news here is that I can read that and understand what you wrote. I was actually more referring to that particular fact as an example if that is something still too naive or a good step in learning more about proofs. I actually did prove that to myself and got feedback in another forum on how to prove the "null set is a subset of every set statement" and went off and learned that the reason why "a false statement implies anything" works in this case is due to the logic idea of "vacuous truth." That was my one point of confusion at the time.

John Baez (Apr 01 2023 at 03:07):

To get good at proofs, one thing you need to do is learn about truth tables and learn a pile of tautologies that "and", "or", "not", "implies" and "iff" obey in classical logic.

John Baez (Apr 01 2023 at 03:08):

(Then later, all the intuitionistic logicians on this forum can tell you why all of that stuff is wrong. :upside_down: But you have to learn it anyway.)

John Baez (Apr 01 2023 at 03:14):

Another thing you need to learn is Venn diagrams and the rules governing set operations like intersection, union, complement.

Jacob Zelko (Apr 01 2023 at 03:17):

Absolutely, this has given me plenty to gnaw on at the moment -- thank you so much @John Baez and @David Egolf !

If you'll permit me, one final thought I had was to riff (couldn't resist the pun here) on the analogy of guitar practice, the reason why I was asking about any particular proofs is that I didn't start playing guitar just to play it but because I wanted to rock. For me, learning how to play Green Day, Johnny Cash, eventually joining a small indie pop type band and occasional lessons was great to build foundations. However, I really wanted to play more metal riffs like Escape the Fate or ambient progressions like from Sigur Rós. Because I had those foundations in place, I could go off and independently practice on my own more advanced songs and techniques as well as jam with or show my other musician friends what I was up to. Rooting it back to mathematics and proof, what I am missing here right now are those beginner "bands" or "songs" (i.e. proofs) every mathematician has at least heard of or encountered. But it seems like you're saying that this might just come with time and practice -- breaking the learning guitar analogy a bit.

(However, as I was typing this message, you just wrote up more info that gave me some very good guidance about such "songs" :guitar: )

Jacob Zelko (Apr 01 2023 at 03:17):

John Baez said:

(Then later, all the intuitionistic logicians on this forum can tell you why all of that stuff is wrong. :upside_down: But you have to learn it anyway.)

I am going to stick a pin in this and come back to this as I am very curious on that front!

David Egolf (Apr 01 2023 at 03:20):

I like the music analogy! To continue it a little bit... for me, I've found that playing a lot of different music (I play the piano!) in all kinds of different styles helps me gradually improve as a pianist. I start seeing patterns that I can employ in improvisation, and different kinds of pieces help me practice different kinds of techniques - even those that I haven't intentionally practised in isolation! I suspect a similar thing is true for learning how to prove things - trying lots of stuff and getting feedback on it can gradually help one discover all kinds of fun patterns.

Maybe I'm just repeating part of what you said in different words. It's a nice analogy I think!

John Baez (Apr 01 2023 at 04:30):

Rooting it back to mathematics and proof, what I am missing here right now are those beginner "bands" or "songs" (i.e. proofs) every mathematician has at least heard of or encountered.

If you grab an introduction to graph theory, or topology, or number theory, or abstract algebra, or real analysis, or complex analysis - an introduction that has proofs of the main theorems, like those listed on my page of books, you will see lots of proof that every good mathematician knows or can at least make up.

John Baez (Apr 01 2023 at 04:32):

So pick a subject or two and dive in. That Introduction to Graph Theory may be fine, but it looks like you started with a proof of a fact so elementary that it's hard to know what you're supposed to do!

John Baez (Apr 01 2023 at 04:32):

Hopefully this book has lots of proofs of theorems in it, so besides doing the homework problem you should read those and learn from that what proofs are like.

John Baez (Apr 01 2023 at 04:33):

But each discipline has a somewhat different style of proofs, and there are hundreds of proofs you should eventually know by heart, just like a piano player at a cocktail bar knows lots of songs.

John Baez (Apr 01 2023 at 04:34):

You learn them by heart not by memorizing them but by understanding the ideas and, somewhat separately, understanding how to write proofs.

Josselin Poiret (Apr 01 2023 at 10:36):

John Baez said:

To get good at proofs, one thing you need to do is learn about truth tables and learn a pile of tautologies that "and", "or", "not", "implies" and "iff" obey in classical logic.

I'm not sure truth tables help understanding most proof methodologies: if I tell you $A ⇒ B$ is equivalent to $\neg A \vee B$, and when it is true, how does that really help you? I think the intuitionistic viewpoint here is a tad more useful, it tells you that to prove $A ⇒ B$, you just have to prove that with $A$ as an assumption, you can prove $B$. To prove $A \vee B$, you just have to prove one or the other, to prove $\neg A$ you have to prove that assuming $A$, you get a contradiction, etc...

Fabrizio Genovese (Apr 01 2023 at 16:25):

In my opinion it can be useful to pick up techniques before practicing proofs. For instance, the path graph exercise can be proved by induction. As soon as I read it, I was like "ok, there is a 'for each $n$' statement, and it's easy to see that in going from $n$ to $n+1$ we add just one edge by definition". Now, the particular exercise is not important, what is important imho is building a toolkit of 'standard techniques' and getting a feeling of how and where you can apply them.

Fabrizio Genovese (Apr 01 2023 at 16:28):

The basic stuff (induction, ex absurdo, zorn's lemma, building bijections, ...) will get you very far. Clearly there are some techniques that are particularly useful in some subfields and useless elsewhere (for instance Zorn's lemma is used quite a lot if you work with sets). I'd say: read as much as you can, try to establish correspondences between proofs ("oh, this seems to be just a variation of this proof I saw here!"), and then try to apply these techniques you picked up to various exercises.
I'd start with induction, which is literally ubiquitous in mathematics.

Jacob Zelko (Apr 02 2023 at 20:28):

Hi folks! I am coming back after spending several hours reviewing syllabi (syllabuses?) from various universities across the globe on courses related to an Introduction to Proofs! I wanted to share some of my findings back here in case it is of use to anyone: in my opinion, the absolute best syllabus with a nice layout of things covered was the course *Introduction to Proofs* by Dr. Emily Riehl at John Hopkins University. It was laid out very clearly in a very approachable manner.

Otherwise, the best textbook I continued to see pop up again and again was How to Prove It by Velleman (this was also recommended by @John Baez too on his great webpage about books). I started reading the book and have found it very approachable so far (i.e. just working through the introduction at the moment) but it seems exactly suited for my level as it says in the introduction, "What is expected of you if you are asked to prove something? What distinguishes a correct proof from an incorrect one? This book is intended to help students learn the answers to these questions[.]"

Finally, I am not sure how much utility this will be, but I generally like to make a "lay of the land" document for myself when I approach a new area to learn things independently. This document synthesizes what I have found across various introduction to proofs courses from across the globe and lays it out in terms of what are the core concepts, what areas may be challenging, and what are the expected skills I should pick up along the way.

Hope this helps those who my be wondering similar things and a huge thank you here to folks pointing me in the right directions with things! Exclesior! :swords:

Mike Shulman (Apr 03 2023 at 04:20):

Also, +1 for Velleman. That's the book I always use to teach intro proofs. It's not perfect, but at least he presents the rules of proof as organized according to connective and quantifer, which I regard as essential. Also it has a fair number of good exercises.

David Michael Roberts (Apr 03 2023 at 08:49):

Another way to think about $X\subseteq Y$, at least classically, is that it's equivalent to $\neg( \exists x\in X, x\notin Y)$. Since there are no elements in $\emptyset$, there are none that can fail be in $Y$.

Having a different proof that proceeds via an equivalent definition is a help to see different aspects of what's going on.

Jacob Zelko (Apr 03 2023 at 12:42):

@Mike Shulman -- glad to hear about How To Prove It! Mind sharing where it wasn't so perfect? Looking out for how to work around those deficiencies if need be. Thanks!

Mike Shulman (Apr 03 2023 at 15:29):

One thing I always omit from Velleman when I teach from it is indexed unions and intersections of sets. He spends a whole section on this at the beginning, mainly (as far as I can see) so that he can use them as examples when he talks about quantifiers. I feel like the idea of indexed unions and intersections, although something that students have to learn eventually of course, is too difficult to be worth introducing it for this purpose in an intro course, and I prefer to use more "real" examples and exercises involving quantifiers (of which, fortunately, Velleman has some).

Mike Shulman (Apr 03 2023 at 15:30):

For time reasons, I also prefer to go right to a definition of functions without spending a long time talking about different properties of relations first.

Mike Shulman (Apr 03 2023 at 15:31):

(In general I would prefer a more typed and less set-theoretic emphasis, but hey.)

Mike Shulman (Apr 03 2023 at 15:36):

The other big thing, which is probably more controversial, is that after teaching our intro proofs course, which is also a discrete math class, I've developed strong (so to speak) feelings about the way to introduce induction. Velleman follows the traditional approach of introducing "ordinary" induction first and then later "strong" induction as an enhancement. But at least in discrete math -- which for us includes particularly number theory and graph theory -- many or most of the inductions that arise naturally are actually strong ones (e.g. factorization into primes), while pretty much all the examples of "weak" induction that appear in an intro textbook are fairly contrived. Moreover, strong induction is more easily justified by the relationship to recursion -- you just need a condition ensuring that the program (i.e. proof) terminates. I also think the notion of structural induction over things other than numbers (e.g. lists, trees, graphs) should also be introduced right away at the beginning.

Jacob Zelko (Apr 03 2023 at 19:30):

Hey @Mike Shulman -- this is golden! Thank you so much for sharing your thoughts! When you teach, do you have any particular approach to complementing those concerns you have? Is there any other texts or resources you might suggest that I could perhaps take a look at?

Jacob Zelko (Apr 03 2023 at 19:32):

I really want to make sure I have the notion of induction down pat so if you are saying there are concerns or problems, I want to be as prepared as possible in this respect.

Mike Shulman (Apr 03 2023 at 21:11):

Unfortunately, I don't really have any good supplementary references to give. I generally just talk about the points in class. I'd be interested to hear if anyone else does!

Mike Shulman (Apr 04 2023 at 17:36):

By the way, someone in this thread should explicitly mention Clive Newstead's book Infinite Descent. (It was implicitly mentioned in at least one place, being the first textbook for Emily's course that Jacob linked to.) It also treats the rules of proof in a very nice and organized way, and doesn't emphasize pure sets and indexed unions and intersections as much as Velleman (although it does still do weak induction before strong induction). I'm considering trying it out the next time I teach intro to proofs.

Jacob Zelko (Apr 04 2023 at 18:25):

Oh yea! I saw that book and was curious about it. I was swayed to more go with Velleman's book since I had seen it consistently used across many different courses. But, I will give Infinite Descent a look to compliment Velleman -- can always use an additional perspective! Thanks for calling it out explicitly @Mike Shulman !

Jacob Zelko (Apr 12 2023 at 23:31):

Hey @Mike Shulman and @John Baez , do you happen to know of a nice complementary book to Velleman’s How To Prove It? Although I really like the book, I find some of the terms he throws around a bit too ad hoc for my liking — such as not formally defining what a conjecture, counterexample, or other terms are.

David Michael Roberts (Apr 12 2023 at 23:40):

I would say that almost no one would give a formal definition to a conjecture, it should be treated imo as a plain-language phrase referring to something that is guessed to be true but no proof is known. The exact guidelines around what is called a conjecture among mathematicians are vague and sociological, and change over time. Some people would only use the term for big and important results that have a good deal of examples that would follow if the conjecture were indeed true, and prefer to leave smaller, less impactful statements as mere open questions.

A counterexample is an example that shows that a proposed statement (eg a conjecture) cannot be true.

Jacob Zelko (Apr 12 2023 at 23:42):

I looked back through your book recommendations John but nothing jumped out at me that made sense to go alongside Velleman immediately… although this may just be due to my unfamiliarity — I did just recall Infinite Descent being recommended. Illl look there too

Jacob Zelko (Apr 12 2023 at 23:45):

Interesting about conjectures @David Michael Roberts ! I didn’t realize there was a little bit of anthropology at play here with that terminology. It reminds me that I really must read Laboratory Life by Latour one of these days! Thank you for sharing. :smile:

Jacob Zelko (Apr 13 2023 at 05:19):

Ah yup, just looked through Infinite Descent and this is a very handy reference. Will be using that alongside Velleman to complement some of my learnings!

Mike Shulman (Apr 14 2023 at 15:49):

I've never actually tried to teach from any of them, but several books on my shelf that I think have interesting approaches to learning to "speak mathematics" in addition to writing proofs are

• An Accompaniment to Higher Mathematics by George R. Exner
• Proof and the Art of Mathematics by Joel David Hamkins
• How to Read and Do Proofs by Daniel Solow
• Extending the Frontiers of Mathematics by Edward B. Burger

Sam Speight (Apr 14 2023 at 17:14):

The Hamkins and Burger titles make me want to have a look at them.

John Baez (Apr 15 2023 at 01:41):

Jacob Zelko said:

I find some of the terms he throws around a bit too ad hoc for my liking — such as not formally defining what a conjecture, counterexample, or other terms are.

I don't know of anyone trying to formalize these concepts, s you're unlikely to find an introductory book that does it - but maybe someone has done it, or someday will.

A conjecture is a proposition that has not been proved, that you guess is true. The first part - "has not been proved" - can be formalized if you have a formal concept of what has been proved so far, as a function of time. For example, you could have a proof assistant that keeps track of what has been proved at time $t$. The second part - "that you guess is true" - is harder to formalize. But I can imagine that someday all mathematicians (except me) will be doing math on a big computerized system, and one action they can take is "state a conjecture", which would be a formal way of marking some proposition as something they believe is true.

A counterexample to $\forall x P(x)$ is a choice of $x$ such that $\neg P(x)$.

David Michael Roberts (Apr 16 2023 at 11:10):

Good point on a counterexample being a thing in the presence of a $\forall$ claim.