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

Question

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.

Answer 1

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.

Answer 2

In the next two sections we present

$\;$ The recursion theorem in this setting.

$\;$ If a $\text{cc-cyclic}$ (i.e. finite) set $A$ is in bijective correspondence with a set $B$,
$\;$ then $B$ is also a finite set.

---

The Recursion Theorem

Let $C$ be a non-empty $\text{cc-cyclic}$ set defined by $\sigma: C \to C$.
Let $c_s \in C$.
Let $\psi: A \to A$ be a function defined on the nonempty domain $A$.
Let $a_s \in A$.

There is a unique function $F: C \to A$ satisfying

$\tag 1 F(c_s) = a_s$ $\tag 2 \text{If } \sigma(c) \ne c_s \text{ then } F(\sigma(c)) = \psi(F(c))$

The uniqueness is proved using induction in the same way as found in the wikipedia article.

To show existence, you have to provide the argument details for this logic fragment (a comment given by Matemáticos Chibchas),

Brief answer: consider the intersection of all relations satisfying the recurrence requirement. Show that this intersection is indeed a function.

The recurrence requirement is given by $\text{(1)}$ and $\text{(2)}$, rewritten to screen for the more general binary relation over $C$ and $A$. Observe that $C \times A$ satisfies the recurrence requirement.

Now let $\rho$ be the intersection of these relations.

Using induction it is easy to see that the domain of $\rho$ is $C$.

To show $\rho$ is single-valued use induction:

Base Case:
Suppose $(c_s, a) \in \rho$ and $a \ne a_s$. Then $\rho \setminus \{(c_s, a)\}$ satisfies the recurrence conditions which is absurd since $\rho$ is the minimum such set.

Step Case:
Suppose $\rho$ is single-valued on $c$ with $(c, a) \in \rho$. The case where $\sigma(c) = c_s$ is a 'wrap around' to the base case and can be skipped.
Suppose $(\sigma(c), b) \in \rho$ and $b \ne \psi(a)$. Then $\rho \setminus \{(\sigma(c), b)\}$ satisfies the recurrence which is absurd since $\rho$ is the minimum such set

So the relation $\rho$ is a well-defined function $F: C \to A$ satisfying the recurrence requirement.

---

Let $g\colon B \to C$ map the finite set $B$ bijectively to $C$.

Let $(B,f)$, $f\colon B \to B$ be a complete cycle that 'erects' $B$ as a finite set.

Exercise: Show that $(g \circ f \circ g^{-1},C)$ makes $C$ a finite set.