3
$\begingroup$

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

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ But perhaps you didn't intend that D and D' are disjoint, and in this case, your relation may not be a strict partial order. $\endgroup$ Jan 23, 2010 at 22:51
  • $\begingroup$ Correct me if I'm wrong, but aren't these called meet and join? If we only require the meet and join to be partial functions won't that give us a good enough definition? $\endgroup$ Jan 23, 2010 at 23:31
  • 1
    $\begingroup$ In a lattice order, the meet and join are the greatest lower bound and least upper bound, yes. But in the context of the question, the OP seems to entertain non-unique upper bounds, whereas I think meet and join usually imply uniqueness. $\endgroup$ Jan 23, 2010 at 23:49
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.