#math proof

[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 🤡

[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]

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)

[hercarisntyours]

she's so, geometric

[the-way-astray]

yeah so fitz is actually still sixteen in the latest book

[anghraine]

Nothing like attempting basic division to sharpen my hatred of "everyone is mentally disabled in their own way :) don't let labels define you :) :)" anti psych posts

[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 and bounded arithmetic (great introduction for beginners)

Jan Krajíček's personal page is full of old teaching materials and resources for students (click past teaching). 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.

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

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

[max1461]

"Visual proofs", more commonly known as "examples",

[necromimetics]

I’m an enjoyer of applied math. Hypothetically. The problem is half the time I do applied math they’re like “so first we’re going to make 25 assumptions” and my pure math brain immediately violently recoils

[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

[quintiple-a]

Guys math is just literal wizard shit. Like the way they can transmute numbers and invoke higher dimensions and conjure imaginary entities to elegantly solve a seemingly impossible problem…

It’s like “ha ha! I have constructed the impenetrable sphere! It is literally impossible to defeat it by brute force!” And then another guy is like :) and draws a funny shape and suddenly the whole sphere turns into a line and the wizard just goes around it and you’re like whaaaat. “Ah ha, but if I merely tesselate this periodic tiles like so…” and then it turns out a puzzle that has stumped scholars for ages is not only instantly resolved but opened up entire new worlds of research in the process.

This post brought to you by YouTube videos explaining math and physics concepts about things like the recently discovered aperiodic monotile

[lipshits-continuous]

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

[felixcloud6288]

I have been itching to teach someone some math for a while and I desperately need to scratch it.

To start, look at this totally amazing gif I once made for a discrete math class.

This is the proof that the square root of 2 is irrational (infinitely long, non repeating decimal value which cannot be represented as a fraction of two numbers). This proof is actually one of the most important proofs out there because it opened the door to new fields in continuous mathematics.

People also died trying to prove this because there was a mathematic religious cult (the Pythagoreans) that believed irrational numbers do not exist.

Read more for discussion and proof explanation.

Welcome aboard. I'll try to make this as understandable as possible. First we'll do some onboarding so you know how the proof methodology works, then we'll do the actual proof.

Prerequisite Knowledge

Implication

Here's a basic implication statement in mathematic notation:

p->q

In human words that means "If statement p is true, statement q will also be true."

Here's a quick exercise. Think of a standard-issue cat. The cat has no unusual features about it, it is as normal and average as can be.

Does your cat have four legs? How about whiskers? A mouth?

I bet I'm right and that's because those are things that are naturally true if you are thinking about a cat.

So back to the implication definition. If p = "I am thinking of a standard-issue cat" and q = "I am thinking of something with four legs, whiskers, and a mouth." then

"I am thinking of a standard-issue cat" -> "I am thinking of something with four legs, whiskers, and a mouth."

Or in human,

"If I am thinking of a standard-issue cat, then I am thinking of something with four legs, whiskers, and a mouth."

While not necessary for the proof, I want to make something clear, p->q is NOT the same as q->p. Just because standard-issue cats have four legs, whiskers, and a mouth doesn't mean everything with those characteristics is a cat.

Proof by Contradiction

So now that you know what implication is about, here's a question:

What happens when p being true leads to a statement that can only be false?

The answer: You have a contradictory statement and p cannot be true.

Now recall that a standard-issue cat has four legs. What if I told you I am thinking of something with 57 legs. Well a cat can't simultaneously have only 4 legs and 57 legs. Therefore, I can't be thinking of a standard-issue cat because if I was, then two contradictory statements would be true.

So proof by contradiction works as follows:

Assume the opposite of what you want to prove

Show what would be true if that assumption were true

Repeat until you have two contradicting statements

Close the proof by saying the assumed statement is false

Definition of even numbers

Okay. I'll try to explain this slowly, since Tumblr doesn't understand what odd and even numbers are.

Let's say X is some arbitrary even number. That means numbers like 0, 2, 4, 6, 8, 10, etc, and -2, -4, -6, -8, -10, etc. X can be any even number. Just fill in the blank.

If X is even, there's some other whole number (whole number means you don't need a decimal. 1.5 or any other number that needs a . in it is NOT a whole number.) that when multiplied by 2 equals X.

0 is even because 2 * 0 = 0. 2 is even because 2 * 1 = 2. 17 is NOT even because 2 * 8.5 = 17 and 8.5 is NOT a whole number. Negative numbers can also be even. -10 is even because 2 * -5 = -10.

Similarly, if you take any whole number and multiply it by 2, the result will be even.

Greatest common divisor

The greatest common divisor (gcd for short) is the largest number that can evenly divide two numbers. The gcd of 9 and 21 is 3 for example. If two numbers have nothing in common, their gcd is 1.

I'll use gcd(x,y) as shorthand for the gcd of two numbers.

A fraction is in lowest terms when the gcd of the numerator(top value) and denominator (bottom value) is 1.

2/3 is in lowest terms because gcd(2,3) = 1. 4/6 is not in lowest terms because gcd(4,6) = 2

Rational vs Irrational numbers

A rational number can be represented as a fraction of two whole numbers in lowest terms. .25 is rational because it is equal to 1/4 1.3333333..... is rational because it is equal to 4/3 10 is rational because it is equal to 10/1

Irrational numbers cannot be represented as a fraction of two whole numbers. Pi is a classic example. Irrational numbers are non-repeating, meaning there's never a point where the value is repeating the same sequence forever. Don't worry about wrapping your head around this. Human brains aren't made to comprehend infinite. Just understand that you can't write it as a fraction of two whole numbers.

Misc

I'm just going to fill in some additional things here in case you're rusty on high school math.

The square root of a number is whatever value times itself equals the original number. The square root of 16 is 4 because 4 * 4 = 16. Since Tumblr doesn't support math notation (as far as I can tell), I'll use sqrt(x) to mean the square root of a value.

The opposite of the square root is the exponential power of 2. Normally, the exponent is represented as a smaller-size number floating to the right of the number (called a superscript) but since Tumblr doesn't support math notation, I'll use x^2 to mean a value to the power of 2.

Exponents mean you are multiplying a number by itself as many times as the power. So 4^3 = 4 * 4 * 4 = 64.

If you square a square root, they cancel each other out. (sqrt(25))^2 = 25 because sqrt(25) = 5, and then 5 * 5 = 25.

If you multiply and divide something by the same value, they cancel each other out. 3 * 2 / 2 = 3 because 3 * 2 = 6 and then 6 / 2 = 3.

When you have an equation, you can do the same thing to both sides and the equation is still equal. If a/2 = b, then I can multiply both sides by 2 and the equation is now a = 2*b.

The actual proof

So we want to prove sqrt(2) is irrational.

To start, we'll use Proof by Contradiction and say sqrt(2) is rational. This IMPLIES sqrt(2) can be represented as a fraction of two whole numbers. We don't care what those numbers are so we'll just use a and b as placeholders.

sqrt(2) = a/b

And since a/b is the fraction representation of sqrt(2) this implies

gcd(a,b) = 1

Now we'll move onto some equation finagling. square root and square power are opposites so if we square both sides, we can remove the square root part.

sqrt(2) = a/b (sqrt(2))^2 = (a/b)^2 2 = (a/b)^2

Exponential power means we're multiplying something by itself however many times the power is so (a/b)^2 = a / b * a / b. We can rearrange these because they're in the same priority on PEMDAS. So a/b*a/b = a*a/b/b = a^2 / b^2

2 = (a/b)^2 2 = a^2 / b^2

Now we can multiply both sides by b^2 to get rid of the division

2 = a^2 / b^2 2b^2 = a^2

a^2 and b^2 are whole numbers. a^2 is equal to 2 times a whole number. This means a^2 is even. a^2 = a * a and a is either even or odd. When you multiply two odd numbers, you get another odd number. When you multiply two even numbers, you get an even number. So a must be even.

If a is even, then there is some other whole number (We don't care what it is so we'll use c as a placeholder) such that a = 2 * c.

And if a = 2*c, then a^2 = (2*c)^2 = 2*c*2*c = 4c^2

2b^2 = a^2 = 4c^2 2b^2 = 4c^2

We can divide both sides by 2.

2b^2 = 4c^2 b^2 = 2c^2

And now we can do the same song and dance for b^2 that we did with a^2 and conclude b must be even.

And now we get to the contradiction part of Proof by contradiction. We earlier said gcd(a,b) = 1 because a/b was a fraction in lowest terms. But we also showed that a and b are even which means gcd(a,b) is at least 2. So we have two contradictory statements gcd(a,b)=1 and gcd(a,b) > 1.

So if sqrt(2) was rational, it would lead to a scenario where a fraction both is and is not in lowest terms. Therefore, we conclude sqrt(2) is irrational.

Now that you have this forbidden knowledge beware the Pythagoreans, lest you too meet your end.

Note: Any genuine questions asking for clarification will be answered in the comments. Any "Um, ackually" comments will be ignored unless you actually are pointing out a genuine mistake I made, which I will correct and acknowledge.

[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

[knottybliss]

Good mornthing my darling thingmakers it is that day of days:

WIP WEDNESDAY

[reesescuffs]

This

This is desert duo canon (I've only watched Scott third life you can trust me)