# 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

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?
• 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