#mathematical proof

[xypheris]

Grad school math: Imagine a space that exists but doesn’t really exist. Now prove something about it.

[simplicius-simplicissimus]

Q.E.D. - quod erat demonstrandum (that which was to be demonstrated)

-Placed normally at the end of mathematical proofs or philosophical arguments

[catscomputerscreativewriting]

It's so funny to me that people think of Math/Mathematicians as being hyper-logical and rational. Like, have you seen some of the wild things hiding in the Math?

Did you know there are non-computable numbers?? (https://en.wikipedia.org/wiki/Chaitin%27s_constant)

Did you know that there are things that are true, but we can't prove them??? (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems)

Did you know that we can prove that something exists, and yet never actually figure out what that thing is?? (https://mathworld.wolfram.com/NonconstructiveProof.html)

Math is crazy. Math is wild. Math hardly makes sense, and when you think you understand the weirdest parts of it, everyone who hears you explain it to thinks you're a gibbering lunatic.

"In mathematics you don’t understand things. You just get used to them." - von Neumann

(please share more unhinged math with me, i want to see more scary math)

[xyymath]

Things Math Professors Say

"The proof is trivial." (Oh, cool. Guess I’m just an idiot then.)

"Left as an exercise." (Translation: You’ll never solve this in a million years.)

"It’s obvious, really." (Sure, if you’re a demigod.)

"By inspection." (Stares harder at problem… still nothing.)

"For small values of epsilon." (How small? Subatomic? Microscopic? Vibes?)

"WLOG (Without Loss of Generality)." (Oh, we’re just assuming it doesn’t matter now? Alright.)

"Details omitted." (Because apparently, you don’t need to understand it.)

"By the usual argument." (Which you somehow don’t know because you weren’t born in 1702.)

"Assume the rest holds." (That’s some impressive optimism right there.)

"The usual abuse of notation." (Why does this feel like an emotional wound?)

"Almost surely correct." (But also possibly wrong? Cool, thanks for the clarity.)

"A non-rigorous approach." (I thought math was supposed to be precise?!)

"Assume it’s obvious." (Buddy, NOTHING about this is obvious.)

"The reader may verify." (No, the reader may CRY.)

"To the interested reader." (Guess I’m not interested enough, huh?)

"Well-behaved functions only." (We’re function-shaming now?)

"Obvious to the trained eye." (Guess I’ll never make it out of amateur league.)

"A trivial case analysis." (Trivial to WHO??)

"Integrate by parts, twice." (Bold of you to assume I got it the first time.)

"As you can clearly see." (Oh, I clearly see my FAILURE, alright.)

"It works in practice too." (Unlike me, who barely works at all.)

"Assume a spherical cow." (Are we doing math or abstract sculpture?)

"A standard result." (Not in my standards, pal.)

"We skip the tedious algebra." (No, no, please—I wanted to suffer MORE.)

"Assume non-zero solutions exist." (Okay, now we’re just assuming life works out.)

"The usual topology." (Bro, I don’t even know the unusual topology.)

"Finitely many cases left." (Just kidding, there’s 72.)

"By virtue of symmetry." (Virtue? I have none left.)

"Don’t worry about the constant." (The constant is probably my GPA dropping.)

"Assume continuity." (I’m assuming my brain is breaking.)

"Smooth functions only." (Guess I’ll leave, I’m clearly not smooth enough.)

"The simplest non-trivial case." (Simplest? NON-TRIVIAL? Pick a side!)

"Epsilon goes to zero." (Epsilon isn’t the only one losing it.)

"And the rest follows." (Where? Straight to my breakdown?)

[catboydan]

my very specific prediction for the upcoming AITA video: he'll open by explaining that last week on the gaming channel he had an 'AITA' moment himself [insert clips from the dan eye incident here]

then he'll lead into the vid by saying something like "and that inspired me to ask you all for your 'am I the hole' moments", and only then will he bring up that this time, he asked for specifically dating/love-related stories, leaving us to piece together that the intro is a dating/love related story via the maxim of relevance

[mentalknot]

Sharing of Proof Between Friends

After spending over nearly eight hours of each day in a mathematics department for two years straight, I’m shocked that many high schoolers believe math is a solitary pursuit.

In reality, this community seems to be one of most welcoming and collaborative academic communities I’ve found. Let me share some moments:

“Hey! How’s it going?”

“Alright, been stuck on this interesting question my friend emailed me the other day… he said the first part of the proof is pretty easy, but I’ve been at it for 10 hours…”

“Never trust a mathematician who throws around the word ‘easy,’ c’mon let’s try it together at the board.”

Thirty minutes later, they had completed the proof, and sat back with wide smiles to admire their work. In truth, there was rarely a conversation that didn’t eventually turn to math in that department…

“Yeah, and I heard that the guy cheated with his best friend’s sister… wild right?”

“Yeah… not to interject, but I have this representation theory question… would you all be willing to take a look?”

The conversation took an immediate turn with collective enthusiasm. I have been lucky to have my own “collaborative math” moments since returning to my undergraduate studies, and do my best to share this part of “math culture” with younger students curious about the major.

“So that’s the proof that motivates our paper! It’s quite short, but there’s something about it I love.”

“Wait… but you’ve only done half, and this is a biconditional statement, let’s try it together.”

There was a reason my mentor never encouraged me to look at the other side of the proof… it was far more “ugly,” but tons of fun to piece together with a fiend. We looked back at our work after forty minutes with satisfaction before returning to our neglected problem sets…

And finally, I tried to assist a student with a calculus question using the “process of questioning” the research world had taught me:

“I need to find a closed-form equation for this geometric series… but I can’t seem to get the alteration sign?”

“Try writing out the first six terms, do you see anything that you could simplify? Look at the denominator specifically…”

“Well, they’re all multiples of three…”

“Try pulling that three out, any more similarities?”

“The numbers multiplying the threes are powers of two! But I still need that alternating sign…”

“Remind me, what happens when you raise a negative number to an odd/even power? Try it with (-1)^n”

“If it’s odd, the number stays negative, and positive if even… so if I add this to the denominator, the sign is alternating depending on the index n!”

“YES! This little (-1)^n trick comes up everywhere, it’s a nice ‘tool’ to hold on to if you decide to take more math.”

The exchange was wonderful… and motivated me to review the calculus I’d excitedly ran past when I was younger. I wish this type of discourse was taught more expansively.

[simplydnp]

who's hand is in this picture?

A Mathematically Rigorous Proof That I Spent Too Long Writing

welcome to university math: dnp hand edition

(no, don't leave, you'll be fine i promise)

to begin, we need a statement to prove. we have two options:

- the hand is dan's hand

- the hand is phil's hand

now, for most proofs in university math, you are told a true statement, and you must show why it is true using logic rules, definitions, and theorems. but, we do not know which of these statements are true, so we have to find out.

to prove that a statement is true, we must show that it is always true for the situation presented. to show a statement is false, we must present a single instance where the statement is false (also known as a counter example).

a quick not scary math example:

definition: a prime number is only divisible by 1 and itself.

statement: all prime numbers are odd

(this is false, because 2 is a prime number and it is even. you don't even need to check if there's any others, all you need is one single case where it isn't true to disprove it)

so now that we have a little background on proofs and how to prove and disprove them, we go back to our two statements.

the thing with this situation is, one of them must be true (unless you're gung-ho on someone else holding dan's face while phil takes a picture on his phone of dan in his glasses, in which case, i applaud your commitment, but in actuality this proof will cover that option too)

the full statement we have is: dan is touching his face or phil is touching dan's face

now, because this is Real Life and we have a picture where a hand is touching dan's face, we know already that one of these options is true (as mentioned above) but! using symbolic logic you could also come to this conclusion.

this type of statement is an 'or' statement, and if you're curious, you can look into 'truth-tables' and see why, but at least one of the options must be true.

back to the proof at hand (bah-duhm-tss)

okay. now, proofs also must be 'general' in order to mean anything, really. these are statements of truth of the universe, not just for individuals. so, we will prove this generally.

we have 2 people involved, so individual 1 (dan, the owner of the face and potential face toucher) will be labelled as 'D' , and individual 2 (phil, the possible face toucher who does not own the face) will be labelled as 'P'. thus, this can be true for any such D and any such P.

so with our 'or' statement, in order to prove it, we pick one of the options and say that it is not true, and we have to show then that the other is true.

step 1: let's assume this is not P's hand. (assumption)

step 2: thus, it must be D's hand. (what we take from our assumption)

step 3: now, if it is D's hand, we look at what a hand on one's own face is capable of appearing like. (a definition or true fact about step 2)

the position in the given photo shows the hand with a thumb on the cheek, and a finger on the forehead. so, we find an example of a person with their fingers in the same position (or close to) and see if this supports our claim.

consider:

now, with this image, you can clearly see how the subject's right hand has the thumb on the temple and index finger on the top of their head, however, it is a close enough position for our case.

from the view of the camera, the closest finger to the camera is the edge of the pinkie. in fact, it will always be the closest finger to the camera in this position, assuming the subject has all fingers and no additional appendages.

step 4: we now compare this to our photo (we verify if this holds to our claim or contradicts it)

in our photo, the closest appendage to the camera is the edge of the thumb.

step 5: thus, it cannot be the case that D is touching their own face. (what the evidence says)

step 6: as we assumed it was not P's hand and have shown it cannot be D's hand, and as this is an 'or' statement both of these claims cannot be false, we can therefore conclude it must be P's hand. (our conclusion: re-stating the statement and assumptions and conclusion)

step 7: we verify that P is true (optional step but in beginner proofs you generally show why your case works)

to do this, i will show a picture of a person touching another's face, and compare it to our image.

consider:

now, this image is not exactly the same, similar to above. however, P's left thumb is on the cheek, with their index on D's temple. the closest appendage to the camera (if it were in a similar perspective as our original) would be the edge of the thumb.

comparing it to our original:

our comparison holds.

thus, we can conclude that the true claim in this statement is that P must be touching D's face, which, in particular means that:

phil is touching dan's face in the image

thank you for partaking in phannie mathematics. we now know. i am not sorry.

bonus:

phil has a hitchhikers thumb and dan doesn't so why was this necessary at all 🤡

[pv1isalsoimportant]

(Semi-regularly updated) list of resources for (not only) young mathematicians interested in logic and all things related:

Igor Oliveira's survey article on the main results from complexity theory and bounded arithmetic is a good starting point if you're interested in these topics.

Eitetsu Ken's list for resources on proof complexity, computational complexity, logic, graph theory, finite model theory, combinatorial game theory and type theory.

The Complexity Zoo for information on complexity classes.

The Proof Complexity Zoo for information on proof systems and relationships between them.

Computational Complexity blog for opinions and interesting blog posts about computational complexity and bunch of other stuff.

Student logic seminar's home page for worksheets on proof complexity, bounded arithmetic and forcing with random variables (great introduction for beginners).

Jan Krajíček's page is full of old teaching materials and resources for students (click past teaching) concernig logic, model theory and bounded arithmetic. I also recommend checking out his books. They are basically the equivalent of a bible for this stuff, although they are a bit difficult to read.

I also recommend the page of Sam Buss, there are downloadable versions of most of his articles and books and archive of old courses including resources on logic, set theory and some misc computer science. I especially recommend his chapters in Hnadbook of Proof Theory.

Amir Akbar Tabatabai's page for materials on topos theory and categories including lecture notes and recordings of lectures.

Andrej Bauer's article "Five stages of accepting constructive mathematics" for a funny and well-written introduction into constructive mathematics.

Lean Game Server for learning the proof assistant Lean by playing fun games.

[noosphe-re]

In 1931, the Austrian logician Kurt Gödel pulled off arguably one of the most stunning intellectual achievements in history. Mathematicians of the era sought a solid foundation for mathematics: a set of basic mathematical facts, or axioms, that was both consistent — never leading to contradictions — and complete, serving as the building blocks of all mathematical truths. But Gödel’s shocking incompleteness theorems, published when he was just 25, crushed that dream. He proved that any set of axioms you could posit as a possible foundation for math will inevitably be incomplete; there will always be true facts about numbers that cannot be proved by those axioms. He also showed that no candidate set of axioms can ever prove its own consistency. His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what’s provable and what’s true. What mathematicians can prove depends on their starting assumptions, not on any fundamental ground truth from which all answers spring.

Natalie Wolchover, How Gödel’s Proof Works, Quanta Magazine, July 14, 2020

[rabbiteclair]

love to deploy something to production while telling the head of engineering "listen, when you guys built this thing about a decade ago you didn't make it capture any metrics, so I had to really guess about the throughput, and if I got it wrong then it will explode horribly in the morning, but the good news is that I'm the one on-call so it's ultimately my problem if that happens anyway"

[lipshits-continuous]

Pretty neat that for a topological group G with identity element e, we have that π₁(G,e) is abelian

[xypheris]

Them : Do you ever sleep?

Me : No, I’m busy wondering if my proof is rigorous enough for the ghost of Euclid to approve.

[felixcloud6288]

Did you know if a number is divisible by 3, you can add all the digits of the number and the sum is divisible by 3? For example, 327 is divisible by 3 and 3+2+7 = 12, which is divisible by 3.

For the Proof on why this is, click Read More

Prerequisite Knowledge

Numbers

Yes, I need to explain how numbers work for this proof.

Let's go back to elementary school. You're being taught basic addition of multi-digit numbers. You're given the number 54,321. 54,321 = 50,000 + 4,000 + 300 + 20 + 1

Let's expand that a little.

54,321 = 5*10,000 + 4*1,000 + 3*100 + 2*10 + 1

Now I''m going to take an aside and mention exponents, just in case.

Normal notation for exponents are a base number with a smaller number floating on the top right corner of your base value. Since Tumblr can't support that notation, I'll use a^b as the notation.

When you have an exponent, you have to multiply the base number by itself however many times the exponent number is. For example, 3^4 = 3*3*3*3 = 81.

Also, if the exponent value is 0 or smaller, you start dividing by the base number instead. So 3^0 = 3/3 = 1.

Now that I've explained that, let's go back to earlier.

54,321 = 5*10,000 + 4*1,000 + 3*100 + 2*10 + 1

Each digit in 54,321 is beling multiplied by an exponential power of 10.

54,321 = 5*10^4 + 4*10^3 + 3*10^2 + 2*10^1 + 1*10^0

This expanded form of an arbitrary number is going to be necessary for the proof.

Modulo and Equivalence

Let's go back to elementary school again. Remember how in division, you'd give a remainder as part of your answer? 12 / 5 = 2 remainder 2.

The modulo operator returns the remainder when you divide two numbers. In programming, % is used for modulo so I'll use that for notation. So 12 % 5 = 2.

An expansion of modulo is equivalence. Two numbers are equivalent under a modulo value when both numbers have the same remainder when divided by the modulo value. Under modulo value 5, 7 and 12 are equivalent because 7 % 5 = 2 and 12 % 5 = 2.

The normal notation for equivalence is the equal sign with 3 lines instead of 2. I'll use == for the notation here.

Since 7 and 12 are equivalent under mod 5, the notation is 7 == 12 (mod 5)

If a number is evenly divisible by a modulo power, it's equivalent to 0. 5 / 5 = 1, therefore 5 % 5 = 0, therefore 5 == 0 (mod 5)

There are some special rules about numbers that are equivalent. We'll let a, b, c, and m be arbitrary numbers.

If a == b (mod m), then a+c == b+c (mod m) If a == b (mod m), then a*c == b*c (mod m) If a == b (mod m), then a^c == b^c (mod m)

The Proof

Now let's move onto the proof.

Let's say we have some arbitrary whole number X which is divisible by 3. That means there is some whole number c such that X = 3*c. So if X is 327, c would be 109 because 109*3 = 327.

Now let's rewrite X into the expanded form from the Numbers section. We'll let d(0) refer to the least significant digit (The one at the far right). d(1) will be the next least significant digit and so on until we reach d(n), the most significant digit.

X = d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0

Since X is divisible by 3, that means the long form of X is equal to 3c.

d(n)*10^n + d(n-1)*10^(n-1) + … + d(1)*10^1 + d(0)*10^0 = 3*c

Now let's start doing some modulo.

10 == 1 (mod 3)

By the earlier rules mentioned in the Modulo section, we can multiply and exponentiate each term (The parts between the +) and they're still equivalent. So now we'll replace each term with an equivalent term under mod 3.

d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0 == d(n)*1^n + d(n-1)*1^(n-1) + … + d(1)*1^1 + d(0)*1^0 (mod 3)

1 exponentiated to any power is 1 so

d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0 == d(n) + d(n-1) + … + d(1) + d(0) (mod 3)

Meanwhile 3*c == 0 (mod 3). Since 3*c = X, then anything equivalent to X is equivalent to 0.

d(n) + d(n-1) + … + d(1) + d(0) == 0 (mod 3)

At this point we can say the sum of all the digits of X can be divided by 3 because the sum would have no remainder.

So in conclusion, if the sum of all the digits of a number can be divided by 3, then the number can be divided by 3.

[catscomputerscreativewriting]

Listen, textbook, I admire the dedication to grifting my students into learning most of Constructive Logic before they've realized it. They are computer scientists after all. It's good for them. But... really? No explanation of formal proofs by contradiction in the undergraduate, Logic for CS textbook? You do include double negation elimination, which is an equivalent Classical axiom, but not, like, (A -> Bottom) -> ~A?

You mean I'm gonna have to derive that myself from the completely random and arbitrary Classical axioms you've decided to adopt and then neglected to prove the completeness of? Otherwise, all of these proofs will become extremely cumbersome and all of my students will swear off CS theory for the rest of their lives?

... ok fine, it'll be in the slides. T-T

[humormehorny]

Yo math people, what was your first proof?

[lorei-writes]

... Isn't it funny that in order to gain confidence, you need to do things you don't feel confident about, the ones that push you simply force you to confront exactly how much you can do?

Ha. I tell myself to do things "in the ways I do not know". Maybe there is some merit to that, after all.