Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently trying to learn about conducting proofs by using subsets. In my textbook, there is an example on this very matter; however, the seem to do something that is in contradiction with what my professor has said: in the example, they use laws of propositional calculus, yet my professor has claimed that doing this is incorrect, but she herself is guilty of doing this in her own examples (she is a rather incompetent teacher). So, who is at fault, the book or her? Are we allowed to use laws in our proofs by subsets? I have been trying to find information on the internet, but have been unsuccessful.

Edit: As an example problem, "Show that if $A$, $B$, and $C$ are sets, then $(A∩B∩C)^c=A^c∪B^c∪C^c$.

share|improve this question

closed as not a real question by BenjaLim, ncmathsadist, Potato, Jim, TMM Mar 17 '13 at 2:06

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

This question is impossible to understand. What exactly are you doing? Moreover, claiming "incompetency" at teacher side without even writing down carefully what has been said doesn't make the reader very happy. –  Giuseppe Negro Mar 17 '13 at 0:18
I think it rather clear what I am inquiring into: I am asking about the general approach to proofs by subsets. Additionally, I thought that this would be better than posting a problem I am working on and asking help with it, without having done any work myself. The intimation towards her incompetency explains why she contradicted herself in class--and on several occasions, if I might add. –  Mack Mar 17 '13 at 0:22
proof using subsets?! Please give an example. –  user59671 Mar 17 '13 at 0:28
I'm sorry, I didn't mean proof using subsets, I meant to say proof by subsets. Here is an example problem: Show that if $A$, $B$, and $C$ are sets, then $(A∩B∩C)^c= A^c∪B^c∪C^c$. And I am asked to prove that these are subsets of each other, thus proving that they are equivalent. –  Mack Mar 17 '13 at 0:30
I would describe the "general approach to proofs by subsets" as "first prove the left hand side is a subset of the right hand side, then prove that the right hand side is a subset of the left hand side, and together these results imply equality." More concretely, "show that an arbitrary element of the left hand side is also an element of the right hand side, and then show that an arbitrary element of the right hand side is also an element of the left hand side, and together these imply that the collections of elements are the same." (I'm still not entirely sure what you're asking.) –  lamb_da_calculus Mar 17 '13 at 0:44

1 Answer 1

up vote 1 down vote accepted

This is a useful way to prove that two sets are equal. If you can prove that each is a subset of the other, you have succeeded in proving them equal. In your specific example, you would say something like "Let $x \in (A \cap B \cap C)^c$ and prove $x \in A^c \cup B^c \cup C^c$. This gives you one direction of inclusion. Then you say "Let $x \in A^c \cup B^c \cup C^c$" and prove $x \in (A \cap B \cap C)^c$. This gives you the other direction of inclusion. The comparable thing in the real numbers (but is seems less often useful) would be to prove $y=z$ by proving $y \le z$ and $z \le y$.

share|improve this answer
Okay, I see. That's pretty much what I understood the process to be. Just to be clear, I am allowed to use laws (such as De Morgan's) while proving either side is a subset of the other? –  Mack Mar 17 '13 at 10:59
@Mack: yes, you can use any logicallgy acceptable method of proof. In this case, using De Morgan's laws without going through the subset argument would be easier. The subset approach will get you there just fine. –  Ross Millikan Mar 17 '13 at 13:36
Okay, but if I was to strictly do a proof by subsets, I would just suppose $x \in~thing_1$, and describe how $x$ being in $thing_1$ also describes $x$ being in $thing_2$, and not use any sort of laws? –  Mack Mar 17 '13 at 13:51
@Mack: you might well need to use some laws to get there. In this case, probably not. For the reverse direction, you can say if $x \in x \in A^c \cup B^c \cup C^c$, it must be in the complement of one of them, so will not be in $(A \cap B \cap C)$, so will be in $(A \cap B \cap C)^c$. But in a more complicated case, you might need to use some set laws to discover the important structure of one of the sets so that you can make the proof. –  Ross Millikan Mar 17 '13 at 14:06
@Mack: you will have to clarify that with your teacher. –  Ross Millikan Mar 17 '13 at 14:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.