<p>&quot;Smallest relation with property <span class="math-container">$\mathscr{P}$</span>&quot; just means &quot;subset of every relation with property <span class="math-container">$\mathscr{P}$</span>&quot; - thinking of a relation as a set of ordered pairs. Basically, we write down some &quot;starting&quot; conditions and some &quot;inductive&quot; conditions as our property, and the smallest relation with that property is the set of all ordered pairs we can &quot;justify&quot; using the starting/inductive conditions in finitely many steps.</p>
<p>It may help to see an example of this in action. Consider the following (very silly!) way of defining the (unary) relation <span class="math-container">$E=$</span> &quot;Is an even integer:&quot;</p>
<ol>
<li><p><span class="math-container">$0\in E$</span></p>
</li>
<li><p>If <span class="math-container">$x\in E$</span> then <span class="math-container">$x+2\in E$</span>.</p>
</li>
<li><p>If <span class="math-container">$x\in E$</span> then <span class="math-container">$x-2\in E$</span>.</p>
</li>
<li><p><span class="math-container">$E$</span> is the smallest relation satisfying properties <span class="math-container">$(1)$</span>-<span class="math-container">$(3)$</span> above.</p>
</li>
</ol>
<p>If we drop property <span class="math-container">$(4)$</span> we haven't fully pinned down <span class="math-container">$E$</span>; for example, the set of <em>all</em> integers satisfies properties <span class="math-container">$(1)$</span>-<span class="math-container">$(3)$</span>, but is &quot;too big.&quot; Property <span class="math-container">$(4)$</span> rules out this sort of nonsense.</p>

CC BY-SA 4.0
2021-07-31T13:32:28.230Z
Thank you for answering, but I'd like to know in the mentioned context which is such relation.
user402843
CC BY-SA 4.0
2021-07-31T01:44:05.277Z
2021-07-31T01:44:05.277Z
Noah Schweber
<p>I'm following a university course based on <a href="http://www.diag.uniroma1.it//degiacom/didattica/metodiformali/aa2014-15/materiale/3-Pre-Post-program-analysis/3-1-StructuralOperationalSemantics-2up.pdf" rel="nofollow noreferrer">these slides</a>, and I have a question about structural operational semantics.</p>
<p>As you can see at page 7 (4-th slide), a structural rule is interpreted logically as: <code>∀(antecedent ∧ side-condition ⊃ consequent)</code>. Then it says that &quot;The structural rules define inductively a relation, namely: the smallest relation satisfying the rules&quot;, and the professor told us that such &quot;smallest relation&quot; implies that we must use second-order logic for expressing it.</p>
<p>I can understand the reason why we need second-order logic (we need to predicate over such relation).<br/>But my question is: what do we mean with &quot;smallest relation&quot;?</p>

CC BY-SA 4.0
2021-07-30T19:51:12.277Z
A (binary) relation $\mathcal{R}$ on a set $X$ is just a subset of $X\times X$, with $x\mathcal{R}y$ being a notation for $(x,y)\in\mathcal{R}$. The subset $\{\mathcal{R} \in X\times X \text{ such that }\mathcal{R}\text{ validates the rules}\}$ of the set of binary relations can be ordered by inclusion: $\mathcal{R}_1$ is smaller than $\mathcal{R}_2$ means $\mathcal{R}_1\subseteq\mathcal{R}_2$ (or equivalently $\forall x, \forall y,x\mathcal{R}_1y \text{ implies }x\mathcal{R}_2y$).
xavierm02
CC BY-SA 4.0
2021-07-30T19:54:46.000Z
Smallest means that it is smaller than (i.e. included in, since the order is inclusion) all other relations that satisfy the rules.
xavierm02
CC BY-SA 4.0
2021-07-31T13:31:38.030Z
@xavierm02 Yes, in general I can understand it, but I would like to know in this context which is such relation.
user402843
CC BY-SA 4.0
2021-08-09T19:28:36.787Z
It's false that you need second-order logic. You could use first-order logic and set theory, or a predicative formal system with inductive definitions.
Andrej Bauer
CC BY-SA 4.0
2021-08-09T19:32:22.267Z
@user402843: you keep asking "which" relation. The answer is: **the smallest one**. Among all relations satisfying the given conditions there is *exactly one* that is smallest - and that is the one we mean. There need not be any other description.
Andrej Bauer
CC BY-SA 4.0
2021-08-09T20:33:33.840Z
@AndrejBauer I didn't ask for a definition of "smallest relation". I just want to know, **in this context** intuitively which is such relation and why it must be the smallest one.
user402843
CC BY-SA 4.0
2021-08-09T21:21:19.000Z
Well, it's kind of hard to guess what you consider intuitive. It's the smallest one because that is the relation that corresponds to the idea that the operational semantics is generated inductively by the given rules.
Andrej Bauer
CC BY-SA 4.0
2021-08-12T08:32:11.583Z
@AndrejBauer "hard to guess what you consider intuitive": For instance, you could have got me a concrete example indicating such relation, but I understand that being conceited is more fun and you're not here for helping me. Thanks anyway.
user402843
CC BY-SA 4.0
2021-08-12T14:15:11.850Z
@NoahSchweber gave you such a concrete example, see below where says "it may help to see an example of this in action". You dismissed his answer. This is what lead me to say "it's hard to guess what you consider intuitive". There is no point in anyone showing you another example, because it will be quite similar to the one that you already dismissed.
Andrej Bauer
<operational-semantics>
Why structural rules define the "smallest relation" satisfying the rules?
user402843
# Why structural rules define the "smallest relation" satisfying the rules?

(Asked by: username_0 on 2021-07-29)

I'm following a university course based on [these slides](http://www.diag.uniroma1.it//degiacom/didattica/metodiformali/aa2014-15/materiale/3-Pre-Post-program-analysis/3-1-StructuralOperationalSemantics-2up.pdf), and I have a question about structural operational semantics.

As you can see at page 7 (4-th slide), a structural rule is interpreted logically as: `∀(antecedent ∧ side-condition ⊃ consequent)`. Then it says that "The structural rules define inductively a relation, namely: the smallest relation satisfying the rules", and the professor told us that such "smallest relation" implies that we must use second-order logic for expressing it.

I can understand the reason why we need second-order logic (we need to predicate over such relation).  
But my question is: what do we mean with "smallest relation"?

**Tags:** operational-semantics

> **Comments:**
> **username_1**: A (binary) relation $\mathcal{R}$ on a set $X$ is just a subset of $X\times X$, with $x\mathcal{R}y$ being a notation for $(x,y)\in\mathcal{R}$. The subset $\{\mathcal{R} \in X\times X \text{ such that }\mathcal{R}\text{ validates the rules}\}$ of the set of binary relations can be ordered by inclusion: $\mathcal{R}_1$ is smaller than $\mathcal{R}_2$ means $\mathcal{R}_1\subseteq\mathcal{R}_2$ (or equivalently $\forall x, \forall y,x\mathcal{R}_1y \text{ implies }x\mathcal{R}_2y$).  
> **username_1**: Smallest means that it is smaller than (i.e. included in, since the order is inclusion) all other relations that satisfy the rules.  
> **username_0**: @username_1 Yes, in general I can understand it, but I would like to know in this context which is such relation.  
> **username_2**: It's false that you need second-order logic. You could use first-order logic and set theory, or a predicative formal system with inductive definitions.  
> **username_2**: @username_0: you keep asking "which" relation. The answer is: **the smallest one**. Among all relations satisfying the given conditions there is *exactly one* that is smallest - and that is the one we mean. There need not be any other description.  
> **username_0**: @AndrejBauer I didn't ask for a definition of "smallest relation". I just want to know, **in this context** intuitively which is such relation and why it must be the smallest one.  
> **username_2**: Well, it's kind of hard to guess what you consider intuitive. It's the smallest one because that is the relation that corresponds to the idea that the operational semantics is generated inductively by the given rules.  
> **username_0**: @AndrejBauer "hard to guess what you consider intuitive": For instance, you could have got me a concrete example indicating such relation, but I understand that being conceited is more fun and you're not here for helping me. Thanks anyway.  
> **username_2**: @NoahSchweber gave you such a concrete example, see below where says "it may help to see an example of this in action". You dismissed his answer. This is what lead me to say "it's hard to guess what you consider intuitive". There is no point in anyone showing you another example, because it will be quite similar to the one that you already dismissed.  

---

## 1 answers

### Answer by username_3 on 2021-07-31. Score: 3

"Smallest relation with property $\mathscr{P}$" just means "subset of every relation with property $\mathscr{P}$" - thinking of a relation as a set of ordered pairs. Basically, we write down some "starting" conditions and some "inductive" conditions as our property, and the smallest relation with that property is the set of all ordered pairs we can "justify" using the starting/inductive conditions in finitely many steps.

It may help to see an example of this in action. Consider the following (very silly!) way of defining the (unary) relation $E=$ "Is an even integer:"

1. $0\in E$
2. If $x\in E$ then $x+2\in E$.
3. If $x\in E$ then $x-2\in E$.
4. $E$ is the smallest relation satisfying properties $(1)$-$(3)$ above.

If we drop property $(4)$ we haven't fully pinned down $E$; for example, the set of *all* integers satisfies properties $(1)$-$(3)$, but is "too big." Property $(4)$ rules out this sort of nonsense.

> **Comments:**
> **username_0**: Thank you for answering, but I'd like to know in the mentioned context which is such relation.  

---

