On P(X) > X

  • Thread starter Organic
  • Start date
  • #1
Organic
1,232
0
An edited version:

General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than P(|N|)>=|N|.

If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped with.

n in D because {} not in N, therefore D is not empty.

Q.E.D

t=n
X=N
S=D

-----------------------------------------------------------------------------


Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

Q.E.D

=================================================
=================================================

Let us look at this proof from another point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All the members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .

Member t is simpler than member S .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
43,021
970
General:

We say that A > B if A not= B but there is a bijection between A and subset of B .
No, that's exactly backwards but I imagine it was a typo. A is larger than B is there is a bijection between B and a subset of A. And it is the same as saying "the cardinality of A is greater than or equal to the cardinality of B".

Actually, your proof uses a different statement which may be what you intended to say: A> B is A not= B AND there is NOT a bijection between A and a subset of B.

Let us say that there exist subset S in P(X) which includes every member of X that has no image Included in the subset which it is mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

By this example S ={1,3,5,…}.
Why should we say that? Do you have any reason to believe that such a subset does exist? If there doesn't exist such a set your proof fails. You need to prove that set's existence, not just "say" it.
 
  • #3
phoenixthoth
1,605
2
tricks of the trade

P(X)>X is equivalent to saying there is no function that maps X onto P(X).

we will show that every function which maps X to P(X) is not onto. let f be any function mapping X to P(X). consider the set
D:={x in X such that x is not an element of f(x)}.

(D is for diagonal as in the diagonal argument. note that D is a subset of X and is therefore an element of P(X).)

D is not in the image of f because if it was, then we could say that
f(y)=D for some y in X which would imply that y is an element of
f(y) if and only if y is not an element of f(y).

since D is not in the image of f, f is not onto. since f was arbitrary, this shows that no function from X to P(X) is onto.
 
  • #4
Organic
1,232
0
Hi phoenixthoth,

Thank you for your correction.

I wrote:
General:

We say that A > B if A not= B but there is a bijection between A and subset of B .

It is my mistake, and it has to be:
General:

We say that B > A if A not= B but there is a bijection between A and a subset of B .


I have a simple question:


The power of aleph0 is 2^aleph0, so if we construct a list of X subsets, then
by Cantor's diagonal second argument we can find maps between only aleph0 X
members and aleph0 X subsets, and always there is some subset (the diagonal subset) which is out of the map range.

Is this the idea that stands behind the proof that P(X) > X ?




Organic
 
Last edited:
  • #5
phoenixthoth
1,605
2
yes. D is always out of the range of any function from X to P(X).

if you look at random examples of X's and P(X)'s and D's and maps f from X to P(X), you can see what D is in particular to see what the example f misses.

example. of course, the proposition is clear for finite sets, but let's say X={1,2}. then P(X)={Ø,{1},{2},X}. let f be defined so that f(1)=Ø and f(2)={1}. as you can see, f is not onto P(X) since {2} and X are out of the range but let's see what D would be in this case.
D:={x in X such that x is not an element of f(x)}. one by one, let's go through elements in X and see if x is not an element of f(x). if so, then x is an element of D. let's start with 1. is 1 not an element of f(1)? yes, since 1 is not an element of Ø=f(1). then 1 is an element of D. is 2 not an element of f(2)? yes, since 2 is not an element of {1}=f(2); so 2 is an element of D. in this case, D=X. and, as we know, X is not in the range of f. but this was automatic from the beginning.

perhaps this is like fitting a carpet into a room where if we just fix the problem, fit the carpet in one corner, then it will fit the room. alas, no, if we pull the carpet to this corner by making sure X is in the range of f, the carpet will pull out of another corner.

let's say f(1)=Ø and now that f(2)=X. maybe this will fix things since now that X is in the range of f. let's see what D is. i can guarantee you that it will either be {1} or {2} because neither of those are in the range of our new f even though X is. is 1 not an element of f(1)? yes, because 1 is not an element of Ø=f(1); so 1 is in D. is 2 not an element of f(2)? no, because 2 is an element of X=f(2); so 2 is not an element of D. therefore, D={1}. D is not in the range of f.

the carpet will not fit the room no matter which corner we force it to fit in. whenever we fit it into one corner, it will always come up in another corner.

an example with infinite sets? ok. let X=R and P(X) is the power set of R. define f to be the following function:
for x in R, f(x)=(-infinity, x].
this f is an injection from X into P(X). as you can already see, f is hopelessly not onto. but let's see if we can get a handle on what is automatically out of the range of f, ie, what D is. let's follow our noses. x is an element of D if and only if x is not an element of f(x); therefore, x is an element of D if and only if x is not an element of (-infinity, x]. but wait, x is an element of (-infinity,x]; therefore, D is the empty set. and as you can see from the definition of f, Ø=D is not in the range of f.

here's an amusing exercise: let A and B be sets. prove there is no function from A onto B if and only if there is a bijection between A and a proper subset of B. (B is the only nonproper subset of B.) thus, either definition will suffice to mean A<B. i hope that's right...
 
Last edited:
  • #6
Organic
1,232
0
Hi phoenixthoth,

You wrote:
an example with infinite sets? ok. let X=R and P(X) is the power set of R. define f to be the following function:
for x in R, f(x)=(-infinity, x].
this f is an injection from X into P(X). as you can already see, f is hopelessly not onto. but let's see if we can get a handle on what is automatically out of the range of f, ie, what D is. let's follow our noses. x is an element of D if and only if x is not an element of f(x); therefore, x is an element of D if and only if x is not an element of (-infinity, x]. but wait, x is an element of (-infinity,x]; therefore, D is the empty set. and as you can see from the definition of f, Ø=D is not in the range of f.

I will try to write it in a short way, please tell me if I do it right, thank you:

x in X such as f(x)=(-[oo],x]

x in D iff x not in (-[oo],x] --> D={}

D not in (-[oo],x] therefore D is out of the range of f.


Organic
 
  • #7
phoenixthoth
1,605
2
D not in (-oo,x] therefore D is out of the range of f.

since D = Ø != (-oo,x] = f(x) for any x, D is not in the range of f.
 
  • #8
Organic
1,232
0
Sorry I can't follow it.

Can you please write it again in simple english?

Thank you.
 
  • #9
phoenixthoth
1,605
2
for x in R, f(x):={z in R : z <= x}.

in other words, f(x)=(-oo,x].

D={x in R such that x is not an element of f(x)}.

f(x)={z in R : z <= x}, so this means that

D={x in R such that x is not an element of {z in R : z <= x}}.

note that for all x in R, x *is* an element of {z in R : z <= x}.

therefore, the set of x in R such that x is *not* an element of
{z in R : z <= x} is empty.

since D is the set of x in R such that x is not an element of
{z in R : z <= x}, D=Ø.

in the argument i wrote about in "tricks of the trade," D is an element of P(X) automatically not in the range of any function from X to P(X). this last bit was an investigation into what various versions of D are for particular cases. in the last example, D=Ø and so Ø is not in the range of f. another way to say that is that for no x in R is the set {z in R : z <= x} empty. {z in R : z <= x}=f(x), so this is saying that f(x) != Ø for any x in R which means that Ø is not in the range of f. the central argument gives us a set, D, which is automatically not in the range of f and we can see what D looks like in this case; D=Ø.

triva question: true or false? if m and n are positive integers and A is any infinite set, then the set of funtions from A to a set of m elements is in 1-1 correspondance with the set of functions from A to a set of n elements; i.e., m^A = n^A.
 
  • #10
Organic
1,232
0
phoenixthoth,phoenixthoth,

Please hold your horses.

I'll give a number to each line that is written below.
Please just answer by yes(if ok) or no(if not ok) to each line.
And if your answer is no, then please explain it in a simple and not formal way. Thank you.

1) x in X such as f(x)=(-[oo],x]

2) x in D iff x not in (-[oo],x] --> D={}

3) D not in (-[oo],x] therefore D is not in the range of f.


Organic
 
  • #11
phoenixthoth
1,605
2
1) x in X such as f(x)=(-oo,x]
i'm not sure what "such as" means. for x in R, f(x) is defined to equal (-oo,x].

2) x in D iff x not in (-oo,x] --> D={}
yes since x *is* in (-oo,x] for all x in R.

3) D not in (-oo,x] therefore D is not in the range of f.
no. D != (-oo,x] (for all x in R) therefore D is not in the range of f. in other words, D != f(x) (for all x in R) therefore D is not in the range of f.
 
  • #12
Organic
1,232
0
An edited version:


General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than P(|N|)>=|N|.

If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped with.

n in D because {} not in N, therefore D is not empty.

Q.E.D

t=n
X=N
S=D

-----------------------------------------------------------------------------


Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

Q.E.D

=================================================
=================================================

Let us look at this proof from another point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All the members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .

Member t is simpler than member S .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:
  • #13
phoenixthoth
1,605
2
We say that B > A if A not= B but there is a bijection between A and subset of B .

i think it should be B > A and A not= B but there is a bijection between A and proper subset of B, where S is a proper subset of B if S is a subset of B and S != B.

with this in mind, let's prove X<P(X):
at least when X!=Ø, your map f(x)={x} will do the trick, but we have to show that the image of f is a proper subset of P(X). the image of f is precisely the set of all elements of P(X) that are singletons. therefore, Ø is not in the image of f but is in P(X), so the image of f is a proper subset of P(X). this proof doesn't work for X=Ø, but X=Ø<{Ø}=P(X) via the empty function which is a bijection (by vacuous truth) between Ø and Ø, a proper subset of {Ø}.

in some sense, this proof is "better" because it doesn't use a trick like the set D. note that the above definition of B>A is equivalent to the following: there is a function from B onto A and there is no function from A onto B. in this definition of B>A, i think one needs the trick set D.

this is related to the thread
https://www.physicsforums.com/showthread.php?s=&threadid=7924
though it doesn't look like it because that thread is analysis related and not set theory related. here's what I'm trying to accomplish in that thread. we know that P(A)=2^A. I'm trying to find a function f such that f(f(x))=2^x that is as well-behaved as possible. then the next step is to determine if a set B exists such that f(A)=B for any infinite A. (let's let all subsequently mentioned sets be infinite.) then we would have
P(A)=2^A=f(f(A))=f(B). the hope is that f is strictly increasing on sets; i.e., there is a bijection between X and a proper subset of f(X) for all sets X. thus, we would have a set B such that A<B<P(A) for any set A. since, i believe, this would prove the continuum hypothesis, i think i will fail. the idea then would be to analyze what the failure implies. perhaps it implies that there is no such well-behaved f. or it may be that the existence of a set with cardinality f(A) is equivalent to the continuum hypothesis. in that case, if we assume the continuum hypothesis, we would then be closer to actually finding a set B such that A<B<P(A). we gots to find the f first, though.

if A=N, then aleph_0=A and aleph_1=P(A). we'd then have fractional cardinals. for example, aleph_(1/2)=f(A). if we let h(x)=2^x, then aleph_(m/n) would be equal to g(A) where g is some function such that
g^n(x)=h^m(x) and by g^n, i mean the nth iterate of g. (this will also potentially work for negative m.) having defined what aleph_x means for rational x, one wonders if it can be defined for real x.
 
Last edited:
  • #14
Organic
1,232
0
Hi phoenixthoth,


Please look again at my previous post, and please tell what
do you think about what I wrote after
this
|
|
|
V
=================================================
=================================================
 
  • #15
phoenixthoth
1,605
2
you define D to be "the subset in P(N) [that] includes the members of N that have no image in the subset of P(N)." what do you mean by "the subset of P(N)"? which subset are you talking about? did you mean, "...no image in P(N)?" if that's what you mean, then D is automatically empty because for any map f from N to P(N), all members of N have an image in the set P(N), namely f(n). if f(N) is the image (or range) of f, are you defining D to be P(N)\f(N), the set of elements in P(N) not in the image of f? when you define D that way, there doesn't seem to be a guarantee that D will or won't be empty.

it's kinda confusing to be reusing the letter D in this thread because D has been referred to as something different, namely D used to be the set of elements n of N such that n is not an element of f(n).
 
  • #16
Organic
1,232
0
No, I mean please read this part, which is another point of view on Cantor's proof.

=================================================
=================================================

Let us look at this proof from another point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All the members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing subset, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to subset S .


The general idea behind this point of view is the power of existence of member t and subset S .

Member t is simpler than subset S .

Subset S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:
  • #17
phoenixthoth
1,605
2
i'll just start with the first thing i don't understand.

Any member of X can be put in map with some subset of P(X), once and only once.

do you mean put in a map or mapped to?

do you really mean "some subset of P(X)" or really an element of P(X)? if you're talking about subsets of P(X), it sounds like we're dicussing the relationship between X and P(P(X)) since subsets of P(X) are elements of P(P(X)).
 
  • #18
Organic
1,232
0
Hi phoenixthoth,

Well, I am a bad formalist.

What I mean is this: no object in X is a set, all objects in p(X) are sets.


An example of X objects is: 23,5,17,...

An example of P(X) objects is: {23},{5},{17},{12,67},{},{2,4,6,...),...


So, I'll correct it to:

Any member of X can be mapped with some member of P(X), once and only once.

I'll write this corrected part again.

=================================================
=================================================

Let us look at this proof from another point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All the members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .

Member t is simpler than member S .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:
  • #19
phoenixthoth
1,605
2
What I mean is this: no object in X is a set, all objects in p(X) are sets.
actually, every element of a set is also a set. that's why if you look in a set theory book, most sets are denoted by lower case letters rather than lower case for "elements" and upper case for "sets." there is *no* distinction, fundamentally, between a group of things called "elements" (which are not sets) and a group of things called "sets." for example, natural numbers are even sets:
1={Ø}
2={Ø,1}
3={Ø,1,2}
...
23={Ø,1,2,...,21,22}. note that "23" is a set with 23 elements.

Any member of X can be mapped with some member of P(X), once and only once.
it's clear now that you mean "can be mapped to some member of P(X)" and not a subset of P(X).

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

i'm assuming that t is an arbitrary element of X and S is "a set in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with."

"includes" should be "consists of," i think. for example, if i say S is a set including the empty set, it's ambiguous because S could be {Ø} or it could be {Ø,1}. i'll assume you mean "consists of." let me try to symbolize the definition of S:

actually, do you mean "a set in P(X)," which would mean that S is a set that is an element of P(X) so that S would be a subset of X, or "a subset of P(X)" which would mean that S consists of subsets of X? i'll assume you mean the latter. f is our arbitrary function from X to P(X).

S={x in X such that f(x) is not an element of f(x)}.

"the image of x" is f(x) and "members which they are mapped [to]" is also f(x). to put the word "no" in front of "image" is what lead me to put "not" in front of "an." let me know if this is the definition of S and then i'll be able to read the rest. if this isn't what you mean by S, then please write it down using symbols like the italycized ones above because that tends to be less ambiguous.
 
  • #20
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
For the record, some set theories permit there to be objects that are not sets, and that list of natural numbers as sets is merely a model; natural numbers don't have to be those sets. (and, in general, they don't have to be sets at all, though in ZFC they do)
 
  • #21
phoenixthoth
1,605
2
there are proper classes and such. i guess what i mean is that for what we're talking about, there need not be a second entity that is not a set.
 
Last edited:
  • #22
Organic
1,232
0
An edited version:

General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than P(|N|)>=|N|.

If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped with.

n in D because {} not in N, therefore D is not empty.

Q.E.D

t=n
X=N
S=D

-----------------------------------------------------------------------------


Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

Q.E.D

=================================================
=================================================

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,...}:
Code:
0 = { } 

1 = {{ }} = {0}
               
2 = {{ },{{ }}} = {0,1}
  
3 = {{ },{{ }},{{ },{{ }}}} = {0,1,2}

4 = {{ },{{ }},{{ },{{ }}},{{ },{{ }},{{ },{{ }}}}} = {0,1,2,3}

and so on.
So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn
that in the base of this number system, there is the idea of dependency, which can be
translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


More you simple less you depended, therefore more exist.

I'll write S defenition again, in an informal way:

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.


Now, the power of existence of X members is bigger than the power of existence of
P(X) members.

Member t, which is some arbitrary member of X(and mapped with S), is simpler than S, which is a member of P(X) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:
  • #23
phoenixthoth
1,605
2
General:

We say that B > A if A not= B but there is an injection between A and subset of B .
i'm having second thoughts about this definition. if we let N be the set of natural numbers and E be the set of even natural numbers, then, by this definition, E<N with the injection f(x)=x.

the previously used definition was that A < B if A not= B but there is a bijection between A and a proper subset of B. even with this, f(x)=x is a bijection from E to E which is a proper subset of N.

in fact, i think one defining attribute of an infinite set could be that there exists a bijection between it and a proper subset of it. (triva question true or false: let X be a set. there is an injection from N to X if and only if there is a bijection between X and a proper subset of X. the first part is the equivalent to saying X is an infinite set. recall that B is a proper subset of X if B is a subset of X and B!=X.)

therefore, i would contend that the definition of A<B has to be this: there is a function from B onto A but there is no function from A onto B. (if f maps X to Y and f(X) is the range of X, ie {y in Y such that f(x)=y for some x in X}, then f is defined to be onto if f(X)=Y).) in other words, there is a function f from B to A such that f(B)=A and for all functions g from A to B, g(A)!=B.

another approach is to define A <= B to mean that there is an injection from A to B and then say that A<B if
1. A <= B AND
2. there is no bijection from A to B.
(this is like saying A<B if A<=B but A!=B.)

(if this is the definition of < and = means that there is a bijection, is it always the case that for any sets A and B that either A<B, A=B, or B<A? about a zillion years ago i remember hearing something about the trichotomy of ordinals which vaguely makes me think that the answer might be yes.)

with this definition of < in mind, it seems to me that the best way to prove that X<P(X) for all sets X is to note that the set
D_f:={x in X such that x is not an element of f(x)} is an element of P(X) not in the image of f for all functions f mapping X to P(X).
 
  • #25
Organic
1,232
0
Dear phoenixthoth, dear Hurkyl,


Please reply detailed remarks to my previous post.


Thank you.

Organic
 
  • #26
phoenixthoth
1,605
2
there's a problem with the first line:

organic:
General:

We say that B > A if A not= B but there is an injection between A and subset of B .
phoenix:i'm having second thoughts about this definition. if we let N be the set of natural numbers and E be the set of even natural numbers, then, by this definition, E<N with the injection f(x)=x.

furthermore, what i didn't mention in my last post was that since there is a bijection between E and N, it wouldn't make sense to say that E<N.

using the definition hurkyl quoted, A<=B if there is an injection from A to B. (technically, it's |A|<=|B|, where |A| is the cardinal number of A.) in this case, we can say that "A is dominated by B." furthermore, we can say that A and B are "equipollent" if there is a bijection from A to B and write without ambiguity that |A|=|B| and A=B with some ambiguity. the standard way of then exctracting the < from the <= is to say < means "<= but not =." in other words, A<B if there is an injection from A to B but there is no bijection from A to B. i think this is equivalent to saying that there is a function from B onto A but no onto function from A to B.

using the definition in bold which reflects hurkyl's quote, one can proceed to prove that for any set X, X<P(X):
1. f(x)={x} is an injection from X to P(X). this proves that X<=P(X).

2. to prove X!=P(X), note that any function g from X to P(X) fails to be a bijection because it is not surjective. g is not surjective (onto) because the element of P(X) defined as {x in X such that x is not an element of g(x)} is not in the image of g.
 
  • #27
Organic
1,232
0
Hi phoenixthoth,

Please, please this time try to answer to what I write in this post.

Thank you.

By step 1 of Cantor's prof (P(X)>X) we can say that P(X) >= X .

Let us continue from step 2 (and please give your detailed remarks to each part of it)

Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than P(|N|)>=|N|.

If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped with.

n in D because {} not in N, therefore D is not empty.

Q.E.D

t=n
X=N
S=D

-----------------------------------------------------------------------------


Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

Q.E.D

=================================================
=================================================

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,...}:
Code:
0 = { } 

1 = {{ }} = {0}
               
2 = {{ },{{ }}} = {0,1}
  
3 = {{ },{{ }},{{ },{{ }}}} = {0,1,2}

4 = {{ },{{ }},{{ },{{ }}},{{ },{{ }},{{ },{{ }}}}} = {0,1,2,3}

and so on.
So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn
that in the base of this number system, there is the idea of dependency, which can be
translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


More you simple less you depended, therefore more exist.

I'll write S defenition again, in an informal way:

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.


Now, the power of existence of X members is bigger than the power of existence of
P(X) members.

Member t, which is some arbitrary member of X(and mapped with S), is simpler than S, which is a member of P(X) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
  • #28
phoenixthoth
1,605
2
There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.
"includes" should be "consists of," i think.

"...that have no image Included in the P(X) members which they are mapped [to]." when talking about an element x of X, to say that x has no image with a certain property simply means that f(x) doesn't have that property. would the following formalization be a correct interpretation:

S={x in X such that f(x) is not an element of f(x)}? (here, f is the arbitrary map from X to P(X) we are trying to show is not a bijection.)

or do you mean, "...that are not themselves included in the P(X) members which they are mapped to?" if so, then
S={x in X such that x is not an element of f(x)}.

in your example, it looks like you're using the last definition i just gave but in the way you phrased it, it looks like the first formalized S is what you mean.
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)
question: are we assuming X=N?

if yes, then what is written may be relevant. if not, then what is written is not relevant (directly).

some observations about what comes after the "therfore." one doesn't have to define 0 to be a natural number. furthermore, one doesn't have to adopt the definition that {}=0. but if 0 is a natural number and if the definition of 0 is {}, then {} is in N. it is true that {} is in P(X) for any set X but the argument provided isn't what proves that. furthermore, it's not clear how what comes after the "therefore" follows from the argument given.
N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.
"subsets of N" is equivalent to "the empty set + subsets of N + N itself."
It is easy to show an injection between any n of N to any singleton member {n} of P(N).
when you say "map between @ and *," it usually means that @ is the whole domain of the map and not one element in the domain. one way to rephrase this is to say, "an injection that maps any n of N to any singleton member {n} of P(N)." by the way, the word "any" that comes before "singleton" means that the notation {n} is misleading because the notation {n} implies that n is mapped to a specific singleton {n} and not just any singleton which one might denote {m}. a way to rephrase that is to say, "...any n of N to the singleton {n}..."
When we define this injection thEn P(|N|)>=|N|.
since |N| refers to the cardinal number of N, i think it would be better to just say either |P(N)|>=|N| or P(N)>=N. when you say P(|N|), you're talking about the set of all subsets of the cardinal number aleph_0 and not the set of all subsets of N. I'm not even sure a cardinal number is a set. if it is, it might be something like the set of all things with that cardinality in which case P(|N|) would include many things irrelevant to N or P(N), including subsets of rational numbers for example.
If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped [to].
just out of curiosity, why use a second letter, D, to denote something you've already named S? doing so doesn't hurt the logic of the proof, of course, but it makes it less streamlined. here, the questions i asked of S now apply to D.
n in D because {} not in N, therefore D is not empty.
it's not clear how what comes after the "therefore" follows from what preceeds the "therefore." either it's a non sequitor or I'm just not understanding the argument (or both).

the essential thing that needs to be addressed before i can continue is the clarity of the definition of S=D.

i'm wondering (a) if D is really empty all the time and (b) whether the emptiness of D affects whether or not X=P(X). if you go back to what I've written with my version of D, D was sometimes empty in the examples i gave but that just meant that the empty set was an element of P(X) not mapped to and, hence, that the example map from X to P(X) was not a bijection.
 
  • #29
Organic
1,232
0
Hi phoenixthoth,


Thank you very much for your last post.

It is hard for me to express my ideas in English, so I really want to thank you for your help.

Please continue to help me to write it right, thank you.

Here is a corrected version, based on your remarks:

-------------------------------------------------------------------------

By step 1 of Cantor's prof (P(X)>X) we can say that P(X) >= X .

Let us continue from step 2 (and please give your detailed remarks to each part of it)

Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which is consists of ALL members of X that are not themselves included in the P(X) members which they are mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

{} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + N itself + other subsets of N.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than |P(N)|>=|N|.

If |P(N)|=|N| then S is a member in P(N), which is consists of ALL members of N that are not themselves included in the P(N) members, which they are mapped to.

n in S because {} not in N, therefore S is not empty.

Q.E.D

t=n
X=N

-----------------------------------------------------------------------------


Now, let us say that there exist some member in X (let us call it t ) which is mapped with S (t <--> S ).

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(X) and X and we can conclude that P(X) > S .

Q.E.D

=================================================
=================================================

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,...}:
Code:
0 = { } 

1 = {{ }} = {0}
               
2 = {{ },{{ }}} = {0,1}
  
3 = {{ },{{ }},{{ },{{ }}}} = {0,1,2}

4 = {{ },{{ }},{{ },{{ }}},{{ },{{ }},{{ },{{ }}}}} = {0,1,2,3}

and so on.
So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn
that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of X can be mapped with some member of P(X), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


More you simple less you depended, therefore more exist.

I'll write S defenition again, in an informal way:

There exists member S in P(X) which is consists of ALL members of X that are not themselves included in the P(X) members which they are mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

Now, the power of existence of X members is bigger than the power of existence of P(X) members.

Member t, which is some arbitrary member of X(and mapped with S), is simpler than S, which is a member of P(X) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:
  • #30
phoenixthoth
1,605
2
There exists member S in P(X) which is consists of ALL members of X that are not themselves included in the P(X) members which they are mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

S is nonempty in this example but there are instances in which S would be empty.

example: X=N and f(n)={n}. note that for all n in N, n is a member of f(n) and so the set of n in N such that n is not a member of f(n) is empty.

but it doesn't matter if S=Ø. this just means that Ø is not mapped to; that's good because it still shows that f is not a bijection because it's not onto.
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

{} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + N itself + other subsets of N.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than |P(N)|>=|N|.

If |P(N)|=|N| then S is a member in P(N), which is consists of ALL members of N that are not themselves included in the P(N) members, which they are mapped to.

n in S because {} not in N, therefore S is not empty.

Q.E.D
in the line when n is recently mentioned, is n an arbitrary element of N? if so, by saying "n in S," you're saying that N is a subset of S which entails that for all n in N, n is not an element of f(n). and this claim is made for all maps f from N to P(N). but this is not always the case. the counterexample f(n)={n} gives an example where not only is it not that case that, "for all n in N, n is not an element of f(n)," but it is that case that for no n in N is n not an element of f(n). in other words, saying n in S implies N in a subset of S when, in fact, S could be empty for the right f.

however, the last line feels like you're talking about a special n and not an arbitrary n, in which case saying "n in S" would be equivalent to asserting S is nonempty. however, if f(n)={n}, then
S={n in N such that n is not a member of f(n)}=Ø.

that S is empty (1) doesn't seem to matter and (2) isn't always true. it doesn't seem to matter because, in that case, it just means that Ø is not in the range of f and that's a good thing.

another thing is that N is continually referred to. if this is a prove that is supposed to work for all sets X, then N should not be referred to ever. your work amounts to proving N<P(N), not X<P(X) in general.

maybe it would be better to try to prove the following:
1. let X be any set
2. let f be any function from X to P(X)
3. let S={x in X such that x is not an element of f(x)}
4. prove that S is an element of P(X) not mapped to by f.

in 3-4, it doesn't matter if S=Ø. also, there is no need to prove S exists. the way S is defined, it exists by the subsets axiom. in fact, anytime you say "let S={x in X such that A(x)}," then S is a set as long as X is a set and A(x) is some well formed logical formula dependant on x such as "x is not a member of f(x)." the crux of that axiom is the part of the definition that says, "the set of elements of X such that..." as soon as a context is defined, and that context is a set like X is, then you can basically say any condition you want and the result exists and is a set. it might be empty, of course, like if you say {x in X such that x>0 and x<0}. empty or not, it exists and is a set. no need to prove S exists. no need to prove S!=Ø. step 4 doesn't require S to be nonempty.

the conclusions from 1-4, when those are done, are these:
5. there is always an element of P(X) not mapped to by any function f from X to P(X). (that element is S but at this point it no longer matters which element it is that isn't mapped to or even how many elements of P(X) are not mapped to.)
6. every function from X to P(X) is not onto
7. every function from X to P(X) is not a bijection
8. for every set X, X!=P(X)
9. since you already proved X<=P(X), this combined with 8 proves that X<P(X).

try to prove #4 and you'll be done.

regarding the notion of how many elements of P(X) are not mapped to, i think it's the following might be true:
let f be any function from X to P(X), let A\B be the set of elements in A that are not in B, and let f(X) be the set of all outputs of f.
1. for finite X, |P(X)\f(X)| >= 2^|X| - |X|. for example, if X has 10 elements, then the size of the set of targets in P(X) not mapped to by f is at least 2^10 - 10 = 1014. it could be even more than that if f is not injective. for example, if f(x)=Ø for all x, then
|P(X)\f(X)|=1023. if this number is greater than 0, f is not onto. 2^|X|-|X| is greater than 0 for all sets X, even if X=Ø.

2. for infinite X, |P(X)\f(X)|=|P(X)|. all it takes for f to not be onto is if |P(X)\f(X)|>0; for infinite X, not only is it >0, it's infinite! and not just that, but an infinity greater than X.
 
  • #31
phoenixthoth
1,605
2
cardinality question for hurkyl or whoever

in this thread, we've been talking about |P(X)|.

there's another set operation i'd like to discuss if the thread originator doesn't mind.

i hope it won't be too distracting to use lower case for all sets now. if x is a set, then let Ux be defined as follows:

z is in Ux if and only if there is an element y in x such that z is in y.

in other words Ux={z such that z is in y is in x for some y in x}.

Ux is the set of members of members of x.

(one can define x u y to be U{x,y}.)

for any set x, UP(x)=x.

(to see this we can prove that z is in UP(x) if and only if z is in x. suppose z is in x. then {z} is a subset of x; so {z} is in P(x). since z is in {z} is in P(x), z is in UP(x). now suppose z is in UP(x). then z is in y is in P(x) for some y in P(x). since y is in P(x), y is a subset of x; therefore, since z is in y, z is in x.)

however, it is not always the case that P(Ux)=x. the sets for which this is true are called transitive, i think. a quick counterexample is x=Ø.

hence, if P and U were functions on sets, which there not (what would their domain be?), then U would be a kind of left inverse for P.

since |UP(x)|=|x|, I'm wondering what |Ux| is. could we define a log on cardinals to be |LOG(x)|=|Ux|? generally speaking, what is |Ux| in terms of |x|?

i'm doubting a log would be appropriate. if x={P(N)}, then while |x|=1, |Ux|=2^|N|. however, UP(x)=U{Ø, x}=Ø u x=x, so |UP(x)|=|x|=1.
 
Last edited:
  • #32
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
generally speaking, what is |Ux| in terms of |x|?

There certainly can't be an exact relationship; e.g. consider

x = {{1}} and y = {N}

|x| = |y| = 1
but
|Ux| = 1 and |Uy| = aleph0


However, there is something interesting you can say. Consider the finite case:

Theorem: Suppose x is a finite set of sets. Then, |Ux| >= lg |x|. (lg is the base two logarithm)

The proof is simple. It is clear that x must be a subset of P(Ux). If |Ux| is finite, |x| <= 2^|Ux|, and the conclusion follows. If |Ux| is infinite, then the conclusion ollows as well.
 
  • #33
phoenixthoth
1,605
2
on an earlier notion of X<=Y

an earlier notion of X<=Y (technically |X|<=|Y|) was that there is a bijection between X and a subset of Y. this notion was rejected but i'd like to give concrete reasons for it to be rejected (just for fun).

i claim that there is an injection from N to X if and only if there is a bijection between X and a proper subset of X.

if the above were the definition of <=, then this entails that X is infinite if and only if X<=X. since we'd like to say X<=X for all sets X, this would imply that all sets are infinite. in other words, defining <= in the above way entails that either all sets are infinite or it is not the case that X<=X for all sets X.

proof:
suppose f is an injection from N to X. define h to be a map from X to X in the following way: if x is in X\f(N), h(x)=x and if x is in f(N), h(x)=f(finv(x)+1). finv is the inverse of f that is defined on f(N) which exists because f is injective. i claim that h is a bijection between X and X\{f(0)}, a proper subset of X. to show h is injective, suppose h(a)=h(b). there are two cases: a is in f(N) or a is in X\f(N). if a is in f(N), then h(a)=f(finv(a)+1). since h(a)=h(b), h(b) is in f(N) since f(finv(a)+1)=h(b). b must be in f(N) because if b is not in f(N), then h(b)=b which would imply h(b) is not in f(N) yet we just said that h(b) is in f(N). since b is in f(N), f(finv(a)+1)=h(b)=f(finv(b)+1). since f and finv are injections, a=b. the second case is if a is not in f(N). then h(b)=h(a)=a. since h(b)=a and a is not in f(N), b must not be in f(N) because if b is in f(N), h(b) would be f(finv(b)+1) which is in f(N) yet we just said that h(b)=a is not in f(N). since b is not in f(N), b=h(b)=h(a)=a. h is injective. to show that h is surjective, let x be any element of X\{f(0)}. (note that f(0) is not mapped to by h since if it were the case that h(x)=f(0), that would imply that f(finv(x)+1)=f(0) so that finv(x)=-1 which is impossible since the range of finv is N and -1 is not in N. no problem. x is an element of X\{f(0)} anyway.) there are two cases: x is in f(N)\{f(0)} or x is in X\f(N). if x is in f(N)\{f(0)} then h maps f(finv(x)-1) onto x. to see this, first note that since x!=f(0) and x is in f(N), finv(x)-1 is in N and so it is in the domain of f and, furthermore,
h(f(finv(x)-1)) = f(finv(f(finv(x)-1))+1) = x. the second case is if x is in X\f(N). then h maps x onto x. h is a bijection.

the driving idea behind that was to use the following two facts: (1) f inserts a copy of N into X and (2) N is in bijection with N\{0} and so the copy of N must be in bijection with the copy of N\{0} if the rest of X is left alone.

for the converse, suppose there is a bijection between X and a proper subset of X. let's call this map f and the proper subset X'. X cannot be a finite set. this is pretty clear, but to see this, let n be any natural number and to arrive at a contradiction, suppose g is a bijection from {1,...,n} onto X (the existence of such an n and bijection g is equivalent to saying X is finite--btw, if n=0, then {1,...,n}:=Ø which wouldn't happen here anyway since Ø has no proper subsets and so X!=Ø). this entails that f o g is a bijection from {1,...,n} to X'. the contradiction is that this means X and X' both have n elements yet X' is a proper subset of X. so X is infinite. the map h from N to X will be defined now:
let h(0) be any element of X
for n>0, let h(n) be any element of X\{h(0),...,h(n-1)}. such an element will always exist because X is infinite and {h(0),...,h(n-1)} is finite.
to show that h is an injection, suppose that h(a)=h(b). we will show that a<b and b<a both lead to contradictions and so a=b. if a<b, then h(b) is an element of X\{h(0),...,h(b-1)} which implies h(b)!=h(k) for all k<b. since a<b, this contradicts the assumption h(a)=h(b). that argument was symmetrical, so b!<a. there is an injection from N to X.

this also proves that there is an injection from N to any infinite set.
 
  • #34
phoenixthoth
1,605
2
Theorem: Suppose x is a finite set of sets. Then, |Ux| >= lg |x|. (lg is the base two logarithm)
me likey.

it's also pretty clear that there is no upper bound on |Ux|.

i would suspect that since lg |x| <= |Ux|, |x| <= 2^|Ux| which would entail that there is an injection from x to P(Ux). this works even if x=Ø if we define lg 0 = -oo (or anything less than 0). it's definitely not the case that there is an injection from P(Ux) to x for every x and so not only is x!=P(Ux) for all x, |x|!=|P(Ux)| for all x, although we already said that.

by the way, organic, one can show that if there is an injection from A to B and an injection from B to A, then there is a bijection from A to B. thus, another way to show that X<P(X) is to show that there is no injection from P(X) into X.
 
Last edited:
  • #35
Organic
1,232
0
Hi phoenixthoth,

Please limit your detailed answer only to the case of N and P(N).

Thank you.

---------------------------------------------------------------------------

|N|=aleph0

|P(N)|=2^aleph0

There exists member S in P(N) which is consists of ALL members of N that are not themselves included in the P(N) members which they are mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.



Bucause {} does not exist in N, but {} exists in P(N), then S have at least one member of N, for example:

n <--> {}

In this example S ={n}.


Now, let us say that there exist some member in N (let us call it t ) which is mapped with S (t <--> S ).




--------------------------------------------------------------------------

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(N) and N and we can conclude that P(N) > N .

Q.E.D

=================================================
=================================================

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,...}:
Code:
0 = { } 

1 = {{ }} = {0}
               
2 = {{ },{{ }}} = {0,1}
  
3 = {{ },{{ }},{{ },{{ }}}} = {0,1,2}

4 = {{ },{{ }},{{ },{{ }}},{{ },{{ }},{{ },{{ }}}}} = {0,1,2,3}

and so on.
So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn
that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


(S exists iff t is out of the scope of its definition. it means that the word ALL is omited from S definition).


More you simple less you depended, therefore more exist.

I'll write S defenition again, in an informal way:

There exists member S in P(N) which is consists of ALL members of N that are not themselves included in the P(N) members which they are mapped to, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

Now, the power of existence of N members is bigger than the power of existence of
P(N) members.

Member t, which is some arbitrary member of N(and mapped with S), is simpler than S, which is a member of P(N) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic
 
Last edited:

Suggested for: On P(X) > X

Replies
19
Views
398
Replies
4
Views
275
Replies
8
Views
465
  • Last Post
Replies
1
Views
428
Replies
1
Views
323
MHB Find x
  • Last Post
Replies
0
Views
453
  • Last Post
Replies
3
Views
465
  • Last Post
Replies
13
Views
822
  • Last Post
Replies
5
Views
768
Replies
2
Views
679
Top