Math Is Fun Forum

dchilow

Member

Registered: 2007-03-05

Posts: 27

Need Abstract Math Help!

Let A be a set. Prove that there is no injection f: P(A) to A.

Please someone help me on this!

I have started it by supposing there is an injection f: P(A) to A.
I am not sure where to start.  I don't even know what my cases could be.

Last edited by dchilow (2007-04-19 13:09:41)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

You're off on the right foot.  Unfortunately, this proof requires a trick.  At least that's the only way I know how to do it.  Consider the set:

T = {f(x) : f(x) is not in x}.

Remember, x is an element of the powerset, and is thus a set itself.  f(x) is an element of A.

Use the fact that f is injective to prove that this is a valid set (i.e. it can't have an element both in and out of it.  This is not a valid set if f is not injective).  Now, note that this is a subset of A, and thus, must be in the domain of f.   Finally, assume two cases, f(T) is in T and f(T) is not in T.  Reach a contradiction in each case.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

dchilow

Member

Registered: 2007-03-05

Posts: 27

Re: Need Abstract Math Help!

Ricky, I tried doing the proof like you said, I am not sure I fully understood what you were saying.  Could you please look at the draft I sent my professor and help me on this, thanks. The red comments are from my professor.

Last edited by dchilow (2007-04-21 10:09:04)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

z is an element of the  power set, and thus, a set itself.

That should be "S is a subset of A, and thus, an element of the power set".

Your teacher says:

sets aren't statements, so you can't speak about their validity (or lack thereof)

This is incorrect. It is possible to construct a set such that there exists an element a such that a is in the set, and a is not in the set.  But inclusion in a set is exclusive, you can't be both in and out of a set.  Thus, such a set would be invalid.  To see this, just come up with a non-injective mapping between a set and its power set, then compute what S would be.  You will find there is at least one element which is both in and out of S.

Now when you say "z = S", I believe you got to my post early.  I later edited this part out, as it was stupid (on my part).

From your teacher's writing, it sounds like there is an easier way to do this proof, though I have no idea what it would be.

I'll post a full proof either tonight or early tomorrow, but I really recommend you don't use it, as it sounds like it would go a little bit beyond your knowledge.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

dchilow

Member

Registered: 2007-03-05

Posts: 27

Re: Need Abstract Math Help!

Ricky,

In my proof where I have "Now we will assume two cases, either f(s) is an element of s or f(s) is not and element of s.  If f(s) is an element of s, then s is a subset of A and f(s) is not an element of S." My professor says that I need to be more explicit here.  He says that I need to use the assumption that f is injective here to have it make more sense before I declare it a contradiction.  I have stared at it for hours and don't understand what it is he wants me to say.  Maybe you could help me out on this.  Also, where I have my other case too. He is asking for clarification.  I don't know how to do it.

Last edited by dchilow (2007-04-22 15:51:05)

Eeyore

Member

Registered: 2007-04-16

Posts: 8

Re: Need Abstract Math Help!

If you would just Lemma use the theorem that "in an injection, the cardinality of the domain must be less than or equal to the cardinality of the range, then this proof would be easy.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

If f(s) is an element of s, then s is a subset of A and f(s) is not an element of S.

The "then s is a subset of A" doesn't make any sense.  f(s) being an element of s doesn't imply that s is a subset of A.  But the rest is fine, it's simply by the definition of what S is.  I don't see any way to be more explicit.

If you would just Lemma use the theorem that "in an injection, the cardinality of the domain must be less than or equal to the cardinality of the range, then this proof would be easy.

That's pretty much the exact lemma you're trying to prove.  While assuming the conclusion can be fun, it's not exactly what is going to get you any credit.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Eeyore

Member

Registered: 2007-04-16

Posts: 8

Re: Need Abstract Math Help!

I'm sorry but this is not what we are trying to prove.
If I can prove the Lemma then the theorem that we are trying to prove can be easily proven.

That is what a Lemma is.

Of course we MUST prove the Lemma  before we have a full proof of the theorem.

What I was trying to do was use a pun to point out the meaning of the word Lemma.  But thanks for your help.

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,713

Re: Need Abstract Math Help!

"If you would just Lemma" ... doh!

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman