Why is the set of formal propositions enumerable?

Question

Thanks for your reading,

A set S is recursively enumerable if one can write a program such that, once the program is launched, it will print a list of elements of S and, for all elements s ∈ S , the program will eventually print out the element s .

Which of the following are recursively enumerable sets?

A. N (where N means nature numbers)

B. N×N (where N means nature numbers)

C. The power set P(N) of subsets of N.

D. The set of formal propositions.

E. The set of rational numbers Q .

The answer is "A,B,D,E"

I'm confused about the choice "D. The set of formal propositions"

Thanks indeed!

PS: "formal propositions" means "the proposition made up of specific symbol rather than English words" (for instance, ョx∈N, x<5)

==========

I have already posted this on stack-overflow by my mistake but get some answer:

Reference: https://stackoverflow.com/questions/21499731/why-is-the-set-of-formal-propositions-enumerable

"Formal propositions are recursively enumerable only if we assume that we are only interested in the "writable" ones (such, which have finite length in terms of symbols from some finite/enumerable vocablurary).

In such case we can write the program, which given pair (A,B) writes A'th proposition of length B, and than use our program for writing down NxN to write them down. The existance of the first program is based on assumption that: we use some finite set of symbols to write them down (or at least enumerable); our propositions are finite in terms of length (our program has to be able to print them out)."

==> If I can do with this technique, why "C. The power set P(N) of subsets of N." is not the answer to this question?

Answer 1

The power set P(N) is not even enumerable, let alone recursively.

Answer 2

Note that every recursively enumerable set $S$ is countable. This is because we can assign each element in $S$ the least step after which it was printed. Since "eventually" means "after finitely many steps", we have established an injection from $S$ into $\Bbb N$. Therefore $S$ is countable.

The power set of $\Bbb N$, however, is not countable. Therefore it couldn't possibly be enumerable.

As for the set of formal propositions, note that this is really just the set of finite strings over the alphabet (which I assume is countable). So this is really just the same thing as printing all the finite sequences of integers, which can be done by a Turing machine (e.g. we can decode from each integer the prime numbers which divide him without remainder, and for each such prime number we can find the largest power of the prime number dividing the integer; then we can decode a finite sequence by reading off the powers of prime numbers.)