The type of transitive relations [closed]

Question

Let $A$ be an infinite set and $R$ be a transitive relation on $A$ such that sets $\{a:(a,y)\in R\}$ and $\{a:(x,a)\in R\}$ are finite for any $a\in A$. What does $R$ look like?

Answer 1

Interesting question, I'm assuming you arrived at it by thinking about some possible relations, and realising that transitivity seems to force those sets to be infinite, for example the "less than" operator on $\mathbb N$

Since $1<2$ and $2<3$, and so on, for transitivity to hold every number must be less than all of its successors, and so those sets you described are all infinite

But there are ways around this (2 that I can think of)

Let $$ R := \{ (a,b) \in \mathbb N × \mathbb N | a = b\}$$

Indeed, $|[R]_a| = 1$ for all $a \in \mathbb N$

And it is trivially transitive

A more exciting example could be

$R^k := \{(a,b) \in \mathbb N × \mathbb N| a//k = b//k\}$

For some $k\in \mathbb N^+$ Where "//" denotes floor division

This works because it "groups" together subsets of size $k$ in $\mathbb N$

So if k = 5, then the numbers 0-4 all appear together in all there permutations, and with nothing else, 5-9 same thing, etc.

A subset of this relationship could contain only cycles within these groupings

For uncountably infinite sets its a bit harder, since grouping intervals in the reals analgous to our second example won't work because each point will appear in a k-ball with infinitely many others, I'f you don't require that every point appears at least once in the relation, then the above examples still work since $\mathbb N \subset \mathbb R$, if you do require that, then I'm not sure, I don't think $\mathbb R$ can be covered by infinitely many finite discrete cycles for example