[Turkmath:7928] İstanbul Bilgi University Tuesday Seminars - October 11, David Pierce

[Uğur Doğan]

Dear All,

David Pierce will give a talk at our departmental seminar on Tuesday (Oct
11) at 16:00 in the room D-135. The title and abstract below.

Best,

Piotr Kowalski
------------------------------**------------------------------**-----------
Title:  Induction and Recursion

Abstract:

One can consider the collection of so-called natural numbers as being
defined recursively by two rules:

i) 1 is a natural number.

ii) If n is a natural number, then so is n+1.

This definition means simply that the collection of natural numbers
admits proof by induction:  If A is a collection of natural numbers
such that A contains 1, and A contains n+1 whenever it contains n,
then by induction, A contains all natural numbers.

However, the admission of proof by induction does not itself justify
recursive definitions of functions on the collection of natural
numbers.  Richard Dedekind understood this when (in 1888) he
identified the properties of the natural numbers that came to be known
as the Peano Axioms.  Guiseppe Peano himself (in 1889) apparently did
not understand the difference between induction and recursion.  Some
textbooks today fail to convey the distinction.

The point of this talk is to show that it is worthwhile to pay
attention to the distinction.

For example, a finite cyclic group admits proof by induction; but it
does not admit recursive definition of a binary operation of
exponentiation, unless the order of the group is 1, 2, 6, 42, or 1806.

In a given logic, the collection of formulas is defined recursively.
This collection does allow recursive definition of functions---for
example, the function that assigns to each formula its interpretation
in a given model.  The collection of provable formulas in the logic is
also recursively defined; but this collection does not generally admit
recursive definition of functions (such as a function that assigns to
each provable formula a proof).

The natural numbers admit recursive definitions of functions because
they compose a free algebra.  This algebra has a signature with

a) one constant and

b) one function symbol, which is

c) singulary.

The usual notion of sets corresponds to this signature:

1) There is one empty set.

2) There is one kind of nonempty set (that is, sets are determined by
their members alone).

3) A member of a set is a member in one way.

The free algebra of natural numbers sits inside the larger structure
of ordinal numbers; such numbers are readily defined as sets.  If one
starts with a different algebraic signature, one can develop a
corresponding notion of sets, with a corresponding notion of ordinals,
among which are the elements of a free algebra in the new signature.
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/private/turkmath/attachments/20111008/60f94695/attachment.htm>