Question About Bijections

[RussellE]

In ZFC, if I have an injection, A->B, and an injection, B->A,
does there always exists a bijection between A and B?
If so, which axioms do I need to prove it?


Russell
- Zeno was right. Motion is impossible.

[David Libert]

RussellE (reas...@gmail.com) writes:
> In ZFC, if I have an injection, A->B, and an injection, B->A,
> does there always exists a bijection between A and B?
> If so, which axioms do I need to prove it?

Yes.

[1] http://en.wikipedia.org/wiki/Cantor-Bernstein-Schroeder_theorem

As noted in [1], Cantor's original proof used the well-ordering
theorem and hence implicitly AC, but the later proofs, which are now
usually the ones given, only need ZF.

The bijection is explictly definable from parameters for both
injections.

The most obvious formalization of the usual proof uses separation
and the axiom of infinity. The latter being used because of an omega
sequence in the proof.

I think that formalization can be pared down to only use separation.


--
David Libert ah...@FreeNet.Carleton.CA

[MoeBlee]

On Nov 15, 10:52 pm, RussellE <reaste...@gmail.com> wrote:
> In ZFC, if I have an injection, A->B, and an injection, B->A,
> does there always exists a bijection between A and B?
> If so, which axioms do I need to prove it?

The axioms of Z\{regularity, infinity} are enough. Don't need choice,
replacement, infinity or regularity.

You can see various proofs (usually, they are bit complicated) in
textbooks in set theory. Note that, for example, Enderton does use
recursion over the set of natural numbers, but there are other proofs
that do not require that there be a set of all the natural numbers (so
infinity is not required).

MoeBlee

[RussellE]

Thanks.

Can a countably infinite set, X, have a bijection
with the powerset of X?


Russell
- 2 many 2 count

[MoeBlee]

On Nov 17, 10:28 pm, RussellE <reaste...@gmail.com> wrote

> Can a countably infinite set, X, have a bijection
> with the powerset of X?

Since you already know that there is no bijection between a set and
its power set, I wonder what non-frivolous purpose you have in asking.

MoeBlee

[RussellE]

Assume we have a countable non-standard model of PA in ZFC.
There is a bijection between N, the set of all standard naturals,
and N*, the universe of our non-standard model.

Let e be a nonstandard natural number.
E = {0,1,2,...,e}.
There is a bijection between N and E.

Let b = log2(e)
B = {0,1,2,...,b)
There is a bijection between N and B.

Doesn't this mean there is a bijection
between B and E?

[MoeBlee]

On Nov 18, 12:17 am, RussellE <reaste...@gmail.com> wrote:
> On Nov 17, 9:32 pm, MoeBlee <modem...@gmail.com> wrote:
>
> > On Nov 17, 10:28 pm, RussellE <reaste...@gmail.com> wrote
>
> > > Can a countably infinite set, X, have a bijection
> > > with the powerset of X?
>
> > Since you already know that there is no bijection between a set and
> > its power set, I wonder what non-frivolous purpose you have in asking.
>

> Assume we have a countable non-standard model of PA in ZFC.
> There is a bijection between N, the set of all standard naturals,
> and N*, the universe of our non-standard model.
>
> Let e be a nonstandard natural number.
> E = {0,1,2,...,e}.
> There is a bijection between N and E.
>
> Let b = log2(e)
> B = {0,1,2,...,b)
> There is a bijection between N and B.
>
> Doesn't this mean there is a bijection
> between B and E?

I don't know what you mean by 'log2' in this context.

Anyway, no matter what 'e' and 'b' stand for, if E = N u {e} and B = N
u {b}, then there is a bijection between N and B, and there is a
bijection between N and E, and there is a bijection between B and E.
So what? You still have not said why you ask whether there is
bijection between X and PX when you already know that there is not
one.

MoeBlee

[Frederick Williams]

RussellE wrote:

> Let e be a nonstandard natural number.
> E = {0,1,2,...,e}.
> There is a bijection between N and E.

It isn't clear to me what those three dots mean.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[FredJeffries]

Yes. But you can't "identify" the powerset of B "in ZFC" with E in

[RussellE]

> "the universe of our non-standard model".- Hide quoted text -
>
> - Show quoted text -

E is not the powerset of B, but E has the
same cardinality as the powerset of B.

If x is a natural number, isn't 2^x the size
of the powerset of x?

Why can't I "identify" the powerset of B "in ZFC"?
The powerset of B exists from the powerset axiom.


Russell
- Never never means never in set theory.

[David Libert]

RussellE (reas...@gmail.com) writes:
> On Nov 18, 12:35=A0pm, FredJeffries <fredjeffr...@gmail.com> wrote:
>> On Nov 17, 10:17=A0pm, RussellE <reaste...@gmail.com> wrote:
>>
>>
>>
>>
>>
>> > On Nov 17, 9:32=A0pm, MoeBlee <modem...@gmail.com> wrote:
>>
>> > > On Nov 17, 10:28=A0pm, RussellE <reaste...@gmail.com> wrote

>>
>> > > > Can a countably infinite set, X, have a bijection
>> > > > with the powerset of X?
>>
>> > > Since you already know that there is no bijection between a set and

>> > > its power set, I wonder what non-frivolous purpose you have in asking=

> .
>>
>> > > MoeBlee
>>
>> > Assume we have a countable non-standard model of PA in ZFC.
>> > There is a bijection between N, the set of all standard naturals,
>> > and N*, the universe of our non-standard model.
>>
>> > Let e be a nonstandard natural number.

>> > E =3D {0,1,2,...,e}.

>> > There is a bijection between N and E.
>>

>> > Let b =3D log2(e)
>> > B =3D {0,1,2,...,b)

>> > There is a bijection between N and B.
>>
>> > Doesn't this mean there is a bijection
>> > between B and E?
>>
>> Yes. But you can't "identify" the powerset of B "in ZFC" with E in
>> "the universe of our non-standard model".- Hide quoted text -
>>
>> - Show quoted text -
>
> E is not the powerset of B, but E has the
> same cardinality as the powerset of B.
>
> If x is a natural number, isn't 2^x the size
> of the powerset of x?
>
> Why can't I "identify" the powerset of B "in ZFC"?
> The powerset of B exists from the powerset axiom.

You are basically rediscovering Skolem's paradox.

http://en.wikipedia.org/wiki/Skolem%27s_paradox

You can code integers and hereditarily finite sets over integers
into PA. Code integer n as 2n. Codes for heritarily finite sets
over integers will be of form 2n + 1, where the binary
representation of n has its 0 and 1 coding membership of intergers
and lower rank hereitarily fininte sets over integers with codes
inductively defined.

Then the membership relation is coded by a primiative recursive
function, definable in PA.

In this way in a nonstandard model of PA, you can code the set
B = {0, 1, ... b}, ie the set of all numbers <= b, and you can code
the powerset of B.

This coded set theory can code Kurattowski ordered pairs and
functions and so bijections.

This theory interprets enough set theory to interpret Cantor's
theorem as you were noting.

Your B actually has cardinality b+1, so we should take
e = 2^(b+1) to correspond to its powerset.

So indeed we get as a theorem of PA there is no bijection between
these sets, as a statemrnte coding set theory into PA.

You can actually get even more results similar to this, without
Cantor's theorem. PA proves that if b and e are distinct numbers
then the sets {0, ... , b} and (0, ... , e} have no bijections
between them.

So that way, just take e ~= b , instead of b = log2(e) or
e = 2^b or as I noted above corrected to e = 2^(b+1).

Now as you point out, consider a countable nonstandard PA model, and
suppose b is nonstandard in there.

Take your e, or my suggestion take e nonstandard and ~= b.

Being nonstandard elements in a countable PA model,
{0, ... , b} and {0, ... , e} are both countable.

So they have a bijection.

So they don't have a bijection yet they do have a bijection. What
gives?

Just like a countable ZFC model. ZFC proves aleph_1 exists, so a
countable ZFC model has an element it believes satsifies the
definition of aleph_1. So the model says there are no bijections.

But they both have countably many model eleements which the model
satisifes as being their members, so there is a bijection between
their modelled elements.

The models say there is no bijection. But model theory over the
models says there is. Skolem's paradox.



--
David Libert ah...@FreeNet.Carleton.CA

[Frederick Williams]

RussellE wrote:
>
> [...]

>
> If x is a natural number, isn't 2^x the size
> of the powerset of x?

Is x a number or a set? It might be both, but if so, what is the
definition of one in terms of the other?

[FredJeffries]

The set of standard numbers or one particular chain are each subsets
of B in ZFC. But neither are a set in your model since neither has a
greatest element and the second has no first element either.

[RussellE]

> greatest element and the second  has no first element either.- Hide quoted text -

>
> - Show quoted text -

I don't understand what you mean by "set in your model".

We have two models of PA, one standard and one non-standard.
PA doesn't have axioms for sets, powersets, or countable sets.
Sets exist in the meta-theory, ZFC.

Let X and Y be sets that represent the non-standard natural
numbers x and y in our non-standard universe. Assume x != y.

We can prove there is no bijection between x and y
"in the model", but there is a set in ZFC that is a
bijection between x and y.

You will argue that no bijection exists "in the model".
No sets exist "in the model". ZFC proves the axioms
of PA require that no bijection exist between x and y.
ZFC also proves such a bijection exists.

ZFC proves a bijection exists and ZFC proves
a bijection can't exist. This is a contradiction.

What does "set in the model" mean?

[RussellE]

Every set of natural numbers, even non-standard natural numbers,
has a least element with respect to some ordering.

In "What Does a Non-Standard Model of PA Look Like in ZFC",
http://groups.google.com/group/sci.math/browse_thread/thread/9c6a302796385add
I asked what the universe of such a model looks like in ZFC.

I was told we can represent natural numbers in the non-standard
universe as ordered pairs, (a,b), where a is an integer and b is
a rational number. Integers can be represented as ordered
pairs, (c,d), where c is a standard natural number and d is 0 or 1.
Rational numbers can be represented as ordered pairs, (e,f),
where e is a standard numerator, and f is a standard denominator.
Since there is more than one way to represent a rational number,
I will choose the pair with the smallest denominator.

Each natural number in our non-standard universe can be
encoded as a 4-tuple, (c,d,e,f), of standard natural numbers.
We can now encode these 4-tuples into a single standard
natural number.

In ZFC, we can represent every standard natural number
as a finite ordinal. The universe of our non-standard
model can be encoded as a set of finite ordinals.

Every set of natural numbers in our non-standard
model is a set of finite ordinals. Every set of finite
ordinals has a least element with respect to the
standard ordering of ordinals.
(ordinals ordered by membership.)


Russell
- The universe is one dimensional.

[FredJeffries]

See excellent post by David Libert
http://groups.google.com/group/sci.logic/msg/ff8e179d0f46b291

[RussellE]

On Nov 18, 11:43 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:

> RussellE (reaste...@gmail.com) writes:
> > On Nov 18, 12:35=A0pm, FredJeffries <fredjeffr...@gmail.com> wrote:
> >> On Nov 17, 10:17=A0pm, RussellE <reaste...@gmail.com> wrote:
>
> >> > On Nov 17, 9:32=A0pm, MoeBlee <modem...@gmail.com> wrote:
>
> >> > > On Nov 17, 10:28=A0pm, RussellE <reaste...@gmail.com> wrote
>
> >> > > > Can a countably infinite set, X, have a bijection
> >> > > > with the powerset of X?
>

>

>   So that way, just take  e ~= b ,  instead of  b = log2(e)  or
> e = 2^b   or as I noted above  corrected to  e = 2^(b+1).
>
>   Now as you point out, consider a countable nonstandard PA model, and
> suppose  b is nonstandard in there.
>
>   Take your e,  or my suggestion take e  nonstandard and ~= b.
>
>   Being nonstandard elements in a countable PA model,
> {0, ... , b}  and  {0, ... , e}  are both countable.
>
>   So they have a bijection.
>
>   So they don't have a bijection yet they do have a bijection.  What
> gives?
>
>   Just like a countable ZFC model.  ZFC proves aleph_1 exists, so a
> countable ZFC model has an element it believes satsifies the
> definition of aleph_1.  So the model says there are no bijections.

What do you mean by "the model says there are no bijections"?

Let B = {0,1,2,...,b-1}.
I show how we can encode each non-standard natural number
as a finite ordinal. B is a set of finite ordinals.

B has a smallest and largest element "in the model".
We can order these ordinals by set membership.
With this ordering, we can prove B has a smallest
element and no largest element.

Let E = {0,1,2,...,e-1} where e != b.
Again, E can be ordered so it has no largest element.
B and E are both countably infinite and have a bijection.
This bijection is a countable set of ordered pairs,
(a,b), where a and b are finite ordinals.

This bijection can be encoded, "in the model",
just like any other bijection can be encoded.

>   But they both have countably many model eleements which the model
> satisifes as being their members, so there is a bijection between
> their modelled elements.
>
>   The models say there is no bijection.  But model theory over the
> models says there is.  Skolem's paradox.

What do you mean by "The models say there is no bijection"?

[Frederick Williams]

RussellE wrote:

> Every set of natural numbers, even non-standard natural numbers,
> has a least element with respect to some ordering.

That is an uninteresting claim. Every non-empty set has a least element

with respect to some ordering.

[RussellE]

On Nov 18, 11:43 pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
> RussellE (reaste...@gmail.com) writes:
>

>   Just like a countable ZFC model.  ZFC proves aleph_1 exists, so a
> countable ZFC model has an element it believes satsifies the
> definition of aleph_1.  So the model says there are no bijections.

I don't understand this part at all.
Let B = {0,1,2,...,b-1} where b is non-standard.
Let P be the powerset of B.
In the model, the cardinality of P equals
some non-standard natural number.
Let e = |P|. In the model, there is
a bijection between P and E where
E = {0,1,2,...,e-1}.

In ZFC, P is an uncountable set.
Who is right? Is the model correct
and the cardinality of P is "countable"
(equal to some natural number).
Or is ZFC correct in believing P
is uncountable.

If there is a bijection between E and P
in the model, why isn't there one in ZFC?

[Frederick Williams]

RussellE wrote:

> Who is right? Is the model correct
> and the cardinality of P is "countable"
> (equal to some natural number).
> Or is ZFC correct in believing P
> is uncountable.

As David Libert remarked, you've come up against Skolem's paradox.

[Chris Menzel]

On Mon, 21 Nov 2011 11:23:38 +0000, Frederick Williams
<freddyw...@btinternet.com> said:
> RussellE wrote:
>
>> Who is right? Is the model correct
>> and the cardinality of P is "countable"
>> (equal to some natural number).
>> Or is ZFC correct in believing P
>> is uncountable.
>
> As David Libert remarked, you've come up against Skolem's paradox.

Better: Skolem's "paradox".

[David Libert]

I wrote

[1] David Libert "Re: Question About Bijections"
sci.logic Nov 19, 2011
http://groups.google.com/group/sci.logic/msg/ff8e179d0f46b291

relating Russell's recent comments in this thread to Skolem's paradox
(or as Chris points out: Skolem's "paradox" :-) .)

You followed up to [1]:

[2] RussellE "Re: Question About Bijections"
sci.logic Nov 19, 2011
http://groups.google.com/group/sci.logic/msg/537764d7df7b00c3

This is following up to [2] .


In [1] I wrote about the analogue to the PA discussions with models
of ZF and Skolem's "paradox" :

> So they don't have a bijection yet they do have a bijection. What
>gives?
>

> Just like a countable ZFC model. ZFC proves aleph_1 exists, so a
>countable ZFC model has an element it believes satsifies the
>definition of aleph_1. So the model says there are no bijections.
>

> But they both have countably many model eleements which the model
>satisifes as being their members, so there is a bijection between
>their modelled elements.
>
> The models say there is no bijection. But model theory over the
>models says there is. Skolem's paradox.

That [1] writing of mine was sloppy. So I will give more details
now.

Take our countable ZFC model, which I didn't name in [1] but I will
now call M. Let the binary relation E on M be M's interpretation
of the epsilon relation symbol from the ZFC language.

As I noted in [1], M has a element which in M satifies the
definition of aleph_1. In [1] I didn't name that element, but now let
us call it w1.

I neglected to spell out in [1] that M also has an element which
in M satisfies the usual ZF definition of omega. Call this element w.

ZFC proves there is no bijection from omega to omega_1. So M will
satisfy the corresponding sentence about w and w1.

This sentence talks about bijections, which are functions, which are
formalized in ZFC as sets of Kuratowski ordered pairs. So we expand
out all those definitions, including the definition of Kuratoswki
ordered pairs. That becomes a definition in just primitive relation
symbols = and epsilon, and usual f.o. logic over those relation
symbols.

To see how that sentence evaluates in M, we replace all occurences
of epsilon symbol by E.

So we get a complicated statement in M, mentioning E and all
f.o. quantifiers from the definition become quantiofication over the
universe of M.

In this sense we get the statment that there is no bijection between
w and w1 in M, ie "omega" and "omega_1".

In [1] I neglected to mention "omega" and the bijection in question
was between "omega" and "omega_1".

But stepping back up to ZFC above M, there is another sentence true
in ZFC language about M, not in M's internal language, which is a
reasonable formalization of the statement that in some sense there is
a bijection between w and w1.

Namely w is an object in M, a model of set theory. So w has
certain "members" in the sense of that model, namely those element in
the universe of M which are in the E relation to w.

Since M was a countable model, this set of E members of w is a
countable set.

Similarly, we can in ZFC over M form the set of all those elements
of the M universe which are in E relation to w1, ie E members of
w1.

These 2 sets are reasonable formalizations in ZFC over M of what
those "sets" from inside M represent.

But w1 only has according to ZFC countably many such actual E
members, since ZFC knows M was only a countable model.

So ZFC sees both those defined sets based on w and w1 are actually
countable and so have a bijection.

That is what [1] was trying to write about, though it sure skipped
details.

In [2] you wrote, respopnding to [1]:

>I don't understand this part at all.

Yes, I had skipped over too much in [1]. I hope I have explained it
better now.

You continued:

>Let B = {0,1,2,...,b-1} where b is non-standard.
>Let P be the powerset of B.
>In the model, the cardinality of P equals
>some non-standard natural number.
>Let e = |P|. In the model, there is
>a bijection between P and E where
>E = {0,1,2,...,e-1}.

Yes, I agree.

>In ZFC, P is an uncountable set.
>Who is right? Is the model correct
>and the cardinality of P is "countable"
>(equal to some natural number).
>Or is ZFC correct in believing P
>is uncountable.

I thought we were talking about countable nonstandard PA models in
this thread.

The PA model would interpret hereitarily finite sets over integers
as I wrote in [1]. That interprets the epsilon symbol into symbols
=, S, +, *. Then those symbols are interpeted into realtions ond
functions on the PA model.

If we want to recast those as sets in ZFC meta-theory over the PA
model we would extract sets, similar to how I discussed over a ZFC
model M as above.

If we do that we don't get back ZFC full powerset over the extracted
version of B = {0, ... , b-1}.

Instead we just get the PA models weak version of powerset, recoded
back into ZFC. In general a subset of the true ZFC pwerset.

And if the PA model was countable, it will indeed be a proper subset
since it will be only a countable set in ZFC.

So ZFC will take that P to be countable.

The issue is, PA sets those different sized finite sets having no
bijections. ZFC over the PA models, sees these sets hich the PA model
thought were "finite" are really nonstandard and infinite. And in
case of a countable PA model they are actually both countable and so
have a bijection.

Uncountabilty or not came up in the ZFC case for Skoelm's "paradox".
The difference between the model and the ZFC meta-theoryt was the
model satisdfied that certain sets were uncountable, but the ZFC
meta-language satifies that they are actually really countable. So
the 2 levels disagreed about whether bijections exist based on that
difference.

In the PA case, everything is countable in ZFC over the model (if we
are talking about a countable model). Now the disrepancy is not
countable/"uncountable" but instead "finite"/infinite.

The analogy between this PA cases from this thread and the usual
Skoelm's "paradox" prhrased over ZFC is that in both cases a little
model thinks there are no bijections, and big set thoery over the
model sees that there really are.

In the model, quantifiers just range over the universe of the
model. In ZFC meta-language over the model, quatnifiers range over
the entire set theoretic universe above that model. ZFC can see
further than the little model, and can find those bijections the
little model missed.

Don't try to prtess the analogy too far by them both processing
uncountability the same way. Uncountability doen's come up in thr PA
version, where PA doesn't talk about uncountability, and ZFC doesn't
have it relevant to talk about the countable PA model.

The analogy was just about bijections. Relating these issues in the
new PA case to the better known similar things with Skolem's "parasox"
and ZFC.


You continued in [2]:

>If there is a bijection between E and P
>in the model, why isn't there one in ZFC?

There is such a bijection in ZFC. This is a general fact. If the
model satisfies that there is a function, then in ZFC over the model
you can extractt a corresponding function. The function that
evaluates just as was done in the model.

So if a model satsfies that two sets are bijective, then in ZFC
above you can extract a similar corresponding bijection between the
extracted sets.

Existence statements about bijections lift from the model to ZFC
over the model.

Above with Skolem's "paradox" was non-existence statements about
bijections need not lift from the model to above.

Ie, you are the model and I am ZFC over the model. You are
nearsighted, and I can see farther than you.

When you see things, I see them too, and they are really there.

When you can't see something and you say there are no such things,
maybe there really are none as you said, or else maybe there are and
I can see them, and you just couldn't because you didn't see far
enough.

Anyway, the issue here was never about the bijection between E and
P. The PA model see it, and as your question suggests ZFC over the
model sees it.

The bijection in question is not that, but instead the bijection
between B = {0, ... , b-1} and B's powerset P.

That was also my fault for being so sloppy writing [1].



--
David Libert ah...@FreeNet.Carleton.CA

[RussellE]

I want to compare a standard model with a non-standard model.
Call the standard model M and the non-standard model M'.

> As I noted in [1], M has a element which in M satifies the
> definition of aleph_1. In [1] I didn't name that element, but now let
> us call it w1.
>
> I neglected to spell out in [1] that M also has an element which
> in M satisfies the usual ZF definition of omega. Call this element w.

M has w and w1, M' has w' and w1'.

> ZFC proves there is no bijection from omega to omega_1. So M will
> satisfy the corresponding sentence about w and w1.

M proves there is no bijection from w to w1.
M' proves there is no bijection from w' to w1'.

> This sentence talks about bijections, which are functions, which are
> formalized in ZFC as sets of Kuratowski ordered pairs. So we expand
> out all those definitions, including the definition of Kuratoswki
> ordered pairs. That becomes a definition in just primitive relation
> symbols = and epsilon, and usual f.o. logic over those relation
> symbols.

Sets don't exist "inside the model" because PA doesn't have
axioms for sets. We can define a weak set theory "inside the model".

> To see how that sentence evaluates in M, we replace all occurences
> of epsilon symbol by E.

I assume E somehow encodes order type.
Given two sets, E and E', could we tell which
one is the epsilon function for the standard model?

Does a standard model have to have order type omega?

> So we get a complicated statement in M, mentioning E and all
> f.o. quantifiers from the definition become quantiofication over the
> universe of M.
>
> In this sense we get the statment that there is no bijection between
> w and w1 in M, ie "omega" and "omega_1".

Our weak set theory "inside the model" doesn't have
an axiom of infinity, so the model can't "prove" w and w1
even exist.

Are you saying ZFC proves the set that is a
bijection between w and w1 (as defined in ZFC)
can't exist inside the model?

> In [1] I neglected to mention "omega" and the bijection in question
> was between "omega" and "omega_1".
>
> But stepping back up to ZFC above M, there is another sentence true
> in ZFC language about M, not in M's internal language, which is a
> reasonable formalization of the statement that in some sense there is
> a bijection between w and w1.

Does "in some sense" mean we can construct a set of
ordered pairs, (wi, w1i). If so, why can't we encode
this set using our weak set theory inside the model?

> Namely w is an object in M, a model of set theory. So w has
> certain "members" in the sense of that model, namely those element in
> the universe of M which are in the E relation to w.
>
> Since M was a countable model, this set of E members of w is a
> countable set.

I don't think PA has any models, let alone a
countable non-standard model.

Infinite Sets Can't Exist
Posted: Feb 19, 2010 1:45 PM
http://www.mathforum.com/kb/message.jspa?messageID=6987273&tstart=0

I show how, given a bijection between A and B,
we can construct a bijection between A/B and B/A.
This construction always works when A and B are finite.
If A is infinite and B is a proper subset of A,
the method constructs a bijection between a
non-empty set and the empty set.

What Does a Non-Standard Model of PA Look Like in ZFC?
RussellE Nov 2, 6:10 pm
http://groups.google.com/group/sci.logic/browse_thread/thread/9c6a302796385add

I show how we can use the powerset of a non-standard
number to define an "uncountable" number of
different Z chains in the model.

> Similarly, we can in ZFC over M form the set of all those elements
> of the M universe which are in E relation to w1, ie E members of
> w1.

ZFC proves "uncountable in the model" is really countable in ZFC.

> These 2 sets are reasonable formalizations in ZFC over M of what
> those "sets" from inside M represent.
>
> But w1 only has according to ZFC countably many such actual E
> members, since ZFC knows M was only a countable model.

Because Compactness is a theorem of ZFC.

> So ZFC sees both those defined sets based on w and w1 are actually
> countable and so have a bijection.

Can ZFC "construct" this bijection?
If so, we can encode the bijection "in the model".
The model can't prove this is a bijection
but the bijection would exist in the model.

> That is what [1] was trying to write about, though it sure skipped
> details.
>
> In [2] you wrote, respopnding to [1]:
>
> >I don't understand this part at all.
>
> Yes, I had skipped over too much in [1]. I hope I have explained it
> better now.
>
> You continued:
>
> >Let B = {0,1,2,...,b-1} where b is non-standard.
> >Let P be the powerset of B.
> >In the model, the cardinality of P equals
> >some non-standard natural number.
> >Let e = |P|. In the model, there is
> >a bijection between P and E where
> >E = {0,1,2,...,e-1}.
>
> Yes, I agree.

Where P is the powerset of B "in the model".
Since B is an infinite set in ZFC,
ZFC thinks the powerset of B is P2,
an uncountable set.

> >In ZFC, P is an uncountable set.
> >Who is right? Is the model correct
> >and the cardinality of P is "countable"
> >(equal to some natural number).
> >Or is ZFC correct in believing P
> >is uncountable.
>
> I thought we were talking about countable nonstandard PA models in
> this thread.

We are assuming there are such models.

> The PA model would interpret hereitarily finite sets over integers
> as I wrote in [1]. That interprets the epsilon symbol into symbols
> =, S, +, *. Then those symbols are interpeted into realtions ond
> functions on the PA model.
>
> If we want to recast those as sets in ZFC meta-theory over the PA
> model we would extract sets, similar to how I discussed over a ZFC
> model M as above.
>
> If we do that we don't get back ZFC full powerset over the extracted
> version of B = {0, ... , b-1}.

Huh? A natural number is a natural number.
Let M be a standard model and let B={0,1,2}.
ZFC says the powerset of B is infinite?
The standard model only "extracts" a finite
subset of "true" powerset of B?

In PA, the cardinality of the poweset of a
natural number is equal to a natural number.

> Instead we just get the PA models weak version of powerset, recoded
> back into ZFC. In general a subset of the true ZFC pwerset.

Our "weak" set theory inside the model can't
define the entire powerset of a natural number?

> And if the PA model was countable, it will indeed be a proper subset
> since it will be only a countable set in ZFC.
>
> So ZFC will take that P to be countable.

We are talking about two different sets here.
We have P which is what our weak set theory
inside the model says is the powerset of B.

ZFC thinks B is an infinite set and the
powerset of B is P2, an uncountable set.

The model and ZFC agree there is a bijection between P and E.
The model thinks P is the powerset of B.
ZFC thinks B and E have a bijection.
ZFC proves there is a bijection between B and P.
We can encode the bijection between B and P
inside the model.

> Above with Skolem's "paradox" was non-existence statements about
> bijections need not lift from the model to above.

So, this isn't really Skolem's paradox.
ZFC and the model agree there is a bijection
between P and E.

> Ie, you are the model and I am ZFC over the model. You are
> nearsighted, and I can see farther than you.

I don't know why you think "the model" is smaller than ZFC.
Yes, we are only allowing the model to have a
weak form of set theory. Even so, sets ZFC thinks
are "infinite" are "finite" in the model.

If we allowed the model to have its own
non-standard version of ZFC, this non-standard
ZFC would laugh at our puny standard ZFC.
Imagine a set theory that thinks {0,1,2}
is an infinite set.

> When you see things, I see them too, and they are really there.
>
> When you can't see something and you say there are no such things,
> maybe there really are none as you said, or else maybe there are and
> I can see them, and you just couldn't because you didn't see far
> enough.
>
> Anyway, the issue here was never about the bijection between E and
> P. The PA model see it, and as your question suggests ZFC over the
> model sees it.

This is like the great and powerful Oz saying
"Pay no attention to that man behind the curtain!"
http://www.imdb.com/title/tt0032138/quotes

> The bijection in question is not that, but instead the bijection
> between B = {0, ... , b-1} and B's powerset P.

ZFC proves there is a bijection between P and E.
ZFC proves there is a bijection between B and E.
ZFC proves there is a bijection between B and P.

We don't even have to talk about powersets.
Proving there is a bijection between B and E
is enough to get a contradiction.

B = {0,1,2,...,b-1}
E = {0,1,2,...,e-1}

e > b

B is a proper subset of E.

In ZFC, B and E are infinite sets of finite ordinals.
Finite ordinals can be ordered by set membership.
(I mean set membership as defined in ZFC,
not the model.)

Assume we order B and E by set membership.
We can now define a bijection between B and E.
This bijection is a set of ordered pairs, (b,e),
where b and e are finite ordinals.
This bijection can be encoded as a set
"in the model".

There exists a bijection between B and E
"in the model" even if the model can't
prove such a bijection exists.

[Frederick Williams]

RussellE wrote:

>
> In PA, the cardinality of the poweset of a
> natural number is equal to a natural number.

What is the powerset of a natural number?

And what is "in PA" doing there? In PA is there is no concept of
powersets, because PA isn't about sets.