L'insieme dei numeri naturali ha un numero infinito di elementi. Per un insieme finito è sempre possibile trovare un algoritmo che enumera tutti gli elementi...
E' interessante notare l'analogia con gli iteratori, ma più in generale con una classe che implementa un enumeratore: rappresenta l'algoritmo con cui vengono "snocciolati" tutti gli elementi dell'insieme.
Un insieme ricorsivo (http://en.wikipedia.org/wiki/Recursive_set) è un insieme ricorsivamente enumerabile, il cui complemento è, a sua volta, ricorsivamente enumerabile. Non tutti gli insiemi sono ricorsivamente enumerabili e, a maggior ragione, non tutti gli insiemi sono ricorsivi... Questi argomenti sono legati alla teoria della calcolabilità, una parte interessantissima dell'informatica teorica. Sono concetti isomorfi a quelli di computabilità di una funzione. Wikipedia indica una serie di approfondimenti in tal senso.
Per chi fosse invece interessato ad una divagazione informale su questi argomenti consiglio di leggere http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach, un vero capolavoro!
Possiamo cercare di scrivere una semplice classe C# che implementa il concetto di insieme ricorsivamente enumerabile e che "prova" ad enumerarne il complemento:

class RecursivelyEnumerableSet : IEnumerable<int>
{
   private IEnumerable<int> sequence;
   public RecursivelyEnumerableSet(IEnumerable<int> sequence)
   {
      this.sequence = sequence;
   }

   public virtual IEnumerator<int> GetEnumerator()
   {
      foreach (int n in sequence)
         yield return n;
   }

   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
   {
      foreach (int n in sequence)
         yield return n;
   }

   public bool Contains(int number)
   {
      foreach (int n in this)
      {
         if (n == number)
            return true;

         // Se non ponessi un limite, per insiemi infiniti, non mi fermerei mai...
         if (n > 10000)
            return false;
      }
     
      return false;
   }