2
$\begingroup$

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:

enter image description here

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

Any help is highly appreciated.

$\endgroup$
5
  • $\begingroup$ What definition do you use for relation? $\endgroup$
    – Joe
    Sep 16, 2019 at 9:34
  • 1
    $\begingroup$ I didn't get your question @Joe $\endgroup$ Sep 16, 2019 at 10:05
  • $\begingroup$ 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. $\endgroup$
    – Joe
    Sep 16, 2019 at 11:25
  • $\begingroup$ @Joe thought you needed some clarification $\endgroup$ Sep 16, 2019 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 17, 2019 at 23:28

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Thanks, could you elaborate: "so any sequence of at least 𝑁+1 relations over 𝑋 must contain a repetition." $\endgroup$ Sep 16, 2019 at 11:21
  • 2
    $\begingroup$ Elaboration: Pidge-on-hole principle $\endgroup$
    – Berci
    Sep 16, 2019 at 15:12
  • 2
    $\begingroup$ it's actually typed pigeonhole principle @Berci $\endgroup$
    – user645636
    Sep 17, 2019 at 14:40
  • $\begingroup$ @Berci what do you mean by any sequence of N+1 relations? $\endgroup$ Oct 19, 2019 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .