- #1
setsofvectors
- 24
- 0
Trying to understand the proof of "|S|<|P(S)| for all S"
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.
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.
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.