Can we do a proof by induction on something which looks like an infinite tree?

Question

Introduction

I am used to applying proof by induction to infinite paths.

An example of an infinite path is $Q = \left \{\,\,(\,k \,\,,\, k+1): n \in \mathbb{N} \cup \{0\}\,\,\right\}$

$$Q =\left\{\,\,(0 \,\,,\, 1), \,\,(1 \,\,,\, 2), \,\,(2 \,\,,\, 3), \,\,(3 \,\,,\, 4), \,\,(4 \,\,,\, 5), \,\,(5 \,\,,\, 6), \,\,(7 \,\,,\, 8)\,\cdots\, \right\}$$

Is a proof by induction valid if performed on an infinite tree?

Attempt to Define an infinite Path

Maybe a "non-finite path$\,$" is simply a subset $\smile$ of a strict total ordering $<$ such that:

• there is nothing sandwiched in-between two nodes which have an edge between them.
  • $\forall x,z \in V, x \smile z \implies \forall y \in V, \text{ NOT } x < y < z$
  • Equivalently, $\forall x,y \in V, x < y \text{ and } y < z \text{ implies not } x \smile z$
• Every node in the path has one incoming edge and one outgoing edge (except the start of the path)
  • one outgoing edge means$\dots\dots$   $\quad \forall x \in V: \exists \text{ unique } y \in V : \,\, x \smile y$

---

For any non-finiite set $V$ and $E \subseteq V \times V$, $P = (V, E)$ is a "infinite path" if and only if all of the following hold:

• The path has a starting point, beginning, or left-most node.   $\quad \exists y \in V: \forall x \in V,\,\, (x, y) \not\in E$
• Every node has one incoming edge and one outgoing edge (except the start of the path)
  • one outgoing edge means$\dots\dots$   $\quad \forall x \in V: \exists \text{ unique } y \in V : \,\, (x, y) \in E$
  • The in-degree of $x$ ($\mathtt{indeg}(x) = 1$) for all $x \in V$ except the first node in the path.
• The path is connected
  • there exists a strict total ordering consistent with path $P$, and for every strict total ordering, if $(x, z)$ is an edge in path $P$, then there is nothing between $x$ and $z$ in the strict total ordering
    • For any strict total order $P^{\prime} = (V, E^{\prime}), \quad \text{ if } E \subseteq E^{\prime} \text{ then } \forall x,y \in V, (x, y) \in E^{\prime} \text{ and } (y, z) \in E^{\prime} \text{ implies } (x, z) \not\in E$
    • $P^{\prime} = (V, E^{\prime})$ is a strict total order if and only if all of the following conditions are satisfied:
      • $(V, E^{\prime})$ is irreflexive.
        • $\forall a \in V, (a, a) \not\in E^{\prime}$.
      • $(V, E^{\prime})$ is transitive
        • $\forall a, b, c \in V a < b \text{ and } b < c \implies a < c$
      • $\forall a, b, c \in V, \text{ if } a \neq b$, then $a < b$ or $b < a$

---

That definition of "infinite path" was a mess.
Let us move on, shall we? $\dots\dots\quad$

Proof by Induction on an Infinite Path

Anyway $\dots\dots$

Let $P = (V, E)$ be an infinite path on vertex set $V$

$\forall x \in V$, $x$ is black
  if and only if
both of the following are true:

• The start of the path (left-most node) is black
• $\forall x, y \in V, \text{ if } (x, y) \in E \text{ and } x \text{ is black then } y \text{ is black}$.

Is a proof by induction valid if done on an infinite tree?

Definition of Infinite Tree

An "infinite tree" is an ordered pair $T = (V, E)$ such that:

• $V$ is a non-finite set.   $\quad \not\exists m \in \mathbb{N}: \exists \text{ bijection between } V \text{ and } \{k\in\mathbb{N}: 1 \leq k \leq m\}$
• The transitive closure of $E$ is a strict total ordering (similar to strictly-less-than for real numbers)
• The tree has exactly one root node, or source node (starting point, beginning, whatever )   $\quad \exists y \in V: \forall x \in V,\,\, (x, y) \not\in E$
• There is a surjective function $F$ from $V-\mathtt{root}(V)$ to $V$ such that $(x, y)$ is an edge if and only if $x = F(y)$. In other words, every node has exactly one parent node, except for the root node.
• The tree is connected

Example of an infinite tree

Suppose we have tree $T = (V, E)$ such that:

• The empty set is the root node.
• $V = \{A \subseteq (ℕ \cup \{0\}) \text{ such that } A \text{ is finite }\}$
• For any $A \in (ℕ∪ \{0\}) $, $(A, A \cup \{\mathtt{max}(A)+1\}) \in E$
• For any $A \in (ℕ∪ \{0\}) $, $(A, A \cup \{\mathtt{max}(A)+2\}) \in E$
• There are no other edges in the tree except those described above.
• $(ℕ ∪ {0})$ denotes the set of all subsets of $ℕ$

The Method of Induction on an Infinite Tree

Let $T = (V, E)$ be a tree-like thing on non-finite vertex set $V$

$\forall x \in V$, $x$ is black
  if and only if
both of the following are true:

• The root of tree $T$ is black
• $\forall x, y \in V, \text{ if } (x, y) \in E \text{ and } x \text{ is black then } y \text{ is black}$.

To reiterate, is a proof by induction valid if done on an infinite tree?

Answer 1

Yes, because the set of all nodes between an arbitrary vertex $v$ and the tree's root is a path. In other words:

$$\forall x \in V ~ (\{ v \in V \mid v \lt x \} \text{ is well ordered with the root of the tree as the least element}).$$

By the way, I often find it useful to think of induction using the well-ordering principle. In other words, if your proposition is false, then by the well-ordering principle there must be a minimum counterexample. Prove that the root of the tree isn't a counterexample, and then use the inductive step to prove that any counterexample necessarily leads to a smaller counterexample, thereby contradicting the minimality of any possible counterexample. Thus, there can be no counterexamples and the proposition must be true.