Name for "lower/upper bounds" of arbitrary relations?

Question

Given a partial order $R_{\leq}$ over a set $D$, the set of upper bounds under $R$ of a subset $S$ of $D$ is commonly defined as $\{ y \in D | \ \forall x\in S, x R y \}$.

(The set of lower bounds of $S$ may be defined as the set of upper bounds of $S$ under the converse relation $R^{-1}$)

Is there a common name for the generalization of this notion where $R$ is not a partial order, and is possibly a heterogenous relation between domain $D$ and codomain $D'$ (hence the $y$ would be elements of the codomain)? This would be a subset of the image of $S$ under $R$ (and conversely, the dual notion would be a subset of the preimage).

Answer 1

If your relation is at all order-like, then I would recommend just staying with the upper/lower bound terminology. And unless I misunderstand you, the example you describe is actually a (strict) partial order, no? If the relation only goes from disjoint sets D to D', then this is (vacuously) transitive, irreflexive and assymetric.

But in general, every binary relation is ultimately a directed graph. In this case, you would say that y is a common direct successor (or common target) of the elements of S if x R y for all x in X. And y is a common direct predecessor if y R x for all x in S.

If your relation is a tree, in one direction or the other, then you could use the common parent and common child terminology.

Answer 2

In a pre-order $\prec$ (or a category) one can speak of initial objects $0$, or terminal objects $1$, meaning that $0\prec x$ for all $x$ --- (or $0\rightarrow^! x$ ) --- which also gives the notion of a universal object under several. E.g., among objects preceding both of $b_1,b_2$, with the restricted relation $\{(a_1,a_2)|a_1\prec a_2 ,a_i\prec b_j\}$ one can talk again about maximal objects and terminal objects, either of which notions might make a sensible candidate for "greatest lower bound" in this setting.

If you're not assuming the relation is transitive, you might want to take a (possibly graded category) transitive closure, or look at "transitive neighborhoods", or even just immediate neighborhoods as suggesed by Joel David Hamkins.

Of course, this is all quite speculative; I've not done any work where this notion was wanted.

Answer 3

You might look at Galois connections arising from relations between sets or even classes. The common example is between subgroups of a group of automorphisms of a field, and subfields of that field fixed by those automorphisms, stemming from the relation "(phi,k) iff phi(k)=k" There are many other examples however arising from a general relation, one of which is "(id,mod) iff the identity id is satisfied in mod, a model of the appropriate language" . One looks at closed classes which turn out to be equational theories along with varieties of universal algebras, and these arise from the Galois connection stemming from the above relation of satisfaction.

When you study Galois connections, the generalization of your upper bound is "closed" or "Galois-closed under the relation" .

Gerhard "Ask Me About System Design" Paseman, 2010.01.23