Prove U1+U2+U3 Theorem with Dimensions

[pte419]

1. For subsets U1, U2, U3 of a finite set, prove that

dim(U1+U2+U3) = dimU1 + dimU2 + dimU3 - dim(U1∩U2) - dim(U1∩U3) - dim(U2∩U3) + dim(U1∩U2∩U3)



2. dim(U1+U2) = dimU1 + dimU2 - dim(U1∩U2)



3. I found that U1+U2 theorem in my book, and I think I should use that, but I'm not sure where to start...

 

[EnumaElish]

Let V = U1 + U2. Now apply the theorem to V + U3.

Unless you are asked to prove 2 before proving 1. If this is the case please make it clear.

 

[StatusX]

The two equations are also true, and easier to see, with the vectors spaces replaced by finite sets and the dimensions replaced by the sizes of the sets. It's possible, by picking certain bases, to make the two problems equivalent. But, as enumaelish hints, induction is probably easier.

 

[pte419]

proof

I am only asked to prove equation one, but in doing that, I am allowed to use equation 2.

 

[pte419]

Thanks guys, I've got one more question.

I did: dim(V+U3)
and I've ended up with:
dim(V+U3) = dimU1 + dimU2 - dim(U1∩U2) + dimU3 - dim(V∩U3)

Is there a property I can use to show that dim(V∩U3) is equivalent to the terms I still need to include for the proof? I can't find anything helpful in my book...

 

[Vid]

$$dim(V\cap U_{3}) = dim((U_{1}+U_{2})\cap U_{3}) = dim((U_{1}\cap U_{3}) + (U_{2}\cap U_{3}))$$

Break that term up again using the second part and you're done.