I was going about this by trying to come up with a bijection between this set and the set of all infinite sequences of zeros and ones (like 010100....), which I know in uncountable. But I didn't have much success. Other thoughts on how to get started?

  • $\begingroup$ What is a complete relation? $\endgroup$ – bof Sep 14 '16 at 4:54
  • $\begingroup$ For any x and y, either xRy or yRx or both $\endgroup$ – bitter-sweet Sep 14 '16 at 14:34
  • $\begingroup$ So complete implies reflexive? or is it only for distinct x and y? $\endgroup$ – bof Sep 14 '16 at 20:52

It is enough to come up with an injection from the set of infinite sequences of zeros and ones into the set of complete and transitive relations.

So suppose you have a sequence like $(a_n)=(0,1,0,1,0,0,\ldots)$. You want to define a relation $R$ that depends somehow on $(a_n)$. You're going to say that $iRj$ if and only if... [something to do with $a_i$ and $a_j$]. Can you come up with a definition that makes $R$ complete and transitive? And is the mapping from sequences to relations injective?

| cite | improve this answer | |
  • $\begingroup$ I thought about the conditions ai>aj, aj>=aj, ai=aj, ai=aj=0, ai=aj=1. None of them work. Can you please give a further hint? $\endgroup$ – bitter-sweet Sep 14 '16 at 14:38
  • $\begingroup$ Which condition came closest to working? Is it close enough, or is the problem small enough to work around? $\endgroup$ – Chris Culter Sep 14 '16 at 17:29
  • $\begingroup$ Ok how about I keep the condition ai=aj=0, except that for sequences with ak=0 for exactly one value of k, I take the corresponding relation to be kRw for all w, and not mRn for any other m,n? $\endgroup$ – bitter-sweet Sep 14 '16 at 19:32
  • $\begingroup$ Well, if the condition requires $a_i=a_j$, then whenever $a_i\neq a_j$, we have that $i$ and $j$ are not related by $R$, which means $R$ isn't complete. What about the other conditions? $\endgroup$ – Chris Culter Sep 14 '16 at 21:11
  • $\begingroup$ Can't believe I missed that. Then ai>=aj is the candidate condition. This gives complete & transitive relations, but it isn't an injection because for eg. the relation corresponding to 'all zeros' and 'all ones' is the same.. $\endgroup$ – bitter-sweet Sep 14 '16 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.