debugMinor
Example of inductive sets that are neither least nor greatest fixed point
Viewed 0 times
greatestareexamplepointsetsthatnorleastfixedinductive
Problem
Do there exist a set of inductive rules and a fixed point of these rules but is neither the least nor the greatest fixed points?
Solution
Here's a non-trivial example:
Suppose we want to define inductively a subset of reals, so we work on the complete lattice $\mathcal{P}(\mathbb{R})$ ordered by inclusion.
Then, consider the rules
$$
\dfrac{\qquad}{0} \qquad \dfrac{x}{x+1}
$$
This induces the (monotonic, Scott-continuous) function $f : \mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R})$ given by
$$
f(X) = \{0\} \cup \{ x+1 \ |\ x\in X\}
$$
All of the following are fixed points of $f$:
If we want our definition to be well-formed, beyond specifying the rules, we need to single out one the fixed points. This is typically done by taking the least (induction) or the greatest (coinduction).
Suppose we want to define inductively a subset of reals, so we work on the complete lattice $\mathcal{P}(\mathbb{R})$ ordered by inclusion.
Then, consider the rules
$$
\dfrac{\qquad}{0} \qquad \dfrac{x}{x+1}
$$
This induces the (monotonic, Scott-continuous) function $f : \mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R})$ given by
$$
f(X) = \{0\} \cup \{ x+1 \ |\ x\in X\}
$$
All of the following are fixed points of $f$:
- $\mathbb{N}$ (least)
- $\mathbb{Z}$
- $\{x/2 \ |\ x\in \mathbb{Z}\}$
- $\{x/3 \ |\ x\in \mathbb{Z}\}$
- etc.
- for any natural $k \geq 1$, the set $\{x/k \ |\ x\in \mathbb{Z} \}$
- $\mathbb{Q}$
- $\mathbb{R}$ (greatest)
If we want our definition to be well-formed, beyond specifying the rules, we need to single out one the fixed points. This is typically done by taking the least (induction) or the greatest (coinduction).
Context
StackExchange Computer Science Q#71846, answer score: 7
Revisions (0)
No revisions yet.