1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 31, 2013 #1
    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. jcsd
  3. Oct 31, 2013 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi setsofvectors! :smile:
    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 :wink:
     
  4. Oct 31, 2013 #3
    Hi, tiny-tim :smile:


    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.
     
  5. Oct 31, 2013 #4
    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.
     
  6. Oct 31, 2013 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi setsofvectors! :smile:
    you mean S and the empty set?

    S does contain x :confused:
    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)​
     
  7. Oct 31, 2013 #6
    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).
     
  8. Oct 31, 2013 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    the whole space (ie, S) does contain x :confused:
    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)
     
  9. Oct 31, 2013 #8
    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?
     
  10. Oct 31, 2013 #9
    "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.
     
  11. Oct 31, 2013 #10
    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
     
  12. Oct 31, 2013 #11
    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?
     
  13. Oct 31, 2013 #12
    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?
     
  14. Oct 31, 2013 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi setsofvectors! :smile:
    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 :wink:
     
  15. Oct 31, 2013 #14
    Does the post #12 look in\correct to you?
     
  16. Oct 31, 2013 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    i don't understand this line :redface:
     
  17. Oct 31, 2013 #16
    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?
     
  18. Oct 31, 2013 #17

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    sorry, i don't understand it at all :redface:

    "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
     
  19. Oct 31, 2013 #18
    Ok, in what situations can you invoke LEM?

    Thanks.
     
  20. Nov 1, 2013 #19

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    the axiom "P or not-P is always true" is LEM
     
  21. Nov 3, 2013 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Trying to understand the proof of |S|<|P(S)| for all S
  1. Stuck :s (Replies: 6)

  2. A limit :s (Replies: 5)

  3. Transformations? :S (Replies: 2)

  4. Trig. :s (Replies: 1)

Loading...