# De Morgan's Law

I'm reasonably certain about (b) since I found a proof online. However, I'm not sure about (a) and the part where I have "for all n." Sorry for the poor quality.

http://i111.photobucket.com/albums/n149/camarolt4z28/Untitled.png?t=1296529661

http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110131_210113.jpg?t=1296529704 [Broken]

Last edited by a moderator:

Mark44
Mentor
I'm pretty sure that you are intended to use induction on these.

I'm pretty sure that you are intended to use induction on these.

I don't know how that would work in this case. It's all new to me.

What's wrong with the way I did it?

Dick
Homework Helper
I'm pretty sure that you are intended to use induction on these.

Why? You don't know the index set is even ordered. And you don't need to.

chiro
Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

I'm not familiar with induction.

Dick
Homework Helper
Like Mark said induction is a good tool.

If you are familiar with induction you can see that it is well suited to it.

Extending the case from k to k+1 would require just a little manipulation and some rearrangement of terms.

This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

Last edited:
chiro
I'm not familiar with induction.

Induction is basically a way to prove things by "domino theory".

When I say domino theory I mean that you prove it for the first case, then you assume its true for k cases and prove it for the (k+1)th case.

So in your example we know its true for NOT(A and B) = NOT(A) OR NOT(B).

Now assume its true for n = k

So lets say you have NOT(A(0) and A(1) and A(2) and ... and A(N-1)) = NOT(A(0)) or NOT(A(1)) or ... or NOT(A(N-1)).

Lets say LHS = B, RHS = C

D = NOT(NOT(B) AND A(N)) = NOT(NOT(B)) or NOT(A(N)) = B OR NOT(A(N)

But B = C so

D = B OR NOT(A(N)) = C OR NOT(A(N)) = RHS for term k + 1

Proved for term k+1 assuming true for term k.

Therefore proven by induction.

If you want to know more about induction pick up a book on discrete mathematics or if you are keen enrol in a course in discrete mathematics.

chiro
This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

I said induction is a good tool. I did not say induction is the only tool. With mathematics there will for most problems be more than one method that yields the correct solution.

Dick
Homework Helper
I said induction is a good tool. I did not say induction is the only tool. With mathematics there will for most problems be more than one method that yields the correct solution.

What's wrong the original proof? Why do you need induction?

Mark44
Mentor
Why? You don't know the index set is even ordered. And you don't need to.
The index looks to be 1, 2, 3, ..., n.

Mark44
Mentor
This is baloney. There is nothing really wrong with the proof as presented. This is logic. There's no difference between the proof with two sets and the proof with an uncountable infinity of sets.

How do you get an uncountable infinity of sets?
$$(\cup_n A_n)^C = \cap_n A_n^C$$

Dick
Homework Helper
How do you get an uncountable infinity of sets?
$$(\cup_n A_n)^C = \cap_n A_n^C$$

I'm saying it wouldn't make any difference to the proof if there were.

The index looks to be 1, 2, 3, ..., n.

n ISN'T the number of sets. It's an index. That's why it's a subscript on the A. And the index looks to me like n is an element of 1,2,3,... reading between the lines on the problem statement. I.e. perhaps there are an infinite number. Perhaps there aren't. It doesn't matter to the proof. Just because you see 1,2,3... in a problem doesn't mean it's solved by induction.