Proof via contradiction

In summary: I mean, what does that have to do with anything?)That doesn't really make sense to me. Can any number in Z, (since that... I mean, what does that have to do with anything?)
  • #1

Homework Statement


For any integer n, let A(n) be the statement:
“If n 2 = 4k + 1 for some k ∈ Z, then n = 4q + 1 or 4q + 3 for some q ∈ Z.”

Use proof by contradiction to show that A(n) is true for all n ∈ Z.

The Attempt at a Solution


[/B]
the answer sheet says that since n !=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. I am confused why n!=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Why only those two examples? couldn't n = 4q+x where x = 0,2,4,5,6,7,... basically any integer that is not 1 or 3, since 'x' is defined to NOT be those with the proof via contradiction.
 
Physics news on Phys.org
  • #2
UOAMCBURGER said:

Homework Statement


For any integer n, let A(n) be the statement:
“If n 2 = 4k + 1 for some k ∈ Z, then n = 4q + 1 or 4q + 3 for some q ∈ Z.”

Use proof by contradiction to show that A(n) is true for all n ∈ Z.

The Attempt at a Solution


[/B]
the answer sheet says that since n !=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. I am confused why n!=4q+1 and n != 4q+3 implies that n = 4q or n = 4q+2. Why only those two examples? couldn't n = 4q+x where x = 0,2,4,5,6,7,... basically any integer that is not 1 or 3, since 'x' is defined to NOT be those with the proof via contradiction.
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##

Now which remainders for ##n## by division with ##4## are possible?
 
  • #3
fresh_42 said:
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##
yes i understand that, its just applying De Morgan's laws. But why does that imply that n=4q or n = 4q+2 ONLY? on the answer page it says "since n≠4q+1∧n≠4q+3, it follows that n = 4t or 4t + 2 for some t ∈ Z." My question is why do they say it follows that, that is the case? because how do we know n can be written in the form: n = 4q or 4q + 2 for some q ∈ Z? How do we know it couldn't be written as n = 4q+4 or something else?
 
  • #4
UOAMCBURGER said:
yes i understand that, its just applying De Morgan's laws. But why does that imply that n=4q or n = 4q+2 ONLY? on the answer page it says "since n≠4q+1∧n≠4q+3, it follows that n = 4t or 4t + 2 for some t ∈ Z." My question is why do they say it follows that, that is the case? because how do we know n can be written in the form: n = 4q or 4q + 2 for some q ∈ Z? How do we know it couldn't be written as n = 4q+4 or something else?
Sorry, I've edited my post while you posted yours. Consider the division of ##n## by ##4##.
 
  • #5
fresh_42 said:
You want to show ##n^2=4k+1 \Longrightarrow n=4q+1 \vee n=4q+3## by contradiction. This means we still have given ##n^2=4k+1## but assume ##(n=4q+1 \vee n=4q+3)## is false. So in order for an OR statement to be false, both components have to be false; otherwise the OR statement would be true. Now if ##(n=4q+1 \vee n=4q+3)## is false and so both have to be false, we assume ##(n\neq 4q+1 \wedge n\neq 4q+3)\,.##

Now which remainders for ##n## by division with ##4## are possible?
0,2,4,8,12,16,... so on right?
 
  • #6
UOAMCBURGER said:
0,2,4,8,12,16,... so on right?
Only ##0## and ##2##. Any other integer has another multiple of ##4## and is swallowed by ##q##. The multiple ##q## isn't specified and can be any. Now e.g. ##n=4q+7=4(q+1)+3=4q' +3## or ##n=4q+12=4(q+3)+0=4q''\,.## The entire statement is all about the remainders by division with ##4\,.##
 
  • #7
fresh_42 said:
Only ##0## and ##2##. Any other integer has another multiple of ##4## and is swallowed by ##q##. The multiple ##q## isn't specified and can be any. Now e.g. ##n=4q+7=4(q+1)+3=4q' +3## or ##n=4q+12=4(q+3)+0=4q''\,.## The entire statement is all about the remainders by division with ##4\,.##
That doesn't really make sense to me. Can any number in Z, (since that is what we are working with), be represented by 4q+x : x,z ∈ Z? Because it is for n ∈ Z.
 
  • #8
UOAMCBURGER said:
That doesn't really make sense to me. Can any number in Z, (since that is what we are working with), be represented by 4q+x : x,z ∈ Z? Because it is for n ∈ Z.
Yes, ##\mathbb{Z}## is a Euclidean ring, that means we have division with remainder: Given two integers ##x,y## there are always integers ##q,r## such that ##x=qy+r## with ##0\leq r < y##. Here we have given ##x=n## and ##y=4##. As I said, the specific value of ##q## isn't part of the statement, only its existence. The contradictory assumption is ## ... \neq 1,3## for all ##q\in \mathbb{Z}## as "for all" is the negation of "there is some", so we can use any ##q\,.##
 
  • #9
fresh_42 said:
Yes, ##\mathbb{Z}## is a Euclidean ring, that means we have division with remainder: Given two integers ##x,y## there are always integers ##q,r## such that ##x=qy+r## with ##0\leq r < y##. Here we have given ##x=n## and ##y=4##. As I said, the specific value of ##q## isn't part of the statement, only its existence. The contradictory assumption is ## ... \neq 1,3## for all ##q\in \mathbb{Z}## as "for all" is the negation of "there is some", so we can use any ##q\,.##
Right, but I don't understand what you mean in post #6.
What is clear to me so far is this: For any n ∈ Z, n can be written in the following way, n = x*y + r, where x,y,r ∈ Z also.
Now given (in this example) that n != 4q+1 and n != 4q+3, (this is where I'm confused), Why wouldn't it follow that n = 4q + r where r ∈ Z \ {1,3}, or even n = x*y + r as long as the two cases where (x,r) = (4,1) and (4,3) are left out?
 
  • #10
UOAMCBURGER said:
Right, but I don't understand what you mean in post #6.
What is clear to me so far is this: For any n ∈ Z, n can be written in the following way, n = x*y + r, where x,y,r ∈ Z also.
Now given (in this example) that n != 4q+1 and n != 4q+3, (this is where I'm confused), Why wouldn't it follow that n = 4q + r where r ∈ Z \ {1,3}, or even n = x*y + r as long as the two cases where (x,r) = (4,1) and (4,3) are left out?
Because we can choose ##q## in such a way that ##0 \leq r < y=4##. So we are left with the cases ##r \in \{\,0,2\,\}\,.## In all other cases, we simply choose another ##q## such that we have ##r<4## again.
 
  • #11
$$
\lnot \,(\,\exists\, q\in \mathbb{Z}\, : \,n=4q+1 \vee n=4q+3)
\Longleftrightarrow
(\,\forall q\in \mathbb{Z}\, : \,n \neq 4q+1 \wedge n\neq 4q+3)
$$
The "for all" quantifier allows us to change the value of ##q## as it is supposed not to hold for all of them.
 

1. What is "Proof via contradiction"?

"Proof via contradiction" is a method of proving the truth of a statement by assuming its opposite and showing that it leads to a contradiction or inconsistency, thereby proving the original statement to be true.

2. How does "Proof via contradiction" work?

This method works by assuming the opposite of the statement to be proven and then logically deducing a contradiction or inconsistency. If a contradiction is reached, then the original statement must be true.

3. What are the benefits of using "Proof via contradiction"?

One benefit is that it can be used to prove the existence of something without explicitly constructing it. It also allows for a more direct and concise proof compared to other methods.

4. When should "Proof via contradiction" be used?

"Proof via contradiction" is best used when the statement to be proven is difficult to directly prove or when other methods have been unsuccessful. It is also useful when proving existence or uniqueness of a solution.

5. Are there any limitations to "Proof via contradiction"?

One limitation is that it can only prove the existence of something, not its uniqueness. It also requires a certain level of logical reasoning and may not always be the most efficient method of proof.

Suggested for: Proof via contradiction

Replies
32
Views
1K
Replies
2
Views
815
Replies
10
Views
2K
Replies
14
Views
345
Replies
1
Views
687
Replies
12
Views
1K
Replies
3
Views
1K
Back
Top