Disproving a statement about whole numbers

  • #1
177
9
Prove/Disprove: There exists ## a \in \mathbb{N} ## such that for all ## n,m \in \mathbb{Z} ## that satisfy ## n \cdot m = a ## then ## n > 0 \text{ or } m > 0 ##.

My attempt (The statement's false, here's proof by contradiction ):
Suppose There exists ## a \in \mathbb{N} ## such that for all ## n,m \in \mathbb{Z} ## that satisfy ## n \cdot m = a ## then ## n > 0 \text{ or } m > 0 ##.
Let ## n,m \in \mathbb{Z} ## be arbitrary such that ## n \cdot m = a ##, then also ## n > 0 \text{ or } m > 0 ##.
## \underline{ \text{Case I , } } m < 0 ##:
In this case, since ## n \cdot m = a ## then ## n < 0 ## ( since ## a ## is a natural number )
Therefore ## n,m ## are negative, therefore it isn't true that ## n > 0 \text{ or } m > 0 ##, a contradiction.
Q.E.D

Is this disproof correct?
Also, My instructor said I should've had to "Choose ## a ##" and that therefore my disproof is not correct.
However I don't agree with him since I've assumed that there exists ## a ## then it is not correct to choose a value for ## a ## ( In my disproof ).

Note: I understand I can disprove the statement directly by explicitly choosing a value for ## a ## , but such disproof is different from what I did and I want to know if what I did is correct.
 
Last edited:

Answers and Replies

  • #2
35,442
11,883
You didn't prove anything. You just assumed that there is an m<0.

There is a much simpler approach. You can explicitly give n,m to show it's wrong.
I understand I can disprove the statement directly by explicitly choosing a value for a
No you cannot. You cannot disprove "there is a natural number such that..." by saying "but it's not true for 5235".
 
  • #3
177
9
You didn't prove anything. You just assumed that there is an m<0.

But why? In the case where ## m < 0 ## then the only way ## n \cdot m = a ## can be positive is if ## n < 0 ## and this is in contradiction to ## n > 0 \text{ or } m > 0 ##
( I know the other approach, but I want to practice this one. )

Looking more closely ( Please tell me if I'm right ) there was in fact a contradiction but it contradicted the assumption that ## m < 0 ## ? ( and so it did not contradict ## n > 0 \text{ or } m > 0 ## for arbitrary ## n,m ##)
 
Last edited:
  • #5
177
9
The case ## m < 0 ## is just an assumption. when I assume it, I arrive to concluding that ## n < 0 ## , but that is in contradiction to ## n > 0 \text{ or } m > 0 ## . Therefore since my assumption was ## m <0 ##, then this assumption is contradicted and nothing more, therefore I proved nothing ( besides the fact that ## m ## cant be negative ).

Is this better? or am I completely off?
 
  • #6
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,552
587
Yes, all you have proven is that if nm=a, m must be positive.
 
  • #7
177
9
Thanks, I've been doing such mistake in other proofs without noticing...

Doing the same methodology for ## n ## , I also get that if nm=a, n must be positive.
So basically I'm stuck with my attempt of disproving the statement.

Another question:
If I were to find a contradiction for the cases where I assume ## m < 0 , n < 0 , m \geq 0 , n \geq 0 ## ( doing 4 cases in my disproof )
Only then I would've found a contradiction for ## n > 0 \text{ or } m > 0 ## for abritrary ## n , m ## ( since I've exhausted all cases )?
 
Last edited:
  • #8
659
538
Just the two cases, ##m<0, m\geq0## is exhaustive.

The point is one of those cases must be true. So if you find neither can be true, then there is a contradiction.

If you wanted to do cases with ##m## and ##n##, they would be ##(m<0 \wedge n<0)##, ##(m<0 \wedge n\geq0)##,## (m\geq0\wedge n<0)##, ##(m\geq0 \wedge n\geq0)##. So that only one of them can be true.
 
Last edited:
  • #9
Stephen Tashi
Science Advisor
7,664
1,500
So basically I'm stuck with my attempt of disproving the statement.

Trying to prove the negation of a statement using indirect proof can be confusing. You are dealing with a statement of the form "##\exists a.....\forall n \forall m ....##". The negation of a statement of that form has the pattern "##\forall a ....\exists n \exists m....##".

A direct proof of the negation using the method of "universal generalization" could begin:
"Let ##a## be a given natural number."

case 1: ##a \ne 0##.

Now you must show the existence of numbers ##n,m## such that ##nm = a## and ( ##n \le 0## or ##m \le 0##). Hint: ##n = -a## exists.

case 2: ##a = 0## etc. (Only needed if your course materials allow zero to be included in the natural numbers.)
 
  • Like
Likes Jarvis323 and CGandC
  • #10
trees and plants
Find a counterexample, make a question like:what if i put two specific values for n and m and disprove the statement for an ##a \in \mathbf{N}## ?
 
  • #11
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,552
587
The other question is:why not ask more interesting and difficult questions than this one

If you can't answer this question, you won't be able to understand more complicated stuff in a serious way. Understanding how to do proofs is not trivial, and based on some of your other posts I would guess a more basic proofs class would help solidify your understanding of math as well.
 
  • #12
mathwonk
Science Advisor
Homework Helper
2020 Award
11,154
1,349
the basic lesson of proofs is to learn first about the language of "propositional calculus" or predicate calculus. You need to learn how statements are composed using "logical connectives" like 'and', 'or', 'if-then', 'not', and then the "quantifiers" such as "for all", and "for some" = "there exists". And you must learn to form the "negation" of a statement, i.e. to form a statement equivalent to your statement being false.

E.g. your statement problem above, has the form: there exists a natural number a, such that, for all integers n,m, if nm = a, then either n>0 or m>0. This is false, so we want its negation.

the negation of a statement like this: "there exists a in N such that: for all n,m in Z, P is true",
is the statement: "for all a in N, there exist n,m in Z, such that P is not true". I.e. you change each quantifier into the other one, but keeping their respective order, and then negate the following statement P.

So now we have to know how to negate the statement P:
"if nm=a, then either n>0 or m>0". The rules of logic say that the negation of "if A is true, then B is also true", is the statement: "A is in fact true, but B is not true".

So in our case the negation is "nm=a, but neither of n nor m is >0."

So we must prove: "for all a in N, there exist n,m in Z, such that nm=a, but neither n nor m is >0."

This is "easy". Just think of ways to factor any positive a, using two negative numbers n,m.

The hard part is mastering the use of the logical language. but it is very useful to do so. I myself learned this stuff in high shool from the book Principles of mathematics, by Allendoerfer and Oakley, probably out of print. The first edition of the book Geometry, by Harold Jacobs, also possibly out of print, had a nice chapter on logic, which was unfortunately essentially removed in later editions. But surely many other more recent books on proofs contain this material. It is absolutely fundamental.
 
  • #13
35,442
11,883
Find a counterexample, make a question like:what if i put two specific values for n and m and disprove the statement for an ##a \in \mathbf{N}## ?
That's the approach I suggested in post 2, and Stephen Tashi made it more obvious how to choose them.
 
  • #14
177
9
The logical format of the statement is:
## \exists a \in \mathbb{N} . \forall n,m \in \mathbb{Z} ( n \cdot m = a \rightarrow (n>0 \lor m>0) ) ##
The negation of it is:
## \forall a \in \mathbb{N} . \exists n,m \in \mathbb{Z} ( n \cdot m = a \land (n \leq 0 \land m \leq 0) ) ##
If I were to disproof I'd prove the negation. I would say something like:
Let ## a \in \mathbb{N} ## be arbitrary. Chose n = ( some value ) , m = ( some value ) , ... ( showing that the following is satisfied: ## n \cdot m = a \land (n \leq 0 \land m \leq 0) ## )

The reason I a-priori chose to prove the way I did was not just to prove the statement but actually to intricately get stuck in the little details of logic in order to learn more because I learned alot from the mistakes I did here. For example, just yesterday I learned that in order to prove that two graphs aren't isomorphic, If we assume there does exist an isomorphism then we have a lot of cases in which the isomorphism can be one out of many options, and for each of these options you need to find a contradiction in order to fully contradict the statement that there is isomorphism between the two graphs ( and many students thought that it is sufficient only to find 1 contradiction which is the same mistake I did in my question here )
Proof theory actually is not being taught anywhere in my country ( not in high schools and not in universities, only a few colleges ) which is unfortunate, so I self-studied proof methods but sometimes you get stuck on problems that you can't figure out on your own without someone expert assisting you.
 
  • #15
mathwonk
Science Advisor
Homework Helper
2020 Award
11,154
1,349
your logical statements seem perfect. in the proof i would say, let a>0 be arbitrary, and then let n = -a and m = -1. then nm=a, but n≤0 and m ≤0. QED.
 
  • #16
Mark Harder
Gold Member
241
59
Proof by contradiction is overly complicated and you don't need to make any assumptions about a, n and m or break the proof into separate cases. The disproof derives from the facts that a is a natural number and so must be positive, while its factors n and m are drawn from the integers, which can be negative. Since any positive number can be the product of two numbers <0, there is no nonprime natural number for which one or both factors must be >0.
 
  • #17
35,442
11,883
there is no nonprime natural number for which one or both factors must be >0.
There is also no prime number where this would be different. No need to make such a distinction.
-1 might not be the most interesting integer to multiply with, but it's still an integer.
 
  • #18
40
6
Prove/Disprove: There exists a∈N such that for all n,m∈Z that satisfy n⋅m=a then n>0 or m>0.

The statement is false. Pick a = 4, then for all n, m that satisfy n*m = 4, n > 0 or m > 0. If n = -2 and m = -2, then n*m = 4, but neither of them is bigger than 0.
 
  • #19
1,961
1,209
Have we even yet decided whether ##0 \in \mathbb N## (by which I mean is zero a natural number)?
 
  • #20
496
68
That's a matter of notational convention. In some books (or in some sub-fields) it is almost default to refer to ##\mathbb{N}## to mean ##\{0,1,2,3,4,5,.....\}##. And in that case ##\{1,2,3,4,5,.....\}## is referred to with ##\mathbb{N}^+##.

But this doesn't seem to be universal by any means, since even a number of recent texts refer to the set ##\{1,2,3,4,5,.....\}## with ##\mathbb{N}##. So it is based on context.
 
Last edited:
  • #21
35,442
11,883
The statement is false. Pick a = 4, then for all n, m that satisfy n*m = 4, n > 0 or m > 0. If n = -2 and m = -2, then n*m = 4, but neither of them is bigger than 0.
You contradicted yourself. You found an example disproving the "for all n,m" statement preceding it. Therefore a = 4 is not a counterexample.
Have we even yet decided whether ##0 \in \mathbb N## (by which I mean is zero a natural number)?
Doesn't change the result. We can even write the (dis)proof in such a way that it works for both definitions.
 

Related Threads on Disproving a statement about whole numbers

Replies
1
Views
274
  • Last Post
Replies
3
Views
1K
Replies
8
Views
248
Replies
3
Views
148
Replies
9
Views
376
Replies
55
Views
4K
Replies
2
Views
103
Replies
83
Views
14K
Top