Tag Archives: Logic

The Fundamental Theorem of Well Orders

Posted in Logic, Mathematics, Set Theory, Things that are true by

Following our work on here we shall consider a definition of an initial similarity between well orders, where we can define a mapping between a well ordered set U and and an initial segment of a well order V. More formally, U is an initial similarity of V if the function \pi exists where:

\pi : U \rightarrow \pi [U] \sqsubseteq_{seg} V

with this in mind we define an order based comparison relation on the length of each well order. Firstly, we note that two well orders are equivalent if there is an order preserving bijection between them i.e.

U =_{o} V \Leftrightarrow \exists \text{ a bijection } f \text{ s.t. } x \leq_{U} y \Rightarrow f(x) \leq_{V} f(y)

now we defined a comparison relation for any two well orders:

U \leq_{o} V \Leftrightarrow \exists I \sqsubseteq_{seg} V ( I =_{o} U)

Lemma: An Alternative Definition of Initial Similarity.

A function \pi : U \rightarrow V is an initial similarity of a well ordered set into another \Leftrightarrow \pi satisfies the identity:

    (ID) = \Big[ \pi(x) = min_{V} \{y \in V | \forall u ( u <_{U} x) [ \pi(u) <_{V} y ] \} \; \; \; \; (x \in U) \Big]

\Rightarrow

Assume \pi is a initial similarity, then it is an order preserving injection, so \forall u (u \leq_{U} x) [\pi(u) \leq_{V} \pi(x)], then there is a minimal element z, where

z = min_{V} \{ y \in V | \forall u (u <_{U} x) [ \pi(u) <_{V} y ] \} \leq_{V} \pi(x)

which further entails that there is a u_{z} \in U such that \pi(u_{z}) = z \leq_{V} \pi(x) since \pi is an injection. We want to show that z = \pi(x). Now assume for reductio that z = \pi(u_{z}) < \pi(x), from which it follows that u_{z} <_{U} x because \pi is an order preserving injection. For all u <_{U} x since \pi is order preserving it follows in particular that (\pi(u) <_{V} \pi(x)). Now by definition of z we have for all u \pi(u) <_{V} z \leq_{V} \pi(x), so in particular we have \pi(u_{z}) < z, which is absurd since \pi(u_{z}) = z hence by reductio we have found \pi(x) = z as desired.

\Leftarrow

Assume that \pi satisfies the identity, then we need to prove the \pi is an initial similarity. Firstly note that \pi is an order preserving injection, so u <_{U} x \Rightarrow \pi(u) <_{V} \pi(x). Now suppose \pi[U] is not an initial segment of V. Choose x least in V such that there exists some y <_{V} \pi(x), where y \not\in \pi[U].

Recall that seg_{U}(x) =_{def} \{ u \in U | u <_{U} x \}, then by our choice of x we have y \not\in \pi(seg_{U}(x)) \sqsubseteq V so since \pi(seg_{U}(x)) \sqsubseteq V not  containing y it follows that \pi(seg_{U}(x)) = seg[min_{V} \{y \in V | \forall u (u <_{U} x [\pi(u) <_{V} y \}] = seg_{V}(z) \; \; \; \text { for some } z \in V. Which by the assumption of our identity statement proves z = \pi(x), but then y <_{V} z and hence y \in seg_{V}(z), which equal to \pi(seg_{U}(x)) and so must contain y , contrary to our initial assumption. This is absurd, so  \pi[U] is an initial segment of V by reductio. This completes the proof.

Proof: The Fundamental Theorem of Well Orders:

The Claim: For any two well ordered sets U, V either U \leq_{o} V or V \leq_{o} U.

The Idea : We define a recursive function which maps the structured elements of U into V until such a time that we run out of elements in either U or V, thereby proving one to be an initial similarity of the other. We are able to construct such a function because we have proven the Transfinite recursion theorem in the last post.

The Proof: We can distinguish the case where V = \emptyset as this case is trivial. Now we define our mapping function as follows:

 \pi(x) = \left\{ \begin{array}{lr} min_{V} \{ y \in V | \forall u (u <_{U} x) [\pi(u) <_{V} y ] \} & : \text{ if } (\exists y \in V)(\forall u (u <_{U} x) [\pi(u) <_{V} y] \\ 0_{V} & : \text{ otherwise}) \end{array} \right.

This as we said above is an instance of transfinite recursion, where we continue to map each variable x \in U to its opposite number \pi(x) = z \in V if z exists.

An example

An example

Now in the general case we have two scenarios:

  1. \forall x \neq 0_{U}, \pi(x) \neq 0_{V}. In other words, V is bigger than U, since V exhausts the mapping without reverting to the second case in our function. But then \pi satisfies to appropriate identity to trigger our Lemma above, so we can conclude that U is an initial similarity of V.
  2. \exists a \in U (a \neq 0_{U}) where \pi(a) = 0_{V}. In other words (intuitively) U is bigger than V, since U has exhausted the elements of V. It remains to prove that V is an initial similarity of U. Let a \neq 0_{U} be the least in U such that \pi(a) = 0_{V}. Now consider the restriction:

\mu = (\pi \upharpoonright seg_{U}(a)) : seg_{U}(a) \rightarrow V

Now by definition of \pi we know that \mu satisfies (ID), so by our lemma above seg_{U}(a) is an initial similarity of V. The function \mu is identical to \pi when restricted to seg_{U}(a), so we have \mu(seg_{U}(a)) = \pi(seg_{U}(a)) is an initial segment of V. Now there are two cases either \pi(seg_{U}(a)) is properly contained in V, or not. Assume it is, then \pi(seg_{U}(a)) = seg_{V}(z) for some z \in V and then since z exists we get to apply our recursion theorem to show that \pi(a) = z \neq 0_{V} since by definition z is strictly greater than the empty set. Hence \pi(a) \neq 0_{V} which is a direct contradiction of our choice of a \in U. Thus \pi(seg_{U}(a)) is a non proper initial segment of V, proving \pi(seg_{U}(a)) = V, which ensures that V =_{o} seg_{U}(a) i.e. that there is an initial similarity between V and U at the point of a \in U.

This completes our proof of the fundamental theorem of well orders.

The Recursion Theorem: A Set Theoretic Proof

Posted in Logic, Mathematics, Set Theory, Things that are true by

We prove the recursion theorem holds for any Peano System. Where a Peano System is defined as follows:

( \mathbb{N} , 0 , S) is a Peano system where the set \mathbb{N} with the least element 0 and the successor function S satisfy the following properties:

  1. 0 \in \mathbb{N}
  2. S: \mathbb{N} \rightarrow \mathbb{N}
  3.  S(m) = S(n) \Rightarrow m = n
  4. \forall (n) \in \mathbb{N}, S(n) \neq 0
  5. Induction Principle: For each X \subseteq \mathbb{N} if 0 \in X and \forall n \in \mathbb{N}(n \in X \rightarrow S(n) \in X) then X = \mathbb{N}

Now we state the recursion theorem.

Let ( \mathbb{N} , 0 , S) be a Peano System. E is a set with a \in E and h: E \rightarrow E is some function. Then it follows that there is exactly one function f : \mathbb{N} \rightarrow E which satisfies the following identities:

  • f(0) = a
  • f(S(n)) = h(f(n)) \: n \in \mathbb{N}

The idea behind recursion is that we effect an ordered process which iteratively builds on the results of steps enacted earlier in the process. So an evolutionary development can be seen as a recursive process which tracks the inheritance of traits over time. Assume the existence of mitochondrial Eve, then in a highly idealized sense the inherited traits of your children can be fully determined by your own projected traits, just as the inherited traits of her first child were determined by her projected traits and so on… Your genetic traits are the result of an nth-stage recursive projection process, in the same way your children’s genetic traits will depend on yours.

Strictly speaking this sketch is inaccurate since the recursive function which determines inheritance is more complicated, possibly non-deterministic and requires two inputs. That said, the broad impression will suffice for our purposes. You may think of this kind of process to give yourself a real world intuition about the nature and importance of a recursive development.

Preliminaries of the Proof

To prove the recursion theorem we need to establish a uniqueness and existence result. We shall first prove uniqueness:

We begin by defining the set \mathbb{A} of approximations of the function we want to construct.

p \in \mathbb{A} \Leftrightarrow Function(p) \: \& \: Domain(p) \subseteq \mathbb{N} \: \& \: Image(p) \subseteq E \\ \& \: 0 \in Domain(p) \: \& \: p(0) = a \\ \& \: (\forall n \in \mathbb{N}) [ S(n) \in Domain(p) \\ \Rightarrow n \in Domain(p) \: \& \: p(S(n)) = h(p(n))

The idea is that every function p \in \mathbb{A} should appropriately mimic the behavior we desire of a recursive function. In particular we can see that the function p is “closed downward” in the sense that if S(n) is in the domain of our function, then n is too. Better, each such function satisfies the identities required by the recursion theorem. We shall show that there is only one such function.

First we prove a quick Lemma.

A Lemma

For all  p, q \in \mathbb{A} and n \in \mathbb{N}, the following holds:

n \in Domain(p)  \cap Domain(q) \Rightarrow p(n) = q(n)

We want to use the Induction property of \mathbb{N} to establish this result. So we will take an X \subseteq \mathbb{N} such that the base case holds, and then prove the induction step. Clearly the set

X = \{ n \in \mathbb{N} | \forall p, q \in \mathbb{A} [ n \in Domain(p) \cap Domain(q) \Rightarrow p(n) = q(n) ] \}

contains 0 as each p, q satisfies the equality p(0) = a by construction of the set.

Now we shall show that if the second equality holds for the nth case, it must also hold for n+1. In other words we assume that n \in X and it follows that p(n) = q(n) by construction, and we wish to show that p(Sn) = q(Sn). To see this observe that:

p(S(n)) \\ = h(p(n) \\ = h(q(n)) \\ = q(S(n))

since both p, q \in \mathbb{A} and the identity holds for the nth case. This completes the induction step. So by the Induction Principle we have that X = \mathbb{N} which completes the Lemma.

Uniqueness

The uniqueness of the function f on ( \mathbb{N} , 0 , S) is a direct consequence of the lemma, since any other function with the properties of f is shown to be in \mathbb{A} and therefore indistinguishable from f.

Existence

It remains to show that the function f exists. To show existence we take

f = \bigcup\mathbb{A} = \{(n, w) | (\exists p \in \mathbb{A}) [ n \in Domain(p) \& p(n) = w ]\}

This is a function because clearly f \in \mathbb{A} and the lemma ensures that the values of f(n) are always unique. We need to show simply that Domain(f) = \mathbb{N}

Again this is established by the Induction Principle. First note by construction that 0 \in Domain(f). Now assume that n \in Domain(f) we wish to show that S(n) \in Domain(f).

By assumption we know there must be some Function(p) \in \mathbb{A} such that n \in Domain(p), but then we can construct a

Function(q) = p \cup \{ (S(n), h(p(n)) \} so that q \in \mathbb{A}

This shows that S(n) \in Domain(q) \subseteq Domain(f) for any n \in \mathbb{N} as desired. This completes the proof since the Induction Principle ensures that Domain(f) = \mathbb{N}.