Dual Cantor-Bernstein (Attn: Herman Rubin)
Arturo Magidin
Bernstein" problem: if we have surjections A-->B and B-->A, does there
exist a bijection between A and B? If we assume AC, this follows from
the usual Cantor-Bernstein, but in the absence of Choice it would
appear that it fails.
Herman Rubin made a post in which he sketched how the existence of an
amorphous set (a set that cannot be expressed as a disjoint union of
two infinite sets) would imply that the dual Cantor-Bernstein does not
hold:
http://groups.google.com/group/sci.math/msg/28543d2b17d8f4ab
In a recent post in MathOverflow,
http://mathoverflow.net/questions/38771/dual-schroeder-bernstein-theorem
someone asked about this, and I pointed him to that thread. I thought
I could turn Prof Rubin's argument into a proof that if we assume ZF
+Dual of Cantor-Bernstein, then it would follow that every infinite
set has a denumerable subset, which would give at least countable
choice. The argument is:
Let U be an infinite set. Let A be the set of all n-tuples of elements
of U with n even, and let B be the set of all n-tuples of elements of
U with n odd. Map A to B by deleting the first entry; map B to A by
mapping singletons to a specific element of A, and the rest by
deleting the first entry. This gives surjections A-->B and B-->A, so
if we assume the dual of Cantor-Bernstein, we have a bijection f:B--
>A.
In his original post, Prof Rubin says that this "quickly gives a
countable subset of U"; I seem to remember working it out in my head
at the time, but I'm having trouble reconstructing it now. The
original poster also is having trouble constructing such an argument
without using some form of choice (e.g., that a countable union of
finite sets contains a countable set).
I was hoping someone could either fill out this last part, i.e., how
to get a countable (infinite) subset of U from the bijection B-->A.
Thanks in advance.
--
Arturo Magidin
Don Coppersmith
Start with a finite subset K of U with at least 3 elements.
Consider the set S of all tuples of distinct elements from K.
Suppose |K| is even; then there are more such tuples in A
than in B.
So the collection {f(t): t in S intersect A} must
contain tuples in B but not in (S intersect B),
thus must contain (finitely many) elements of U not in K.
Pick one and add it to K.
(Similarly if |K| is odd, switching roles of A and B.)
Continue, keeping track of the order in which elements
are added to K.
Don Coppersmith
Arturo Magidin
> How's this?
> Start with a finite subset K of U with at least 3 elements.
> Consider the set S of all tuples of distinct elements from K.
> Suppose |K| is even; then there are more such tuples in A
> than in B.
> So the collection {f(t): t in S intersect A} must
> contain tuples in B but not in (S intersect B),
> thus must contain (finitely many) elements of U not in K.
> Pick one and add it to K.
> (Similarly if |K| is odd, switching roles of A and B.)
> Continue, keeping track of the order in which elements
> are added to K.
Wouldn't this require that a countable union of finite sets is (or
contains) a countable set? I believe this cannot be proven in ZF
without some form of Choice...
--
Arturo Magidin
Don Coppersmith
I don't think so.
At each stage S is finite (has size about |K|!*e).
We can even give a deterministic ordering for
{t: t in S intersect A}, and pick the earliest one
for which f(t) is not in S intersect B, and pick
the earliest non-K element of f(t).
As long as we can get that initial K we're okay.
Don Coppersmith
Arturo Magidin
> > > How's this?
[...]
>
> I don't think so.
> At each stage S is finite (has size about |K|!*e).
> We can even give a deterministic ordering for
> {t: t in S intersect A}, and pick the earliest one
> for which f(t) is not in S intersect B, and pick
> the earliest non-K element of f(t).
> As long as we can get that initial K we're okay.
Thank you.
--
Arturo Magidin
David Libert
At the base of this thread, Arturo references the old 2003 thread:
[1] Mar 14 - 17 2003 "Bi-surjectiveness"
sci.math 12 articles
http://groups.google.com/group/sci.math/browse_thread/thread/caef4ba545bab3cb/28543d2b17d8f4ab
and specifically from [1] :
[2] Herman Rubin "Bi-surjectiveness"
sci.math Mar 15 2003
http://groups.google.com/group/sci.math/msg/28543d2b17d8f4ab
In [2], Herman wrote:
>There exist counterexamples galore. One is to let U_1 be an
>amorphous set, and let U_n be set of ordered n-tuples of
>distinct elements of U_1. Then let A be the union of the U_n
>for n even, and B_n the union for n odd. Each can easily be
>mapped onto the other. However, an 1-1 mapping of B into A
>quickly gives a countable subset of U_1.
In the base article of thour current thread, Arturo wrote a
summary of the outline from [2] :
>Let U be an infinite set. Let A be the set of all n-tuples of elements
>of U with n even, and let B be the set of all n-tuples of elements of
>U with n odd. Map A to B by deleting the first entry; map B to A by
>mapping singletons to a specific element of A, and the rest by
>deleting the first entry. This gives surjections A-->B and B-->A, so
>if we assume the dual of Cantor-Bernstein, we have a bijection f:B--
>
>>A.
>
>In his original post, Prof Rubin says that this "quickly gives a
>countable subset of U";
There is a difference between these two accounts. Herman's version
for the later steps is only claiming to use an injection : B >-> A,
and Arturo's version is using the full available conclusion from
earlier that there is a bijection : B >->> A .
If my own writing that I will summarize below is correct this
difference is significant.
I posted 4 atticles to [1]. Relevant now are the last 2 of these 4,
from Mar 16 and 17 :
[3] David Libert "Bi-surjectiveness"
sci.math Mar 16 2003
http://groups.google.com/group/sci.math/msg/0a8320acb6e6baa8
[4] David Libert "Bi-surjectiveness"
sci.math Mar 17 2003
http://groups.google.com/group/sci.math/msg/dd9474f50b01187d
I also posted 2 related followup articles in respective singleton threads:
[5] David Libert "Amorphous set with injection distinct tuples evens to odds"
sci.math June 14, 2003
http://groups.google.com/group/sci.math/msg/9c47f00a2fb3689b
[6] David Libert "Followup about injecting tuples of amorphous set"
sci.math June 21, 2003
http://groups.google.com/group/sci.math/msg/870d0bd4a5387711
The proof outlines above started from a set called either U_1 or U,
defined sets A and B, and from a claim about A and B contradicted
the starting U_1 or U being amorphous.
In Herman's version the claim was B injects into A. In Arturo's
version the claim was B bijects with A.
In [3] I constructed from Con(ZF) a model of ZF with an amorphous
set U_1 so for A,B as above B injects into A.
This shows the original form of the outline in [2] cannot be done.
As a technical side note, [5]-[6] gave another ZF model
showing the other direction of single injection claim fails
the same way. A ZF model with a different U_1 amorphous,
but the A,B as defined above having A injects into B.
In [3] and [4] ([4] correcting a point in [3]) I gave a proof
in ZF, or A,B defined as above for U_1, B bijects with A
contradicts U_1 amorphous.
This stronger claim, B bijective with A, still follows from
the original question in [1], as Arturo notes, so the [3]-[4]
proof shows an amorphous set answers the original [1] question.
The [3]-[4] proof has another difference from the outlines by
Herman and Arturo.
The outlines wanted to have some claim contradict U_1 or U is amorphous.
Both outlines planned to do this by showing omega injects into
U_1 or U.
The [3]-[4] proof did not show omega injects into U_1. It just
contradicted U_1 being amorphous more directly.
Namely [3]-[4] from the B bijective to A claim got a strictly
growing tower of finite subset of U_1 .
This is easilty equivalent to U_1 surjecting onto omega.
So [3]-[4] instead of injecting omega into U_1
surjected U_1 onto omega.
This surjection conclusion is enough to directly contradict
U_1 amorphous, which is all that was required in thw larger outlines
of Herman and Arturo.
To pass from that surjective claim to the injective claim would
on most casual reading seem to need countable choice.
In our current thread, Don Coppersmith gave a proof from
the B bijects with A claim to conclude omega injects into U.
(I use U_1 or U in discussions according to which each article
used.)
Don's proof was similar to [3]-[4]. But Don's proof never isolated
the surjection conclusion as a separate statement. Don went from
the background toward the surjection directly toward and injection.
Don's proof in boroadest outline would look like it was using
countable choice, in the same way to go from the surjection claim
to the injection claim would seem to need it.
This issue was raised in our current thread, and Don noted the
details, to make a more definable version and get back that way
enough choice.
This extra step of mimicing countable choice by keeping
track of definabilty was never done in [3]-[4].
On the other hand, to just contradict amorphousness, the extra
strength of the injection claim over the surjection one is
not required.
Still, with more careful statement, the extra work of Don's
proof over [3]-[4] gives a stronger result.
The [3]-[4] proof shows any ZF model with an amorphous set U_1
has A,B a counterexample to Dual Canotr Berstein.
In
[7] David Libert "Re: Discrete Topology, Partitioning an Infinite Set"
sci.math July 19, 2000
http://groups.google.com/group/sci.math/msg/9ceac20002e350d7
I posted about a ZF model of Sageev with a Dedikind set but no amorphous sets.
(Dedekind set: an infinite Dedekind finite set).
In [7] and with followup in
[8] David Libert "Re: Discrete Topology, Partitioning an Infinite Set"
sci.math July 22, 2000
http://groups.google.com/group/sci.math/msg/d76c6578230934e0
I wrote in outline about my own more direct construction (assuming no errors!)
also of a ZF model with Dedekind set and no amorphous sets.
Don's injection claim not only contradicts that U is amorphous, it also
contradicts that U is Dedekind.
The [3]-[4] proof getting the surjection claim only shows that ZF models
with amorphous sets have counterexamples to DCB (Dual Cantor Berstein).
The [3]-[4] proofs gives no information about DCB counterexamples
in ZF models with Dedekind sets but no amorphous sets.
The extra work of Don's proof shows such extra ZF models as from [6]-[7]
also have DCB counterexamples.
So this article has been about 2 points. Do we use B injects into A
or the full B bijects with A.
And do we conclude U_1 surjects onto omega or so we conclude
omega injects into U.
--
David Libert ah...@FreeNet.Carleton.CA
Arturo Magidin
> Arturo Magidin (magi...@member.ams.org) writes:
[...]
> So this article has been about 2 points. Do we use B injects into A
> or the full B bijects with A.
>
> And do we conclude U_1 surjects onto omega or so we conclude
> omega injects into U.
I confess to having gotten lost as to the conclusions you drew here.
I wasn't really worrying about models with amorphous sets or with
Dedekind sets; the original question in MathOverflow asked whether if
we replaced AC with the dual of Cantor-Bernstein, we could get back
Choice or some weaker form of choice. It seemed to me that Prof
Rubin's argument, if correct, would show that ZF+(Dual CB) implies
countable choice. With Don Coppersmith's construction, it seemed to me
it does indeed follow that ZF+(dual CB) implies countable choice. Was
I incorrect?
--
Arturo Magidin
David Libert
> On Sep 17, 11:04=A0pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
>> Arturo Magidin (magi...@member.ams.org) writes:
>
> [...]
>
> to A
>> or the full =A0B bijects with A.
>>
>> =A0 And do we conclude =A0U_1 surjects onto omega or so we conclude
>> omega injects into =A0U.
>
> I confess to having gotten lost as to the conclusions you drew here.
>
> I wasn't really worrying about models with amorphous sets or with
> Dedekind sets; the original question in MathOverflow asked whether if
> we replaced AC with the dual of Cantor-Bernstein, we could get back
> Choice or some weaker form of choice. It seemed to me that Prof
> Rubin's argument, if correct, would show that ZF+(Dual CB) implies
> countable choice. With Don Coppersmith's construction, it seemed to me
> it does indeed follow that ZF+(dual CB) implies countable choice. Was
> I incorrect?
>
> --
> Arturo Magidin
Don's proof shows in ZF that dual CB -> omega injects into every infinite
set.
I will set notation to talk about fragments of AC.
Consider <Ai | i member of I > a family of sets Ai indexed by index set I,
with Ai Aj disjoint for i ~= j i,j in I.
AC for such family will state there is a choice set C s.t for all i in I
# (C ^ Ai) = 1.
Countablly many finite choices AC will say for all such families with I countable
and each for each i in I Ai finite, we have AC for the family.
(This does not require a common uniform finite bound on all the Ai sizes).
Countably many countable choices AC will say for I countable and each Ai countable
for i in I, we have AC for such a family.
I think ZF proves
(omega injects into every infinite set) -> Countably many finite choices AC.
This is already a significant fragment of AC. In his book Cohen gets a ZF countermodel
to countably many size 2 choices (the obvious definition).
So with Don's proof, over ZF dual CB would already imply a fragment of AC not
provable in ZF. (Assuming ZF consistent as usual).
On the other hand, I think I found a Fraenkel Mostowski model and then a Cohenization
of that to a ZF model of
ZF + omega injects into every infinite set and ~ countablly many countable choices AC.
Ie, omega can inject into every set yet some <Ai | i in omega> with each
#Ai = omega (i in omega), having no choice set.
If that ZF construction I think I have is correct, Don's proof so far takes us
to coubtably many finite choices AC and no higher.
That is only answering what we see from Don's proof.
I don't know how dual CB works in such models.
I don't have any proofs or counter models about dual CB -> higher fragments of AC.
Just to answer what we readily know so far based on the conclusion from Don's proof.
--
David Libert ah...@FreeNet.Carleton.CA
Arturo Magidin
Okay, that much I followed. Thanks.
--
Arturo Magidin
David Hartley
<1768397500.46847.12846...@gallium.mathforum.org>,
Don Coppersmith <dco...@idaccr.org> writes
A form of countable choice is needed in general even to make a countable
sequence of choices from finite sets, as you do above. That can
certainly be avoided if you can define a linear ordering for S intersect
A *for all stages at once*, but not by saying that at each stage S is
finite and so S intersect A can be ordered. What "deterministic
ordering" do you have in mind?
--
David Hartley
Don Coppersmith
> <1768397500.46847.1284666636337.JavaMail.root@gallium.
At stage n, K is an ordered n-tuple of distinct elements from U.
S is the collection of ordered m-tuples of distinct elements from K
with m ranging from 1 to n.
Define an ordering on S where 1-tuples precede 2-tuples,
which precede 3-tuples etc, and among m-tuples of the same size,
impose a lexicographical ordering imposed by the original ordered
n-tuple K.
So if K=(a,b,c), we order its elements as a<b<c,
and the ordering on S is:
(a),(b),(c),(ab),(ac),(ba),(bc),(ca),(cb),(abc),(acb),(bac),(bca),(cab),(cba).
A counting argument shows that if |K| is at least 3, then the tuples in S
whose sizes have the same parity as |K|, strictly outnumber those of
opposite parity.
So (if |K| is even) {f(t): t in S intersect A} can't lie in (S intersect B).
Use the above ordering to pick the earliest t in (S intersect A) such that
f(t) lies outside (S intersect B).
f(t) is some m-tuple which includes elements not in K.
Pick the first element u of f(t) which is not in K, and append u to K,
so that K is now (a,b,c,u).
My use of the word "pick" in the original description was unfortunate.
It's all determinstic, after the initial choice of K of length at least 3.
(If |K| is 1 or 2, this doesn't work; we could have
f((a))=(ab), f((b))=(ba), and we would never discover new elements.)
Don Coppersmith
David Libert
> Arturo Magidin (mag...@member.ams.org) writes:
[Deletions]
I don't know anything new about the hard direction above as from the recent math
overflow discussion, getting AC style consequences to dual CB.
I can add something related to the other side, going from AC style to dual CB.
For kappa a cardinal, let AC_kappa be the statement that any family as above
<Ai | i member of kappa> of pairwise disjoint non-empty sets has a choice set,
as above.
(I notice in my discussion above I forgot to specify all the Ai are assumed
nonemty.)
So AC_kappa says we are allowed to make kappa many choices, this time unlike
the last article with no size restriction on the Ai sets from which we are choosing.
I think I can prove the following:
Suppose M is a countable model of ZFC + GCH + kappa is a cardinal.
Then there is a countable model M' end extending M with the same
cardinals and cofinalites as M, with M' satisfying
ZF + AC_kappa + ~ dual CB .
End extend means all the sets from M are still in M' and they have
exactly the same members as they did in M : same membership relations
with the old sets from M, and no positive membership relations on
new sets m' inside M' that were not previously in M.
So M' extends the universe of M, but all the old M information
is preseverved: the old M sets are exactly as before.
This would say any particular definable fragment like AC_aleph_1 etc
is not enough in ZF to prove dual CB.
The proof was inspired by Herman's proof.
I will describe the proof now. The full proof is to be a Cohen
permutation construction. these typically have a similar Fraenkel
Mostowski proof, which is easier to describe.
See
[1] David Libert "Cohen symmetric choiceless ZF models"
sci.logic July 6, 2000
http://groups.google.com/group/sci.logic/msg/b4271c2585d2f1e5
I will describe this new proof this same way, in simplified
Fraenkel Mostowski language and then the Cohen reworking.
In M, we form a tree of depth omega, branching at node of depth
n to the n successor cardinal of kappa.
So the nodes of the tree will be finite sequences
of ordinals, the ordinal at i'th location being < (i-1)th successor
of kappa ordering.
The permutation group acting on the tree with be automorphisms
respecting the tree ordering. So at every level simultaneously
you permute among siblings and induce that on the subtrees.
There is no requirement to have the corresponding "copy" of
a permutation on kappa+ at different nodes of the tree.
The support notion for the Freaenkel Mostowski model will
be support of cardinality <= kappa, ie that many total nodes
of the tree to be a support set.
Then we form sets A, B corresponding to Herman's. The even
and odd deoth nodes. Depth is respected by the permutation action
so these are in the Fraenkel Mostowski symmetric model.
These surject onto each other as in Herman's proof, by deleting
last coordinate.
On the other hand, they can't inject to each other, because
by making the cardinakity of the branching grow with depth
and injection can't always map to lower depth, so some places
beyond a kappa sized support set must map to higher depth
find such a pair associated by the injection both outside
the support set and permute the output.
That would be the Fraenkel Mostowski version.
For the Cohen version, generically blow up the power set of
the omega + 2 th successor of kappa with conditions of size
the omega + 1 th successor of kappa.
The various generic sets added this way will be the labels for
the branchings in our tree making the atoms.
The forcing had closure to the omega + 1 th successor of kappa,
beyond and of the closures arising in the Fraekel Mostowski
proof, so this lets the forcing stay in the background and mimic
Fraenkel Mostowski.
The support sets were all kappa size or more, and to cofinality
>= kappa, so the AC in M has AC_kappa inherit into the
ZF model.
GCH in M is used for a combination of closure and chain conditions
of the forcing to say cardinalities and cofinalities are preserved.
That last point along the lines if you took kappa = aleph_2 in M
you want kappa to still be M' 's aleph_2 so by the end
you can still claim to have the AC_aleph_2 as understood in M'.
--
David Libert ah...@FreeNet.Carleton.CA
David Hartley
<272738196.71125.12848...@gallium.mathforum.org>, Don
Coppersmith <dco...@idaccr.org> writes
>> A form of countable choice is needed in general even
>> to make a countable
>> sequence of choices from finite sets, as you do
>> above. That can
>> certainly be avoided if you can define a linear
>> ordering for S intersect
>> A *for all stages at once*, but not by saying that at
>> each stage S is
>> finite and so S intersect A can be ordered. What
>> "deterministic
>> ordering" do you have in mind?
>> --
>> David Hartley
>
>At stage n, K is an ordered n-tuple of distinct elements from U. S is
>the collection of ordered m-tuples of distinct elements from K with m
>ranging from 1 to n. Define an ordering on S where 1-tuples precede
>2-tuples, which precede 3-tuples etc, and among m-tuples of the same
>size, impose a lexicographical ordering imposed by the original ordered
>n-tuple K. So if K=(a,b,c), we order its elements as a<b<c, and the
>ordering on S is:
>(a),(b),(c),(ab),(ac),(ba),(bc),(ca),(cb),(abc),(acb),(bac),(bca),(cab),
>those of opposite parity. So (if |K| is even) {f(t): t in S intersect
>A} can't lie in (S intersect B). Use the above ordering to pick the
>earliest t in (S intersect A) such that f(t) lies outside (S intersect
>B). f(t) is some m-tuple which includes elements not in K. Pick the
>first element u of f(t) which is not in K, and append u to K, so that K
>is now (a,b,c,u).
>
>My use of the word "pick" in the original description was unfortunate.
>It's all determinstic, after the initial choice of K of length at least
>3.
>
>(If |K| is 1 or 2, this doesn't work; we could have f((a))=(ab),
>f((b))=(ba), and we would never discover new elements.)
Thanks, very neat.
--
David Hartley
David Libert
Arturo Magidin (mag...@member.ams.org) writes:
> Many years ago (2003) there was a discussion on the "Dual Cantor-
> Bernstein" problem: if we have surjections A-->B and B-->A, does there
> exist a bijection between A and B? If we assume AC, this follows from
> the usual Cantor-Bernstein, but in the absence of Choice it would
> appear that it fails.
>
> Herman Rubin made a post in which he sketched how the existence of an
> amorphous set (a set that cannot be expressed as a disjoint union of
> two infinite sets) would imply that the dual Cantor-Bernstein does not
> hold:
>
> http://groups.google.com/group/sci.math/msg/28543d2b17d8f4ab
>
> In a recent post in MathOverflow,
>
> http://mathoverflow.net/questions/38771/dual-schroeder-bernstein-theorem
>
> someone asked about this, and I pointed him to that thread. I thought
> I could turn Prof Rubin's argument into a proof that if we assume ZF
> +Dual of Cantor-Bernstein, then it would follow that every infinite
> set has a denumerable subset, which would give at least countable
> choice. The argument is:
Recently, Sept. 21, on the mathoverflow page Andres Caicedo
added a note about a related result: Assume dual CB, and suppose
X is equipollent with XxX. Then if there is a surjection from
X onto a set Y, then there is an injection from Y into X.
This implies if dual and CB and all infinite X are ~ XxX,
then all surjections X ->> Y from infinite X have
injections Y >-> X.
But the premise all infinite X have X ~ XxX is already strong.
It implies AC over ZF. An old thoerem of Tarski. For this see
[1] Mike Oliver Feb 11 '99 "Re: Addition on Infinities"
sci.math
http://groups.google.com/group/sci.math/msg/6e5db95434e2a1c3
But Andres result still gives information beyond Tarski's, over
ZF on a case by case basis for some X.
For completeness I will write here a proof of the result Andres
noted above.
So suppose dual CB, suppose X ~ XxX, and suppose X surjects
onto Y by f: X ->> Y. We seek an injection of Y into X.
We can surject XxX onto YxX: by g1:
g1(<x1, x2>) = <f(x1), x2>.
We can surject YxX onto X by g2: g2(<y,x>) = x.
We assumed X ~ XxX, hence X surjects onto XxX.
Compose g2 : YxX -> X with this surjection : X -> XxX,
obtaining
g3 surjecting YxX ->> XxX.
So g1 surjects XxX onto YxX, and g3 surjects YxX onto XxX.
So by dual CB, there is a bijection from YxX to XxX.
In particular, there is an injection g4 : YxX >-> XxX.
But Y injects to YxX by picking a fixed x0 member of X
and sending y |-> <y, x0>.
Also XxX injects to X by the assumed X ~ XxX.
Composing these 3 last mentioned injections Y >-> YxX >-> XxX >-> X
we get the desired injection Y >-> X .
--
David Libert ah...@FreeNet.Carleton.CA