Understanding Equivalence: Exploring the Meaning and Purpose

[flyingpig]

The word "equvilalent"

Homework Statement

Yes I know I spelled equivlaence wrong.

[PLAIN]http://img834.imageshack.us/img834/9285/unledkzo.png

The Attempt at a Solution

What do they mean by equivlance? What is to show?

 

[SammyS]

Statement (i) means the same thing as statement (ii) which means the same thing as statement (iii) .

They're equivalent logically speaking.

(A ⊆ B) iff (A ∩ B = A)

etc.

 

[Mark44]

Homework Statement

Yes I know I spelled equivlaence wrong.

[PLAIN]http://img834.imageshack.us/img834/9285/unledkzo.png

The Attempt at a Solution

What do they mean by equivlance? What is to show?

Two statements P and Q are equivalent if P implies Q and Q implies P. To show that three statements, P, Q, and R, are equivalent you could show that P implies Q and Q implies P, then show that P implies R and R implies P, and finally, show that P implies R and R implies P.

A simpler way to show that statements P, Q, and R are equivalent is to show that these implications are true.

P ==> Q (that is, P implies Q)
Q ==> R
R ==> P

i) Yes A is a subet of B? But so what? I so confused with the whole equivlance thing. Is it a relation condition?

See above.

ii) Isn't this true only if A = B??

No, it's also true if A is a subset of B, which is what statement i says.

iii) Can't be A = B otherwise it is empty

The three statements don't stand alone. What you are supposed to do is to show that they are all equivalent; loosely speaking, that they all say the same thing.

 

[flyingpig]

Before I even attempt this (don't want to head a long direction), this is my idea.

SHould I let some element x be in A and then deduct that since (i) A is a subset of B then x is also in B?

Then to go from there, I say that x is indeed (from what I just said) is in the intersection of A and B, i.e. x is in A ∩ B, which also means that x is in A (I am not sure about the whole A ∩ B = A (being only A?)

Then to go from there, I would say that from (i), since x is in A or in B, it follows that x is in either A or B?

That equal sign is messing me up

 

[Mark44]

Before I even attempt this (don't want to head a long direction), this is my idea.

SHould I let some element x be in A and then deduct that since (i) A is a subset of B then x is also in B?

No, you can assume that statement i is true, then deduce that statement ii is true.

IOW, assume that A $\subseteq$ B. Now let x be an element of A ∩ B. Show that x is necessarily in A.

And so on.

Then to go from there, I say that x is indeed (from what I just said) is in the intersection of A and B, i.e. x is in A ∩ B, which also means that x is in A (I am not sure about the whole A ∩ B = A (being only A?)

Then to go from there, I would say that from (i), since x is in A or in B, it follows that x is in either A or B?

That equal sign is messing me up

 

[flyingpig]

No, you can assume that statement i is true, then deduce that statement ii is true.

But that doesn't say if ii) is true, then i) is true. What if you assume ii) is true first? (follow below)

IOW, assume that A $\subseteq$ B. Now let x be an element of A ∩ B. Show that x is necessarily in A.

And so on.

No that can't right

$$x \in A \cap B \iff x \in A$$ and $$x \in B$$$$\therefore x \in A$$

But that doesn't say that $$A \subseteq B$$

And I just realize I did nothing at all...

No, you can assume that statement i is true, then deduce that statement ii is true.

Let's say now I do believe you (or the question) that $$A \subseteq B$$

(ii)
$$x \in A \cap B \iff x \in A$$ and $$x \in B$$$$\therefore x \in A$$

But (i) is true, so that $$x \in B$$ is unnecessary, and that only $$x \in A$$ because A is a subset of B

(iii) $$x \in A \cup B \iff x \in A$$ or $$x\in B$$

Since (i) is true, i.e., then only $$x \in B$$ is necessary

How do I link (ii) and (iii) together? They give off the same results from agreeing on (i), but they don't have relations

 

[Mark44]

Assume i is true.
Show that if i is true, then ii must be true.
Show that if ii is true, then iii must be true.
Show that if iii is true, then i must be true.

If you have done all this, then you're finished. How does this show that ii ==> i? It does so in a roundabout way.
Having done all the things I said in the first paragraph, we have
ii ==> iii ==> i

How do you link ii and iii together?
Assume ii is true (i.e., that A ∩ B = A). Show that this being true implies that A U B = B.

It would be helpful to your understanding to draw a simple Venn diagram, but you won't be able to use the diagram in your actual proof.

 

[flyingpig]

My example in post 6 says it is true, so i know they are true, just how to prove it.

So I just showed that

Assume i) is true and that ii) is true

(ii)
$$x \in A \cap B \iff x \in A$$ and $$x \in B$$$$\therefore x \in A$$

But (i) is true, so that $$x \in B$$ is unnecessary, and that only $$x \in A$$ because A is a subset of B

Then I showed that

Assume i) is true, then iii) is true

$$x \in A \cup B \iff x \in A$$ or $$x\in B$$

Since (i) is true, i.e., then only $$x \in B$$ is necessary

How do I link (ii) and (iii) together? They give off the same results from agreeing on (i), but they don't have relations

Now I need to show that ii) and iii), $$x \in A \cap B = x\in A$$I don't know how to go from here.

My so far proof did

i) -> ii)
i -> iii)

Does ii) -> iii) complete the circle?

 

[SammyS]

For two sets, C & D : To show (prove) they are equal, you must show that C ⊆ D and that D ⊆ C .

So for (i) implies (ii), show that A ∩ B = A is true by proving that A ∩ B ⊆ A and that A ⊆ A ∩ B , of course you prove these assuming that A ⊆ B is true.

 

[Mark44]

My so far proof did

i) -> ii)
i -> iii)

Does ii) -> iii) complete the circle?

No, because you don't have a circle.
You have i --> ii, ii --> iii, and i --> iii. You don't have anything that shows i is true.

Did you not understand this?

Assume i is true.
Show that if i is true, then ii must be true.
Show that if ii is true, then iii must be true.
Show that if iii is true, then i must be true.

 

[SammyS]

fp,

If i --> ii and ii --> iii then you have i --> iii by default.

That along with iii --> i , gives i <--> iii .

 

[flyingpig]

Show that if (i) is true, then (ii) is true


This is a bit messy, but I think I did this part correctly.

$$x \in A \cap B \iff x \in A$$ and $$x\in B$$


$$x \in A \iff x \in B \iff x \in A \cap B$$

Assume $$A \subseteq B$$ is true

Then $$x \in A \iff x \in A \cap B$$

So I just showed

phew...

 

[SammyS]

What do you mean by your two way arrows? ⟺

I know what Mark means by them, nut what do you mean?

 

[flyingpig]

if and only if? That seems to be used correctly in this problem

 

[SammyS]

Some of the iff's shouldn't be there.

 

[flyingpig]

Some of the iff's shouldn't be there.

You mean this right...?

$$x \in A \iff x \in B \iff x \in A \cap B$$So everything after this is wrong...

that is my guess because that looks the most suspicious.

I am going nowhere with this...

 

[flyingpig]

Actually wait, something hit me$$x \in A \iff x \in B \implies x \in A \cap B$$

I just have to change iff to an "implies"

Which flows better

 

[Mark44]

Actually wait, something hit me


$$x \in A \iff x \in B \implies x \in A \cap B$$

I just have to change iff to an "implies"

Which flows better

The above makes no sense as you have written it.

$$x \in A ~\text{and}~ x \in B \iff x \in A \cap B$$

Definitions are often written as iff statements. Otherwise, P <==> Q means P ==> Q and Q ==> P.

 

[flyingpig]

Sigh, this is due tomorrow and i have another midterm tomorrow.

But it does make sense because I assumed that $$A \subseteq B$$

 

[flyingpig]

I've attached a picture of where I was going with my algebra

[PLAIN]http://img198.imageshack.us/img198/91/unledctr.png

 

[Mark44]

Your drawing makes an assumption about sets A and B. The statement x in A <==> x in B is not true if you don't state that assumption.

To show that two sets (C and D) are equal, show that C $\subseteq$ D, and show that D $\subseteq$ C. This is done by showing that if x is an element of the set on the left is also an element of the set on the right.

To go from i) A $\subseteq$ B to ii) A $\bigcap$ B = A, show that 1) x in A $\bigcap$ B implies that x in A, and 2) x in A implies that x in A $\bigcap$ B.

 

[flyingpig]

Your drawing makes an assumption about sets A and B. The statement x in A <==> x in B is not true if you don't state that assumption.

But I did state it! perhaps not as clear. Sorry about that

To show that two sets (C and D) are equal, show that C $\subseteq$ D, and show that D $\subseteq$ C. This is done by showing that if x is an element of the set on the left is also an element of the set on the right.

I've shown one side, but the other side, I can't do

i.e.

I could show that some element of x in the intersection of A and B is also an element of A. BUt i can't figure out how to show if x is in A, it is also in the intersection of A and B other than what I did in that drawing.

 

[Mark44]

But I did state it! perhaps not as clear. Sorry about that



I've shown one side, but the other side, I can't do

i.e.

I could show that some element of x in the intersection of A and B is also an element of A. BUt i can't figure out how to show if x is in A, it is also in the intersection of A and B other than what I did in that drawing.

This is where you use the assumption that A $\subseteq$ B.

 

[flyingpig]

This is where you use the assumption that A $\subseteq$ B.

Yeah and I eventually ended up with $$x \in A \iff x \in B \iff x \in A \cap B$$, but you pointed it [picture] out it was wrong.

 

[Mark44]

You should not be using the <==> symbol, since you apparently don't know what it means.

Here's a counterexample to the statement in the previous post.

A = {2, 4, 8, 16}, B = { 1, 2, 3, 4}
The intersection of these sets is nonempty, but there are elements of B that are not also in A, and are also not in the intersection. There are elements of A that don't belong to B, and also don't belong to the intersection.

You have to use the assumption that A is a subset of B (second time!).

 

[flyingpig]

You should not be using the <==> symbol, since you apparently don't know what it means.

DOesn't that mean both ways to go?

Here's a counterexample to the statement in the previous post.

A = {2, 4, 8, 16}, B = { 1, 2, 3, 4}
The intersection of these sets is nonempty, but there are elements of B that are not also in A, and are also not in the intersection. There are elements of A that don't belong to B, and also don't belong to the intersection.

I guess that points out it doesn't go both ways

You have to use the assumption that A is a subset of B (second time!).

No it's the fourth time, but i keep messing it up.

I had to look up again on the definition of subset and it says A set A is called a subset of a set B if every element of A also belongs to B, because I was really thinking about that counterexample, but it looks like it doesn't matter

So I have come to the final conclusion

$$A \subseteq B \implies \forall x \in A$$, then $$\forall x \in B$$

$$\therefore \forall x \in A \cap B$$

Pleaes, please tell me this is right...