# Homework Help: Trying to understand the proof of |S|<|P(S)| for all S

1. Oct 31, 2013

### setsofvectors

Trying to understand the proof of "|S|<|P(S)| for all S"

1. The problem statement, all variables and given/known data

Here's the 1st half of the proof:

Suppose that f is a function that maps S into P(S).

Let x be an element in S.

Since f maps into P(S), f(x) ∈ P(S).

Thus, f(x) is a subset of S.

So, x ∈ f(x) or x ∉ f(x).

Let C = {x in S |x ∉ f(x)}

Since C is a subset of S, C ∈ P(S).

Assume that f maps S onto P(S).

Then there exists an x in S such that f(x) = C.

Either x ∈ C or x ∉ C.

2. Relevant equations
3. The attempt at a solution

Are we allowed to define C as C = {x in S |x ∉ f(x)} because we know for a fact that some x never end up in f(x)? I mean the sentence "So, x ∈ f(x) or x ∉ f(x)." precedes the sentence "Let C = {x in S |x ∉ f(x)}". Basically, we would not be allowed to let C = {x in S |x ∉ f(x)} if we didnt know beforehand that sometimes x ∉ f(x). All I want to know is if "C = {x in S |x ∉ f(x)}" is a direct logical consequence of "So, x ∈ f(x) or x ∉ f(x).".

Also, about "Either x ∈ C or x ∉ C." The sentence immediately before it, "Then there exists an x in S such that f(x) = C." is trying to convince us that x is in C, but since this is a mere assumption and not a fact, there's still a possibility that x is not in C. Hence, Either x ∈ C or x ∉ C. I am trying to find a logical glue between "Then there exists an x in S such that f(x) = C." and "Either x ∈ C or x ∉ C.". Do you think I am thinking in the right\wrong direction?

Thanks.

2. Oct 31, 2013

### tiny-tim

hi setsofvectors!
i think your'e seeing a difficultly that isn't there

C can for example be the empty set or the whole space, and the proof still works

there's no logical glue between those two statements

the second statement (Either x ∈ C or x ∉ C) applies to any x ∈ X and to any C ∈ P(X) …

it does not depend as the first statement at all

3. Oct 31, 2013

### setsofvectors

Hi, tiny-tim

But neither of those sets contain x anyway?

Isnt "Then there exists an x in S such that f(x) = C." saying suppose there's x in C which is in P(S)?

Thanks.

4. Oct 31, 2013

### setsofvectors

P(S) contains f(x)'s. Depending on a function, there will be sets in P(S) where x is not in f(x). So there's a need to define C so that we can refer to such elements of P(S).

???

Say, you're the first person in history who've come up with this proof. What would you have done first- define C or realize that some elements of P(S) dont contain x's from S?

Thanks.

5. Oct 31, 2013

### tiny-tim

hi setsofvectors!
you mean S and the empty set?

S does contain x
no

how can x be in P(S)? x is in S

({x} is in P(S))

"Then there exists an x in S such that f(x) = C." means what it says

it is true because f is onto P(S), and C is in P(S)​

6. Oct 31, 2013

### setsofvectors

You said "C can for example be the empty set or the whole space...". That's what I meant when I said both of those sets wont contain any x from S.

Assumption goes f(x) = C, where x is in S. So we can suppose x is in the set C and the set C is in P(S).

7. Oct 31, 2013

### tiny-tim

the whole space (ie, S) does contain x
no, we're not using the definition of C at this stage (we'll use it later)

we're only using the fact that C is in P(S)

8. Oct 31, 2013

### setsofvectors

Do you mean S can equal C? Like this below?:

Say, S = {1, 2}. Define functions as f(1) = {2}, f(2) = {1}. So, C = {1} and C = {2}. {1} U {2} = {1, 2}? Something like that?

Where does "Either x is in C or x is not in C' come from?

9. Oct 31, 2013

### setsofvectors

"Where does "Either x is in C or x is not in C' come from?"

Assume that f maps S onto P(S). -> Then there exists an x in S such that f(x) = C.->
Either x ∈ C or x ∉ C -> contradiction which makes the assumption invalid.

We start with an assumption and keep deriving logically linked sentences till we hit a contradiction.

In the chain above, the second sentence is logically derived from the first one- for onto relation to exist f(x) has to be equal to C. I am having difficulty linking the 3rd sentence to the second in a logical way.

10. Oct 31, 2013

### R136a1

Formally, it can be seen as a logical axiom. The law of the excluded middle says that either a statement must hold or its negation (and not both). For example: either the sun shines, or it doesn't shine.

So by this axiom: either x is an element of C, or it is not true that x is an element of C.

http://en.wikipedia.org/wiki/Excluded_middle

11. Oct 31, 2013

### setsofvectors

Thank you. "The law of excluded middle states that for any proposition, either that proposition is true, or its negation is true."

So, "x is an element of C" has to be the proposition according to the law, correct? So then, this proposition has to be linked to "Then there exists an x in S such that f(x) = C". Right/Wrong? The only link I see is that this assumption is saying that there exists such C in P(S) that contains x from S. Yes/No?

12. Oct 31, 2013

### setsofvectors

It's not true that a statement is both true and false.

-(p and -p)

p

or

-(p and -p)

-p
------------------------------------------------

-(cold and hot)

cold

or

-(cold and hot)

hot
-------------------------------------------------------
We can also flip them:

hot

-(cold and hot)
------------------------------------------------------------------------

Since f(x) is a subset of S, it's obvious x is in f(x). But we need to define C for the assumption, so we make use of the Law of Excluded Middle.

-(x is in f(x) and x is not in f(x)) is a true statement just like -(China is in Africa and China is in Asia). So then,

-(x is in f(x) and x is not in f(x))

x is in f(x)

or

-(x is in f(x) and x is not in f(x))

x is not in f(x)

We use the first case, because we already have x is in f(x). Flip it and we got,

x is in f(x)

-(x is in f(x) and x is not in f(x))

x is in f(x) or x is not in f(x))
--------------------------------------------------------------------------

I hope that's where "x is in f(x) or x is not in f(x))" comes from. Does it?

13. Oct 31, 2013

### tiny-tim

hi setsofvectors!
ahh … your difficulty is is caused by your idea of a "chain"

it's not a chain, it's a network

each step does have to be logically derived from some previous step or steps (including axioms), it does not have to be derived from the immediately preceding step

in this case, "Either x is in C or x is not in C" is derived purely from a basic axiom

14. Oct 31, 2013

### setsofvectors

Does the post #12 look in\correct to you?

15. Oct 31, 2013

### tiny-tim

i don't understand this line

16. Oct 31, 2013

### setsofvectors

It comes from my raging desire to link sentences into logically consistent chains. So that turns out to be wrong. Let's scratch the part you dont understand. Does the derivation of "x is in f(x) or x is not in f(x)" look ok now?

17. Oct 31, 2013

### tiny-tim

sorry, i don't understand it at all

"x is in f(x) or x is not in f(x)" doesn't need a derivation

"x is not in f(x)" is the same as not-"x is in f(x)"

P or not-P is always true

18. Oct 31, 2013

### setsofvectors

Ok, in what situations can you invoke LEM?

Thanks.

19. Nov 1, 2013

### tiny-tim

the axiom "P or not-P is always true" is LEM

20. Nov 3, 2013

### setsofvectors

Let me see if I got a little closer to understanding the proof.

First, the proof is either true or false. Roughly speaking, if it's false there's onto relation and x is in f(x). If it's true, there's no onto relation and x is not in f(x). The rest of the proof deals with showing x is not(might not be) in f(x).

Does the above sound in\correct?

Thanks.

21. Nov 3, 2013

### tiny-tim

you mean the theorem (or the statement) is either true or false

a proof is always true (if it's not, it's not a proof)
if it's false, yes there's an onto relation …

but what does "x is in f(x)" mean? what x are you talking about?

22. Nov 3, 2013

### setsofvectors

I made yet another mistake, but it looks like it just dawned on me why the statement "x is either in f(x) or x is not in f(x)." is included in the proof. Depending on the mapping function, some subsets of S dont contain x, some do. If we can prove that there's at least one subset of S that doesnt contain x, we will have proved the theorem. Look better?

Thanks.

23. Nov 3, 2013

### tiny-tim

sorry, i still don't understand what "x" you are talking about

24. Nov 3, 2013

### setsofvectors

x is an element in S?

25. Nov 3, 2013

### tiny-tim

yes, of course, but which element?

when you introduce a new symbol into a proof, you have to say what it represents

(unless any element will do, which in this case it won't)