Set theory and induction

Prove that for any two sets A and B, (AUB)' = A' intersects B'
I have done that.

Prove by induction that the complement of the union of any number of sets is equal to the intersection of the complements.
What? I don't know how to do induction with something so abstract.

(edited 11 years ago)

Reply 1

Hopple

18

(AUBUC)'=((AUB)UC)'

Or write out the sets as

A_i

Reply 2

Y__

13

It works the same as for less abstract concepts. What the question wants you to do is:

1. Prove that this holds for two sets. You have done that.
2. Assume that this holds for n sets, i.e. that (A1 u A2 u ... u An)' = A1' intsc A2' intsc ... An', and conclude that it holds for n+1 sets (Hint: Use part 1 for this.).

You have then shown, by induction, that it holds for any number of sets.

Reply 3

bbrain

OP

2

Original post by Y__

It works the same as for less abstract concepts. What the question wants you to do is:

1. Prove that this holds for two sets. You have done that.
2. Assume that this holds for n sets, i.e. that (A1 u A2 u ... u An)' = A1' intsc A2' intsc ... An', and conclude that it holds for n+1 sets (Hint: Use part 1 for this.).

You have then shown, by induction, that it holds for any number of sets.

I used the Venn diagram for the first part, so surely I shouldn't use that for an infinite number of sets?

Reply 4

Y__

13

I don't think "I drew a Venn diagram" is an acceptable solution for the first part. Also, you're not dealing with an infinite number of sets, why do you think so?

Reply 5

bbrain

OP

2

Original post by Y__

I don't think "I drew a Venn diagram" is an acceptable solution for the first part. Also, you're not dealing with an infinite number of sets, why do you think so?