Let $A$ be a finite set so: $|A|=j$ and $S$ a relation on $A$.
Prove that there are $i,j\in \mathbb{N}$ that $i>j$ and $S^{i}=S^{j}$.
I tried to prove it with the definition, but without any success.
Asked
Active
Viewed 122 times
0
-
Didn't $A$ happen to be finite? – Berci Nov 25 '17 at 12:08
2 Answers
2
This does not have to be true if $\mathbb N$ is allowed to be unfinite.
If e.g. $A=\mathbb N$ and $nSm\iff m=n+1$ then $nS^im\iff m=n+i$ and $i\neq j\implies S^i\neq S^j$.
edit (after edit of question). If $A$ is finite then the number of relations on $A$ is finite so the function on $\mathbb N$ to the set of relations on $A$ prescribed by $i\mapsto S^i$ cannot be injective. This means that $i,j\in\mathbb N$ must exist with $i>j$ and $S^i=S^j$.
drhab
- 151,093
-
-
If $X$ is infinite and $Y$ is finite then a function $f:X\to Y$ cannot be injective. Do you understand? – drhab Nov 26 '17 at 10:13
-
I can't find a proof for this theorem. I only found that if $X$ and $Y$ are finite sets and if there is an injective function so $|X|=|Y|$ – kicklog Nov 26 '17 at 10:24
-
Can you prove yourself that e.g. a function $f:\mathbb N\to{0,1,2}$ is not injective? This purely on base of the definition of injectivity. – drhab Nov 26 '17 at 10:30
0
Suppose not, then for all $i$ and $j$, $S^i\neq S^j$. But now $S^i\subseteq A\times A$ for all $i$, and how many subsets can $A\times A$ even have?
Asaf Karagila
- 393,674
-
I think that it has $2^{n^{2}}$ but how does it help us in solving the problem? – kicklog Nov 26 '17 at 09:54
-