Why relations are defined as the smallest

Question

Often relations are defined as follows:

The xxxxx relation is the smallest relation satisfying...

My question is why relations are defined as the smallest relations. I thought it may be so relation is uniquely defined but I have never see a proof that there is exactly one smallest relation. Does such proof exists? Are there any other reasons?

Answer 1

In the example you mentioned in the comments, the author is defining a relation something like this:

$R$ is the smallest relation satisfying:

1. If $a$ and $b$ are ... then $aRb$.
2. If $a$ and $b$ are ... then $aRb$.
3. ...

In this case, the use of "smallest" is just like the use of "if and only if" rather than "if". Let's say I define a relation $R$ by saying "if $a$ is the brother of $b$, then $aRb$". If it turned out that $\text{Charlemagne}\ R\ \text{Richard Nixon}$, would I have lied to you? No! I only said that if $a$ is the brother of $b$, then $aRb$, I didn't say only if.

In order to deal with this problem, I could either just use "only if" instead of "if", or I could say that $R$ is the smallest relation satisfying "If $a$ is the brother of $b$, then $aRb$". "Smallest" here means that $R$ is contained inside every other relation satisfying that property. It is possible to prove that such an $R$ exists, and that it's the same as the relation that would be defined by using "only if" rather than "if".

Answer 2

To understand your specific example, we have to refer to Lamport'book, which I'm not able to browse.

In general, a relation is not defined as "the smallest" something ...

See order relation :

A partial order on a set $X$ is a relation $R ⊆ X^2$ such that

(i) $(x, y) ∈ R$ and $(y, z) ∈ R$ implies $(x, z) ∈ R$

(ii) $(x, x) ∈ R$

for all $x, y ∈ X$.

The "smallest" approach is needed when we want to impose a "closure" condition.

See Herbert Enderton, A Mathematical Introduction to Logic (2ed - 2001), page 16 :

[the definition of] well-formed formulas (wffs) [...] will have the following consequences:

(a) Every sentence symbol is a wff.

(b) If $α, β$ are wffs, then so are $(¬α), (α∧β), (α∨β), (α→β)$, and $(α↔β)$.

(c) No expression is a wff unless it is compelled to be one by (a) and (b).

This sort of construction, of taking some basic building blocks (here the sentence symbols) and “closing” under some operations (here five operations), occurs frequently both in logic and in other branches of mathematics.

One feature of this sort of construction is that it yields an induction principle. Say that a set $S$ is closed under a two-place function $f$ iff whenever $x ∈ S$ and $y ∈ S$ then $f(x, y) ∈ S$, and similarly for one-place functions and so forth.

INDUCTION PRINCIPLE If $S$ is a set of wffs containing all the sentence symbols and closed under all five formula-building operations, then $S$ is the set of all wffs.

This is a type of construction [see page 34] :

that occurs frequently both in logic and in other branches of mathematics. We may want to construct a certain subset of a set $U$ by starting with some initial elements of $U$, and applying certain operations to them over and over again. The set we seek will be the smallest set containing the initial elements and closed under the operations. Its members will be those elements of $U$ which can be built up from the initial elements by applying the operations some finite number of times.

To simplify our discussion, we will consider an initial set $B ⊆ U$ and a class $\mathcal F$ of functions containing just two members $f$ and $g$, where

$f : U \times U \to U$ and $g : U \to U$.

Thus $f$ is a binary operation on $U$ and $g$ is a unary operation. [Think at $U$ as the set of expressions, the initial elements are the sentence symbols, and the operations are $\land$ (binary) and $\lnot$ (unary)].

[We want to build the set $C$ of "admissible" objects.] In defining $C$ more formally, we have our choice of two definitions. We can define it “from the top down” as follows: Say that a subset $S$ of $U$ is closed under $f$ and $g$ iff whenever elements $x, y$ belong to $S$, then so also do $f(x, y)$, g(x)$.

Say that $S$ is inductive iff $B ⊆ S$ and $S$ is closed under $f, g$. Let $C^*$ be the intersection of all the inductive subsets of $U$; thus $x ∈ C^*$ iff $x$ belongs to every inductive subset of $U$.

It is not hard to see that $C^*$ is itself inductive. Furthermore, $C^*$ is the smallest such set, being included in all the other inductive sets.