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

[setsofvectors]

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

Homework Statement

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.

Homework Equations

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.

 

[tiny-tim]

hi setsofvectors!

… 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."

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

 

[setsofvectors]

Hi, 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

But neither of those sets contain x anyway?

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

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.

 

[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) don't contain x's from S?

Thanks.

 

[tiny-tim]

hi setsofvectors!

But neither of those sets contain x anyway?

you mean S and the empty set?

S does contain x

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)?

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)​

 

[setsofvectors]

hi setsofvectors! you mean S and the empty set?

S does contain x

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 won't contain any x from S.

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)​

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).

 

[tiny-tim]

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 won't contain any x from S.

the whole space (ie, S) does contain x

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

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)

 

[setsofvectors]

the whole space (ie, S) does contain x

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?

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)

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

 

[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.

 

[R136a1]

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?

"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.

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

 

[setsofvectors]

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

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?

 

[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?

 

[tiny-tim]

hi setsofvectors!

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.

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 ​

 

[setsofvectors]

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 ​

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

 

[tiny-tim]

i don't understand this line …

Since f(x) is a subset of S, it's obvious x is in f(x).

 

[setsofvectors]

i don't understand this line …

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 don't understand. Does the derivation of "x is in f(x) or x is not in f(x)" look ok now?

 

[tiny-tim]

Does the derivation of "x is in f(x) or x is not in f(x)" look ok now?

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

 

[setsofvectors]

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

Ok, in what situations can you invoke LEM?

Thanks.

 

[tiny-tim]

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

 

[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.

 

[tiny-tim]

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

First, the proof is either true or false.

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)

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).

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?

 

[setsofvectors]

you mean the theorem (or the statement) is either true or false
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?

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 don't contain x, some do. If we can prove that there's at least one subset of S that doesn't contain x, we will have proved the theorem. Look better?

Thanks.

 

[tiny-tim]

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

 

[setsofvectors]

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

x is an element in S?

 

[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)

 

[setsofvectors]

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)

I am not sure what you're asking. Do you need me to show a specific function that constructs C from certain x in S?

 

[tiny-tim]

you need to show what "x" you are talking about

 

[setsofvectors]

I give up - I don't know what "x" I am talking about. all I know is that x is an element of S. I am not sure about the new symbol I might have introduced(?).

Sounds like you know that specific "x" you're asking about. Can you tell me what it is, because I don't know?