# Prove that the set of complete & transitive relations on a countably infinite set is uncountable

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?

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

## 1 Answer

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?

• 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? – bitter-sweet Sep 14 '16 at 14:38
• Which condition came closest to working? Is it close enough, or is the problem small enough to work around? – Chris Culter Sep 14 '16 at 17:29
• 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? – bitter-sweet Sep 14 '16 at 19:32
• 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? – Chris Culter Sep 14 '16 at 21:11
• 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.. – bitter-sweet Sep 14 '16 at 22:23