# Questions tagged [relation-algebra]

The relation-algebra tag has no usage guidance.

**66**

votes

**13**answers

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 ...

**7**

votes

**1**answer

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 ...

**2**

votes

**2**answers

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 ...

**2**

votes

**1**answer

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 ...

**1**

vote

**2**answers

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 ...

**1**

vote

**1**answer

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 ...

**1**

vote

**0**answers

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 ...

**1**

vote

**0**answers

141 views

### Substitution semiring?

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)$ ...

**-1**

votes

**1**answer

109 views

### 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=\{...