# Questions tagged [relation-algebra]

The tag has no usage guidance.

9 questions
4k views

### Why is Set, and not Rel, so ubiquitous in mathematics?

The concept of relation in the history of mathematics, either consciously or not, has always been important: think of order relations or equivalence relations. Why was there the necessity of singling ...
471 views

### 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}\}$?

Given any finite relation $R$ if we let $\circ$ denote relation composition and define $R^n=\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}$ then does there exist an explicit formula for the ...
527 views

### Categories with binary relations as objects

For the category of functions, pairs of functions making commutative diagrams are the canonical morphisms $\alpha:f\rightarrow g$. For binary relations there is an alternative, to consider the ...
335 views

### Why is a UNION operation independent in relational algebra?

Why is a set union operation independent in relational algebra? Why it cannot by expressed by the other four basic operations (selection, projection, cartesian product and difference)? What kind of ...
431 views

### Calculus of Binary Relations

I was reading "Origins of the Calculus of Binary Relations" by Vaughan Pratt where he says "it consists of two components, a logical or static component and a relative or dynamic component" but it ...
56 views

### Generalizing cycle/pseudo-tree factorizations for permutations/transformations to arbitrary binary relations

It's well known every permutation has a unique factorization into disjoint cycles (up to a re-ordering of these factors since they commute), while similarly it can be shown that every transformation ...
69 views

### The relation on the set of functions

Let $\varphi: \mathbb{R}^{2} \to \mathbb{R}$ be a symmetric (not necessarily continuous) function (so, $\varphi(x,y)=\varphi(y,x)$ $\forall (x,y)\in \mathbb{R}^{2}$), let $\mathcal{F}$ be the set of ...
Let G be a [ CF ] grammar, and let elements of semiring be sets of rules. Define multiplication as: $$x\otimes y = \{ t| \exists r \in x \exists s \in y (t=subst(r,s))\}$$ where $subst(r,s)$ ...
### Group associated to the monoid $({\cal P}(X\times X), \circ)$
Consider the set ${\cal P}(X\times X)$. It can be endowed with a binary operation $\circ$ where $$A\circ B = \{(a,b)\in X\times X:\exists z\in X((a,z)\in A\land (z,b)\in B)\}.$$ Note that \$\Delta_X=\{...