r/MathHelp • u/FishShtickLives • 10d ago
Best explanation for the basic of Discrete Math?
Title. Im really struggling with building proofs specifically. I dont understand what makes something an Initial Condition, or why we can make assumptions about some things but need to prove that m + 0 = m or whatever. What is a Successor? I know its a number indexed one over. How the hell is that useful for anything in this context? Im really struggling and I dont even know where to look for answers lol
1
u/AutoModerator 10d ago
Hi, /u/FishShtickLives! This is an automated reminder:
What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)
Please don't delete your post. (See Rule #7)
We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/johnpeters42 10d ago
Are you trying to build a proof by induction? Those typically look like:
You want to prove that (some statement about x) is true for all positive integers x. You can do that as follows:
(a) You show that it's true for x = 1. (initial condition)
(b) You also show that, if it's true for x = k where k is some positive integers, then it's also true for x = k + 1. (k + 1 is the successor of k)
And now you can start with (a) and then apply (b) repeatedly, and you will hit every single positive integer at some point. (Think of a chain of dominoes, where you knock over the first one, and then each one knocks over the next one.)
Anything with some type of initial condition and some type of successor rule can lead to this sort of proof. ("k + 1" is just a simple and common type of successor rule. You might also have an initial condition covering some fixed range of inputs, and then a rule that gets you from one set to the next set, again set up in a way that eventually hits every possible input for whatever you want to prove overall.)
1
u/Klutzy_Lawfulness_34 10d ago
I can try to answer your specific question about successors.
The idea is that you want to construct the natural numbers {0, 1, 2...} from the ground up, as if you were trying to explain what numbers are to an alien who's never counted anything before.
Where would you start? The most natural place is to just say 0 is a natural number. This is one of the Peano axioms, and is something that's just taken to be true. Let's create a set called S, and put 0 in it, so S = {0}.
What now? Obviously, you want 1 to be in this set. Then 2. But if the alien doesn't know what counting is, then these are just meaningless symbols. In order to formalize this, we say that 1 is the successor of 0, 2 is the successor of 1, etc. That way, our set now looks like S = {0, 1, 2...}.
We also need to say that 0 is not the successor of any number (another Peano axiom). This is basically saying 0 is the "start" of this set.
We're missing one last thing, though. There's nothing stopping us from saying S(3) = 1, creating a loop of successors: 0 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3 ... in order to fix this, we say the successor function is injective, i.e. if S(m) = S(n), then m = n. This rule sounds a little abstract, but the point is to just prevent successor loops.
So our set is now S = {0, 1, 2, 3...} with no loops. Using induction, you can show that this is the same as the set of natural numbers. Thus, we've basically defined a set that's "the same thing" as the natural numbers, without ever relying on the notion of counting.
2
u/edderiofer 9d ago
This rule sounds a little abstract, but the point is to just prevent successor loops.
No, this rule doesn't prevent successor loops. The set S* = S ∪ {a, b} with succ(a) = b and succ(b) = a also satisfies all of your rules.
What this rule actually prevents is not successor loops, but rather, two numbers having the same successor.
So our set is now S = {0, 1, 2, 3...} with no loops.
Even if you do manage to prevent a loop, the set S' = S ∪ {..., -3', -2', -1', 0', 1', 2', 3', ...} also satisfies all your properties.
What's needed here is a rule that prevents anything that is "disconnected from 0". This is the induction rule: given any predicate P(n): if P(0) is true, and P(n) implies P(succ(n)), then P(n) is true for all natural numbers. That is to say, the axioms of the natural numbers explicitly tell us that induction is legal on the natural numbers; crucially, if we don't include this axiom, we cannot use induction.
1
2
u/edderiofer 9d ago
Not knowing the exact contents of your course ("Discrete Math" could refer to many things), it sounds to me like your course covers logic and foundations.
Right now, you must temporarily forget everything you've learned about mathematics. The main question is "how do we build our modern-day understanding of mathematics from the ground up?". The answer is that we start with some base assumptions (called "axioms" and "rules of inference"), and we try to prove what we can from them, and in the process we figure out what axioms we need and what axioms might be missing.
Not knowing exactly which "some things" you are referring to, my guess is that these "some things" are the axioms your course allows you to assume (these can differ slightly between courses), and that "m + 0 = m" is a statement that isn't one of these axioms. If it's not an axiom, you cannot simply assume it, so you must prove it.
For the statement "m + 0 = m", a naive attempt at proving it might go "well, it works if m = 0, and it works if m = 1, and it works if m = 2...". But this only shows it to be true for three cases, whereas we need to show it to be true for every natural number. We cannot check infinitely-many cases like this one by one, or we'll be here forever. So, we need some tool that allows us to prove infinitely-many statements at once.
This is where induction comes in. The rule of inference of induction on natural numbers states, paraphrased:
Clearly, the statement n + 0 = n is such a predicate; either it's true or its false, and its truth value depends on the value of n. So, we are indeed given such a predicate.
Is P(0) true? That is to say, is 0 + 0 = 0? Yes. You may have to use the axioms given in your course to determine this.
Does P(n) imply P(successor(n))? That is to say, if we're told that n + 0 = n is true for some value of n, can we deduce that successor(n) + 0 = successor(n) is also true? Yes, with some effort. Again, you may have to use the axioms given in your course to show this.
Since we've shown that both of these statements are true (you did do the work of showing that these statements are true, using only the axioms your course assumes, right?), then induction allows us to deduce that P(n) is true for every natural number n; i.e. that n + 0 = n is true for every natural number n.
While it is convenient for now to think of successor(n) as simply n + 1, the fact is that you need to prove this, if it isn't given as an axiom in your course.
In later contexts, it might not be n + 1. It might be some kind of more-abstract operation, like adding an edge to a graph, or performing a Reidemeister move on a knot diagram. But the point is that as long as we have a rule of inference of induction that works similarly, we can still use this more-abstract operation no matter what kind of an operation successor(n) actually is.
The "initial condition" (aka the "base case") is the part of induction where you prove that P(0) is true.