Re: Enumerable sets



george wrote:

herbzet@xxxxxxx wrote:
What is the difference between an enumerable set and a recursively
enumerable set?


Thank you for your detailed response.


The main difference is that the latter exists and the former
doesn't. OK, that is overstating the case, but the point is,
if you were working with the concepts regularly instead of
just stumbling across them occasionally, you would know
what people usually say and what they don't.


If this is a rebuke, well excuuuuuuuuse me!


If this is _not_ a rebuke, ........, well alright then!


And people
don't usually ever refer to any set as "enumerable". Enumerable
sets are referred to NOT as "enumerable" but as "countable",
which means exactly what it sounds like, namely, that you
can count their elements, that you can assign a natural number
to each element in order.


Not sure about the significance of the last "in order". If
I can assign each natural number uniquely to each element,
I'm happy. That the elements have some particular order,
(other than the numbering I give them) I don't really care
at this point.


Countable sets come in two flavors, finite and infinite.
The finite ones each have ONE natural number that is
their cardinality. The infinite ones have the SMALLEST
infinity as their cardinality and are usually, again, referred to
NOT as "enumerable" but RATHER as Denumerable.

All finite sets are trivially countable, enumerable, and recursively
enumerable, so the question of the difference between the
concepts REALLY arises for AND ONLY for denumerable
sets. All recursively enumerable sets are enumerable, either
trivially so if they are finite, or, definitionally, denumerable if
they are infinite.

But Not All Denumerable sets are Recursively enumerable.

These questions generally arise about sets that are
known-in-advance to be denumerable because they
are known-in-advance to be proper subsets of some
larger set that is known to be denumerable (like the
naturals themselves, or the set of all strings over an alphabet,
or all strings in a clearly-described language). "The problem",
in this context, is, given some known element of the larger
denumerable domain, to determine whether it is or is not
also an element of the denumerable subset.

If a denumerable [sub]set has the property that both it AND its
complement [with respect to the larger total set; there usually
IS one, in this context] are r.e., then it is recursive, or decidable.
This means you can design a [finite!] TM [all TMs have finite programs
and finite state-spaces; even though they have infinite tapes,
only a finite part of the tape has ever had anything on it, at any
finite time]
that, given an arbitrary element of the larger domain as input, always
halts with the correct answer as to whether that element is or isn't
in the subset. A more complicated kind of [sub]set is one that is
recursively enumerable but has a complement that is NOT recursively
enumerable. Here, you can write a TM that confirms membership in
the [sub]set and always halts when the input is in the set, but may
run forever (as opposed to reject-halting) if the input is not in the
set.
Finally, the most complicated subsets (of a denumerable set) are
the ones where neither the set NOR its complement is recursively
enumerable.

This was all very clear. Thanks.

What I was really thinking about was less counting a given
set or determining if x is an element of the set or not,
as in specifying or generating a set, particularly a set of
axioms. I was interested in whether if I specify an infinite
set of axioms by use, say, of a finite number of axiom schemata,
is there any difference between the resulting denumerable set of
axioms and a "recursively enumerable" set of axioms? Can
I specify a denumerable set of axioms that is not recursively
enumerable? (I would guess there wouldn't be much point in
doing that, if it's possible to do.) Are there distinctions,
terminological or otherwise, that I need to be aware of in
this context?

--
hz

--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: infinity
    ... >> Not while discussing the consequences of the axioms as they ... I commented that they were irrelevant to, and contradictory ... existed for over 2 millennia without needing any infinite naturals. ... A natural number is finite if the set of naturals less than or equal to ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... The same axioms that give us transfinite set theory are needed to ... give us the naturals, and from them the other number systems on ... The invertible functions of IFR map reals to reals. ... infinite number. ...
    (sci.math)
  • Re: How seriously do you take mathematics?
    ... >>> naturals as naturals, everywhere on the number line, that there are equal ... >>> Is it possible, as set theorists seem to believe, that an infinite ... > In an infinite binary tree, as you asserted, there ARE no terminal nodes, ... >>> When you look at this set of axioms from a purely logical ...
    (sci.math)
  • Re: infinitely many nns = infinite nns?
    ... than the naturals in any case. ... infinite sequences OF RATIONALS ... quantifier and an additional quantifier on a property ... MORE than just these 5 axioms. ...
    (sci.logic)
  • Re: Well Ordering the Reals
    ... >>> and that there is no need for infinite labels. ... specify an element in the set, then you can still have one element there, as ... I suppose if you have the null set, the power set of the null set is ... weren't specified as the naturals with no restriction of finiteness, ...
    (sci.math)