Set Theory Help

I have a test coming up on set theory, so the basic definitions, set operations, relations and functions. On the test I will have to do proofs involving all of these (subset, unions, intersections, relative complements, cartesian products, different kinds of relations, partial order/strict order, inverse, composition, fuctions, one-to-one functions, onto funtions, etc.)

What I was wondering is if anyone has any tips for doing proofs. Usually I have a problem getting started with the proof...what rules to start with and what exactly I want to end up with. Then I think of using certain theorems but when I look at solutions from my teacher he uses different theorems.

Any tips would be great

-
So what specific problems do you have when starting proofs? – Ink Nov 16 '12 at 18:16
trying to decide which direction to take, usually I like to use direct proofs but deciding where to start and figuring out what I need to get to. For example I was trying to prove this problem: (A-B)-C = (A-C)-(B-C) I thought I would just need to look at the definition of - and work my way to (x is an element of A and x is not an element of C)and ~(x is an element of B and x is not an element of C) I got part way through this proof and got stuck, but when I looked at my teachers solutions he used a theorem that brought in absolute complements – Kristen Nov 16 '12 at 18:21
Kristen There are usually MANY ways to prove a statement. Lots of angles of approach. Don't get discouraged if your proof is a little different than another proof. You do, of course, want to make sure you proof is sound. – amWhy Nov 16 '12 at 18:29
When proving set equality, you prove that each set is contained in the other. So when proving things like $(A - B) - C = (A - C) - (B - C)$, just appeal to the definition. Let $x \in (A - B) - C$. This means that $x \in A - B$ and $x \notin C$, which further implies that $x \in A$ and $x \notin B$. Therefore, $x \in A - C$, and $x \notin B - C$. Hence $x \in (A - C) - (B - C)$. That's one inclusion. – Ink Nov 16 '12 at 18:30
Feel free post questions here at math.se for clarification of any definitions you've encountered, or in knowing when one definition applies, vs. another; first, you might want to search math.se for prior questions and answers address your problem. – amWhy Nov 16 '12 at 19:06

3 Answers

The key to writing proofs is to "let the definitions do the work", but to do so, you need to have a firm grasp of the definitions you've learned, and how/when to unpack and apply them: e.g., what does it mean to say one set is a subset of another subset? Similarly for the definitions of the union and intersection of a set, the relative complement of a set (set minus), etc.

In addition to having a solid grasp of the definitions you need to know, keep in mind that any "givens" you have to work with are also tips that you'll probably need to use in the ensuing proof.

One tip: You'll want to keep in mind that typically one proves that two sets are equal by showing each is the subset of the other, i.e., $A = B \iff A\subseteq B \;\text{ and}\;\;B\subseteq A.$

Another tip: To show that the cardinality of one set is equal to that of another, you can show that there exists a bijective (one-to-one & onto) function that maps the elements of one set to the other. Conversely, if you know that there exists a one-to-one correspondence between two sets, you know that the sets are equivalent, in terms of cardinality. Do you see how, in this case, you'd need the definitions of what it means to be a "function" that is "one-to-one" and "onto".

There's really no shortcut to having a firm grasp of the definitions you've learned.

Simply "memorizing" definitions can easily lead to confusion (going blank); and in any case, such rote "learning" is quickly forgotten. Try to understand the definitions, using examples, when necessary, until they make sense, and more, try to understand how those definitions relate with one another, and with what you've already learned.

There are many ways to approach a proof, in terms of "direction." Direct proof, proof by contradiction, inductive proofs: you'll want to develop facility and flexibility with such strategies. Note that there is no "right" solution/approach - in terms of proving a statement - as there is with arithmetic calculations, or finding a derivative.

-
Another thumbs up wouldn't hurt. :-) +1 – Amzoti May 17 '13 at 1:17

Try to recollect the relevant laws and then eliminate the ones which do not have direct application thereafter use the concept of equality of two sets or use the unknown element method remember maths is about pattern

-

You should start by fully understanding what you have to prove. Then you have to fully understand the definitions and theorems related to the proposition. Then you should begin by unwinding the definitions using the above tools, and then derive the wanted conclusion.

This is the only general approach I can recommend. Mathematics is about creativity, not about algorithmic solutions.

-