6
votes
Accepted
Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?
$\newcommand{\N}{\mathbb{N}}$
Recall that Landau function $g(n)$ is the biggest possible $\mbox{lcm}$ of numbers wich sum up to $n$. It's asymptotic is well-studied.
I'll prove the following
$\textbf{...
- 6,476
5
votes
Why is Set, and not Rel, so ubiquitous in mathematics?
(With apologies for reviving an old question which already has many answers) here are two perspectives:
Ponder the fact that
$\mathsf{Set}$ is complete and cocomplete. $\mathsf{Rel}$ is not.
For ...
4
votes
Accepted
Characterizing relations by forbidden induced subsets
I am going to rephrase the question in terms of first order relational structures. I believe the answer will be sufficiently close to what you are looking for.
Let $L$ be the first order language ...
- 3,274
1
vote
Accepted
Generalizing cycle/pseudo-tree factorizations for permutations/transformations to arbitrary binary relations
The situation for binary relations is more complicated than for transformations. Of course your weak component relations can be further decomposed, but into what is less clear. The symmetric groups ...
- 38.6k
1
vote
Why is Set, and not Rel, so ubiquitous in mathematics?
One way to approach the concepts of "elements" (or "its") and "distinctions"
(or "dits") is to start with the category-theoretic duality between subsets
and ...
Only top scored, non community-wiki answers of a minimum length are eligible