1

Set X = {1, 2, ..., n} where n>200

Can I find relation R such that there are n-1 pairs? How about n, n+1, n+2, n+3 and n(n-1) pairs?

If not, how would I prove that there can not exist equivalence relation R such that the number of pairs is one of the above quantities without using contradiction or contrapositive proof?

I've thought about a relation where (x-y)=1 for n-1, but I don't believe its reflexive so its not an equivalence relation.

Andrés E. Caicedo
  • 79,201
George
  • 63
  • 1
    Well, in any equivalence relation we must have $a\sim a$ for every element in the set so... – lulu Apr 02 '20 at 19:40
  • Do you have any specific examples for the other ones (n-1, n+1, etc)? – George Apr 02 '20 at 19:43
  • Please edit your post to include your own efforts. My hint should settle some of those questions instantly (not all of them though). If you are stuck, I suggest trying it with a smaller set. Say $3$ elements or so. – lulu Apr 02 '20 at 19:44
  • I'm still stuck on n-1 case. I can find a relation that works, but not an equivalence relation. I'll keep in mind what you said about a~a. – George Apr 02 '20 at 19:50
  • It sounds like you still might be stuck on the $n-1$ case... let's maybe take a break from that and talk about the $n$ case... Can you think of an equivalence relation with exactly $n$ pairs in it over the set $X={1,2,\dots,n}$? What does that equivalence relation look like? Do you see why there is only one possibility for such an equivalence relation? Do you see why each and every one of those $n$ pairs must be in every equivalence relation? Now, back to the $n-1$ case, if there were $n-1$ pairs do you see why at least one of the $n$ pairs from the previous relation must be missing? – JMoravitz Apr 02 '20 at 19:56
  • Next, for the $n+1$ case... if we take the $n$ absolutely necessary pairs from the $n$ case... and add only a single additional pair $(a,b)$ that wasn't previously present, but didn't add $(b,a)$, is it still an equivalence relation? How about for adding a second and third as well? As for a hint for the final case... can you reason why the most possible pairs in an equivalence relation might happen when everything is related to everything? Can you reason why the second most possible pairs would be where everything but one thing were related to everything but that one thing? – JMoravitz Apr 02 '20 at 19:59
  • For the n case, im was just thinking R is set of (x,x) where x=x. Is that invalid? Thinking of less than or equal to for the final one, but does that guarantee symmetry? – George Apr 02 '20 at 21:01

0 Answers0