A Set of Things Not Implied

The first midterm exam for CS103 focuses heavily on set theory and formal logic, since they form the backbone for so many of the later mathematical structures and concepts that come up the course (and more broadly in discrete mathematics and theoretical computer science), and so each quarter I try to come up with at least one good question relating the two together.

A while back I came up with the following problem, which has had a lot of staying power and is a great way to test the two concepts:

Let A and B be arbitrary sets and consider the set S defined below:

S = \{ x | \lnot(x \in A \to x \in B) \}

Write an expression for S in terms of A and B using the standard set operators (union, intersection, etc.), but without using set-builder notation. Briefly justify why your answer is correct.

I highly recommend taking a minute to work through this problem if you haven’t worked with propositional logic or set-builder notation in a while.

One of the reasons I love this problem so much is that the set-builder notation for the set just plain doesn’t seem to make sense. What on earth is meant by a set of things where it isn’t implied that if the things are in one set, they’re in another? But if you proceed slowly, expand out the negation of the implication x \in A \to x \in B, then read the overall expression, you can see that it ends up working out really nicely to the set A - B. That in turn might cause you to wonder what the connection between a negated implication and the set A - B is, which might you remember that negations only fail to hold when the antecedent holds and the consequent doesn’t. That in turn might then cause you to wonder whether there are other connections between set theory and propositional logic, and now you’re starting to get a better sense for how everything more generally relates to one another.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s