Example:Bad inductive function definition

From CS2800 wiki

When giving an inductive definition of a function [math]f [/math], it is important to only use [math]f(x') [/math] in the definition of [math]f(x) [/math] if [math]x' [/math] is a substructure of [math]x [/math].

For example, the "function" [math]bogus : \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] given inductively by [math]bogus(\href{/cs2800/wiki/index.php/%CE%95}{ε}) := 0 [/math] and [math]bogus(\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}) := bogus(\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}) [/math] is not well-defined. Indeed, try computing [math]bogus("abc") [/math]; any choice of output satisfies the defining equations.

As a more insidious example, consider [math]nasty : \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} \href{/cs2800/wiki/index.php/%5Cto}{\to} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math] given by [math]nasty(\href{/cs2800/wiki/index.php/%CE%95}{ε}) := \href{/cs2800/wiki/index.php/%CE%95}{ε} [/math] and [math]nasty(\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}) := nasty(nasty(x)) [/math]. Here, it is perfectly reasonable to use [math]nasty(x) [/math] in the definition of [math]nasty(\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}) [/math] because [math]x [/math] is a substructure of [math]\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} [/math], but [math]nasty(nasty(x)) [/math] is not ok, because [math]nasty(x) [/math] is not necessarily a substructure of [math]\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} [/math] and we can only apply [math]nasty [/math] to substructures of [math]\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} [/math] in the definition of [math]nasty(\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}) [/math].