[praptak]

> At the very least a good course in discrete mathematics is a good start

I believe that the best starting point to get to incompleteness is formal logic. This is the basic set of concepts that lets us make terms, statements and finally proofs the subject of formal mathematical study, thus tying the loop (formally mathematically defined reasoning about formally mathematically defined reasoning :-) ) that leads to Goedels proof.

Discrete mathematics is helpful but it is rather low level, the core concepts in incompleteness come from formal logic.

[vbtemp]

I consider a solid discrete math curriculum to provide a reasonable background in first and second order logic

[neilc]

I would be surprised to find second order logic discussed in an introductory discrete math curriculum.