PROOF by CONTRADICTION - DISCRETE MATHEMATICS
ฝัง
- เผยแพร่เมื่อ 28 ส.ค. 2024
- We take a look at an indirect proof technique, proof by contradiction.
Visit our website: bit.ly/1zBPlvm
Subscribe on TH-cam: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVg
Like us on Facebook: on. 1vWwDRc
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.
I feel like understanding proofs is just memorizing as many examples as possible and hope you see them on the test because there is no way the average student can come up with this on their own.
any student can come up with proof....
@@crazymathematics3263 no.
For me, I feel like it is a matter of memorizing at first, continue to practice, memorize, practice, learn something new, things start adding up, then you actually can start to develop the proofs after things kind of click in your mind. For me at least, it takes a vast amount of effort on my part to study and study until this starts to occur.
@@crazymathematics3263 ratio + L
It's like solving really complex trigonometric integrals. Where if you don't know all of the trig laws, the integral won't be as easily solved. I agree, there are many possibilities and it is difficult to remember them all.
Watching these videos: Yeah, that makes sense!
Going back to my problems from class: Totally lost.
🤣🤣🤣🤣 so true
Same :/
😂😂😂🤣same😭😭😭
I really wish I was this creative. Proofs are never easy for me.
ok
ok
@@question7615 ok
Usually youtube explanations miss the mark, or aren't as informative as they would like to be. Your video is not one of those. It was very effective in explaining the material, and I feel like I understand it better now. Thank you!
That being said I am NOT ready for my exam tomorrow...
How did your exam go?
@@minhajansari8272 he failed
@@Nerfyy eep, two years ago. Also, yeah its also the same reason I'm here now. xD damn.
@@evans3636 me too man mine is in an hour
@@ronanhunt1884 Hey, ya did good?
Hey man, you literally saved my grade in dm. I love the no bs way that you present things and I would definitely be a patron if I wasn't broke as a joke lol.
+shayan javadi Glad I could help!
why does this type of math exits
Well, this is one of the major proof techniques that builds mathematics. If we didn't have this type of math, we wouldn't have any math at all.
But why I do need to prove anything if its already been done?
This maths forms the bedrock of all computation. In essence without it we would not have any technology whatsoever. Its like someone claiming to be a programmer without knowing this math...would not be a decent programmer
@@lucasmartin4883 You are not learning to proof something proven. You are learning proof something that noy proven yet.
Because this is what real mathematics actually is.
Most of what regular people call mathematics is nothing more than glorified arithmetic.
Thank You TrevTutor For Saving Me in My Midterms. Shout out kay Rosner. Salamat sa pagsend sa GC HAHAHAHA.
I have been watching your videos on discrete math for 2 months now. You made a challenging course easy to understand and easy to follow. I wish I had seen your videos way before this. so THank you Thank you and Thank you!
I've been struggling with proofs but the way you explained it really helped to clarify things
Thanks
Your videos are incredibly helpful and it is very easy to understand what you are saying, thank you.
I'd like to add a comment about your example with the square root of two. When saying that it is equal to a/b, you have to specify that b != 0, especially if some professors are sticklers for taking off points.
Cheers.
Andre Pereira you also need to specify that a and b are integers.
Brindyn Schultz fax
Thanks, our book on applied formal logic is very confusing (mixed up examples and such) but on your channel I can almost find everything that's in there, but more concisely explained. Thanks a lot!
+maurods1 Hopefully you got what you need here :)
Honestly, the first example that you proved was the same exact one on my math quiz...and you really know how to break down a problem to where it's concise and simple to understand. Thanks for providing this video for dummy people like me hahaha.
All these videos are very helpful, thank you for sharing!
When I was in the class, I couldn't understand the proof by contradiction. But now, it's all fine. This video made the subject clear. Thank you!
bless you sir,best and most concise videos.Unlike my professor who rambles about random things for an hour. ill donate once my internship starts next week.
This class is tough! I appreciate the help
I learned more in this video than I did our entire week of class, thank you!
I literally larned nothing
you're incredibly helpful but i hate this section. This is the hardest one for me so far from all discrete math. I would not be able to do a proof by myself, it seems like you need to pull stuff out of your ass to manipulate things to agree with what you want or disagree. I still don't get how to do these
How does this apply to real life? Like, when is someone gonna walk up to you and say "Prove that the square root of 2 is irrational"
You don't really have to answer this, just a thought lol
logic applies to real life pretty well. mathematical logic is not only used in mathematical proofs, or applications of mathematics, but also it can be used to deduce what is correct and what is not in real life. imagine you are -say- teacher and some kids had a fight and you want to figure out who was guilty. you ask to kids and get some responses and conclude the followings:
If Jack is innocent, then both John and Annie are guilty
Either John or Annie is innocent
Either Jack is innocent or John is guilty
Then, who is guilty?
When working with rational (a / b) in any example (where both variables are integers), are you supposed to assume initially that a and b cannot be reduced?
What I did for (A - B) intersection (B - A) = empty set:
Assume x is an element (A - B) intersection (B - A) where
therefore x is an element of (A-B) and x is an element of (B-A)
therefore (x is an element A and x is NOT an element of B) and (x is an element B and x is NOT an element of A)
therefore contradiction
Thank you so much, professor, I can finally understand!
this was beautiful!!!! thank you
why the hell you are so good in teaching DM !!! :') thnx man !!
I still don't understand.
Even now?
prove it
@@spectermakoto9029 prove what
@@aghalimassine9197 it was a math joke
@@spectermakoto9029 it was an amazing joke
Your videos are amazing! You're so effective in explaining the material and make it much more painless. Thank you so much! Without you I would be failing this course.
I attempted the last example at 5:15 a bit differently (please tell me if this is incorrect):
1. Assume ( A - B ) ∩ ( B - A ) ≠ ∅
2. Rewrite:
= ( A ∩ B' ) ∩ ( B ∩ A' )
= A and B' AND B and B'
= A or B AND A' or B'
= ( A ∪ B ) ∩ ( A' ∪ B' )
= ( A ∪ B ) ∩ ( A ∪ B )'
3. Rewrite: A ∪ B
C ∩ C' ≠ ∅
The above does not hold therefore the opposite is true.
Is this counter-example hold true?
Hey TrevTutor, for the proof that rad 2 is irrational can you assume rad 2 is rational thus it’s equal to a/b where b does not equal zero and a and b are integers. If you multiply rad 2 by an int. such as ‘b’ you arrive at a contradiction since ‘a’ is not an integer as you assume in the definition. rad 2 times an integer is an rational number.
THIS WAS BEAUTIFUL
lol I'm going to fail tomorrows exam
Good luck, and report back brother.
Ricardo Skylstad didn’t go as bad as I thought lol
@@dxnes5067 Thats great to hear!
Please , Can you explain that
You assumed " randomly " that ( a/b ) irreducible and after that I could get a contradiction .
But , what if you assumed that (a/b) is reducible , then you won't find any contradiction.
Hopefully you answer me.
If I assume it's reducible, then that's not the definition of a rational number so it's not proving anything. Rational number definition is a/b where a,b are irreducible.
@@Trevtutor Thank you for your quick reply .
It's clear now .
@@Trevtutor sorry i dont quite understand that, why 2a/2b cannot be defined also as a rationale number when a/b is rational? even though 2a/2b is reducible, but is has exactly same value with a/b.
This is an amazing video! Couldn't you also use a venn diagram for #2?
Congratulations.
Notification: I would like to inform you that I plan to include this video among the videos reviewed in my article "Analysis of TH-camTM Videos and Video Comments on Mathematical Proof Methods". Kind regards.
at 2:43 you say the only way (a•a) can be even is if "a" is even...but a negative times a negative equals an even number, so can't "a" also be negative??
Test tomrrow, we gonna cook it. LMAO, i am not ready, but you always gotta have the mindset you are going to get 100% am I right
If rational numbers are irreducible fractions, then how can integers, whole numbers, and natural numbers be subsets of the rational numbers? If a rational number is an irreducible fraction, then wouldn't it be impossible to get a non-decimal number when thr fraction is simplified? *Would integers just be considered rational numbers whose denominator is 1, since (any integer/1) is irreducible?*
i have a test in like 4 hours and hope this helps
Doctor what is the meaning of phi mean false ? Please answer me. I'm from Lebanon
What level is this proof at? Like, university (college?), college (highschool?) Orr?
College
A proof of contradiction is just showing you that the opposite of something that is an infinite set, is a moebiusstrip, which is "as limited as possible" (it is a mathematical object that defines what irrationality is), because it has only one surface and one edge, therefore it also is the collatz conjecture in two different ways and not and because this is not congruent with the theorems of the classic logic, we have proven infinity.
I just hope that the information you acquire while walking along doesn't change your perception of it in the next round you go, which is why you don't see it as the same thing, but always as sth else.
You always have finite infinitys, because an infinite infinity is equal to everything and nothing, which is a contradiction (unless it (consciousness) is just a spacetime distortion or rotational moebiusstrip twist drag, which defines dark energy/dark matter).
Because infinitys are only describable in a set of certain parameters, they can only describe specific boundary-less sets within a set with boundaries, otherwise the complete opposite of any value always cancels out it's counterpart, which means that the the only solution is the empty set "{ }".
It's better not to think about it. W8 but isn't it exactly that?
With someone with a horrible math intuition how can I tell if something has to be proved directly or by using contrapositive and contradiction? :(
i just wanna ask.. where did u get "k"? ps: i'm still 13, still in 8th grade and our lesson is now like this..😱😱
+Joshane Tomado We can write any even number as 2k (where k is a variable and can be any integer). So I just picked k in this instance. I could have called it 2j, 2l, 2x, or anything, but it's just meant to show that the outcome is even.
13 and doing this!! am 23 and am beginning
13 and doing discrete... What are you? A Japanese?? An Indian??
I have a similar problem oof
can i get some high school questions which uses contraposition and cases to prove itself ??
I didn't understand WHY did you assume that the root(2) = a/b where a, b is in lowest terms! Why lowest terms?
A rational number doesn't need to be a irredutible fration.....!
+Caio Zowye Camacho Cabral We assume lowest terms for contradiction. Basically, we want to say "here's an irreducible rational number that sqrt(2) is equivalent to", and then we come around and say "wait, this irreducible number just happens to be reducible. It can't be both, so this number can't be rational."
I also do not understand why the reducibility has anything to do with the rationality. Even after his answer, I don't know what the link is.
I don't get it. Can't I say that root 2 = a/b where be is a flying zebra and then say "wait, a/b is actually a number"
Thats how it looks in my head. What am I missing?
Rational numbers: p/q (or a/b in this case) of two integers, and q (or b) is not 0 (whole number or irreducible fraction). Now, in TrevTutor's example, we come to find out that this "irreducible fraction" of a/b (where a is even and b is not 0 nor even or reducible in terms of the fraction because it is already in lowest terms; i.e. 2/1, 2/3, 2/5, 4/1, 4/3, etc) can be reduced once more, because now b is even (i.e. 2/2, 2/4, 2/6, 4/2, 4/6, etc). Thus concluding a contradiction that sqrt(2) is not rational... hope that helps
Honestly, a/b is assumed to be in lowest terms because the author of the video, who is a straight up boss btw, knew where the problem was going... If a/b wasn't assumed to be in lowest terms, I don't believe a contradiction could be drawn out.
However, if a/b is assumed to be in lowest terms, as ALL rational numbers have a representation in lowest terms this is a fine assumption to make, then we know from the outside that both a and b CANNOT be even because if both were even then you could divide both by two, meaning a/b is not in lowest terms.
How do we prove that proof by contradiction is a valid method of proof?
Thanks!
thank you. i like vids again! 😄
thank you!
Can anyone answer what typing tool he uses? thanks
اللي عنده اختبار منطق وجاي يدور شرح يرفع يده 🙊
Our professor solved sqrt(2) a little differently. He said that at the point 2b^2 = a^2 we can say that 2b^2 has an odd number of prime factors (2,b,b) and a^2 has an even number of prime factors (a,a). Then because each has a different number of prime factors, we can say that this is a contradiction. This relies on some knowledge of number theory, though.
Yeah, there are many proofs of this which will depend on which class/approach you're taking. There are many other problems you'll see consistently in your math courses that have different proofs depending on the approach/background knowledge.
So you show that a/b are not in lowest terms by showing that they are even. So how does that contradict the assumption that sqrt2 is rational(i.e sqrt2 can be expressed as ratio).
@Zachary Madden That definition seems like shooting an arrow and then drawing a circle around it.
Ratios can be expressed in higher terms with common factors. There is no contradiction when you find a common factor in a ratio.
@Zachary Madden I understand with that contorted definition this would be a contradiction, I'm not arguing against the contradiction itself but against the definition that frames this as a contradiction.
@Zachary Madden Any number that can be written as a ratio.
pi is irrational so really there is no ratio that expresses pi.
However, pi can still be written in an algebraic form pi=Circumafrance/diameter. But this doesn't actually mean that pi is rational, it can just be a ratio of two irrational numbers or at least the circumference is irrational.
@@uzairakram899 a rational number can be expressed in ratio a/b with a and b as integers. Whereas in the case with pi, one or the other must be irrational, so it does not fit in rational numbers definition
thank you sir
What software do you use?
how we can prove p then q by contradiction
How do u show that then not not phi is true?
where did the 2k squared come from
I’m dropping out
bless ur soul
thanks! great help ^___^
why does it have to be on the lowest term? please answer :(
Definition of rational numbers.
What if tht was a decimal after being divided by 2
My brain- What the fuck is this.
hey future students watching this...
1.yeah proofs is impossible so goodluck
2. no your not ever gonna use this in real life.
3. good luck on your exam tomorrow :) (don't leave it last minute next time.)
what does it mean to be in lowest terms
Shawn s it means a fraction which can’t be further reduced, meaning a and b does not share any common divisor (common factor) other than 1.
@@wsk5nwytscnkfsu thanks buddy
Yes, I know: it's a super old video, but it would be advantageous to entirely use symbolic logic instead of half symbolism and half written English; For example, at 6:21, you wrote, "such that" when you could've just wrote a semicolon since they mean the same thing. It's much more concise and holds meaning in all languages. Also, one should pick a format and stick with it when writing a paper or even a proof.
"because A squared is equal to two times some other number, we know that A squared is even". In isolation this is not a useful statement, because a student can think of of 3, 5 or 7 squared etc. It needs to be qualified by linking it to the other side of the equality. Held me up for a while figuring that out through some other videos.
I got stuck on this. Can you explain? I don't understand what he means two times X number means a squared is even
@@erzo9005 well what he meant was that since:
2b^2 = a^2
theyre the same thing since theyre both set equal to each other
lets say we plug in 3 (an odd number) for b
2b^2 = 2(3^2) = 2(9) = 18
18 is an even number
and this is true for any odd number we plug in for (b), and since a^2 is set equal to all this,
we can safely say that a^2 is also even.
Sir how we prove that" the sum of any rational and irrational number is irrational?
That is a psi symbol not a phi
Hello BSCS 1B.
good proof but the 2ksquared should be better explained for me it just fellout of the sky
luv u ...................
Luv u 2
I hate the day I signed to this class
BrainComprehension.sys is not responding.
what does bar mean?
A bar means the negation of A
Thank you!
Great video, but I just want to take the time to say that this side of mathematics is complete rubbish! Ha
Not really, without this you wouldn't have any other side of mathematics its like saying you like hate sperm but love babies, I know stupid example, but makes no sense it just sounds stupid.
@@strangerdanger7616 your words is smart
I am really dumb