# Questions tagged [relation-algebra]

A relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the set of binary relations on a set X, that is, the set of subsets of X^2.

11 questions
Filter by
Sorted by
Tagged with
241 views

### Universes from sets of logical relations

Consider any set $I$ and any logical structure $L$. Let $R$ denote some set of $I$-relations over $L$, i.e. each element $r\in R$ sends each $I$-tuple $(x_i)_{i\in I}$ of elements $x_i\in L$ to a ...
• 409
123 views

• 2,371
1 vote
67 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 ...
• 2,371
538 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,371
1 vote
79 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 ...
593 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 ...
• 802
5k 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 ...
368 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
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)$ ...