-1
$\begingroup$

I'm following a university course based on these slides, 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"?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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$). $\endgroup$
    – xavierm02
    Jul 30, 2021 at 19:51
  • $\begingroup$ Smallest means that it is smaller than (i.e. included in, since the order is inclusion) all other relations that satisfy the rules. $\endgroup$
    – xavierm02
    Jul 30, 2021 at 19:54
  • $\begingroup$ @xavierm02 Yes, in general I can understand it, but I would like to know in this context which is such relation. $\endgroup$
    – user402843
    Jul 31, 2021 at 13:31
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Aug 9, 2021 at 19:28
  • $\begingroup$ @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. $\endgroup$
    – Andrej Bauer
    Aug 9, 2021 at 19:32

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for answering, but I'd like to know in the mentioned context which is such relation. $\endgroup$
    – user402843
    Jul 31, 2021 at 13:32

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