HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Example of inductive sets that are neither least nor greatest fixed point

Submitted by: @import:stackexchange-cs··
0
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$:

  • $\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.