# Composition of Relations`

Note: this isn't a HW question. I'm doing problems from the book "Invitation to Discrete Mathematics- Jirí Matousek, Jaroslav Nesetril"

The following is the question:

I tried by contradiction but couldn't make any progress.

Any help is highly appreciated.

• What definition do you use for relation?
– Joe
Sep 16, 2019 at 9:34
• I didn't get your question @Joe Sep 16, 2019 at 10:05
• I was going to see if you said, “A subset of $X \times X$”, then ask you how many subsets there are, but @Berci gave you the answer.
– Joe
Sep 16, 2019 at 11:25
• @Joe thought you needed some clarification Sep 16, 2019 at 12:42
• Note: This is still a homework question, even if you set it for yourself. As such, it is still preferred that you show what you have tried so we might see where you are actually having trouble. Sep 17, 2019 at 23:28

Since $$X$$ is finite, so is the set of its possible relations, $$P(X\times X)$$ (with cardinality $$2^{|X|^2}=:N$$), so any sequence of at least $$N+1$$ relations over $$X$$ must contain a repetition.
So does in particular the infinite sequence $$R, R^2, R^3, \dots$$.