In computation we are profoundly tied to the finite. Useful computations require finite time, finite space, and finite resources to carry out. The material of computation consists of finite data with all manipulations tantamount to the finite operations of arithmetic, however extended over interesting material. Being chained to the finite is no more limiting than it is in logic and in human language, with its recording of finite expressions over any media: sound, print, and digital electronics.
Yet, in reasoning about computation--in having any articulated theories of computation--we bump into notions of the infinite. The theories of logic, of numbers, and certainly of mathematical functions and sets, plunge us squarely into having to account for the infinite and however it is approachable from within the finite, formal world of computation. If for no other reason than to speak of computations that approximate mathematical objects having no finite expression we must at some point introduce enough to see the chasm between the finite and the transfinite, and comprehend its crossing. And to recognize that there are more (mathematical) functions than we can express and compute involves us in establishing that we have nonetheless captured a means to realize, through computation, the most that can be expressed.
I'd meant to avoid set theory and the transfinite as long as possible in the oMiser theoretical development stage. Discussions on electronic distribution lists have shown that there must be "due diligence" on this topic from the outset. Contemporary mathematics reaks of the infinite. Without motivating the connection between the finitary realms of computation with those stellar (no cosmic) degrees of abstract thought, I am too limited in clearly situating computation relative to the reach of mathematical thought.
-- Dennis E. Hamilton
Seattle, 2002 July 25Important Note: This document is encoded in Multi-Lingual HTML using UTF-8 encoding. There is reliance on special character sets for mathematical symbols. These symbols may not render properly in your browser. The intention is to adopt the presentation model of MathML in a future version of this and other Miser Project pages that employ mathematical typography. -- dh:2002-07-25
Content
The Basic idea of a formal system and its interpretation, kept small -- cross-reference another note as needed to do that.
The Peano axioms.
Concerns expressed with reasoning about "all the numbers."
Discussing N as a set and reasoning about that.
Getting ahead of ourselves - all the work in computation theory and in mechanical linguistics that hinges on the denumerable and the countable. Grammars, languages, theories, expressions in logic, computer programs, data, etc. The formal cases are enough to require some sort of resolution -- there is too much success to deny ourselves such methodology if we can bridge the chasm.
The representation of ordinals in set theory - von Neumann ordinals. Capturing the idea of ordering and using ε as the ordering relation.
Consideration that allowing more than we can attain provides the abstraction that covers all matters that we will encounter.
Consolation in [Devlin2000].
We are going to use "the transfinite" for transfinite ordinals and cardinals and for sets that exhibit such transfinite "number."
We will develop the von Neumann ordinals and relate them to the Peano numbers, appealing to the presentation of [Suppes1972].
Then we define the set of all these ordinals, ω (check this nomenclature), and commit ourselves with the axiom of infinity. It's that simple.
Comment on trust and alignment of a large community, the testing in practice, etc. The social dimension of that. (Refer to McKenzie? Probably)
We look at the basic ways of establishing that a subset of an infinite set has the same cardinality as the set - the equivalence operation, M ˜ N and development in [Cantor1915:pp.85-89]
Introduce card M as the cardinal number of a set and use
card M = card N if-and-only-if M ˜ N
Be careful about the use of equality here. This is some other kind of beastie. Maybe don't even talk about cardinal numbers and only deal with particular sets and their cardinality.
Significance of [Cantor1915:pp.89-91]:
The cardinals are well-ordered.
If M ˜ N and N is-part-of P and P ˜ Q and Q is-part-of M, then M ˜ P.
...
- Version 0.10 2002-07-25: Initial Draft and Placeholder (orcmid)
- Provide the basic boilerplate for filling in where I am in Theorizing about Theories: Cantor's Equipollence. This is to provide a better place to work while the material is formative, capturing notes, and stitching the parts together while providing something I can discuss with others as soon as possible.
created 2002-07-25-18:58 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 04-01-06 13:03 $
$$Revision: 6 $