Principle of Recursive Definition/Fallacious Proof

From ProofWiki
Jump to navigation Jump to search


Let $\N$ be the natural numbers.

Let $T$ be a class (which may be a set).

Let $a \in T$.

Let $g: T \to T$ be a mapping.

Then there exists exactly one mapping $f: \N \to T$ such that:

$\forall x \in \N: \map f x = \begin{cases} a & : x = 0 \\ \map g {\map f n} & : x = n + 1 \end{cases}$


Consider $\N$, defined as a naturally ordered semigroup $\struct {S, \circ, \preceq}$.

Let the mapping $f$ be defined as:

$\map f x = \begin{cases} a & : x = 0 \\ \map s {\map f n} & : x = n \circ 1 \end{cases}$

if $\map f n$ is defined.

Let $S' = \set {n \in S: \map f n \text{ is defined} }$.


$0 \in S'$


$n + 1 \in S'$

so by Principle of Mathematical Induction for Naturally Ordered Semigroup:

$S' = S$

Thus the domain of $f$ is $S$.

Consequently, $f$ is a mapping from $S$ into $T$ which satisfies:

$\map f 0 = a$


$\map f {n \circ 1} = \map s {\map f n}$

for all $n \in S$.




In the above argument, $S'$ is not precisely defined.

In order for a set to be defined, that definition should be able to be expressed solely in terms of logic and definitions from set theory.

In this case, the expression "is defined" does not meet that criterion.


The mapping $f$ is not defined properly.

A mapping needs to be defined as a set of ordered pairs which needs to satisfy a condition.

In the above, it is indeed specified that

$\tuple {0, a} \in f$


$\tuple {n \circ 1, \map s x} \in f$ whenever $\tuple {n, x} \in f$

Thus it appears either that:

$f$ itself is used to define $f$

or else that:

$f$ itself changes during the process in which it is being defined.

Neither of these possibilities can be accepted.


The only property of $\struct {S, \circ, \preceq}$ used in the argument is that it satisfies Principle of Mathematical Induction for Naturally Ordered Semigroup.

However, consider the commutative semigroup $\struct {D, +}$ which has elements $0$ and $1$, such that:

$D$ is the only subset of $D$:
containing $0$
containing $x + 1$ whenever it contains $x$.


for any set $T$
any mapping $g: T \to T$
any element $a \in T$

there exists a mapping $f: D \to T$ such that:

$\map f y = \begin{cases} a & : y = 0 \\ \map s {\map f x} & : y = x + 1 \end{cases}$

But consider the additive group of integers modulo $2$:

$\struct {\Z_2, +_2}$

which is indeed a commutative semigroup containing $0$ and $1$ which satisfies the hypothesis.

But if $g: \N \to \N$ is the mapping defined as:

$\map g n = n + 1$

there is no mapping $f: \Z_2 \to \N$ which satisfies:

$\map f y = \begin{cases} 0 & : y = 0 \\ \map s {\map f x} & : y = x +_2 1 \end{cases}$

for all $x \in \Z_2$.

Hence the argument is invalid.