• Support PF! Buy your school textbooks, materials and every day products Here!

Need help with proof of sets of integers

  • Thread starter Ethers0n
  • Start date
  • #1
27
0
1.From the problem statement
Let Z+ be the set of all positive integers; that is,
Z+ = {1,2,3,...}
Define Z+ x Z+ = {(a1, a2) : a1 is an element of Z+ and a2 is an element of Z+ }




2. If S is contained in Z+ and |S| >=3, prove that there exist distinct x,y that are elements of S such that x+y is even.



3. I need some help on where to start as I'm quite lost.
I can see how this would be true. for example the set S = {1,2,3,4}
The pairs (1,3) and (2,4) both satisfy the condition of x+y being even.


the are extensions of this homework problem as well, but I'm having trouble with the first bit...
 

Answers and Replies

  • #2
exk
119
0
Try proof by contradiction:

Assume that there are no elements x,y in S such that x+y is even and see where that leads you.

You may want to note that since S has to contain 3 or more elements these can be all odd, all even or a combination. If they are all odd then adding two of them gives an even. if they are all even then adding any two gives an even and if it's a combination then once again combining two of them gives an even integer.
 
  • #3
27
0
how does this sound?
there is a set S with three elements that are integers. Assume that any two of these elements are added together and always produce an odd value. (ie x1+x2 or x1+x3 or x2+x3 is always odd).

assuming that all three elements of S have even values, take the sum of any two of these elements.
k is even which makes k+2 even.
k+k+2 = 2k+2. This value is even
k+2 is even which makes k+2+2 even also.

k+2+(k+2+2) = 2k+6. This value is even.

assuming that all three elements of S have odd values, take the sum of any two of these elements.
k is odd which makes k+2 odd.
k+k+2 = 2k+2. This value is even
k+2 is even which makes k+2+2 even also.

k+2+(k+2+2) = 2k+6. This value is even.

next assume that the set of S has elements some of which are even and some of which are odd.
if two of the values are even, sum those two values. the result will be an even number.
if two of the values are odd, sum those two values. the result will be an even number.

Therefore, the original assumption that any two elements of S that are summed will produce an odd value is false.

how is that?
the third criteria seems weak.
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,770
911
You didn't actually use your assumption that "any two of these elements are added together and always produce an odd value" so you might as well drop that: what you did was break the situation into cases: three members odd, three members even, 2 even and 1 odd, 1 even and 2 odd.
 
  • #5
27
0
ok
so it's not really a proof by contradiction then.
is it still sufficient though?
I still feel like the wording could be better.
 

Related Threads for: Need help with proof of sets of integers

Replies
11
Views
3K
  • Last Post
Replies
4
Views
9K
  • Last Post
Replies
12
Views
441
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
5
Views
838
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
769
Top