2

If we define a partial order $\preceq _R$ on any set $A$ by $B\preceq_R C$ if and only if $B\subset C$ for subsets $B$ and $C$ of $A$. Then how would the term "smallest" be interpreted in this relation?

I ask this, because when we define the transitive closure of a relation we define it by saying that for a relation $R$ on a set $S$, the transitive closure of $R$ is the "smallest" set that contains $R$ and is transitive. I have been told that "smallest" here refers with respect to the partial order relation $\preceq_R$ defined at the beginning.

Could someone give an example of this and maybe explain how it should be interpreted. I am assuming we say $B$ is smaller than $C$ if $B\preceq_R C$. Is this the case?

Seeker
  • 3,594
  • Sure. There generically won't be a "smallest" element, since there may be multiple branches of the "tree" of comparisons (and it's only a partial order, so these minimal elements may not be comparable between branches). For example, just take two disjoint subsets... – Brevan Ellefsen Aug 24 '22 at 03:28
  • @BrevanEllefsen So we could restate the definition of a transitive closure as: The transitive closure of a relation $R$ on a set $S$ is the set $T$ such that $R\preceq_R T$ and $T$ is transitive? I don't see the need to specify "smallest" in the definition. – Seeker Aug 24 '22 at 03:40
  • 1
    No the transitive closure of $R$ is best defined as the intersection of all transitive relations containing $R$. This means that it is 'smaller' than any other transitive relation containing $R$ in the sense given by the partial order. – Fishbane Aug 24 '22 at 04:02
  • @Fishbane Oh right, So if $T_1$ is the transitive closure of a relation $R$ and $T_2$ is any other transitive relation containing $R$, then we have that $T_1\preceq_R T_2$. Or in other words, $T_1\subset T_2$. Am I thinking about this right. This seems to make sense. – Seeker Aug 24 '22 at 04:05
  • 1
    Yes that is correct. – Fishbane Aug 24 '22 at 04:09
  • @Fishbane Thanks a lot! That was really helpful in clearing the doubts I had! – Seeker Aug 24 '22 at 04:10

1 Answers1

3

Yes, smaller and bigger are exactly the intuitive definitions in a partial order. Formally, those concepts are kind of interchangeable, but given a specific order and a convention of what should be thinked as "bigger", it's just the natural idea. But this does not address what "smallest" means and your specific case, so I'll explore it:


First of all, a general definition: Let $\le$ be a partial order on some set $S$. An element $a \in S$ is said to be minimal (resp. maximal) if $\forall\ b:\ b \le a \implies b = a$ (resp. $a \le b \implies a = b$); that is, it's pretty much the intuitive notion of minimum (but those are actually not the same!). A minimal element does not need to be comparable with every other term. When it is comparable, we call it a minimum (and, informally, the "smallest"), and it's not hard to prove that it is unique.

Specifically, when working with posets by inclusion,we have $S \subseteq \mathcal P(X)$ for some set $X$ and the smallest element that has a property is simply a minimum with the desired property (that might, or might not exist). In our case, the transitive closure (which you defined as the smallest transitive relation that contains $R$) does indeed exist. Fix your $R\subseteq A\times A$ and define $$S = \{\text{transitive binary relations on A that contain R}\}.$$ This is a poset with inclusion and obviously $A\times A\in S$. Now we can do this little trick: take $\bar R = \bigcap\limits_{R_S \in S} R_S$. This is a minimal element on $S$! In fact, $\bar R \ne \emptyset$ because $S$ has at least one element, and $R \subseteq \bar R$ (because each $R_S \supseteq R$); you can prove as an exercise that $\bar R$ is, in fact, a transitive relation. It is minimal because given any $R' \in S$, if $R' \subseteq \bar R$, then by construction $R'$ appears in the intersection thus $\bar R \subseteq R'$ (also, this proves that $R'$ is comparable w.r.t. every other term), so $\bar R = R'$. That is your transitive closure, the minimum on $S$.


Note that this is easier to comparatively describe/give an "universal property" than to explicitly compute.

In general, every time you have structures given by subsets/supsets of a given set, the smallest/biggest structures s.t. something is satisfied are given by this exact construction. You build the poset of all those that satisfy your condition and join/intersect all of them.

A few examples include: in topology the closure, interior; in analysis, the generated $\sigma$-algebra; in algebra, the field subextension generated by an element).

You can find a few (not so clear) examples on Wikipedia's page on minimal and maximal elements.

  • 1
    Thanks for answering! That was really helpful! – Seeker Aug 24 '22 at 04:10
  • I feel that in the case of 'smallest' elements, I would always interpret that as meaning a minimum element, although I suppose that is mostly semantics, and in this case it makes no difference. – Fishbane Aug 24 '22 at 04:12
  • There's one trivial case I didn't consider: $R = \emptyset$. But, eh, this relation is transitive by vacuity so there's nothing to prove. – Lucas Henrique Aug 24 '22 at 04:23