In this article, we have presented Dickson's Theorem in Theory of Computation along with its proof using Induction and use of Dickson's theorem. This theorem was formed in 1913 by Leonard Eugene Dickson and is used to prove Higman's Theorem in Theory of Computation. Dickson's Theorem / lemma is applied in Mathematics as well.

Table of contents:

1. Dickson's Theorem in Theory of Computation
2. Proof of Dickson's theorem
3. Use of Dickson's theorem

Let us get started with Dickson's Theorem in Theory of Computation.

Dickson's Theorem in Theory of Computation

Basic terms to understand Dickson's theorem:

1. N is a set of positive integers. Let n ∈ N.
2. Let us define two points p and q in Nⁿ.

p = (p₁, p₂, ..., p_n)
and
q = (q₁, q₂, ..., q_n)

3. Point p is dominated by q if p_i <= q_i for all i from 1 to n. This means all points of p is smaller than or equal to corresponding point in q.

Dickson's theorem states that:

Let S ⊆ (proper subset of) Nⁿ and M is a set of all elements in S that are minimal in the relation "is dominated by".

This means:

M = {q ∈ S : there is no p in S \ {q} such that p is dominated by q}.

According to this theorem, the set M is finite.

Proof of Dickson's theorem

Dickson's Theorem in Theory of Computation can be proved using Induction. There are two steps:

1. Prove for n = 1.
2. Prove for n >= 2.

Prove for n = 1.

If n = 1, then:

1. M = ∅ (empty) if S = ∅
2. M consist of exactly one element (if S != ∅) if n = 1.

If n >= 2 and assume that the theorem is true for N^n-1.

S is a subset of Nⁿ and M be the set of minimal elements in S.

If S = ∅, then M = ∅ so M is finite as it is empty.

If S != ∅, we take a random element q in M. If p belongs to M \ {q}, then q ia not dominated by p. This implies there exists an index i such that p_i <= q_i - 1.

This results in:

M \ {q} ⊆ (N^i-1 x [1, q_i - 1] x N^n-i)

which is equated to:

M \ {q} = Union (i=1 to n) Union (k = 1 to q_i-1) M_ik

There is a lemma:

M_ik is a subset of all elements in S_ik that are minimal in the relation "is dominated by".

Therefore, S_ik is a subset of N^n-1.

As per our induction hypothesis, S_ik consist of finite elements so M_ik is finite set as well.

M \ {q} is union of finitely many finite sets so M is finite.

Hence, Dickson's theorem is proved.

Use of Dickson's theorem

Dickson's theorem is used to prove Higman's theorem in Theory of Computation.

A variant of Dickson's theorem exist in Mathematics in which it is known as Dickson's lemma in Algebric theory.

With this article at OpenGenus, you must have a strong idea of Dickson's Theorem in Theory of Computation.