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.

The Wikipedia article on the algebra of sets briefly mentions the following:

These are examples of an extremely important and powerful property of set algebra, namely, the principle of duality for sets, which asserts that for any true statement about sets, the dual statement obtained by interchanging unions and intersections, interchanging U and Ø and reversing inclusions is also true. A statement is said to be self-dual if it is equal to its own dual.

The article doesn't talk about how this is proven and the linked article wasn't particularly enlightening to me. This is a surprising theorem to me and I am interested in finding out how to prove it. What kind of math would be involved in proving it? How would we prove this?

share|improve this question
    
What is statement about sets supposed to mean? –  Git Gud Jul 1 '13 at 23:51
    
You would prove this by applying the complement operator to an equality of sets involving unions and intersections. We have $(A\cap B)^C=A^C\cup B^C$ and $(A\cup B)^C=A^C\cap B^C$ so when the dust clears after applying $-^C$, all sets are replaced by their complements, all $\cup$s replaced by $\cap$s and vice-versa. –  anon Jul 2 '13 at 0:00
    
I think this is not as deep of a theorem as that excerpt alludes to. As anon points out, this is essentially Demorgan's Laws and elementary properties of Boolean algebras: en.wikipedia.org/wiki/Boolean_algebra_(structure) –  Ryan Sullivant Jul 2 '13 at 1:28

1 Answer 1

up vote 2 down vote accepted

As written,the statement is false. For example, the statement $\neg (\exists x)(x\in \varnothing)$ won't flip around that way. The actual point, however, is that the set of all subsets of a set $U$ forms a lattice with join $\cup$, meet $\cap$, bottom $\varnothing$, top $U$, and ordering $\subseteq$. Thus the usual lattice dualities apply.

share|improve this answer
    
Fairly sure the Wikipedia article was talking about statements involving sets, unions, intersections and equalities. What are the usual lattice dualities, and does OP know of them? –  anon Jul 1 '13 at 23:55
    
Surely, it is not saying what you say in the first sentence, but instead is referring to lattice duality. Actually, algebra of sets are always Boolean algebras... –  Ryan Sullivant Jul 2 '13 at 1:23
    
Thank you, this is exactly what I was looking for. I've been reading up on lattices now it is very interesting. Can you recommend any resources for learning more about lattice theory? –  crf Jul 4 '13 at 4:30
    
Not really. I've only read a little about them myself. –  dfeuer Jul 4 '13 at 19:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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