Maths - Number Theory

Concepts

Enumerable Sets

A set Σ is enumerable iff its members can be listed (possibly infinite list) off in some numerical order with every member appearing on the list (allowing repetitions). enumerate

Effectively Enumerable

A set Σ is effectively enumerable iff either Σ is empty or there is an effectively computable function that computes it.

theorem

The set W of all effectively enumerable sets of natural numbers is itself enumerable.

theorem

Some sets of numbers are not effectively enumerable and hence not effectively decidable.

theorem

There is an effectively enumerable set of numbers K such that its complement

K
is not effectively enumerable.

theorem

Some effectively enumerable sets of numbers are not decidable.

Effectively Computable

A one-place total function f: ΔΓ is effectively computable iff there is an algorithm which can be used to calculate, in a finite number of steps, the value of the function for any given input from the domain Δ.

Characteristic Function

The characteristic function of the numerical property P is the one-place function
cP: NΩ such that if n is P, cP(n)=true else cP(n)=false.

(see subobject classifier in category theory/topos).

The characteristic function of the two-place numerical relation R is the two-place function cR: (N,N)Ω such that if m is R to n,then cR: (m,n)=true else cR: (m,n)=false.

Effectively Decidable

A property/relation is effectively decidable iff there is an algorithmic procedure that a suitable programmed computer could use to decide, in finite number of steps, whether the property/relation applies to any appropriate given items(s).

or

A numerical property/relation is effectively decidable iff its characteristic function is effectively computable.

Numerical Domain

The numerical domain of an algorithm Π is the set of natural numbers n such that, when the algorithm Π is applied to the number n as input, then the run of the algorithm will eventually terminate and deliver some number as output.

theorem

W is an effectively enumerable set of numbers iff it is the numerical domain of some algorithm Π.


metadata block
see also:

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.