Please help me understand a set theory proof.

[╔(σ_σ)╝]

Homework Statement

Let A be a set and let P(A) denote the set of all subsets of A. Prove that A and P(A) do not have the same cardinality

Homework Equations

NOne

The authors proof is as follows:

Suppose there is a bijection f:A -> P(A). Let B= {x\in A| x \notin f(x)}. There is a y \in A such that f(y)= B, since f is onto. If y \in B, then by definition of B we conclude that y\notin B. Similarly, if y \notin B, then we conclude y \in B. In either case we get a contraditon, therefore, no such function exist.This proof probably make a lot of sense but I can't understand it. Why define a set B that only consist of elements of A but is not elements of f(x)? Isn't f(x) supposed to be all subsets of x, which means f(x) contains x and the subsets of x? How can the set B even exist ? I'm completely lost.

The Attempt at a Solution

Am not sure why the author provides the proof he does and I am having a hard time understanding it. But if I were to attempt it I would have given a counterexample. I know that cardinality is another word for number of elements when we are talking about finte sets.

If i formed a set A= { 1,2} I know that P(A) has subsets \oslash,{1},{2},{1,2}

Clearly they do not have the same cardinality. I am not sure if this is enough to prove the proposed statement partly because I didn't even talk about infinite sets. What do you guys think ?

 

[Hurkyl]

Isn't f(x) supposed to be all subsets of x

No.

Since f is a function from A to P(A), f(x) must be an element of P(A). Equivalently, f(x) is a subset of A.

A priori, f(x) has no interesting properties whatsoever; it's just the result of a function applied to a value.

 

[╔(σ_σ)╝]

No.

Since f is a function from A to P(A), f(x) must be an element of P(A). Equivalently, f(x) is a subset of A.

A priori, f(x) has no interesting properties whatsoever; it's just the result of a function applied to a value.

Okay, thanks for the clearification. But I still have a problem understading f(x). I believe it is an element of P(A) but what is its "value" ?

Suppose I have A= {1,2}

1 is an elements of A
f(1) = ? what does this even mean ?

Something about this is unsettling to me. From what I understand f is a mapping of a set to another set; why should it even work on elements of a set and not on sets themselves?

f( {1}) = {\oslash, {1}} , would make sense to me .


Can you explain a bit more, please ?

 

[malicx]

Okay, thanks for the clearification. But I still have a problem understading f(x). I believe it is an element of P(A) but what is its "value" ?

Suppose I have A= {1,2}

1 is an elements of A
f(1) = ? what does this even mean ?

Something about this is unsettling to me. From what I understand f is a mapping of a set to another set; why should it even work on elements of a set and not on sets themselves?

f( {1}) = {\oslash, {1}} , would make sense to me .


Can you explain a bit more, please ?

Well, there is no explicit definition given for the function, f, so it would be impossible to tell you any value. All you know is that f is a bijection, which is surjective (onto) and injective (one-to-one), and its domain and co-domain.

 

[Raskolnikov]

I still have a problem understading f(x). I believe it is an element of P(A) but what is its "value" ?

f is some bijection from A to P(A). i.e., for each element a \in A, we have the element f(a) \in P(A)..

Suppose I have A= {1,2}

1 is an elements of A
f(1) = ? what does this even mean ?

There's no one correct answer, because the mapping f has not been fully defined. Right now, we're just supposing there is SOME bijection f. But if it would make things clearer to you, consider the following mapping:

f: x \mapsto \left\{ x \right\}

So f(1) = \left\{ 1 \right\} and f(2) = \left\{ 2 \right\}.

Something about this is unsettling to me. From what I understand f is a mapping of a set to another set; why should it even work on elements of a set and not on sets themselves?

f( {1}) = {\oslash, {1}} , would make sense to me .

Can you explain a bit more, please ?

EDIT#2: I was right the first time:
No, that does not make sense. The domain of f is the elements of A and the range of f is the elements of P(A). The type of elements of A is different than the type of elements of P(A). Do you understand?

 

[╔(σ_σ)╝]

Okay if that is the case in the proof the author says :

There is a y \in A such that f(y)= B, since f is onto. If y \in B, then by definition of B we conclude that y\notin B. Similarly, if y \notin B, then we conclude y \in B. In either case we get a contraditon, therefore, no such function exist.

My problem is I don't understand what's going on with the set B.

The elements of B are elements of A but are not elements of f(x). What does an element of f(x) even look like ?

 

[malicx]

Okay if that is the case in the proof the author says : My problem is I don't understand what's going on with the set B.

The elements of B are elements of A but are not elements of f(x). What does an element of f(x) even look like ?

f(x) takes an element from A and does SOMETHING to make into an element of P(A). Elements of P(A) are all subsets of A, so it looks like a subset of A.

EDIT: And, the elements of B are not elements of A. It takes its input from each member of A.

 

[╔(σ_σ)╝]

f is some bijection from A to P(A). i.e., for each element a \in A, we have the element f(a) \in P(A)..



There's no one correct answer, because the mapping f has not been fully defined. Right now, we're just supposing there is SOME bijection f. But if it would make things clearer to you, consider the following mapping:

f: x \rightleftharpoons \left\{ x \right\}

So f(1) = \left\{ 1 \right\} and f(2) = \left\{ 2 \right\}.

I understand this.

No, that does not make sense. The domain of f is the elements of A and the range of f is the elements of P(A). The type of elements of A is different than the type of elements of P(A). Do you understand?

[/QUOTE]

I understand there is a difference, ofcourse there is. I mean A has elements like 1,2 etc but P(A) has sets as elements.

 

[Raskolnikov]

The elements of B are elements of A but are not elements of f(x). What does an element of f(x) even look like ?

Like I said, the range of f is P(A). P(A) is the set of SUBSETS of A, i.e., the elements of P(A) are sets themselves. Thus, the elements of f(x) are sets themselves.

e.g., Let A = {1 , 2}. Then P(A) = { {}, {1}, {2}, {1, 2} }.

 

[Raskolnikov]

Suppose there is a bijection f:A -> P(A). Let B= {x\in A| x \notin f(x)}. There is a y \in A such that f(y)= B, since f is onto. If y \in B, then by definition of B we conclude that y\notin B. Similarly, if y \notin B, then we conclude y \in B. In either case we get a contraditon, therefore, no such function exist.This proof probably make a lot of sense but I can't understand it. Why define a set B that only consist of elements of A but is not elements of f(x)?

The point is that B \subseteq A. Thus, we have by definition: B \in P(A). This guarantees us a y such that f(y) = B.

Isn't f(x) supposed to be all subsets of x, which means f(x) contains x and the subsets of x?

No, f(x) is simply some subset of A. It doesn't have to contain x. The point is that there aren't "enough" x in order for us to "count" all the subsets of A.

How can the set B even exist ? I'm completely lost.

If we assume that f is a bijection, then B cannot exist. This is exactly why we have a contradiction, i.e., we realize f cannot be a bijection.

 

[╔(σ_σ)╝]

f(x) takes an element from A and does SOMETHING to make into an element of P(A). Elements of P(A) are all subsets of A, so it looks like a subset of A.

EDIT: And, the elements of B are not elements of A. It takes its input from each member of A.

Great, that makes sense!

So B= {x\in A| x \notin f(x)} has elements of A but x is not an element of f(x).

What does this mean ? Does this mean we get x from A but x is not in P(A) ? This make sense the elements are of different types.

 

[╔(σ_σ)╝]

No, f(x) is simply some subset of A. It doesn't have to contain x. The point is that there aren't "enough" x in order for us to "count" all the subsets of A.

Nice, this makes sense.

So basically f since f is onto we have f(y) = B if y is an element of A. I got the contradiction part of the argument but I don't see the point that "there aren't "enough" x in order for us to "count" all the subsets of A."

Basically B does not exist.

 

[malicx]

Great, that makes sense!

So B= {x\in A| x \notin f(x)} has elements of A but x is not an element of f(x).

What does this mean ? Does this mean we get x from A but x is not in P(A) ? This make sense the elements are of different types.

It means that for all x such that x is a member of A, you take the elements not in f(x).

EDIT: Actually, is that a typo? x can't be a member of A and not a member of f(x) because the set's elements are completely different.

 

[╔(σ_σ)╝]

Okay I just tried to piece eveything together and I think I understand now. By following the assumption that f is a bijection and the definition of B we get that B\subset A
and B \in P(A). Therefore, since f(y) = B, if y \in B then y \in f(y) which is a contradiction . Therefore, B does not exist if f is a bijection. So our assumption must be wrong.