# Dickson's Theorem in Theory of Computation

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

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:

- Dickson's Theorem in Theory of Computation
- Proof of Dickson's theorem
- 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:

- N is a set of positive integers. Let n âˆˆ N.
- Let us define two points p and q in N
^{n}.

p = (p_{1}, p_{2}, ..., p_{n})

and

q = (q_{1}, q_{2}, ..., q_{n})

- 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^{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:

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

Prove for n = 1.

If n = 1, then:

- M = âˆ… (empty) if S = âˆ…
- 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^{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.