Trying to understand mathematical logic

[Mates]

This is about my attempt at the opposite of proof by contradiction (conditional proof): My professor marked me wrong because he wanted me to prove an equation was true by starting with one side and makin it equal the other. I couldn't figure it out, so instead I just assumed it were true until I simplify it to be axiomatically true. For example, prove abc = xyz. Instead of starting with a side and making it equal the other, I simplified both sides until it gave me something trivially true like 4 = 4 or b = b.



He marked me wrong because he said that my conditional arrows starting with abc = xyz went the wrong way. I tried to ask him why, but I didn't understand his explanation. He said that he might have taken off less marks if I would have started my arrows with the trivial solution and added them through my work to finish pointing at the original question to be proved.


It is hard for me to argue with him since he has a Ph.D in mathematics from Cambridge. So I am wrong, I just don't know why.


If I try to break it down into something simpler like proving 3(2) - 6 = 0, I get something like:


3(2) - 6 = 0 ---> 3(2) - 6 (+6) = 0 (+6) --->3(2) = 6 ---> 6 = 6


Couldn't the arrows have gone this way, or the other way; or even biconditionally?

In my defence, isn't this how proof by induction works in the sense that we assume that the result we test for is true in order to see if it is actually true using n+1? Like, instead of using the operation + 1 to n, I am using other operations to see what the final results will be.

 

[ksdhart2]

Well, I'd caution against automatically assuming that your professor is right and you're wrong. Even people with doctorate degrees make mistakes sometimes. That said, however, in this case, he is correct. If the proof had started from 6 = 6 and worked "backwards" to end up with 3(2) - 6 = 0, that would be a valid proof. When doing proofs, it's important to keep in mind what it is you're trying to prove. In this case you want to prove that 3(2) - 6 = 0, so it intuitively makes sense that that would be the last step in the proof. The way you've situated your proof, it's already invalid right from the very first line...

3(2) - 6 = 0
3(2) - 6 (+6) = 0 (+6)
3(2) = 6
6 = 6

Every line in your proof follows from the previous being true. Except, whoops! The first line has no preceding line to draw from, so how do you know it's true? You always have to start from something you do know is true, or start by stating that it's an assumption and later "back out" of that assumption. Here, not only do you start from a statement that hasn't been proven, it's actually even worse because you're assuming the very thing you're trying to prove!

 

[Mates]

Well, I'd caution against automatically assuming that your professor is right and you're wrong. Even people with doctorate degrees make mistakes sometimes. That said, however, in this case, he is correct. If the proof had started from 6 = 6 and worked "backwards" to end up with 3(2) - 6 = 0, that would be a valid proof. When doing proofs, it's important to keep in mind what it is you're trying to prove. In this case you want to prove that 3(2) - 6 = 0, so it intuitively makes sense that that would be the last step in the proof. The way you've situated your proof, it's already invalid right from the very first line...

3(2) - 6 = 0
3(2) - 6 (+6) = 0 (+6)
3(2) = 6
6 = 6

Every line in your proof follows from the previous being true. Except, whoops! The first line has no preceding line to draw from, so how do you know it's true? You always have to start from something you do know is true, or start by stating that it's an assumption and later "back out" of that assumption. Here, not only do you start from a statement that hasn't been proven, it's actually even worse because you're assuming the very thing you're trying to prove!

Okay, thank you, and if I remember correctly, that's about what he said. But I still don't fully get it.


Instead of poking him anymore, I left his office without asking about specifics, which I regret because I still have a false understanding of math logic in my head. Here is my reasoning and it uses the formulation of proof by induction.


For induction we seem to be doing what I just tried to do. We assume what we want to prove in the 2nd step. We try to prove, say, a strictly increasing function f(n) < c (some constant c) is true for any/all n, by assuming it is true for any/all n. Of course there is the base case where n = 1 and the 3rd step where f(n+1) also has to be < c. But the bottom line is that the outcome of the n+1 input relies on or is contingent on f(n) < c.


So can't I just assume an equation is true, granted I make no arithmetic mistakes, until it results in an obviously true equation?


I just don't understand this logic.

 

[stapel]

...Here is my reasoning and it uses the formulation of proof by induction.

For induction we seem to be doing what I just tried to do. We assume what we want to prove in the 2nd step.

No. In that second, "assumption", step, you're assuming that the statement
[*] (whatever statement it is that you're trying to prove) is true somewhere. The "somewhere" is unstated. Then you go on to prove that
[*] is true at the "next" place, wherever that might be. Then you use the first step, the "at n = 1" (or some other specific named place) to show that
[*] is true everywhere. "If it's true some place, then it'll be true at the next place. And it is true at n = (named place). So then it's true at the next place, and then the next place, and then the next place,... onward forever. So it's true everywhere."

If you're not comfortable with this logic, try reading the second page in this lesson. It provides examples of how induction fails when
[*] is actually false.

We try to prove, say, a strictly increasing function f(n) < c (some constant c) is true for any/all n, by assuming it is true for any/all n.

No. You assume only for some unnamed, unspecified, generic "n = k". Then you try to prove that, if it's true at n = k, then it must be true for n = k + 1.

Of course there is the base case where n = 1...

And if you can prove it's true for n = k + 1, assuming it was true for n = k, then you know that it's definitely true for n = 1 (first step) and, because it must be true for n = k + 1 if it's true for n = k, then it has to be true for n = 1 + 1 = 2, and then for n = 2 + 1 = 3, and so on and so forth. Thus, it's true for all n.

...and the 3rd step where f(n+1) also has to be < c. But the bottom line is that the outcome of the n+1 input relies on or is contingent on f(n) < c.

Can you give a specific example of this? Thank you!

 

[Mates]

No. In that second, "assumption", step, you're assuming that the statement
[*] (whatever statement it is that you're trying to prove) is true somewhere. The "somewhere" is unstated. Then you go on to prove that
[*] is true at the "next" place, wherever that might be. Then you use the first step, the "at n = 1" (or some other specific named place) to show that
[*] is true everywhere. "If it's true some place, then it'll be true at the next place. And it is true at n = (named place). So then it's true at the next place, and then the next place, and then the next place,... onward forever. So it's true everywhere."

If you're not comfortable with this logic, try reading the second page in this lesson. It provides examples of how induction fails when
[*] is actually false.


No. You assume only for some unnamed, unspecified, generic "n = k". Then you try to prove that, if it's true at n = k, then it must be true for n = k + 1.


And if you can prove it's true for n = k + 1, assuming it was true for n = k, then you know that it's definitely true for n = 1 (first step) and, because it must be true for n = k + 1 if it's true for n = k, then it has to be true for n = 1 + 1 = 2, and then for n = 2 + 1 = 3, and so on and so forth. Thus, it's true for all n.

I am really just trying to understand what we are really saying when using conditional arrows to prove equations.

So let's say I have to prove that 4(1 + 2) = 12. In this situation I would start with the brackets 4(3) = 12 then multiply 4(3). Now it would seem like I could use the conditional arrows here starting with 4(1 + 2) = 12 then the arrow ---> 4(3) = 12 ---> 12 = 12. But my professor said that I have to start with 12 = 12 and go backwards. I don't even know what the arrows mean, or are saying, in this situation.

It's not like other kinds of conditional statements that are more obvious like x^(1/2) = 4 ---> x = 16.

Can you give a specific example of this? Thank you!

It's given that f(n) is increasing for all n E N. Let's use a(n) for traditional notation as this is a sequence. It is defined inductively as a(n+1) = (a(n)+2)^(1/2) where a(1) = 0.


Because we are told it is an increasing sequence, we know that a(n+1) - a(n) = or > 0. We also know that by quadratic decomposition that (a(n+1))^2 - (a(n))^2 = a(n) + 2 - (a(n))^2 = -(a(n) - 2)(a(n) + 1) which tells us that a(n) must be = or < than 2 in order for the square of a(n+1) minus the square of a(n) to stay positive (since a number larger than the other will still be larger when both are squared.).


Now we must show that a(n) = or < 2 for all n using induction.


Step 1. a(1) = 0 < 2


Step 2. If a(n) = or < 2 then (a(n+1))^2 = or < a(n) + 2 = or < 4 because we assumed a(n) is 2 at the most.


a(n) must be = or < than 2 for all n.

 

[ksdhart2]

I am really just trying to understand what we are really saying when using conditional arrows to prove equations.

So let's say I have to prove that 4(1 + 2) = 12. In this situation I would start with the brackets 4(3) = 12 then multiply 4(3). Now it would seem like I could use the conditional arrows here starting with 4(1 + 2) = 12 then the arrow ---> 4(3) = 12 ---> 12 = 12. But my professor said that I have to start with 12 = 12 and go backwards. I don't even know what the arrows mean, or are saying, in this situation.

It's not like other kinds of conditional statements that are more obvious like x^(1/2) = 4 ---> x = 16.

Actually, in both of your examples, the arrows do mean exactly the same thing. The conditional arrows are typically read aloud as "implies." It's commonly used in logic, in the context of \(\displaystyle P \implies Q\). This would be read as "P implies Q" or "If P then Q."

In your second example, you're saying that the statement \(\displaystyle x^{\frac{1}{2}} = 4\) implies \(\displaystyle x = 16\). In other words, if we know that \(\displaystyle x^{\frac{1}{2}} = 4\) then it follows that \(\displaystyle x = 16\)

In your first example, each arrow is the implication operator. You're saying that if we know that \(\displaystyle 4(1 + 2) = 12\) then it follows that \(\displaystyle 4(3) = 12\). But, as mentioned before, this is already invalid logic because we don't know that \(\displaystyle 4(1 + 2) = 12\). In fact, this is what you set out to prove so you definitely can't start by assuming it's true. However, if you start from the tautology \(\displaystyle 12=12\) and work you way up to \(\displaystyle 4(1+2)=12\), then you can do what you did there to show that the implication is biconditional.

In other words, if you've shown that \(\displaystyle [4(1+2)=12] \implies [4(3)=12] \implies [12=12]\) and \(\displaystyle [4(1+2)=12] \impliedby [4(3)=12] \impliedby 12=12\), then that's sufficient to say that \(\displaystyle [4(1+2)=12] \iff [4(3)=12] \iff [12=12]\).

 

[stapel]

It's given that f(n) is increasing for all n E N. Let's use a(n) for traditional notation as this is a sequence. It is defined inductively as a(n+1) = (a(n)+2)^(1/2) where a(1) = 0. [Edit: To prove: that a(n) < 2 for all n.]

Because we are told it is an increasing sequence, we know that a(n+1) - a(n) = or > 0. We also know that by quadratic decomposition that (a(n+1))^2 - (a(n))^2 = a(n) + 2 - (a(n))^2 = -(a(n) - 2)(a(n) + 1) which tells us that a(n) must be = or < than 2 in order for the square of a(n+1) minus the square of a(n) to stay positive (since a number larger than the other will still be larger when both are squared.).

Now we must show that a(n) = or < 2 for all n using induction.

Step 1. a(1) = 0 < 2

Yes.

Step 2. If a(n) = or < 2 then (a(n+1))^2 = or < a(n) + 2 = or < 4 because we assumed a(n) is 2 at the most.

No.

Please study at least two lessons from this listing, and then re-read the replies you've received. Then please attempt this exercise again, using the standard second step of making an assumption (which must be clearly stated) for when n = k, and then using the working for the standard third step. Thank you!

 

[Mates]

Actually, in both of your examples, the arrows do mean exactly the same thing. The conditional arrows are typically read aloud as "implies." It's commonly used in logic, in the context of \(\displaystyle P \implies Q\). This would be read as "P implies Q" or "If P then Q."

Yes, that is what I always thought. But I also think of proofs like proof by contradiction. This seems to me like we are generally doing the same thing. We are sort of seeing where an assumption takes us. Instead of the result being a contradiction to prove that something is not true, I am just showing that it is true exactly the same way.

In your second example, you're saying that the statement \(\displaystyle x^{\frac{1}{2}} = 4\) implies \(\displaystyle x = 16\). In other words, if we know that \(\displaystyle x^{\frac{1}{2}} = 4\) then it follows that \(\displaystyle x = 16\)

In your first example, each arrow is the implication operator. You're saying that if we know that \(\displaystyle 4(1 + 2) = 12\) then it follows that \(\displaystyle 4(3) = 12\). But, as mentioned before, this is already invalid logic because we don't know that \(\displaystyle 4(1 + 2) = 12\). In fact, this is what you set out to prove so you definitely can't start by assuming it's true. However, if you start from the tautology \(\displaystyle 12=12\) and work you way up to \(\displaystyle 4(1+2)=12\), then you can do what you did there to show that the implication is biconditional.

In other words, if you've shown that \(\displaystyle [4(1+2)=12] \implies [4(3)=12] \implies [12=12]\) and \(\displaystyle [4(1+2)=12] \impliedby [4(3)=12] \impliedby 12=12\), then that's sufficient to say that \(\displaystyle [4(1+2)=12] \iff [4(3)=12] \iff [12=12]\).

Yeah, basically the way I was taught to think of the arrow is that it is a logical implication of deduction.

 

[Mates]

Yes.


No.

Please study at least two lessons from this listing, and then re-read the replies you've received. Then please attempt this exercise again, using the standard second step of making an assumption (which must be clearly stated) for when n = k, and then using the working for the standard third step. Thank you!

Many of the links don't seem to want to explain why we have to make n = k; this just might be a gap in my overall understanding of math in general, so I am very interested in this.


I found something that I have never seen before in the website notes of the University of Illinois. It says that k E Z+. Isn't this the same as saying n E N? http://www.math.illinois.edu/~ajh/213/inductionsampler.pdf


Khan really emphasizes assuming it is true for k, and since k = n, I don't see how we are really not just assuming it for n. https://www.khanacademy.org/math/al...-induction/alg-induction/v/proof-by-induction

My professor said something about this, but it didn't make sense and I was able to prove by induction anyways, so I never felt I had to understand it.


It just seems to me that we are assuming or testing the result that we are looking for in order to see if additional operations to the assumption are equivalently consistent.

 

[JeffM]

This is about my attempt at the opposite of proof by contradiction (conditional proof): My professor marked me wrong because he wanted me to prove an equation was true by starting with one side and makin it equal the other. I couldn't figure it out, so instead I just assumed it were true until I simplify it to be axiomatically true. For example, prove abc = xyz. Instead of starting with a side and making it equal the other, I simplified both sides until it gave me something trivially true like 4 = 4 or b = b.



He marked me wrong because he said that my conditional arrows starting with abc = xyz went the wrong way. I tried to ask him why, but I didn't understand his explanation. He said that he might have taken off less marks if I would have started my arrows with the trivial solution and added them through my work to finish pointing at the original question to be proved.


It is hard for me to argue with him since he has a Ph.D in mathematics from Cambridge. So I am wrong, I just don't know why.


If I try to break it down into something simpler like proving 3(2) - 6 = 0, I get something like:


3(2) - 6 = 0 ---> 3(2) - 6 (+6) = 0 (+6) --->3(2) = 6 ---> 6 = 6


Couldn't the arrows have gone this way, or the other way; or even biconditionally?

In my defence, isn't this how proof by induction works in the sense that we assume that the result we test for is true in order to see if it is actually true using n+1? Like, instead of using the operation + 1 to n, I am using other operations to see what the final results will be.

Before we get to induction, let's make sure you have this.

This is one of those things that are so simple and obvious that you think you are being told something recondite and almost impenetrable.

You are asked to prove that \(\displaystyle 3(2) - 6 = 0.\)

You start YOUR proof by assuming that \(\displaystyle 3(2) - 6 = 0.\)

You have just ASSUMED what you were to PROVE. It is called "begging the question." The point is that order matters in entailment.

"X is a triangle" NECESSARILY entails that "X is a polygon." On the other hand, "X is a polygon" does NOT necessarily entail that "X is a triangle." Order matters. You cannot present a formal proof dependent on what you are to prove. It is in the wrong order.

Do you understand that?

When asked to find a proof, it is a valid method of trying to find a proof to assume that what is to be shown is true and to reason from that assumption until you get to something that is known to be true. As just explained that is not a valid proof. But if you can reverse each step in your deduction from your unjustified assumption, you have now found your valid proof. (If I remember correctly, this is called Proclus's Method.) You were on the right track when you mentioned biconditionality.

\(\displaystyle 3(2) - 6 = 0 \implies 3(2) = 6 \implies 6 = 6\) does not prove \(\displaystyle 3(2) - 6 = 0\) but it suggests a valid proof, namely

\(\displaystyle 6 = 6 \implies 3(2) = 6 \implies 3(2) - 6 = 0.\)

The order of the steps has been reversed, and the arrows of implication can be reversed in each case. Work done.

You have confused what is a fallible (but frequently useful) heuristic for finding proofs with proof itself.

Clear now?

 

[JeffM]

Let's proceed to induction. I hate the vocabulary associated with mathematical induction: it is confusing.

Let's start with an intuition. If something is true for the natural number one and if it is also true that the assertion is true for the natural number k + 1 whenever the assertion is true for k, we say that it is true for every natural number. Peano formalized this intuition as an axiom; it is not proved. But the intuition is obvious: it is true for 1 so it is true for 2 so it is true for 3 so it is true for 4 and so on without end. The dominoes all fall.

Do you have any trouble whatsoever with the intuition or the axiom based on that intuition?

Now a style point. Some people use n throughout proofs by induction. I think that notation is confusing. I like the notation using k, k + 1, and n.

Let's take a very simple proof by induction.

\(\displaystyle \text {PROVE: } n \in N^+ \implies \displaystyle \sum{j=1}^nj = \dfrac{n(n + 1)}{2}.\)

To prove this by induction requires that we prove it is true for the number one (this step is usually trivially easy).

\(\displaystyle \text {STEP I: } n = 1 \implies \displaystyle \sum_{j=1}^nj = \sum_{j=1}^1j \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^nj = 1 \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^nj = \dfrac{2}{2} \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^nj = \dfrac{1(2)}{2} \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^nj = \dfrac{n(n + 1)}{2}.\)

So we have shown that it is true for the number one, which deals with the first domino. Moreover, we have shown that there is at least one natural number for which our assertion to be proved is definitely true. In other words, the set of natural numbers for which the assertion to be proved is true is NOT EMPTY. Thus it is not an assumption (although for some idiotic reason it is called the "induction hypothesis") to identify k as an arbitrary member of that non-empty set. It is important in what follows not to assume that k = 1. We want our result to be true for 2, 3, 4, and so on. So k may be the number one or some higher natural number. All we know about k is outlined in the first line of step II.

\(\displaystyle \text {STEP II: } k \in \mathbb N^+ \text { and } \displaystyle \sum_{j=1}^kj = \dfrac{k(k + 1)}{2}.\)

Do you see why I say calling this an assumption is horrible nomenclature? We have PROVED in the first step that there is at least one natural number for which this is true. We now say pick ANY natural number for which it is true. There is no assumption whatsoever that such a natural number exists: we have proved at least one such natural number exists.

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \left (\sum_{j=1}^kj \right ) + (k + 1) \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \dfrac{k(k + 1)}{2} + \dfrac{2(k + 1)}{2} \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \dfrac{k^2 + k}{2} + \dfrac{2k + 2}{2} \implies\)

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \dfrac{k^2 + 3k + 2}{2}\implies\)

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \dfrac{(k + 1)(k + 2)}{2}\implies\)

\(\displaystyle \displaystyle \sum_{j=1}^{k+1}j = \dfrac{(k + 1)\{(k + 1) + 1\}}{2}.\)

So we have now shown that the assertion is not only true if n = 1, but have also shown that it is true for the next natural number after any natural number for which the assertion is true. All the dominoes fall. Thus our axiom let's us say:

\(\displaystyle \therefore n \in N^+ \implies \displaystyle \sum_{j=1}^nj = \dfrac{n(n + 1)}{2} \text { Q.E.D.}\)

 

[stapel]

Many of the links don't seem to want to explain why we have to make n = k...

It's been explained in this thread, and is clearly explained and demonstrated in the first lesson link you were given. I'm not sure what else can be said about this...?

Khan really emphasizes assuming it is true for k, and since k = n, I don't see how we are really not just assuming it for n.

Once again, with feeling:

Step 1: Show that the formula works at some named place, such as n = 1.

Step 2: Assume that the formula works at some UN-named place, n = k.

Step 3: Show that the formula works at the "next" UN-named place, n = k + 1. In this step, use the assumption which was made in Step 2.

Since, if (assumption) the formula works at some place (Step 2), then (we've proved) it works the next place (Step 3), and since it works at n = 1 (Step 1), then it works at n = 2 (because of Steps 2 and 3), and then n = 3 (because of Steps 2 and 3), and then... forever, so it works everywhere.

It's kind of starting to feel like you're maybe not reading responses thoroughly, because we keep telling you about three steps, and you keep talking about two steps; and we keep telling you about assuming n = k and proving n = k + 1, and you keep talking about assuming both in the same step. There is a huge difference between what we're telling you and what you're replying with. Please slow down and try to see BOTH of the second and third steps. Thank you!

 

[Mates]

Before we get to induction, let's make sure you have this.

This is one of those things that are so simple and obvious that you think you are being told something recondite and almost impenetrable.

You are asked to prove that \(\displaystyle 3(2) - 6 = 0.\)

You start YOUR proof by assuming that \(\displaystyle 3(2) - 6 = 0.\)

You have just ASSUMED what you were to PROVE. It is called "begging the question." The point is that order matters in entailment.

"X is a triangle" NECESSARILY entails that "X is a polygon." On the other hand, "X is a polygon" does NOT necessarily entail that "X is a triangle." Order matters. You cannot present a formal proof dependent on what you are to prove. It is in the wrong order.

Do you understand that?

When asked to find a proof, it is a valid method of trying to find a proof to assume that what is to be shown is true and to reason from that assumption until you get to something that is known to be true. As just explained that is not a valid proof. But if you can reverse each step in your deduction from your unjustified assumption, you have now found your valid proof. (If I remember correctly, this is called Proclus's Method.) You were on the right track when you mentioned biconditionality.

\(\displaystyle 3(2) - 6 = 0 \implies 3(2) = 6 \implies 6 = 6\) does not prove \(\displaystyle 3(2) - 6 = 0\) but it suggests a valid proof, namely

\(\displaystyle 6 = 6 \implies 3(2) = 6 \implies 3(2) - 6 = 0.\)

The order of the steps has been reversed, and the arrows of implication can be reversed in each case. Work done.

You have confused what is a fallible (but frequently useful) heuristic for finding proofs with proof itself.

Clear now?

This all is what I always thought. But I also think of proofs like proof by contradiction. They seem to generally be doing the same thing as what I thought we could do with my example. We are sort of seeing where an assumption takes us. Instead of the result being a contradiction to prove that something is not true, I am just showing that it is true exactly the same way, only I am proving a positive assumption.

Thank for the thorough explanation about induction. My only issue now with induction is why we have to make n = k. Everything else about induction seems pretty clear now.

 

[Mates]

It's been explained in this thread, and is clearly explained and demonstrated in the first lesson link you were given. I'm not sure what else can be said about this...?


Once again, with feeling:

Step 1: Show that the formula works at some named place, such as n = 1.

Step 2: Assume that the formula works at some UN-named place, n = k.

Step 3: Show that the formula works at the "next" UN-named place, n = k + 1. In this step, use the assumption which was made in Step 2.

Since, if (assumption) the formula works at some place (Step 2), then (we've proved) it works the next place (Step 3), and since it works at n = 1 (Step 1), then it works at n = 2 (because of Steps 2 and 3), and then n = 3 (because of Steps 2 and 3), and then... forever, so it works everywhere.

It's kind of starting to feel like you're maybe not reading responses thoroughly, because we keep telling you about three steps, and you keep talking about two steps; and we keep telling you about assuming n = k and proving n = k + 1, and you keep talking about assuming both in the same step. There is a huge difference between what we're telling you and what you're replying with. Please slow down and try to see BOTH of the second and third steps. Thank you!

I should have been more clear. My question is about why we have to make n = k in the first place; why not just use n? Since we can use any n E N, I don't know why adding n = k is a necessary detail.


I fear this small misunderstanding could be a result of my problems here with deeper aspects of math logic.

 

[JeffM]

This all is what I always thought. But I also think of proofs like proof by contradiction. They seem to generally be doing the same thing as what I thought we could do with my example. We are sort of seeing where an assumption takes us. Instead of the result being a contradiction to prove that something is not true, I am just showing that it is true exactly the same way, only I am proving a positive assumption.

At the risk of repeating what you already understand, let's distinguish among three concepts.

In Proclus's Method, we do assume the truth of what we are trying to prove and then try to deduce an axiom or previously proved theorem from that assumption. It is a frequently useful heuristic. But it is not a proof because we have "begged the question" by assuming as true what we are supposed to prove as true. The heuristic works in finding a proof ONLY if we can reverse the order of implication in each step. The proof then becomes the deductive steps of the heuristic deduction in reverse order with the order of implication reversed in each step. Your method of finding a proof was OK (though the method does not always work), but your presentation of that proof was not OK because:

A POSITIVE proof always starts with an axiom or some previously proved theorem and proceeds to what is to be proved.

In a proof by contradiction, there is no begging the question because we assume initially the OPPOSITE of what we are trying to prove.

Are you completely satisfied with that explanation?

Thank for the thorough explanation about induction. My only issue now with induction is why we have to make n = k. Everything else about induction seems pretty clear now.

Not everybody bothers with k. It is a matter of style in presentation. And you need to play along with the style required by your teacher whether you agree or not.

I happen to agree strongly with the k style. At the end of the proof, n stands for ANY natural number. On the other hand, k stands for ANY natural number for which the assertion in question is true. Until we have finished the second step in the proof, we have not shown that the natural numbers for which the assertion is true include all the natural numbers. In fact all we have PROVED so far is that the assertion is true for at least one natural number, namely one itself. So I find it confusing to use n eventually as standing for any member of the set of natural numbers while using it in a different sense in the second part of the proof, where it stands for a member of a completely different set and SEEMS to be assuming what is yet to be proved. So k stands for a member of a set that we do not yet know is the set of natural numbers. All we know about k is that it is a natural number and that the assertion is true for k whether or not it is true all natural numbers. I like using different variables for different concepts. It keeps me from getting confused.

Make sense?

 

[Mates]

At the risk of repeating what you already understand, let's distinguish among three concepts.

In Proclus's Method, we do assume the truth of what we are trying to prove and then try to deduce an axiom or previously proved theorem from that assumption. It is a frequently useful heuristic. But it is not a proof because we have "begged the question" by assuming as true what we are supposed to prove as true. The heuristic works in finding a proof ONLY if we can reverse the order of implication in each step. The proof then becomes the deductive steps of the heuristic deduction in reverse order with the order of implication reversed in each step. Your method of finding a proof was OK (though the method does not always work), but your presentation of that proof was not OK because:

A POSITIVE proof always starts with an axiom or some previously proved theorem and proceeds to what is to be proved.

In a proof by contradiction, there is no begging the question because we assume initially the OPPOSITE of what we are trying to prove.

Are you completely satisfied with that explanation?

I feel closer than ever, thanks.


I just realized that I was really just trying to say that the symmetrical operations on each side implies no change as the equation simplifies (that is based on the 12 basic algebraic axioms of course).


So I was not clear with my proof to my instructor. I should have added an "if" at the beginning that was really saying, "if the following operations on each side hold and simplify the equation to something trivially true, then the equation was right all along.


I don't know if I am just B.S.-ing my way through this, but do you think this is a justifiable reason for the one-way arrows that started from the equation in question?

Not everybody bothers with k. It is a matter of style in presentation. And you need to play along with the style required by your teacher whether you agree or not.

I happen to agree strongly with the k style. At the end of the proof, n stands for ANY natural number. On the other hand, k stands for ANY natural number for which the assertion in question is true. Until we have finished the second step in the proof, we have not shown that the natural numbers for which the assertion is true include all the natural numbers. In fact all we have PROVED so far is that the assertion is true for at least one natural number, namely one itself. So I find it confusing to use n eventually as standing for any member of the set of natural numbers while using it in a different sense in the second part of the proof, where it stands for a member of a completely different set and SEEMS to be assuming what is yet to be proved. So k stands for a member of a set that we do not yet know is the set of natural numbers. All we know about k is that it is a natural number and that the assertion is true for k whether or not it is true all natural numbers. I like using different variables for different concepts. It keeps me from getting confused.

Make sense?

Okay, but I feel like the k part is more about proving that k (some variable from a set that we know nothing about) is from a set of natural numbers more than it having anything to do with proving an equation is true for any natural number.


Which brings me back to why I brought up induction in this thread in the first place. If k is really just n, as n = k seems to suggest, then it seems like we are assuming what we want to prove.


In other words, n = k appears to mean that n and k are interchangeable, so why do we have to show something about k when we really just want to know if an equation works for any natural number?

 

[JeffM]

I feel closer than ever, thanks.


I just realized that I was really just trying to say that the symmetrical operations on each side implies no change as the equation simplifies (that is based on the 12 basic algebraic axioms of course).


So I was not clear with my proof to my instructor. I should have added an "if" at the beginning that was really saying, "if the following operations on each side hold and simplify the equation to something trivially true, then the equation was right all along.


I don't know if I am just B.S.-ing my way through this, but do you think this is a justifiable reason for the one-way arrows that started from the equation in question?

NO, IT ABSOLUTELY IS NOT JUSTIFIED. You seem to be arguing a silly point rather than trying to understand a simple point. In general, it is NOT true that

\(\displaystyle \{A \implies B\} \implies \{B \implies A\}.\)

It is good logic to say that Alice is a mother implies that Alice is female. It is not good logic to say that Alice is female implies that Alice is a mother. Order matters in logic. I refuse to believe that you do not grasp that point. Yet you are essentially trying to argue that order does not matter. If you truly find valid the argument that Alice being female necessarily entails her being a mother, you are going to find math utterly beyond you.

You were asked to prove X. You asserted what was to be proved. Whether you assert it unconditionally or insert an "if" to make it a conditional assertion makes no difference: the order of the proof is wrong. You can't base a proof on what is to be proved. It is a circular argument. It is begging the question. Surely you see that.

You found when trying to prove X that if X is true then Y is true and Y is true. If Alice is a mother, then she is female. But in fact Alice is female. Therefore she must be a mother. That is exactly the kind of silly argument you gave your professor.

There is a famous book in epistemology called The Logic of Scientific Discovery in which the author distinguishes between (a) finding the solution to a problem and (b) proving that solution correct. You are confusing a and b.

As I have tried to explain now several times, what you did (starting at the end and working backwards) frequently is a good way to find a valid proof, but it is not itself a proof. Your chain of reasoning constitutes a valid proof only if the order of the steps and the direction of every arrow can be reversed. If they can, THAT is the proof. What you were saying in effect is that it was obvious to you that the order of each step and direction of each arrow in your particular argument could be reversed, but you could not be bothered to write it all out and wanted your reader, in this case your professor, to do that work.

Okay, but I feel like the k part is more about proving that k (some variable from a set that we know nothing about) is from a set of natural numbers more than it having anything to do with proving an equation is true for any natural number.


Which brings me back to why I brought up induction in this thread in the first place. If k is really just n, as n = k seems to suggest, then it seems like we are assuming what we want to prove.


In other words, n = k appears to mean that n and k are interchangeable, so why do we have to show something about k when we really just want to know if an equation works for any natural number?

I hardly know what to say. If you go back to the example I gave, nowhere did I say n = k. If you look at my previous post, I explained why n and k represent different concepts and why I believe that using k and n interchangeably causes great confusion. It is as though you have not even read what I posted.

What n represents is an element from the set of all natural numbers. What k represents is an element from the set of natural numbers for which proposition P is true. That set may be empty (in which case k does not even exist), or it may contain some but not all natural numbers, or it may contain all the natural numbers. Our objective is to prove that the set of natural numbers for which P is true contains every natural number, but we have not yet proved it and so we cannot assume it.

If P is not true for the number one, P is certainly not true for all natural numbers. So our first step is to prove that P is true for one. That gives us our initial domino and proves that the set of natural numbers for which P is true is not empty, thereby also showing that k exists.

We do not need to show that k is a natural number. Wherever did you get that idea? In fact, k must be a natural number because k comes from a set that contains only natural numbers, although, at this stage of our proof, that set may not contain all the natural numbers and may in fact contain only the natural number one. Our current objective is to prove that k + 1 is in that set. And n is certainly not k and k + 1 at the same time.

Looking back, it seems to me that a common thread in your misunderstandings is that nothing in a proof can depend on what is to be proved. Yes, when we have completed our proof by induction, we know that k, an arbitrary element from the set of natural numbers for which P is true, is interchangeable with n, an arbitrary element from the set of all natural numbers. But that interchangeability is not known, cannot be used, and only confuses the issue during the proof at a stage where all we know for certain is that the number one is in the set of natural numbers for which P is true.

 

[Mates]

NO, IT ABSOLUTELY IS NOT JUSTIFIED. You seem to be arguing a silly point rather than trying to understand a simple point. In general, it is NOT true that

\(\displaystyle \{A \implies B\} \implies \{B \implies A\}.\)

It is good logic to say that Alice is a mother implies that Alice is female. It is not good logic to say that Alice is female implies that Alice is a mother. Order matters in logic. I refuse to believe that you do not grasp that point. Yet you are essentially trying to argue that order does not matter. If you truly find valid the argument that Alice being female necessarily entails her being a mother, you are going to find math utterly beyond you.

You were asked to prove X. You asserted what was to be proved. Whether you assert it unconditionally or insert an "if" to make it a conditional assertion makes no difference: the order of the proof is wrong. You can't base a proof on what is to be proved. It is a circular argument. It is begging the question. Surely you see that.

You found when trying to prove X that if X is true then Y is true and Y is true. If Alice is a mother, then she is female. But in fact Alice is female. Therefore she must be a mother. That is exactly the kind of silly argument you gave your professor.

There is a famous book in epistemology called The Logic of Scientific Discovery in which the author distinguishes between (a) finding the solution to a problem and (b) proving that solution correct. You are confusing a and b.

As I have tried to explain now several times, what you did (starting at the end and working backwards) frequently is a good way to find a valid proof, but it is not itself a proof. Your chain of reasoning constitutes a valid proof only if the order of the steps and the direction of every arrow can be reversed. If they can, THAT is the proof. What you were saying in effect is that it was obvious to you that the order of each step and direction of each arrow in your particular argument could be reversed, but you could not be bothered to write it all out and wanted your reader, in this case your professor, to do that work.

Okay, I think I see the big picture now. Thanks for your help here.

I hardly know what to say. If you go back to the example I gave, nowhere did I say n = k. If you look at my previous post, I explained why n and k represent different concepts and why I believe that using k and n interchangeably causes great confusion. It is as though you have not even read what I posted.

Sorry, I got your posts confused with stapel's posts.

What n represents is an element from the set of all natural numbers. What k represents is an element from the set of natural numbers for which proposition P is true.

Thank you! What you say here has really made it sink in for me now. I was always able to use induction, but I never understood the k vs n part.

That set may be empty (in which case k does not even exist), or it may contain some but not all natural numbers, or it may contain all the natural numbers. Our objective is to prove that the set of natural numbers for which P is true contains every natural number, but we have not yet proved it and so we cannot assume it.

If P is not true for the number one, P is certainly not true for all natural numbers. So our first step is to prove that P is true for one. That gives us our initial domino and proves that the set of natural numbers for which P is true is not empty, thereby also showing that k exists.

We do not need to show that k is a natural number. Wherever did you get that idea? In fact, k must be a natural number because k comes from a set that contains only natural numbers, although, at this stage of our proof, that set may not contain all the natural numbers and may in fact contain only the natural number one. Our current objective is to prove that k + 1 is in that set. And n is certainly not k and k + 1 at the same time.

Looking back, it seems to me that a common thread in your misunderstandings is that nothing in a proof can depend on what is to be proved. Yes, when we have completed our proof by induction, we know that k, an arbitrary element from the set of natural numbers for which P is true, is interchangeable with n, an arbitrary element from the set of all natural numbers. But that interchangeability is not known, cannot be used, and only confuses the issue during the proof at a stage where all we know for certain is that the number one is in the set of natural numbers for which P is true.

 

[stapel]

I hardly know what to say. If you go back to the example I gave, nowhere did I say n = k. If you look at my previous post, I explained why n and k represent different concepts and why I believe that using k and n interchangeably causes great confusion. It is as though you have not even read what I posted.

Sorry, I got your posts confused with stapel's posts.

I hardly know what to say. I never said that "n" and "k" were interchangeable, either. :shock: