Topology beginer some help with proofs please....

Hi,

I am working through Bert Mendelson's "Introduction to Topology" and am having some trouble with proofs.

The text in well presented but to get a proper understanding I am working through the excercises. I am still on Chapter 1 which deals with sets and for the most part the excercises seem trivial to the point where its seems to me no proof is needed BUT there are a couple of questions that have me stumped (there are no worked solutions a problem with most maths books I find).

I would really apreciate it if somebody could walk me through a few proofs (it will probably take more than a couple before I get my head into gear), so here a couple of the excercises..

First one that seems trivial to me but one I am having trouble forming a proof for,

Let $\displaystyle A, B, D \subset S$

Prove $\displaystyle A \cap (B \cup D) = (A \cap B) \cup (A \cap D)$

Secondly not so trivial to my mind,

Let $\displaystyle \{A_\alpha\}_{\alpha\in I}$ be an indexed family of subsets of a set S. Let $\displaystyle J \subset I$

Prove $\displaystyle \bigcap_{\alpha\in J} A_\alpha \supset \bigcap_{\alpha\in I} A_\alpha$

Any help with this most apreciated.

Re: Topology beginer some help with proofs please....

The "standard" way to prove set X= set Y is to show "X is a subset of Y" and "Y is a subset of X". And the "standard" way to show "X is a subset of Y" is to start "if x is in set X" and use the definitions of X and Y to conclude "x is in Y".

So: If $\displaystyle x\in A\cap(B\cup D)$ then $\displaystyle x\in A$ and [tex]x\in B\cup D/tex]. Since $\displaystyle x\in B\cup D$, either $\displaystyle x\in B$ or $\displaystyle x\in D$.

case 1) $\displaystyle x\in B$. Since $\displaystyle x\in A$ and $\displaystyle x\in B$, $\displaystyle x\in A\cap B$.

case 2) $\displaystyle x\in D$. Since $\displaystyle x\in A$ and $\displaystyle x\in D$, $\displaystyle x\in A\cap D$.

In either case, $\displaystyle x\in (A\cap B)\cup (A\cap D)$ so $\displaystyle A\cap(B\cup D)\subset (A\cap B)\cup (A\cap D)$.

Now, if $\displaystyle x\in (A\cap B)\cup (A\cap D)$ then either $\displaystyle x\in A\cap B$ or $\displaystyle x\in A\cap D$.

case 1) $\displaystyle x \in A\cap B$. Then $\displaystyle x\in A$ and $\displaystyle x\in B$. Since $\displaystyle x\in B$, $\displaystyle x\in B\cup D$. Since [tex]x\in A[tex] and $\displaystyle x\in B\cup D$, $\displaystyle x\in A\cap(B\cup D)$.

case 2)$\displaystyle x\in A\cap D$. Then $\displaystyle x\in A$ and $\displaystyle x\in D$. Since $\displaystyle x\in D$, $\displaystyle x\in B\cup D$. Since [tex]x\in A[tex] and $\displaystyle x\in B\cup D$, $\displaystyle x\in A\cap(B\cup D)$.

Re: Topology beginer some help with proofs please....

For the second, $\displaystyle \{A_\alpha}_{\alpha\in I}\}$ and J a subset of I, start the same way:

If $\displaystyle x\in \cap_{\alpha\in J}A_\alpha$ then $\displaystyle x\in A_\beta$ for $\displaystyle \beta\in J$. But J is a subset of I so $\displaystyle \beta\in I$.

That is, $\displaystyle A_\beta\subset \cap_{\alpha\in I}A_\alpha$ thus $\displaystyle x\in \cap_{\alpha\in I}A_\alpha$.

Re: Topology beginer some help with proofs please....

Quote:

Originally Posted by

**HallsofIvy** For the second, $\displaystyle \{A_\alpha}_{\alpha\in I}\}$ and J a subset of I, start the same way:

If $\displaystyle x\in \cap_{\alpha\in J}A_\alpha$ then $\displaystyle x\in A_\beta$ for $\displaystyle \beta\in J$. But J is a subset of I so $\displaystyle \beta\in I$.

That is, $\displaystyle A_\beta\subset \cap_{\alpha\in I}A_\alpha$ thus $\displaystyle x\in \cap_{\alpha\in I}A_\alpha$.

unfortunately, it looks like you proved the wrong thing here.

suppose that: $\displaystyle x \in \bigcap_{\alpha \in I} \{A_\alpha\}$.

this means that $\displaystyle x \in A_\alpha$ for every $\displaystyle \alpha \in I$.

since $\displaystyle J \subset I$, this means that for every $\displaystyle \beta \in J,\ A_\beta = A_\alpha$ for some $\displaystyle \alpha \in I$.

since $\displaystyle x \in A_\alpha$ for *every*$\displaystyle \alpha \in I$, certainly $\displaystyle x \in A_\beta$ for every $\displaystyle \beta \in J$.

thus: $\displaystyle x \in \bigcap_{\beta \in J} \{A_\beta\}$.

Re: Topology beginer some help with proofs please....

Thankyou both. I will work through some more tomorrow and see if I can get into thinking in this way.

Something that struck me when reading HallsofIvy's first post was a similarity to Boolean algebra in places $\displaystyle \cup$ for 'AND' and $\displaystyle \cap$ for 'XOR', complement of a set 'NOT' etc..

Then I remembered using De Morgan's theorem for reducing logic circuits, so I am guessing there is a big cross over?

Re: Topology beginer some help with proofs please....

The similarity between laws for sets and for propositions comes from the fact that $\displaystyle x\in A\cup B\Leftrightarrow x\in A\lor x\in B$ and similarly for $\displaystyle \cap$ and $\displaystyle \land$.

Re: Topology beginer some help with proofs please....

yes. one can make the following correspondence:

union = or

intersection = and

subset = implies

complement = not

symmetric difference = xor

is a member = true

that is, both logical propositions and statements about sets can be formulated in terms of boolean algebra.

and what is germane to topology here, is that "subset" (containment) gives a partial order on the lattice of the power set of a topological space X, which carries over to the sub-lattice of open sets of X. so a lot of theorems in topology consist in merely "translating" logic to sets.

Re: Topology beginer some help with proofs please....

Thanks I'm making some headway with this now.

I am struggling with the following though (I seem to be struggling with anything with a dummy index or rather 2 indices defines on the same set?)

Let $\displaystyle \{A_\alpha\}_{\alpha \in I}$ and $\displaystyle \{B_\alpha\}_{\alpha \in I}$ be two indexed families of subsets of a set S,

Prove for each $\displaystyle \beta \in I$, $\displaystyle A_\beta \subset \bigcup_{\alpha \in I}A_\aplha$

I know its somethimg obvious but just keeps eluding me.

Let $\displaystyle \{A_\alpha\}_{\alpha \in I}$ be an indexed family of subsets of a set S and let $\displaystyle B \subset S$

Prove

a) $\displaystyle B \subset \bigcap_{\alpha \in I}A_\alpha$ if and only (iff?) for each $\displaystyle \beta \in I$, $\displaystyle B \subset A_\alpha$

b) $\displaystyle \bigcup_{\alpha \in I}A_\alpha \subset B$ if and only if for each $\displaystyle \beta \in I$, $\displaystyle A_\beta \subset B$

There is one more trickier question that is puzzling me but I think I can work it out if I can see how the above work.

Thanks again for patientce, I'm finding this whole thing facinating and you are really help me out.

Re: Topology beginer some help with proofs please....

Quote:

Originally Posted by

**Bwts** Let $\displaystyle \{A_\alpha\}_{\alpha \in I}$ and $\displaystyle \{B_\alpha\}_{\alpha \in I}$ be two indexed families of subsets of a set S,

Prove for each $\displaystyle \beta \in I$, $\displaystyle A_\beta \subset \bigcup_{\alpha \in I}A_\aplha$

Suppose a company of soldiers consists of three platoons. Is is not obvious to you that platoon #2 is a subset of the company?

Quote:

Originally Posted by

**Bwts** Let $\displaystyle \{A_\alpha\}_{\alpha \in I}$ be an indexed family of subsets of a set S and let $\displaystyle B \subset S$

Prove

a) $\displaystyle B \subset \bigcap_{\alpha \in I}A_\alpha$ if and only (iff?) for each $\displaystyle \beta \in I$, $\displaystyle B \subset A_\alpha$

Have you tried applying the *definitions* of subset and intersection?

Re: Topology beginer some help with proofs please....

Thanks for the platoon analogy that worked :)

Ok this is how far I got with the next one,

If $\displaystyle x \in \bigcap_{\alpha \in I} A_\alpha$ and $\displaystyle x \in A_\beta$ then $\displaystyle A_\beta \subset \bigcap_{\alpha \in I} A_\alpha$

..now it gets a bit sketchy... how do I introduce B?

am I on the right track?

Re: Topology beginer some help with proofs please....

Quote:

Originally Posted by

**Bwts** If $\displaystyle x \in \bigcap_{\alpha \in I} A_\alpha$ and $\displaystyle x \in A_\beta$ then $\displaystyle A_\beta \subset \bigcap_{\alpha \in I} A_\alpha$

I am assuming you are proving the left-to-right direction:

If $\displaystyle B \subset \bigcap_{\alpha \in I}A_\alpha$, then $\displaystyle B\subset A_\beta$ for each $\displaystyle \beta\in I$. (*)

First, it is not clear what $\displaystyle \alpha$ and $\displaystyle \beta$ in your formulas are. Did you choose them arbitrarily or using some principle? Also, why do you assume $\displaystyle x\in A_\alpha$? How are you going to get rid of this assumption (since the main claim does not have it)? Finally, $\displaystyle A_\beta \subset x \in \bigcap_{\alpha \in I} A_\alpha$ does not make sense. It can't mean $\displaystyle A_\beta \subset x$ because x does not have to be a set (typically, x ranges over points of some topological space and $\displaystyle A_\alpha$ ranges over sets of points). It also can't mean $\displaystyle A_\beta \subset \left(x \in \bigcap_{\alpha \in I} A_\alpha\right)$ because $\displaystyle x \in \bigcap_{\alpha \in I} A_\alpha$ is a proposition, not a set.

To begin with, you need an intuitive understanding why this claim is true. Suppose I is a set of classes and if $\displaystyle \alpha\in I$, then $\displaystyle A_\alpha$ denote the set of students taking class $\displaystyle \alpha$. What does $\displaystyle \bigcap_{\alpha\in I}A_\alpha$ represent? If B is a set of three guys leaving in room 528 and $\displaystyle B\subset\bigcap_{\alpha\in I}A_\alpha$, what does it mean?

Next, please write the definitions of $\displaystyle \subset$ and $\displaystyle \bigcap$ in terms of ∈:

$\displaystyle A\subset B$ if ...

$\displaystyle x\in\bigcap_{\alpha\in I}A_\alpha$ if ...

Finally, start proving (*) one step at a time. To prove "P implies Q", you assume P and prove Q. To prove "for all x, P(x)", you fix an arbitrary x and prove P(x). If you have an assumption of the form "for all x, P(x)", you can instantiate x with any well-formed object. So, the first several step in the proof of (*) would be the following.

(1) Assume $\displaystyle B \subset \bigcap_{\alpha \in I}A_\alpha$; need to prove $\displaystyle B\subset A_\beta$ for each $\displaystyle \beta\in I$.

(2) Fix an arbitrary $\displaystyle \beta\in I$; need to prove $\displaystyle B\subset A_\beta$.

(3) Using the definition of $\displaystyle \subset$, rewrite $\displaystyle B\subset A_\beta$ as "for all x, ..."

Take special care not to use any variable that you don't properly introduce. Each variable must be introduced in one of three ways:

(a) "fix x" as a part of the proof of "for all x, ..."

(b) "fix x such that P(x)" if you have an assumption of the form "there exists an x such that P(x)"

(c) "let x be ..."; you have to provide an explicit definition for x.

Re: Topology beginer some help with proofs please....

some things that may be useful:

we are working on 3 "levels" of organization:

points of a space X, such as x,y,z, etc. there is, in general, very little restriction on what these "points" might actually be. in the most common examples, they are actually "points" like the point (2,5) in the cartesian plane, but they might people as in the set {Thomas, Betty, Ed}, or functions such as the set {L: L is a line through the origin in R^{3}}, or a variety of other entities.

collections of points, organized into sets. these are often denoted A,B,C, etc. what are going to be the main sets of interest (in topology) are open sets containing a certain point x, called neighborhoods of x. note that the "index sets" also belong on this level, in fact an "indexed set" is nothing more than a function

f:I→2^{X}

from the indexing set to the set of subsets of X, in other words f(i) = A_{i}.

collections of sets (also called families of sets). often these sets are indexed by an "outside" set. one common index is the natural numbers, in which case {A_{α}} can be thought of as the more familiar {A_{1},A_{2},A_{3},....}. but we might have "too many A" for the natural numbers to work as an index.

for example, we might want to consider the family of open disks of radius 1 centered at every point (x,y) in the plane. now, there are uncountably many points in the plane (our index set is R^{2}), so we can't just list these as B_{1}, B_{2}, B_{3},...etc. we have to tag these as something like B_{(x,y)}. in some texts, families of sets are denoted by script letters, or bold-face (the topologies themselves are one example of these kinds of families), to indicate we're on "the third level up".

the "grand-daddy" of all families of sets in X, is, of course, 2^{X}, the power set of X. it is easy to get confused and think the singleton set {x} is the same as the point x.

the other mistake that is easy to make is where the space X lies: it is on "the middle level", because it itself is just the collection of all its "points". in other words, a topology on X lies in the level "above X" (families of sets), so it is a kind of "superstructure on X".

because of this "multi-layering", you need to be careful about distinguishing between "∈" (is an element of) and "⊆" (is a subset of):

x ∈ X

{x} ∈ 2^{X}

{x} ⊆ X

elements lie "just one layer down", subsets lie "on the same level" (usually the middle level, but not always: for example a topology τ on X is a subset of 2^{X}, in other words, both of these are on "the third level").

in proving A ⊆ B, one usually goes "one level down", and shows that x∈A leads to x∈B. what you are doing in your exercises (for some of them, at least), is proving relationships between families by passing one level down to relationships between sets. sometimes you have to do this *twice* to get to the individual points.

Re: Topology beginer some help with proofs please....

Quote:

Originally Posted by

**emakarov** To begin with, you need an intuitive understanding why this claim is true. Suppose I is a set of classes and if $\displaystyle \alpha\in I$, then $\displaystyle A_\alpha$ denote the set of students taking class $\displaystyle \alpha$. What does $\displaystyle \bigcap_{\alpha\in I}A_\alpha$ represent?

The set of students who are taking every class?

Quote:

If B is a set of three guys leaving in room 528 and $\displaystyle B\subset\bigcap_{\alpha\in I}A_\alpha$, what does it mean?

B is a subset of the students who are taking all the classes?

Quote:

Next, please write the definitions of $\displaystyle \subset$ and $\displaystyle \bigcap$ in terms of ∈:

$\displaystyle A\subset B$ if ...

$\displaystyle A \subset B$ if for all $\displaystyle x \in A$ then $\displaystyle x \in B$ is this right?

Quote:

$\displaystyle x\in\bigcap_{\alpha\in I}A_\alpha$ if ...

$\displaystyle x\in\bigcap_{\alpha\in I}A_\alpha$ if for any $\displaystyle \beta \in I$, $\displaystyle x \in A_\beta$ ?

Re: Topology beginer some help with proofs please....

Re: Topology beginer some help with proofs please....

Prove $\displaystyle B \subset \bigcap_{\alpha \in I} A_\alpha$ if and only if for each $\displaystyle \beta \in I$, $\displaystyle B \subset A_\alpha$.

If $\displaystyle B \subset \bigcap_{\alpha \in I}$ then for every $\displaystyle x \in B$, $\displaystyle x \in \bigcap_{\alpha \in I} A_\alpha$

If $\displaystyle x \in \bigcap_{\alpha \in I} A_\alpha$ then for every $\displaystyle \beta \in I$, $\displaystyle x \in A_\beta$

So $\displaystyle x \in B$ if and only if $\displaystyle B \subset A_\beta$

For that last line can i just write..

So $\displaystyle x \in B$ if and only if $\displaystyle B \subset A_\alpha$ as $\displaystyle \beta$ is a dummy index?