Viewing a Bijection in Terms of Paths and Cycles
Usually, people induct on the natural numbers.
I want to extend (generalize) the principle of mathematical induction to something other than the natural numbers.
Consider the diagram below:
The diagram shows the disjoint union of a collection of paths and cycles.
For me, a bijective function (one-to-one correspondence) describes disjoint union of a set of paths and/or cycles.
No node can have two incoming edges. That would imply that two inputs map to the same output.
No node can have two outgoing edges. That would imply one input maps to two different outputs.
For example, $F(x) = x + 2$ is a bijection on the integers.
$F(x) = x + 2$ represents the union of the following two things:
- a path which passes through all even integers $\{\cdots, -4, -2, 0, +2, +4, \cdots\}$
- a path which passes through all of the odd integers $\{\cdots, -3, -1, +1, +3, \cdots\}$
Informal Induction on a Bijection
Suppose that we want to prove that every dot, in some set of dots, is black.
Informally, consider the following approach:
- Pick an arbitrary dot $x$. $x$ lies on either a path or a cycle.
- Show that there exists a descendant of $x$ such that the decedent is black.
- Also, we show that there exists an ancestor of $x$ such that the ancestor is black
- Lastly, we show that between any two black dots $a$ and $b$, if there exists a dot of any color between $a$ and $c$, then there exists a black dot between $a$ and $b$.
The Principle of Bijective Induction
We define the The Principle of Bijective Induction to be the following statement:
For any set $A$,
For any predicate $``\text{is black}''$
For any invertible function $F$ whose domain is set $A$
$\forall x \in A, x \text{ is black } $
if and only if
All of the following conditions are satisfied:
$\forall x \in A, \text{ if } x \text{ is black } \text{ then } \exists n \in \mathbb{N} \text{ such that } f^{n}(x) \text{ is black }$
and
$\forall x \in A, \text{ if } x \text{ is black } \text{ then } \exists m \in \mathbb{N} \text{ such that } f^{-m}(x) \text{ is black }$
and
$\forall x \in A$,
$\text{ if }$
$x \text{ is black } \text{ and } \exists n \in \mathbb{N} \text{ such that } n \geq 3 \text{ and } f^{n}(x) \text{ is black } $
$\text{ then } $
$ \exists k \in \{m \in \mathbb{N} \colon \quad 2 \leq m \leq n-1\} \text{ such that } f^{k}(x) \text{ is black } $
Another Variant on Induction
For any set $A$,
For any predicate $``\text{is black}''$
For any invertible function $F$ whose domain is set $A$
$\forall x \in A, x \text{ is black } $
if and only if
All of the following are true:
$\forall x \in A, \exists k \in \mathbb{N} \text{ such that } f^{-k}(x) \text{ is black }$
and
$\forall x \in A, \text{ if } x \text{ is black } \text{ then } f(x) \text{ is black }$
Definition of a Super-scripted Function
Let $D$ be an arbitrary set.
For any function $f$ whose domain (set of inputs) is $D$,
$\forall x \in D,$
$\forall p \in \mathbb{Z},$
$f^{p}(x) = \begin{cases} f^{sgn(x)\cdot(\lvert p \rvert -1)}(x) & \text{ if } p \not\in \{-1, 0, +1\} \\ f(x) & \text{ if } p = +1\\ \text{the unique $w \in D$ such that $f(w) = x$} & \text{ if } p = -1 \\ x & \text{ if } p = 0 \\ \end{cases}$
Potential Counter-Example
I am a little worried that you could prove that every real number is rational.
Note that:
- for any real number $x$ there exists a real number $y$ such that $x < y$ and $y$ is rational
- for any real number $x$ exists a real number $w$ such that $w < x$ and $w$ is rational
- between any two rational numbers $w$ and $y$ there exists a rational number.
However, the less-than operator $(<)$ is NOT a bijection from $\mathbb{R}$ to $\mathbb{R}$.
For a bijection $\Phi$ from $\mathbb{R}$ to $\mathbb{R}$, it sort of feels like $\Phi^{-k}(x) < x < \Phi^{+k}(x)$.
However, the iterated bijection $\Phi^{k}$ does NOT define a strict total ordering.