# infinitary structures

RE01 Rice Brian T. EM2 BRice@vinson.navy.mil
Tue, 15 Dec 1998 15:16:01 +0600

```> well, probably a good place to start chiseling at this problem  would be
> where Godel and Church started: at the countable level and at the
> decidable level.  basically, for countability, we probably would need a
> good arrow description of a general finite-state machine and describe the
> transformations which yield (all?) equivalent machines.  this would tell
> us if simple iteration would terminate on some procedure, which is
> obviously useful in procedural logic and type checking for recursive
> enumerability.  this also seems very simple to do without resorting to
> infinitary measures.  now, i know that standard first-order predicate
> logic has been proven not to be able to distinguish the number of natural
> numbers from uncountable structures, so this system will probably look
> very unorthodox.  this seems like a good viewpoint to start from, and i
> will add to it in the next post.
>
what we're trying to express is that a system based on sequences of finite
actions has a limit on what it can calculate, and we want to be able to
reason about a system to categorize a group of things based on whether or
not it exceeds that limit.  basically, we should probably create a model of
'time' as an infinite sequence and map its elements to the possible places
for execution of state-changes to occur, but then i don't see where the
system distinguishes other infinities from this infinity.  we would, of
course, use the original proof method which distinguishes the number of
elements in a two-dimensional infinite array from the number in a simple
arithmetic sequence, but this seems specific and only useful to a human mind
rather than a logic system.

maybe a simpler thing to do would be to create an arrow with the implicit
meaning of "all arrows created by iterating on this arrow-generation
operator indefinitely".  this doesn't address how we are to say that
iteration does so much and not more.  i mean, how do we logically
distinguish between things that can only do a countable number of things and
things which can do more?  what's the difference between our usual idea of
an iterator and an entity which updates an infinite-state machine?

maybe we should address this by describing state-machines as well.  this
suggests a circular definition to me, which would not be undesirable if it
is the only way to go.

everything isomorphic to the natural number system can be based on a
recursion/ iteration model, which only makes sense.  the natural number
system itself is based on recursion.  even category theory has a model of
the natural number system using a node representing the set of natural
numbers and an infinite number of identity mappings (imagine an arrow whose
source and destination are a single node).  however, the 'infinite' number
is only countable because all of category theory (all the papers that i have
read) assumes countability.  so, what we really have is a method for turning
an implicit assumption into a first-order object.  but even category theory
can distinguish no further.  so, we have a statement that "what i assume to
be my limit of iteration is isomorphic to the number of counting numbers
because that is what i assume", but we have nothing which postulates
uncountable structures and says "iteration is not capable of analyzing
this".  but wait!  maybe i'm wrong.  what if we took that natural number
structure and made each arrow a natural number structure or something like
that?  what if we made statements about mappings from  structures to that
natural number system object and distinguished the order of such systems by
a property of the mapping, i.e. by meta-statements?  let's see...  if i have
my 'natural number system' category with finite (even non-uniform) numbers
of objects attached (mapped) to each arrow, then there must exist a
one-to-one mapping of the whole collection of objects to the arrows.  but if
i can prove that no mapping can satisfy that condition, then the system is
something which iteration cannot encapsulate, based on a finite-state
machine.  (ok, so the statement is still circular.  but i think that we have
a metaphor for encapsulating the statement, as long as we can find a
reasonable representation of the countable numbers).

i'll pull out my book on intuitive category theory and chew on this for a
little.

```