We define $$\overline{\bigcup_{p\in P} Sp} =\bigcap_{p\in P} \overline{Sp}$$ and

$$\overline{\bigcap_{p\in P} Sp} =\bigcup_{p\in P} \overline{Sp}$$ Which are just another way to write de morgans laws. Prove these identities when P is a finite set. You can use the "regular" de morgans law to reason your transformations.

My proof by induction:

Basis: Prove the series for $k = 2$ where k is the number of sets , $k$ is an integer.

... I did this and it's not the focus of this post

Inductive Hypothesis: Suppose these laws work for any $k$ num of sets where $k\ge 2$, so $$\overline{\bigcup_{p\in \{p1,p2,...,pk\}} Sp} =\bigcap_{p\in \{p1,p2,..,pk\}} \overline{Sp}$$ as well as $$\overline{\bigcap_{p\in \{p1,p2,...,pk\}} Sp} =\bigcup_{p\in \{p1,p2,...,pk\}} \overline{Sp}$$

Inductive Step: I want to show that the laws work for $k+1$ so I want to show that firstly : $$\overline{\bigcup_{p\in \{p1,p2,...,pk,pk+1\}} Sp} =\bigcap_{p\in \{p1,p2,..,pk,pk+1\}} \overline{Sp}$$ and then same thing for the other law.

Let's focus on the first law only.

$\overline{\bigcup_{p\in \{p1,p2,...,pk,pk+1\}} Sp} = \overline{\bigcup_{p\in \{p1,p2,...,pk\}} Sp}$ $ \cap $ $\overline{Sp_{k+1}}$ //by DeMorgans

$= {\bigcap_{p\in \{p1,p2,...,pk\}}\overline Sp} \cap \overline{Sp_{k+1}}$ //by Inductive Hypothesis

. . .

Ok, now I am stuck, what else can I do so i deduce $=\bigcap_{p\in \{p1,p2,..,pk,pk+1\}} \overline{Sp}$ ?

Thanks anyone who helps.


Let K be a collection of subsets of some universal set thing S.
Then S - $\cup\ $K = $\cap\ ${ S - A : A in K }. Proof:

x in S - $\cup\ $K iff x in S and x not in $\cup\ $K
iff x in S and for all A in K, x not in A
iff for all A in K, x in S - K
iff x in $\cap\ ${ S - A : A in K }.

The other theorem is the dual of the first and has an immediate proof by taking compliments of both sides and replacing the subsets with their compliments.

As this theorem holds for any collection of subsets, it cannot be proved by induction.
I leave for the reader to transcribe this theorem and proof into that clumbsy indexed notation, if such be their want.
Recall that these are theorems; they are not definitions. The distinction is fundamentally important.

  • $\begingroup$ Thank you for the answer. Its good to note that theorems are not definitions. However I thought induction is OK since i found the answer online, I just don't understand the last statements in the proof I found here: upl.co/upload/l3Hi1Rr0J $\endgroup$ – Mandey May 19 '19 at 15:00
  • $\begingroup$ As the statement of what is to be proved is missing, the link is useless. It is pointless to prove a limited version of the theorem by induction and absurd to prove it by transfinite induction because a direct proof is so easy. The induction proof is a waste of time, $\endgroup$ – William Elliot May 19 '19 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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