Induction and recursion – right out of the set theory starting gate after defining finite sets.

foundationsinductionlogicrecursionset-theory

In the following section a definition is given followed by some claims.

Is the theory valid?

My work

I am interested in the foundations of math and have thought about concepts like Dedekind-infinite set. In the first paragraph of the wikipedia article on the subject you'll find the sentence

Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

The definitions/theory below also does not rely on the construction of the natural numbers.

Also, if the ideas are sound and there are already extant expositions of the theory, please provide some references.

Let the function $f: X \to X$ be a given (set) endomorphsim defined on the set $X$.

If $x \in X$ there is a minimal set $\tau^f_x(X) \subset X$ satisfying the following two conditions,

$\tag 1 x \in \tau^f_x(X) $
$\tag 2 \displaystyle \text{The restriction, } f^{\tau}_x \text{, of } f \text{ to } \tau^f_x(X) \text{ defines an endomorphsim } f^{\tau}_x:\tau^f_x(X) \to \tau^f_x(X)$

A set $X$ is said to be $\text{cc-cyclic}$ if there exists a function $f: X \to X$ satisfying

$\quad \forall \, x \in X, \; f^{\tau}_x = f$

The function $f$ is then said to be a complete closed-chain cycle for $X$.

Puzzle Spoiler: If this theory is correct a well known six letter adjective can also be used to describe the $\text{cc-cyclic}$ set $X$.

Claim 1: Induction can be performed on a $\text{cc-cyclic}$ set $X$; here you can start the base case at any element $x_0 \in X$.

Claim 2: The recursion theorem construction technique can be applied (with a simple adaption) to a $\text{cc-cyclic}$ set $X$; here you can begin the functional recursion at any element $x_0 \in X$.

Claim 3: A function that is a complete closed-chain cycle for a set is also a bijection.

Claim 4: Every subset of $\text{cc-cyclic}$ set is also a $\text{cc-cyclic}$ set.

Best Answer

Okay, with your edits today, it makes more sense.

  • Yes, a set is cc-cyclic if and only if it is finite.
  • Yes, you can do induction on it. Specifically, if there is an $x_0 \in X$ for which $P(x_0)$ is true, and if whenever $P(x)$ is true, then so is $P(f(x))$, then $P(x)$ is true for all $x \in X$.
  • Yes, there are various forms of recursive definition available on a cc-cyclic set. But I'm not sure which form you are thinking of, so I cannot say if yours actually works. For instance, if you were thinking of replacing $\Bbb N$ in the recursion theorem with a cc-cyclic set, that doesn't work (the infinitude of $\Bbb N$ is critical).
  • Yes, a cyclic permutation is a bijection. (Sorry, but I don't see the need of inventing a new name when there is an existing one for the concept.)
  • Yes, every subset of a cc-cyclic set is also cc-cyclic.

$\tau_x^f$ is sometimes called the orbit of $x$ under $f$ (the "$(X)$" part of the notation is redundant, since $X$ is the domain and codomain of $f$). The condition $f_x^\tau = f$ implies $\tau_x^f = X$.

With that recognition, the inductive principle can be easily proven. Let $Q = \{x \in X\mid P(x)\text{ is true}\}$. Then $x_0 \in Q$ and by the induction hypothesis $f(Q) \subset Q$. Ergo, $\tau_{x_0}^f \subset Q$ by its definition. But since $\tau_{x_0}^f = X$ that gives $Q = X$, or equivalently, for all $x \in X, P(x)$ is true.

Related Question