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.
14 questions
3
votes
1
answer
148
views
Two definitions of indecomposability for binary relations
Let $X$ be a set. If $A\subseteq X$ and $R\subseteq (X\times X)$, we say that the relation $R$ is shrinkable to $A$ if there is an injection $\iota: X \to A$ such that $$(x,y) \in R \text{ if and only ...
- 56.5k
15
votes
0
answers
835
views
Indecomposable binary relations
Let $X$ be a non-empty set. We say that a relation $R \subseteq (X \times X)$ is shrinkable to $A \subseteq X$ if there is an injection $f:X \to A$ with $(x, y) \in R$ if and only if $(f(x), f(y)) \in ...
- 56.5k
1
vote
0
answers
40
views
Aggregation relationship in class diagram
How do you transform an aggregation relatinship between to classes in a class diagram (1 to many or many to many) into relational schema and is it needed/possible. Or is enough if we transform only ...
- 11
2
votes
0
answers
267
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 ...
- 329
4
votes
0
answers
177
views
Terminology for the parts of composition?
In function composition, binary relation composition, or more generally category theory, are there distinct names for the two things being composed?
If we have $f:X \rightarrow Y$ and $g:Y \rightarrow ...
- 41
4
votes
1
answer
276
views
Characterizing relations by forbidden induced subsets
Working with relations in a purely set theoretic manner i.e. as just sets of ordered pairs, we see for any relation $R$ there exists unique inclusion minimal sets $A$ and $B$ such that $R\subseteq A\...
- 2,626
1
vote
1
answer
104
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,626
12
votes
1
answer
912
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,626
1
vote
0
answers
105
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 ...
- 11
2
votes
2
answers
745
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 ...
- 862
76
votes
14
answers
7k
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 ...
2
votes
1
answer
441
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 ...
- 21
1
vote
0
answers
202
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)$ ...
- 284
1
vote
2
answers
689
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 ...
