The example you give of "Sam is not the murderer" is a bad example of the usefulness of the law of excluded middle because you don't need the law of excluded middle to prove negations of statements. Not P means the same thing as P implies False, and you prove P implies false by assuming P and getting a contradiction.

* opens video * *”TOBY FO-“*

Can't believe Toby Fox created Math

I do a lot of extremal graph theory and general combinatorics, which essentially makes constructivism impossible in many cases. I like constructive proofs, but avoiding nonconstructive methods would be deadly

Thanks toby

This is a good introduction, if a little light. I didn't know that Bauer's "five stages" paper was a response! Note that our construction of the mean still proceeds by axioms: x < y, so x + x < x + y < y + y by adding x and y to both sides of two copies and pasting; then, divide everything by 2 to show x < (x+y)/2 < y. We do the same steps in the proof as in the algorithm; "add x, add y, divide by 2". This is an instance of the Curry-Howard correspondence!

You can have a proof of contradiction in constructive logic if you want to prove ~p. You assume p and when you reach a contradiction you would have proved ~p. In fact ~p is often defined as (p -> false) The problem is if you want to prove p. If you assume ~p when you reach a contradiction you would have proven ~~p. The problem is you don't have double negation elemenaion in constructive logic because it is equivalent to the law of excluded middle. ~~p in constructive logic is weaker than p.

aaron welson : don't sacrifice a bishop in the opening or middlegame. greek gift sacrifice: allow me to introduce myself

Actually is a common mistake to believe that in constructive (intuitionist) mathematics you can't do proofs by contradiction at all. The law of excluded middle still there in a softer form: a statement is not either true or false, but it's proved true or not proved true. If you have a proposition A that leads to a contradiction, then you have proved "Not A", even in constructive math. No problem in that. What you can't do is having a proposition "NOT A", that leads to a contradiction and therefore deduce A. This is forbidden in constructive math, because it allows the "theological proofs of existence", without show the object that is claimed to exist. That's because is not " the law of excluded middle" that is not valid, but the counternegative: "not not A", doesn't mean A. In constructive math A is true means that, using axioms, you proved A. "Not A" means that, using axioms, you proved that A can't be proved (and It couldn't be proven even if you add tailor-made axioms that do not lead to contradictions). "Not not A" doesn't mean "A" in constructive mathematics, but it means that, using axioms, you can prove that is impossible to prove that A can't be proved (even by adding tailor made axioms, without leading to a contradiction). It seems a twist tongue, isn't it? The fact that the law of excluded middle isn't valid at all in constructive math is a very common misconception that makes most people rise the eyebrow and refute to use constructive mathematics. It's not about the LEM, it's about what you mean by "true". In constructive math it means "provable", while in classical math it is thought that a statement can be true or false, but maybe not provable with the current set of axioms. That is the problem with classical logic: that metaphisical concept of truth that can trascend the system of axioms you are in.

Constructive math is amazing. Especially if one is coming from a lifelong classical perspective. I stumbled upon this through type theory and it was super cool.

A big problem with the Law of Excluded Middle in mathematics is that it is uninformative. Let's say my thesis is: "either 23 divided by 45 plus 86 is equal to 286 or it isn't equal to 286." Within classical logic, this is a tautology and a perfectly valid conclusion. However, what it doesn't tell us is whether this equation does - or does not - equal 286.

The axioms were actually stated long after many many theorems were discovered. That's simply fact of history of mathematics. So talking about "manipulation of axioms" seems misleading to me. The axiomatic method is used to make mathematics more rigorous, but mathematics as a whole is much more creative than that.

There's another huge advantage of constructive mathematics over classical one: computers can follow the former, but not the latter. The reason is that computers can follow algorithms, so if you can construct one, a computer can follow the algoritm to produce a mathematical object as an evidence of the truth of your theorem. This fact is the foundation of the branch of mathematics/computer science called type theory, which investigates the relations between statements and proofs on one hand and between types and programs on the other. Turns out these relations are very similar, which allows us to encode statements as types; programs as proofs and by the virtue of type-checking provide an algorithm to verify whether or not a certain proof (program) proves some theorem. There are programming languages like Agda, Coq, Isabelle and others, which leverage this fact to provide a nice environment for writing proofs and having them automatically verified by the computer. Unfortunately, if you try to introduce LEM into such a system, it immediately falls apart, because computer cannot follow proofs by contradiction (because they're not based on algorithms). So all these systems only support constructive logic.

ok that was probably the most complicated proof of "if x

The two types of math are linear algebra and complex analysis

holy shit undrtail dog

NEW DELTARUNE LEAK LOOKIN' FIRE 🔥🔥

Existence is consistent and non existence is inconsistent Both not only are true, but should be demonstrably true Assume there exists no number in-between x and y. When looking at numbers in an ordered field (which is the case) field and order properties dictate that (x+y)/2 exists in the field and that x < (x+y)/2 < y. This is a contradiction in the hypothesis that there does not exist such a number, therefore there does exist such a number.

Removing Lem doesn't make it less, it makes it more. Constructive mathematics is a superset of mathematics.

It's not that constructive mathematicians don't believe any statement is either true or false, it's rather that they just don't care. Constructive logic, as its name suggests, is not about truthness but about what you *can* construct (proofs). For instance, the "there exists" symbol in classical maths only means that there theoretically exists such an object but with no guarantee at all that you can find it. While in constructive maths, the only way you have to prove a "there exists" statement is to actually exhibit such an object. This is the same reasoning for the LEM. As a matter of fact, everything you've proven with constructive maths also stands in classical maths, but not the other way around. Having a constructive proof with you is more powerful as it just says more, so that's why you should fallback on classical proofs only when mandatory and when you only care about truth.

Wow, i'm undergrad and learning some math as cs. There is a lot of proofs and i have problem with them, especially because i don't understand "why this proof proving theorem" and now i understood why. i should dive into math logic.

toby fox is real

4:29 This is the beginning of everything

Lmao, I saw a community post about this video just 2 minutes ago

Great video!

Lol i just saw a community post by whirow and he clicked on ur video because it started with the fox

3:25: This is a bad example. While it's not generally true in constructive logic that (not not P) => P, it is still true that (not not not P) => (not P). So we can acquit the suspect under constructive logic. 6:25: I don't think a classical mathematician would actively search for a proof by contradiction if there was a much simpler proof that didn't use LEM.

Tobias Fox

I initially thought that classical logic is a subset of constructive logic, since constructive logic has less inference rules than the classical, thus has the potential to add more non-classical inference rules. But everything accepted by constructive logic also accepted by classical logic, so constructive logic is a subset of classical logic like what this video said.

The two types of math are: a) math I understand b) the rest of math

how am I just now finding this shout out the earlsweatshirt background music too!

Can't believe tovy fox create maths

Either way, its fun

I’m gonna research now

The two types of math are : Mathematical math And Engineer maths .

I wonder if the halting problem exists in constructive mathematics

07:23 x=1, y=2, x + y/2 = 2 which is not strictly between x and y. Perhaps (x + y)/2 was meant.

Two questions: 1- can you prove that sqrt(2) is irrational by a constructivist way? 2- where belong the induction proofs?

Why did you use undertale dog 🥶

Notepad for scripts, why not an overkill Screenwriting software?

Acho que faço um pouco das duas formas.

Maybe we can use classical techniques to lazily evaluate the mathematical landscape before constructive techniques come in, it could save a lot of time.

The sleepwalking murder!

The constructive proof is not complete. Firstly, we have to define what our numbers x and y actually are, I think you are referring to real numbers. It remains to be shown, that x+y/2 is indeed in the Intervall (x,y). Firstly, because the real numbers are closed regarding addition and multiplication, we know that (x+y)/2 is indeed a real number. We know that x

Am I the only one who'll react that it should be (x + y)/2 not x + y/2 at 7:21? Otherwise interesting Cuz otherwise imagine x = 2. y=3. Then we'd have x + y/2 = 2 + 1.5 = 3.5 which is not inbetween x and y You meant it as (2 + 3) / 2 = 5/2 which is inbetween x and y

Halfway through, but it seems pointless and that there’s no reason we would ever want to get rid of the law of the excluded middle.

❤

To be honest I think this is nothing but distorting the logical conditions until they generate problems where there are none and then dividing people into opposing sides. Is that simple as getting rid of the _"either always LEM or never LEM"_ mentality. If you wanna construct maths to logically characterize some information, you must *decide* if you wanna work with all the load of truth determined or you just don't mind, but none of this has anything to do with "proof by contradiction". This one type or proof is actually like a proof by counterreciprocal, but instead of proving an implication you prove the sentence by having determined that the other is false (whether by definition, by axiomatics or by whatever reason you want). If it turns out the other one can't be proven or disproved you just just look for another way to prove it (without so much drama). 🤷

x = 10, y = 12. Then x + y/2 = 16 > 12 so it is not between x and y?

You could equally say that classical logic is a subset of constructive logic, by doing a double-negation embedding. It's a huge mistake to claim that something is a subset of something else in math, like, for example "a permutation group is a subset of ALL groups", or, equally, "any group is a subgroup of a permutation group". Both statements are valid. Constructive logic makes manifest the duality between logic and computer programming. Classical logic hides this duality. That's the real difference.

toby fox?

did you have to pick the saddest song for the music :(

‏‪4:34‬‏ dont we know from godel it isnt true?

I don't think this video is very useful since it barely gets into the difference between the two and the motivation for them. I mainly consider myself a constructivist in the sense that you should be able to directly construct anything which you claim exists. I can say that pi exists because I can specify it's value using various definitions, algorithms, etc. The same for sqrt(2), ln(2), the golden ratio, e, etc. But claiming a number exists which you can't actually specify seems dodgy. Using proof by contradiction is completely valid. All kinds of "non-constructive" proofs are valid and often they are technically constructive, especially when dealing with finite sets. Eg) A proof using the pigeonhole principle might not always "construct" a specific solution, but if the total space involved is finite, a simple algorithm for constructing a solution can be specified - just search the entire space! As a specific example, if you pick any 11 positive integers, I know that at least two of them must end with the same digit (since there are only 10 different digits but 11 numbers - there must be an overlap). That's non-constructive, but it's easy to search all 55 pairs among your 11 integers and find the ones which match. So there's no difference in this context between classical and constructive. I only favour constructive maths when we're talking about infinite and very complex objects. That's where some non-constructive proofs rely on objects which can't even be explicitly defined. The axiom of choice is a prime example. It asserts that you can always choose one element from each of an infinite collection of sets, without specifying how. But if you can do that, why does it need to be asserted as an axiom? Shouldn't it be a theorem which you prove? What if it can't always be done? That's where I think a constructive approach is necessary and the axiom of choice is completely invalid. Eg) Breaking the real numbers up into cosets of the form x + Q, where x is a real number and Q is the rationals. Supposedly an infinite set of values for x can be "chosen", but also, it can be proven that no explicit list actually exists. In my opinion, that kind of concept is just useless and meaningless. It has no application in the real world, it only applies to other layers of meaningless maths built on top of it. Hence why the continuum hypothesis is unprovable - it just shows that you've reached a state of making things up, not investigating anything tangible. TLDR: Constructivism only differs from classical maths when dealing with infinite objects. Most proofs in finite contexts are the same and one can easily switch between the two approaches. But with some infinite objects, classical maths is actually quite loose and meaningless while constructivism insists on more concrete reasoning.

I think it's potentially misleading to depict constructivism as a subset of classical mathematics rather than vice versa. In terms of model theory, it's more accurate to say that classical logic is a model of constructivist logic rather than the other way around, since constructivist logic is more general. That is, classical logic would never reject any constructivist proof, but constructivist logic may reject a classical proof; truths of classical logic are either true or undecidable in constructivist logic, but all truths of constructivist logic are true in classical logic.

8:03 "Meanwhile the classical mathematician never actually shows that there exists the number ... " - Sorry, nonsense. "Classical" mathematicians use constructive proofs all the time. As you have said yourself, constructive methods of proof are a subset of classical methods of proof. Classical mathematics has no restriction that would say "you must NOT construct the object and prove it's existence by contradiction itself. Both types of mathematicians will probably use the same proof in this case ...

y-x >0

5:38 "ma-zo-cheest" I'm guessing you meant to say ma-zo-keest ....

nice thumbnail

"The classical mathematician is correct, but the proof - uh, well - it’s rather useless, isn’t it?" That is a ridiculous exaggeration, and pairing it with the condescending tone is not a good sales pitch. It only takes away from what you explained up to that point.

The first thing that comes to my mind is - The empty set is no longer a subset of every other set?

better proof by contradiction. sam was asleep and in a completely different location than where the murder occured. and you can't be in two different places at once

bool non_terminating() { while (1) { }; return true; }

toby fox jumpscare

no bgm pls

your feelings are irrational

There are four levels of maths Numbers Latin letters Greek letters Hebrew letters

what is your opinion on number zero? by introducing number zero negative numbers were introduced which are irregular (can't take square root of, multiplication doesn't give negative number)? wouldn't this make mathematics less perfect ? If we think of number zero as an input/output device of an abstract computing machine (which is mathematics) , wouldn't it be more correct to explicitly construct and destruct numbers instead of having zero which is a placeholder for construction/destruction right now?

I decline to hear this as the music is too loud!~

"Background" music ruined the video

2:12 so these people don't care about precision. They want the easy way out in maths. Funny how emotions can play out in different kinds of people.

Unnecessary music very annoying and distracting - I'm outta here.

Nice material. But instead of wasting your time with that cartoon childish nonsense, focus on your math material. You will be way more prolific.

the "sam is not a murderer" example is tragically terrible: we literally proved the statement ¬(sam is the murderer), which is literally equivalent to (sam is the murderer) ⇒ ⊥. We didn't even need to use the law of excluded middle. also, one can always prove ¬¬¬A ⇒ A in constructive logic. therefore, only statements like "there is an even number that is not the sum of two primes" could possibly only be proved in classical logic by showing that "all even numbers are the sum of two primes" leads to a contradiction.

yooo its the toby dog

Great video!