Induction proof involving arbitrary intersections/unions

[ironspud]

Hi,

So, I was assigned a problem in my Intro Analysis course that involves proving, by induction, that the set [itex]A[/itex] minus some arbitrary number of intersections of the sets [itex]B_{j}[/itex] is equal to some arbitrary number of unions of [itex]A[/itex] minus the sets [itex]B_{j}[/itex].

I've written out a proof, but I'm not too comfortable with it. It's the notation, specifically, the notation for arbitrary intersections/unions, that I'm not 100% on - I've never taken a "Fundamentals" course, and although my professor offered a quick review of sets during the first week, he never covered this sort of stuff.

Anyway, I was hoping someone could take a look at it and help me correct any errors in the proof. Oh, and I'm new here and I've never used Latex before, so sorry in advance if this post comes out sloppy or unreadable.

Homework Statement

Use mathematical induction and your result from problem 1-1a to prove the statement below. (Do NOT prove it by showing that each side of the equation is a subset of the other side. Use induction.)

If [itex]A, B_{1}, B_{2}, ..., B_{n}[/itex] are sets, then [itex]A\setminus\bigcap_{j=1}^{n}B_{j}=\bigcup_{j=1}^{n}A\setminus B_{j}[/itex] .

Homework Equations

Result from problem 1-1a:

[itex]A\setminus(B\cap C)=(A\setminus B)\cup (A\setminus C)[/itex]

The Attempt at a Solution

We use mathematical induction.

Let P(n) be the statement [itex]A\setminus\bigcap_{j=1}^{n}B_{j}=\bigcup_{j=1}^{n}A\setminus B_{j}[/itex] .

Setting n=1, we get [itex]A\setminus B=A\setminus B[/itex], which is trivially true.

Next, we let k be an arbitrary natural number and assume P(k); we will show P(k+1).

So, we have

[itex]A\setminus\bigcap_{j=1}^{k+1}B_{j}[/itex]

[itex]=A\setminus(B_{k+1}\cap\bigcap_{j=1}^{k}B_{j})[/itex]

[itex]=(A\setminus B_{k+1})\cup(A\setminus\bigcap_{j=1}^{k}B_{j})[/itex] (from proof of 1-1a)

[itex]=\bigcup_{j=1}^{k+1}A\setminus B_{j}[/itex] .

Therefore, if [itex]A, B_{1}, B_{2}, ..., B_{n}[/itex] are sets, then [itex]A\setminus\bigcap_{j=1}^{n}B_{j}=\bigcup_{j=1}^{n}A\setminus B_{j}[/itex] .

 

[micromass]

Everything you did is correct!

Note however that you stated "arbitrary unions/intersections". This is not what you proved here. You only proved the case for finitely many unions/intersections. But I guess that is the only thing you had to prove.

 

[Dick]

Everything you did is correct!

Note however that you stated "arbitrary unions/intersections". This is not what you proved here. You only proved the case for finitely many unions/intersections. But I guess that is the only thing you had to prove.

I don't know why people assign these problems as induction. As you said this only covers the finite case. The general case is much easier. I suppose induction practice. Still, it bugs me.

 

[ironspud]

Everything you did is correct!

Note however that you stated "arbitrary unions/intersections". This is not what you proved here. You only proved the case for finitely many unions/intersections. But I guess that is the only thing you had to prove.

Yay. Thanks.

Question, though. What would be the difference between what I said I was asked to prove - i.e, "arbitrary unions/intersections" - and what I was actually asked to prove?

I know that's probably a really stupid question but, like I said, I've never taken any sort of "Foundations" course - or, for that matter, any course above Calc 1. So, yeah, I'm like a virgin, if you will, to higher maths.

 

[Dick]

Yay. Thanks.

Question, though. What would be the difference between what I said I was asked to prove - i.e, "arbitrary unions/intersections" - and what I was actually asked to prove?

I know that's probably a really stupid question but, like I said, I've never taken any sort of "Foundations" course - or, for that matter, any course above Calc 1. So, yeah, I'm like a virgin, if you will, to higher maths.

You proved it for collections of sets B_k where k goes from 1 to any finite number n. So the B's are a finite collection of sets. Induction doesn't prove it's true if the B's are a collection containing an infinite number of sets. But it's true anyway. Can you prove that?

 

[ironspud]

You proved it for collections of sets B_k where k goes from 1 to any finite number n. So the B's are a finite collection of sets. Induction doesn't prove it's true if the B's are a collection containing an infinite number of sets. But it's true anyway. Can you prove that?

No. I don't think so.

I mean, I get what you're saying. I just don't think I have the tools to prove something like that - i.e, I don't know how to represent or manipulate statements like that symbolically.

 

[Dick]

No. I don't think so.

Probably because it's too easy I think. If x is in the left side of your identity then x is in A but x is not in all of the B sets, yes? Now translate the right side into the same sort of phrasing. I.e. try to express both sides in terms of plain language statements. You don't need to prove everything symbolically unless you are Russell and Whitehead. Clearly explained reasoning does it for me. And it works for infinite sets.