Math Proofs

So I’m a Computer Science major, which means that I get to do a lot of proving things.

“Professor! I think this algorithm runs in O(n log n) time, not O(n ** 2) time if you do this!”

“Oh yeah? Prove it.” footnote:[This is a dramatization. Nothing like this has ever happened to me, and I doubt a professor would actually say that.]

So the next required mathematics course for CS majors is Math Proofs - not calculus, which I thought I would be in. footnote:[I’m only a little disappointed. I really like calculus.]

Set Theory

Most proofs are, apparently, based on Set Theory - the study of sets of things.

For example, if I say `X = {1, 2, 3}`, `X` is a set containing `1`, `2`, and `3`. Note that this is order-independent, so `{1, 2, 3} = {3, 2, 1} = {2, 3, 1}`

Like with numbers, there are a few things that you can do with sets: you can make a big set from all the things in smaller sets; you can make a smaller set using only the things that are in a whole group of bigger sets; you can ask if something is in a set; you can ask if all the somethings in a set are in another set, too.

You can have sets with infinitely many things in them! But that would be tiresome to write out, so you can write them using ’…’s, like this: `{1, 3, 5, . . . }`, or by using a condition, like this: `{x : x is a positive odd number}` (This reads as “The set of all x (where/such that) x is a positive odd number.”).

Practice

The first thing that you can do with sets is unify them. If I take the union of `{1, 2, 3}` and `{3, 4, 5}`, the result is the set that has any element that is is either of the two sets: `{1, 2, 3, 4, 5}`. This is written as `{1, 2, 3} U {3, 4, 5} = {1, 2, 3, 4, 5}`.

The second thing you can do is intersect them. If I take the intersection of `{1, 2, 3}` and `{3, 4, 5}`, the result is the set that has elements that appear in both of the two sets: `{3}`. This is written as `{1, 2, 3} ∩ {3, 4, 5} = {3}`.

You can ask “Is `3` in `{1, 3, 5, . . . }`?”. This is written like this: `3 ∈ {1, 3, 5, . . . }`, which is true. This is like saying `8 = 8`; it’s a true statement. You can also say something like `x ∈ {1, 3, 5, . . .}`, which is just telling you something about `x`. `x` is in that set.

There’s other stuff that you can do with sets, but I’m frankly figuring out how to type it for this blog. I edit this blog as plain text, and then the formatting gets applied. If I want to show you proper mathematical notation, I have to figure out how to make my post-processor change certain text into the correct symbols.

I’m still playing a little bit of catch up in this course and with this summary, but I will have more for you next week. In the mean time, there are plenty of resources you can check out if sets really get your blood boiling. I actually recommend link:https://wikipedia.org[Wikipedia], because the basic math-related articles are usually really precise and clear. If they’re not clear enough for you, or if you just want to wait to here my stunning take on the topic, just wait until it’s covered in class, and I’ll summarize it for you!