Question

Cantor's theorem : show that there exists no surjective function from a set to its powerset

Answer 1

i don't get the proof, looking for somebody to discuss with

Answer 2

this proves that the cardinality of the power set X has cardinality greater than the cardinality of set X

Answer 3

| P ( X ) | > | X |

Answer 4

i would have to look at the proof

Answer 5

yes i have the video if u have time

Answer 6

the video?

Answer 7

ok

Answer 8

fastforward to 25th minute

Answer 9

where is the video?

Answer 10

sorry here it is
https://www.youtube.com/watch?v=c8uDJt5-ZYM

Answer 11

its a bit hard to see, the graphics is a bit blurry

Answer 12

watching :)

Answer 13

yeah quality isn't that good but he explains quite well,

however im not getting the how the new subset won't exist in any of the previous subsets

Answer 14

suppose there exists a bijection between A and 2^A

Answer 15

k

Answer 16

2^A is a shorthand way of saying the powerset of A

Answer 17

okay

Answer 18

sorry, im watching , i will respond soon

Answer 19

it is easy to see for finite sets because n < 2^n,

i have trouble with understanding the argument for infinite sets

Answer 20

sure take your time :)

Answer 21

his pictures are a bit confusing

Answer 22

ok lets say A = { S, C , T } , which stands for square circle triangle

Answer 23

lets construct P(A) = { {S} , { C }, { T}, { S, C }, { S, T } , { C , T } , { S , C , T } }

Answer 24

and i will define a function
if 'a' is an element of A , f(a) is a subset of A

Answer 25

ok

Answer 26

would it be general enough for infinite sets like A = all natural numbers ?

Answer 27

yes, you can generalize this

Answer 28

its easier to show with finite sets, and then you get the idea

Answer 29

okay

Answer 30

so i will show that f is not onto. i will construct a subset of A for which there is no element in the domain of f that maps to it

Answer 31

since the codomain of f are subsets of A

Answer 32

I see, constructing a subset that cannot be an image of an element in domain will do

Answer 33

{S, C, T} ----> { {S} , { C }, { T}, { S, C }, { S, T } , { C , T } , { S , C , T } }

Answer 34

so define this subset of A call it B,
B = { a | a is not a member of f(a) }

Answer 35

could you please elaborate, this is the part thats been tripping me

Answer 36

there is more than one possible function
this is one possibility
S -> {S}
C -> { T}
T -> { S, C, T }

Answer 37

we are mapping elements of A to subsets of A

Answer 38

also you need to include the empty set in the power set of A (just a small change there)

Answer 39

yes what do they mean by

"a is not a member of f(a)"

Answer 40

f(a) is a subset right ?

Answer 41

ok so we want to construct a set B , so in our case we would have

Answer 42

right f(a) is a subset of A

Answer 43

and the new set B is also a subset of A ?

Answer 44

yes,

Answer 45

what if

S-->{S}
C-->{C}
T-->{T}

?

Answer 46

oh

Answer 47

oops i made a mistake

Answer 48

B cannot have S/C/T because they exist in f(S), f(C) and f(T) is it ?

Answer 49

if our function f is
S -> {S}
C -> { T}
T -> { S, C, T }

then B = { C}

Answer 50

I think im getting it

Answer 51

if our function f is
S-->{S}
C-->{C}
T-->{T}

then B = { }

Answer 52

sorry that B should just be the empty set

Answer 53

since S elt. of {S} , C elt. of {C} , and T elt. of {T }

there are no elements of A which are not elements of f(A), so B is just the empty set

Answer 54

but notice that in that case, there is no element in A being mapped to the empty set, and the empty set is an element of P(A)

Answer 55

I see the logic now thanks :) how do I put it in steps for a contradiction proof
i don't understand his steps

Answer 56

His proof starts with defining a new subset

so define this subset of A call it B,
B = { a | a is not a member of f(a) }

Answer 57

right

Answer 58

it assumes that B is already in image of f

Answer 59

and arrives at contradiction

Answer 60

no, we don't assume that

Answer 61

B is in P(A) , or the codomain of f , by definition

Answer 62

since it is a set of members of A, so it is a subset of A

Answer 63

well, i guess if you are doing a proof by contradiction,
since you are assuming that it is bijective, then yes you are right

Answer 64

woops, sorry

Answer 65

ok then if there is a bijection, then yes B must be in the image of f. but this will lead to a contradiction

Answer 66

ok so is there an element a of A such that f(a) = B ?

Answer 67

yes so far im with him, his next steps are very confusing

Answer 68

since B is in range of f,
there exists some "a" in A such that f(a) = B

fine

Answer 69

how does this lead to contradiction

Answer 70

if there exists an element a such that f(a) = B,
then either a is inside B or it is not inside B .

Answer 71

ok

Answer 72

if a belongs to B , then a does not belong to B.
if a does not belong to B , then a belongs to B

Answer 73

B = { a | a is not a member of f(a) }

Answer 74

lets use their example

Answer 75

ok going thru pdf

Answer 76

there are a few obvious typos in the pdf, though, when you get to the cantor theorem section

Answer 77

Let S= { 1,2,3,4}

Define a function f

1 -> { 1,3}
2 -> {1,3,4}
3 -> { }
4 -> {2,4}


Let X = { s | s not elt. of f(s) }

then

X = { 2,3 }

Now the question:

Is it possible that there exists some s in S such that
f(s) = X ?

If there does exist some s such that f(s) = X , (which we need if f is onto)
then it is a fact that either s is in X or s is not in X.

If s is in X , then s is not in X.

If s is not in X , then s is in X.

Answer 78

suppose there was an element such that f(s) = X

f(s) = { 2,3 } , in our example

Answer 79

s -> { 2 , 3 }

Answer 80

ok X = {2, 3}

Answer 81

either s is inside { 2, 3 } or is not inside { 2 , 3 }

case 1 :

s is inside { 2, 3 }

Answer 82

Ohh thats not possible because by definition \(s \not \in f(s)\)

Answer 83

right

Answer 84

by definition of X

Answer 85

X contains all elements who map to subsets that dont contain the element itself

Answer 86

s ---> f(s)

if f(s) = X, then X cannot contain s. clear

Answer 87

right, but then what happens when s is not in { 2, 3 }

Answer 88

so we established that

s -> { s , 3 }
s -> { 2, s } are impossible

but so is

s -> { 2, 3 } impossible,

Answer 89

where s =/= 2, and s =/= 3

Answer 90

I get that s cannot be in X

why s->{2, 3} is impossible ?

Answer 91

lets look at the definition of X again

Answer 92

Let X = { s | s not elt. of f(s) }

Answer 93

Oh if it were possible to have a mapping such as : s->{2, 3},
the s must exist in X !!

Answer 94

if s -> { 2, 3 } and s =/= 2 and s =/= 3, then s must be inside X by definition

Answer 95

beautiful! i see how contradiction works, thanks a lot for explaining clearly and being patient :))

Answer 96

but then we get back to where we started