If any binary relation $R$ is dense and irreflexive, then is the set: $R(a)=\{b\in\text{rng}(R):(a,b)\in R\}$ non-finite for any $a\in\text{dom}(R)$?

107 Views Asked by At

If for every binary relation $R$ one defines both $\text{dom}(R)=\bigcup_{(x,y)\in R}\{x\}$ and $\text{rng}(R)=\bigcup_{(x,y)\in R}\{y\}$ Then according to the answer here: https://math.stackexchange.com/a/2220928/499516 , the set $R(a)=\{b\in\text{rng}(R):(a,b)\in R\}$ should be non-finite for every single element $a\in\text{dom}(R)$. Where for review any binary relation $R$ is dense if and only if we have $xRy\implies\exists z:xRz\land zRy$.


However I can't seem to prove this unless I also assume $R$ is acyclic. I tried to show it by writing:

$$xRy\implies xRz_1Ry\implies xRz_2Rz_1Ry\implies xRz_3Rz_2Rz_1Ry\implies xRz_nR\cdots Rz_1Ry\\\implies xRz_n\land xRz_{n-1}\land xRz_{n-2}\land\cdots \land xRz_1\implies z_1,z_2,\ldots z_n\in R(x)\\\implies \underbrace{\{z_1,z_2,z_3,\ldots z_n\}}_{S_n}\subseteq R(x)$$

Therefore I know $R(x)\geq|S_n|$ for any $n\in\mathbb{N}$ however I can't assume $|S_n|=n$ since I might have that $z_k=z_j$ for some $j\neq k$ (unless I assume $R$ contains no cycles or something as this would force $z_nR\cdots Rz_1$ to be a path meaning each $z$ is distinct). So I'm not sure what other approach I should take to showing the set is non-finite and would be grateful for any help.

1

There are 1 best solutions below

1
On BEST ANSWER

I don't think it works, for exactly the reason you said. For example, the relation $R$ on $\lbrace 1, 2, 3 \rbrace$ given by $$R = \lbrace (1, 2), (2, 3), (3, 1), (2, 1), (3, 2), (1, 3) \rbrace$$ is irreflexive and dense, but the image of all three points is finite.