Would nonmath students be able to understand this? For a course, I am required to do a presentation. The topic could either be something mundane, like a career strategy report, or something more interesting, such as a controversial topic, or an exposition on something you find interesting. What I would like to do is to present math in a way that probably no one in the class, other than myself, has seen before. That is to say, math as a deeply conceptual subject that does not necessarily involve computation with literal numbers. 
In order to illustrate what I mean by the above, I would present the following theorem: There are at least two kinds of infinite sets: Countable ones, and uncountable ones (of course I would define bijection and countable). I would present the diagonal argument, since it is elegant, ingenius, noncomputational, and short. 
My question is whether or not the general public (nonmathematicians) would be able to understand the argument. Note, I would not be explicit about the axiom of choice, etc. 
 A: My experience with explaining non-countable sets to non-mathematicians is rather weird. Unfortunately this is what my data suggest (I don't know if it is true, it is just happened every time I tried): an idea of a set you cannot enumerate is too hard for some people, there is a certain threshold (as a function of ability in abstract thinking maybe?) below which the concept just slips away from their grasp. Usually you can tell very fast whether convincing them will be fruitful (maybe long and tedious, but doable), or if their mind rejects the thought as ridiculous and often unimportant (this frequently happened for practical individuals, deeply rooted on Earth as in "Dreams? Fantasies? What I would need that for?"). On the other hand, I hadn't tried this on children, so hopefully they might behave differently.
I second Limitless' idea about showing how the rational numbers are countable: you could do it first and decide on proceeding while in class and seeing their reaction.
Also, there are other theorems that might rock the audience, just stating them
might be enough (it does depend on the audience, but I think it is worth trying). To give you some examples:


*

*[meta] post on math.SE,

*if you stir coffee, then there is a point in it which will return to its original position,

*hairy ball theorem,

*inscribed square problem,

*voting paradox,

*Goodstein's sequence and theorem (hard conceptually),

*ham and sandwich theorem,

*fold and cut theorem.


Good luck!
A: I think you would be best off explaining the idea of countable and uncountable in terms of their relationship with the integers. You would have to rely on your audience's intuition to fully explain the concept; it is best you try not to teach the basics of set theory in one lecture.
Once you explain how a countable set is defined in basic terms (e.g. "A set is countable if if every element can be mapped to one and only one integer."), you will have perfect ground for discussing uncountable sets. You will possibly have to hand-wave the idea of a "mapping" and not treat it rigorously; this would likely lead to confusion.
I don't know if I would personally present the diagonal argument. It depends entirely on how mature my audience is and precisely how much time I would have. If I were you, I would actually prefer to present the argument that the rational numbers are countable. I believe this is rather interesting and challenges you to think about mathematics. It is also just cool.
You may very well pursue your idea. I don't know your conditions well enough to judge. But I would definitely recommend showing how the rational numbers are countable. That is one of my favorite little novelties of set theory.
A: Sure, I think people would be able to understand and appreciate this example. The uncountability of say the binary infinite sequences is usually my choice for illustrating mathematical logic to non-mathematicians. 
As for being able to understand, I think anyone with enough interests in your presentation to seriously think about the definitions would be able to understand what sets, functions, injective, surjective functions are. I think people intuitively understand what functions are. You should explain the domain and range of functions. Usually people are a little surprised at why you would consider non-surjective function, but usually something like a constant real value function will convince them that this very common. Then injective functions and surjective are very intuitive if you at least say that "different things map to different things". The concept of a bijection is very natural. I even heard someone once claim that babies innately understand bijection: If someone asked you if there were more things in box $A$ than in box $B$, would it be more natural to starting pairing things up or invent names for "numbers" and then start counting???
As you mentioned, the diagonalization argument is a very nice example for illustrating an aspect of mathematics that non-mathematician are not often aware of : that mathematics works with understand concepts. Mathematics can work as an sequence of organized, neatly presented ideas rather than long tedious computations. This example shows that mathematics requires creativity to solve problems rather than the view that some may have that mathematics only requires mindless care to not miss a + or - sign. And of course, you can always mention that this very simple proof is one of the most important ideas or technique in mathematics, especially set theory and computability theory. 
A: I have seen some attempts to refute the diagonal argument around the internet (the "good math, bad math"-blog attacked some of these refutations a while ago). This proves that some people don't get it. But maybe that isn't a bad thing: it allows you to add some controversy to your talk.
