Mathematics desk
< January 6	<< Dec \| January \| Feb >>	January 8 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 7[edit]

is this a sound proof?[edit]

Is the following a sound proof? I'd like to prove that there is no largest integer.

Firstly, suppose there were a largest integer. Let's call this L, for "Largest". Without loss of generality, let's say for example it's one million thirty-six, that this is the largest integer and there is no larger one.
Add 1 to L to arrive at a new candidate number, C. In our example, it would be one million thirty-seven.
Since L + 1 is greater than L, therefore the candidate C (which was L+1) must be larger than L.
Therefore L could not have actually been the largest, since without making any other assumptions except that it is the largest, we have constructed a larger candidate and proved it is larger. We were simply wrong that L was the largest.

Since this applies to any potential largest integer, L, therefore there really cannot be such a thing.

In other words, this doesn't just apply to a million thirty-six, but for any number. For example a million eighty-seven. (Or any other number we suppose might be the largest integer.)

It is a simple contradiction to state that there is a largest integer, L. There is no such integer.

Is this argument basically sound? 212.96.61.236 (talk) 02:34, 7 January 2015 (UTC)[reply]

It might be; to do this sort of thing properly, you need to specify what set of axioms you're working from. Step 2 assumes that it's always possible to add 1 to an integer and step 3 assumes that the result is always a larger integer. If you are assuming some version of the Peano axioms including axioms of ordering, then you can indeed make those statements. --65.94.50.4 (talk) 05:45, 7 January 2015 (UTC)[reply]

Would it work at the level of formality (rigor) usually adopted by mathematicians? (Albeit it can be a bit too explicit.) Or would it need to be more explicit to be made as above at all? 212.96.61.236 (talk) 07:55, 7 January 2015 (UTC)[reply]

That depends on what you mean. Is the above rigorous enough in the sense of people not interested in foundations, yes, its a basic result - if anything, it is overdone, "Assume n is the largest integer, n + 1 > n, contradiction." would work just as well. If you're asking if it is rigorous enough to be considered a proof from axioms, no, not really - however, given standard axioms and your proof, it is obvious how they relate; so, it's not really a problem. If you, however, want a fully formal rigorous proof from basic axioms, then, no, you haven't provided that -- but, unless you have a reason to want one, or just for fun, I don't see the point of bothering (especially for something simple).Phoenixia1177 (talk) 08:40, 7 January 2015 (UTC)[reply]

The proof works at the ordinary level of formality (= informality) used in everyday mathematics. Rarely do authors run to the axioms, but it may be instructive to do it in a case like this where the informal proof is easy. YohanN7 (talk) 10:43, 7 January 2015 (UTC)[reply]

It certainly wouldn't work for some machine where the largest positive integer is 2³¹−1 = 2147483647 and if you add 1 you get the large negative number −2³¹ = −2147483648. Dmcq (talk) 10:13, 7 January 2015 (UTC)[reply]

Yes, that isn't relevant on its own - it is true if the goal is a fully formal proof from axioms, then one needs be real specific. However, mathematicians say, "Let n be an integer", etc. all the time, without any real specification - if the goal is just to provide a proof that there is no greatest integer then, while verbose, the above does the job (it could be rewritten to sound more mathematical, but that's not really the point).Phoenixia1177 (talk) 10:31, 7 January 2015 (UTC)[reply]

I would also criticize your use of "Without loss of generality", as you very much are throwing away generality. If you wish to include a specific number to aid in understanding, just say, "Let's say for example it's one million thirty-six, that this is the largest integer and there is no larger one." Invoking WOLOG, as mathematicians use it, would mean that it is sufficient to prove that one million thirty-six is not the largest integer, and that is clearly not what you are asserting. -- ToE 13:28, 7 January 2015 (UTC)[reply]

This is symptomatic of people encountering the phrase wlog but never being explicitly taught what exactly it means. So they apply it where it is not appropriate.

In Hebrew, the phrase for wlog translates roughly as "without the limitation of generality". For a while I thought this should be read as "screw generality, we're not going to let it limit us". I think only after I encountered it in English I realized that it is us who are not limiting generality. -- Meni Rosenfeld (talk) 14:10, 7 January 2015 (UTC)[reply]

Ha! -- ToE 11:26, 8 January 2015 (UTC)[reply]

I agree that it shouldn't be used, but not for the same reasons. There is nothing gained by using a specific number - unless you are unused to using n for some arbitrary number, this is why it makes it look like an example - thus, it just seems out of place. However, I don't think it is an inappropriate use, the proof is easily adapted to the general case, indeed, the exact same logic applies - and this fits with the examples used in the article linked to too - however, as I said, it aids none and looks more like it is attempting to be illustrative than anything else, this makes it seem to sit wrong. It works a lot better, in other cases, because it removes the need for introducing clunky terms or using unpleasant notation (Like with "Wlog assume x <= y", it's more straightforward than two identical proofs or some contrived way to carry around both cases - but, here, it's extraneous, and that makes it awkward).Phoenixia1177 (talk) 17:59, 7 January 2015 (UTC)[reply]

I think the criticism of WLOG is wrong. There are two parallel proofs that I presented. One uses L for the number, the other uses one million thirty-six without loss of generality. This makes the proof stronger, not weaker. For example, here is the example the without loss of generality article gives:

“

To prove: "If three objects are each painted either red or blue, then there must be two objects of the same color." Proof: "Assume without loss of generality that the first object is red. If either of the other two objects is red, we are finished; if not, the other two objects must both be blue and we are still finished."

”

This is how it reads in my parallel construction:

If there are three objects, they can be enumerated 1, 2, and 3.
Their colors are C1, C2, and C3.
Let us start with C1, and its opposite color OC1. Without loss of generality, we could say C1 is Red for example. The opposite color (OC1) is blue then.
If either C2 = C1 or C3 = C1 then the colors of two objects match. (In our example if either C2 or C3 is red - then two objects, C1 and the one that is red, have matched)
If neither C2 = C1, nor C3 = C1 then they both must be a color other than C1. Since there are only two possible colors, they must therefore both be of the color OC1. Since they are both OC1, they both match. (In our example, if neither C2 nor C3 is red, then they must both be a different color. Since there are only two possible colors, the different color must be blue, and therefore they are both blue and thus match.)

You see, we have two parallel constructions here. One is a proof using symbols, another using an example without loss of generality. This aids, does not hinder, the quality of the proof in my opinion. For example, only in the first half of my version is the construction of the 'opposite color' invoked. It's not necessary if you use a WLOG argument, as you do not need to refer to the other color symbolically. So, I disagree with you guys and simply believes that I added to the strength of my proof by including a WLOG argument alongside the symbolic one. 212.96.61.236 (talk) 22:47, 7 January 2015 (UTC)[reply]

What ToE complained about is not the use of a "wlog argument". It was the use of the phrase "wlog". If you did the whole thing exactly the same and simply omitted the words "Without loss of generality", it would have been better. What you've given is an example, not a "wlog argument".

Anyway, regardless of whether the use of an example (and the phrase wlog) was valid or not, there is simply absolutely no way that it made the proof stronger. Giving the proof symbolically is sufficient. There is nothing extra to be gained by adding an illustrative example.

In general, in formal logic a proof is either valid or not. There is no sense in providing two proofs and hoping that together they are stronger. -- Meni Rosenfeld (talk) 23:34, 7 January 2015 (UTC)[reply]

Meni, I am not a working mathematician, but I simply disagree with you completely. The words "without loss of generality" are a very important clue that the example, in fact, serves as a complete independent proof. (A fact which may not be obvious if not mentioned explicitly - after all it could just be an example - and it may not be a valid statement to add to all examples.) By the way it is not always clear exactly how the reader should apply "without loss of generality". You're asking the reader "to repeat this for anything else I could have picked as an example" and basically introduce their mental symbology without being explicit about it.

Let me show you exactly why I stand by this opinion.

The above proof I presented you guys is actually a trick. It's not rigorous enough. You can tell, because I can use the same exact format to convince someone who isn't paying that much attention:

“

I'd like to prove that there is no largest negative integer.

Firstly, suppose there were a largest negative integer. Let's call this L, for "Largest". Without loss of generality, let's say for example it's negative one million thirty-six, that this is the largest negative integer and there is no larger negative integer.
Add 1 to L to arrive at a new candidate number, C. In our example, it would be negative one million thirty-six.
Since L + 1 is greater than L, therefore the candidate C (which was L+1) must be larger than L.
Therefore L could not have actually been the largest, since without making any other assumptions except that it is the largest negative integer, we have constructed a larger negative integer candidate and proved it is larger. We were simply wrong that L was the largest.

Since this applies to any potential largest negative integer, L, therefore there really cannot be such a thing.

In other words, this doesn't just apply to negative a million thirty-six, but for any number. For example negative a million eighty-seven. (Or any other number we suppose might be the largest negative integer.)

It is a simple contradiction to state that there is a largest negative integer, L. There is no such integer. If there were, we could construct a larger one.

”

Now I used the EXACT same reasoning, and the exact same level of rigor. If someone really isn't paying attention, there is a good chance they will believe me.

But this time the proof is wrong. This time there is a largest negative integer: −1. If you add one to it, you get something that isn't a negative integer anymore.

There was a hidden assumption that "any negative integer plus one is still a negative integer". But this is not true at all.

This is blatantly obvious from the proof above. But suppose I had presented only the WLOG. Now someone could have not realized htis fact. Since, in fact, the example works quite well for negative one million thirty-seven. It really isn't the largest negative integer, and negative one million thirty-six is an easy counter-example that's bigger by one.

How is the reader supposed to figure this out? Symbolically, it's easy. With a WLOG argument you're asking the reader to come up with all cases, instead of relying on properties of the symbols. That makes corner cases quite a bit harder to spot.

So, I simply disagree. While a WLOG argument can be perfectly valid, in fact the combination of that with a symbolic proof is strongest of all.

Why prove things one way, when you can prove things and show them as well? One for the intuition and as an exercise, the other to keep from being sneaky. Both are rigorous. Use of both is best. 212.96.61.236 (talk) 00:21, 8 January 2015 (UTC)[reply]

You're contradicting yourself. By your own admission, with your so-called "wlog argument" it's difficult to see whether the argument is fallacious or not. If a valid argument is indistinguishable from an invalid one, it means that the method of argument is completely worthless as a way of obtaining truths. Hence the wlog argument is unnecessary.

Whereas, in the symbolic argument, again by your own admission, it's clearer whether the argument is valid or not. Hence, if a symbolic argument supports a claim, and the argument appears valid, we can be convinced of the truth of the claim. And, if the argument is written formally and we've verified its validity exactly, we can be sure of its truth*.

And again - I agree that giving examples is instructive and can make the proof easier to follow, but there's no basis for your claim that the example somehow makes the proof "stronger".

Finally, the term "wlog" is used in mathematics almost exclusively when there is symmetry in naming of objects, so choosing a particular naming is arbitrary and irrelevant and does not cause a loss of generality. In the color example, "red" and "blue" are just names with no semantics attached to them, so they are interchangeable. Whereas in the numbers example, "1000000" and "10" are very different things. It's not an arbitrary choice of names. By choosing 1000000 you are very much losing generality - claims that are true for 1000000, will be wrong for 10. And your own examples strengthen this point - the claim "if n is a positive integer, then n+1 is a bigger positive integer" happens to be true regardless of n, so the "wlog argument" seems to work. But the claim "if n is a negative integer, then n+1 is a bigger negative integer" works for -1000000 but not for -1. So choosing -1000000 "wlog" gives an ostensibly valid argument for a wrong conclusion. So the "wlog argument" is worthless, and it's not wlog at all.

*modulo some weird insights into the distinction between provability and truth, which I'm sure Trovatore will be happy to point out.

-- Meni Rosenfeld (talk) 02:34, 8 January 2015 (UTC)[reply]

I do think the use of wlog is acceptable, in that it is not wrong, since it applies with regards to the operations used, etc, and the general argument follows an, obviously, identical course. The problem with using it is that it gains you nothing and, indeed, just makes the whole thing clunkier. Consider: if you are presenting this to people who are comfortable with mathematics, then it looks like an example, clunky, and obfuscating (and pointless) - if you are presenting it to someone who is not comfortable with mathematics, the construct is confusing and it still feels like an example. In short, sure, you can use it, but it's not a great usage and, certainly, adds nothing (and definitely takes something away). Good math is like a good novel, it's not just the story that matters, but also how well it is written - you're telling a good story for the topic, but wlog is pretty bad writing in the way you've used it.Phoenixia1177 (talk) 11:53, 8 January 2015 (UTC)[reply]

When using WLOG, then either it has to be obvious that the assertion follows from the restricted case under consideration or it has to be shown explicitly. This is not entirely clear in your proof. It is just about as clear as the original, yet unproven, assertion to begin with, making the WLOG argument, well, murky at best. It doesn't help. There is a false impression that a proof that is easier to read is always easier to understand. This is not the case. The reader may well think he/she understands it because of added gibberish, while, in fact, he/she does not. There is also the risk of logical fallacy as pointed out above. YohanN7 (talk) 12:08, 8 January 2015 (UTC)[reply]

Regarding your "trick", that was addressed in the very first response to your question, where 65.94.50.4 said that to be rigorous you need to show that any integer n has a successor, n+1, and that the successor is always a larger integer, that is, that n+1 is an integer, and that n+1 > n. Dmcq gave an example of a set (not ℤ, the set of Integers that mathematicians deal with, but an integral data type from computer science), where n+1 < n for a n = 2147483647, and you now provided an example using a different set, the negative integers, where n+1 is not a member of that set, even though n=-1 is a member. Did that first response not answer your intended question? -- ToE 17:01, 8 January 2015 (UTC)[reply]