Dickson's Theorem in Theory of Computation

Get FREE domain for 1st year and build your brand new site

Internship at OpenGenus

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 Nn.

p = (p1, p2, ..., pn)
and
q = (q1, q2, ..., qn)

  1. Point p is dominated by q if pi <= qi 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) Nn 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 Nn-1.

S is a subset of Nn 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 pi <= qi - 1.

This results in:

M \ {q} ⊆ (Ni-1 x [1, qi - 1] x Nn-i)

which is equated to:

M \ {q} = Union (i=1 to n) Union (k = 1 to qi-1) Mik

There is a lemma:

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

Therefore, Sik is a subset of Nn-1.

As per our induction hypothesis, Sik consist of finite elements so Mik 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.