"Bi-surjectiveness"
Rolf Bardeli
Let f : A -> B a surjective mapping, g : B -> A also surjective.
In which of the following cases can we construct an isomorphism of A and
B from f and g?
1.) A, B are finite
2.) A, B are denumerable
3.) A, B are not denumerable
If we can construct an isomorphism, how?
If not: Can we give an example (sets A, B and surjective maps f, g as
above) so that A is not isomorphic to B?
Grateful for any comments,
Rolf Bardeli
Zhiqiang Zhang
First,wo have a therom,which is found by Banach:when f:X->Y,g:Y->X is
two mapping,then there is a decomposition
X=A|_|A',Y=B|_|B'
and f(A)=B,g(B')=A'.A and A' have no common element,neither have B and B'.
In fact,denote T={E is a subset of X|E and g(Y\f(E)) have no common
element}
Then denote A the union of all set in T,then T is the BIGGEST set in T.
Denote B=f(A),B'=Y\B,A'=g(B').A' and A have no common element because A
belong T.We want to prove that X is the union of A and A'.Otherwise,there
exist a element in X,which does not belong A and A',Then A''=A|_|{x} is a
element in T,contradict that A is the BIGGEST element in T.
In the posted problem,we first define f^:B->A:for all b in B,f^(x) is a
element in {a|f(a)=b}.Based on the surjection of f and axiom of choice,this
definition can be done.
Also we can define g^:A->B,for all a in A,g^(a) is a element in
{b|g(b)=a}.
Then wo can use the above therom,there exist X is a subset of
A,Y=g^(X),f^(B\Y)=A\X.
And then we can define an isomorphism h of A and B from f^ and g^:
h(a)=g^(a) when a in X,otherwise h(a)=f^(-1)(a),f^(-1) denote
the inverse of f^.
"Rolf Bardeli" <bar...@cs.uni-bonn.de> wrote in message
news:b4s9aa$1050$1...@f1node01.rhrz.uni-bonn.de...
Rolf Bardeli
> I have learned a method in real analysis.
> First,wo have a therom,which is found by Banach:when f:X->Y,g:Y->X is
> two mapping,then there is a decomposition
> X=A|_|A',Y=B|_|B'
> and f(A)=B,g(B')=A'.A and A' have no common element,neither have B and B'.
>
> In fact,denote T={E is a subset of X|E and g(Y\f(E)) have no common
> element}
>
> Then denote A the union of all set in T,then T is the BIGGEST set in T.
> Denote B=f(A),B'=Y\B,A'=g(B').A' and A have no common element because A
> belong T.We want to prove that X is the union of A and A'.Otherwise,there
> exist a element in X,which does not belong A and A',Then A''=A|_|{x} is a
> element in T,contradict that A is the BIGGEST element in T.
>
>
> In the posted problem,we first define f^:B->A:for all b in B,f^(x) is a
> element in {a|f(a)=b}.Based on the surjection of f and axiom of choice,this
> definition can be done.
> Also we can define g^:A->B,for all a in A,g^(a) is a element in
> {b|g(b)=a}.
> Then wo can use the above therom,there exist X is a subset of
> A,Y=g^(X),f^(B\Y)=A\X.
> And then we can define an isomorphism h of A and B from f^ and g^:
> h(a)=g^(a) when a in X,otherwise h(a)=f^(-1)(a),f^(-1) denote
> the inverse of f^.
>
But quite counter intuitively:
So you can surjectively map [0, 1] to [0, 1]x[0, 1] using the Hilbert
Curve and you can surjectively map [0, 1]x[0, 1] to [0, 1] using
projection and thus can construct an isomorphism between [0, 1] and
[0, 1]x[0, 1] ?
David C. Ullrich
<bar...@cs.uni-bonn.de> wrote:
>Let A, B be sets.
>Let f : A -> B a surjective mapping, g : B -> A also surjective.
>
>In which of the following cases can we construct an isomorphism of A and
>B from f and g?
Assuming that "isomorphism" just means "bijection", it
follows from the Schroder-Berstein theorem that there is
an isomorphism in any case.
>1.) A, B are finite
>2.) A, B are denumerable
>3.) A, B are not denumerable
>
>If we can construct an isomorphism, how?
>If not: Can we give an example (sets A, B and surjective maps f, g as
>above) so that A is not isomorphic to B?
>
>Grateful for any comments,
>
>Rolf Bardeli
******************
David C. Ullrich
Michael Barr
The answer to 3 is yes, provided you assume the axiom of choice. AC
implies (is equivalent to) that every surjection splits (has a right
inverse). The right inverse is an injection and so you have
injections from A to B and vice versa and then ordinary
Schroeder-Bernstein takes over. The answer to 1 is yes in any case
since any surjection to a finite set splits and no AC is needed. As
for 2, it seems to me that countable AC is enough to get the
splittings and that Schroeder-Bernstein in that case also requires
only countable choice.
David Libert
As others have pointed out, using AC if it is available, given
f : A ->> B surjective, pick members from the respective pre-images
of B elements, obtaining an injection from : B >-> A.
So with AC, the premise of bi-surjectiviy gets bi-injectivity, and
from bi-injectivity we can define a bijection : A >->> B by the
proof of the Shroeder Berstein theorem. (This C-B is a ZF proof, no
AC needed, and it explicitly defines the bijection using parameters
for the two injections each way.)
Of course, we used AC to get from the two surjections to two
injections, so we don't have a definition of the final bijection from
the original surjections.
Working in ZF only, it is possible for the surjective version to
fail. Ie, over ZF alone we have bi-injective -> isomorphic, but ZF
does not prove bi-surjective -> isomorphic.
Here is one example of this.
Turing reducibility is the relation on functions : omega -> 2 of
being "computable from": ie for f,g : omega -> 2, f is Turing
redicible to g (f <=_T g) iff there is a Turing machine which
given a side read only tape with f's 0 's and 1's written on it, can
compute the charactertic function of g.
(This depends on defining Turing machines with side tapes. Or there
are other ways.)
Turing equivalence is two directions of Turing reducible. It is an
equivalence relation.
Turing degrees are the equivalence classes of Turing equivalence.
So the set of Turing degrees is a quotient of the reals, taking the
reals to mean the set of all functions from omega -> 2. (Don't worry
about, its just logician's terminology.)
There were a couple of articles which gave some results about
relations of reals to Turing degrees:
[1] Mike Oliver sci.logic June 28, 2000
"Re: cardinality of the power set of the integers"
http://groups.google.com/groups?selm=395A6ADF.8A8BC804%40math.ucla.edu
[2] David Libert sci.logic July 3, 2000
"Re: cardinality of the power set of the integers"
http://groups.google.com/groups?selm=8jq5i2%249sb%241%40freenet9.carleton.ca
Let R be the reals, and T be the Turing degrees.
[2] proved in ZF : there is an injection : R >-> T .
[1]-[2] proved
in ZF + every set of reals has the Baire Property :
there is no injection : T >-> R .
From ZF, and the injection : R >-> T,
we get a surjection : T ->> R
(use the inverse on the range of the injection, and some fixed real
number off the range of the surjection).
In ZF, we get a surjection : R ->> T
(send each real to its Turing degree) .
So in ZF, R and T are bi-surjective.
But in any ZF + every set of reals has the Baire Property, there is
no injection : T >-> R, from [1]-[2].
So ZF + every set of reals has the Baire Property has R,T as a
counterexample to bi-surjective -> isomporphic.
Every set of reals has Baire Proeprty is a consequence of ZF + AD,
so ZF + AD has a counterexample to bi-surjective -> isomorphic.
Also, Shelah has a construction of a model of ZF + every set of
reals has Baire Property only assuming Con(ZF), so counterexamples
have consistency strength no higher than ZF.
If the above is correct, and there are really counter models, then I
am sure there must be simpler direct Fraenkel Mostowski counter
models. I haven't yet seen how to do these though.
Returning to the original questions, in the finite case you have
from ZF choice functions for finite sets (by induction on the size
of the sets), so the finite case bi-surjective gets bi-injective and
hence isomorphic.
My example above is uncountable.
Regarding countable. I don't presently know. I would be astonished
if the countable case bi-surjective -> isomorphic could be proved in
ZF. Maybe if we could make a more direct Fraenkel Mostowski model it
could be arranged to make countable counterexamples.
--
David Libert ah...@FreeNet.Carleton.CA
Fred Galvin
> Regarding countable. I don't presently know. I would be
> astonished if the countable case bi-surjective -> isomorphic could
> be proved in ZF. Maybe if we could make a more direct Fraenkel
> Mostowski model it could be arranged to make countable
> counterexamples.
Would you please repeat the question? Something about nonisomorphic
countable sets? What kind of isomorphism are you talking about?
--
It takes steel balls to play pinball.
David Libert
Good point. Yes, it is a triviality if we specify countable. Also
the finite case, one direction of surjection imposes an inequality of
finite cardinals, so bi-surjective forces = finite cardinality,
another existence proof of a bijective.
So the finite and countable cases are trivial, and the uncountable
case can have counterexamples in ~AC models.
Also, let me correct from my article, quoting from 2 back:
> Turing reducibility is the relation on functions : omega -> 2 of
>being "computable from": ie for f,g : omega -> 2, f is Turing
>redicible to g (f <=_T g) iff there is a Turing machine which
>given a side read only tape with f's 0 's and 1's written on it, can
>compute the charactertic function of g.
The definition mixed up f and g. f <=_T g if f can be computed
FROM g, so the Turing machine has side tape with * g * and it
computes * f * , opposite of what I wrote above.
--
David Libert ah...@FreeNet.Carleton.CA
Dave Seaman
> Let A, B be sets.
> Let f : A -> B a surjective mapping, g : B -> A also surjective.
> In which of the following cases can we construct an isomorphism of A and
> B from f and g?
> 1.) A, B are finite
> 2.) A, B are denumerable
> 3.) A, B are not denumerable
If a surjective mapping f: A -> B implies the existence of an injective
mapping f_I: B -> A, then we can apply the Cantor-Schroeder-Bernstein
theorem to conclude that a bijection exists.
In cases 1 and 2 we can conclude immediately that the injective mappings
exist. In case 3, we need the axiom of choice.
> If we can construct an isomorphism, how?
> If not: Can we give an example (sets A, B and surjective maps f, g as
> above) so that A is not isomorphic to B?
I don't have a counterexample at hand for case 3, but I can give a
partial example. Let A be a denumerable collection of unordered pairs,
and let B = N. Then there is a surjective map f: A -> B which maps (n,x)
|-> n. However, an injective map from B to A would amount to a choice
function on the collection of pairs (or at least on a denumerable subset
of the collection of pairs, not necessarily including all of them.) There
would have to be infinitely many pairs with one or both members in the
range of the mapping. If both members of a pair are in the range, then
we have distinguished one member of the pair by assigning it a lower
index than the other.
This does not convert directly into a counterexample for case 3, since
there is no surjection from B to A without the axiom of choice. However,
I believe counterexamples to case 3 do exist.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
Herman Rubin
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.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Deptartment of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
David Libert
> In article <b4vi06$qlj$1...@mozo.cc.purdue.edu>,
> Dave Seaman <dse...@no.such.host> wrote:
> >On Fri, 14 Mar 2003 11:01:41 +0100, Rolf Bardeli wrote:
> >> Let A, B be sets.
> >> Let f : A -> B a surjective mapping, g : B -> A also surjective.
>
> >> In which of the following cases can we construct an isomorphism of A and
> >> B from f and g?
>
> >> 1.) A, B are finite
> >> 2.) A, B are denumerable
> >> 3.) A, B are not denumerable
[...]
> >This does not convert directly into a counterexample for case 3, since
> >there is no surjection from B to A without the axiom of choice. However,
> >I believe counterexamples to case 3 do exist.
>
> 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.
For U_1 an amorphous set produced in a Fraenkel Mostowski (FM) model
in the simplest way, full permutation group on atoms, finite support,
there are no injections in either direction between A and B as above,
so this does give a simple FM counterexample to case 3.
In fact, this last observation can be generalized more abstractly.
Martin Goldstern gave a definition in
[1] Martin Goldstern Feb 3, '03 "strongly amorphous"
http://mathforum.org/discuss/sci.math/a/t/479678
> I think the right notion for "abstractly" showing that ZF does
> not imply "on every set there is a group structure" is not
> the notion of "amorphous", but "strongly amorphous" (perhaps
> also called "superamorphous"?).
>
> An infinite set X is called strongly amorphous if
> 1) every subset of X is finite or cofinite
> 2) every finitary relation (i.e., every R subset X^n)
> is first order definable in the language of equality with
> parameters from X.
> (e.g., { (x,y,z): x=y or z=a=/=x }, for some fixed a in X )
>
> (Note that (1) is a special case of (2), namely n=1)
As Marin noted in [1], the most straightforward Cohen symmetric and
FM model constructions of amorphous sets actually contruct strongly
amorphous sets, ie for example full permutation group on unstructured
atoms with finite support.
And it can argued in ZF that for U_1 strongly amorphous, there are
no injections either way between A and B. This recapturing the
result from the construction from a simply stated property.
But returning to just amorphous:
> 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.
I think for just amorphous, the direction above, B to A, ie odds
to evens, can have an injection in some examples.
Namely, we form the FM model with atoms a_i,j , for i in omega
and j in 2 (ie j = 0 or 1). So each atom a_i,j has an associate
a_i,1-j.
The group will be arbitrary permutations of atoms respecting this
associate relation: ie permutations s.t. for every i in omega there
exists i' in omega and j in 2 so that a_i,0 and a_i,1 are
respectively sent to a_i',j and a_i',1-j.
We form N the finite support FM model for this group action. Let U_1
be the set of atoms in N.
The partitioning of U_1 into the 2 elements sets
{ {a_i,0 , a_i,1 } | i in omega } is a member of N.
Given F any finite set of atoms, first close it off to F' by adding
any associates of F elements, so F' is the smallest superset of F
which is a union of sets of pairs of associates. Then any atom
outside of such an F' can be permuted by some group element to any
atom also outside of the same F'. This shows U_1 is amorphous in N.
Recall:
> 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.
Make that last B. So B is odds, A is evens.
I define an injection from B into A. Namely, given a B element,
t, that is an odd length tuple of distinct U_1 elements, we have the
set of members of t could not be a union of associate pair sets,
otherwise that set would be a union of dosjoint 2 element sets, hence
even, contradicting t is an odd length tuple of distinct elements.
So t contains at least one coordinate that does not have its
associate listed by t. Pick the leftmost such coordinate in t .
Take its associate. We have just defined, (using the associate
relation which is in N), how to pick U_1 element not enumerated by t.
So append this element to the end of t, still distinct elements, and
now an even length tuple. The original tuple can be recovered by
looking at the first coordinates, so this is 1-1.
In N we have just defined an injection : B >-> A. N models ZF, so
from this definition the corresponding set exists in N.
So only knowing U_1 amorphous, we can't conclude on that basis B
won't inject into A.
However, given any U_1 amorphous, we can still use the construction
above to get A,B as a counterexample to the orginal case 3. Namely
I claim as a new argument over ZF that if U_1 is any amorphous set,
and A and B are defined above (even or repsectively odd length
tuples of distinct elements from U_1) then at least one direction of
injection between A and B must be impossible.
I argue that now. So suppose for contradiction over ZF that U_1
is amorphous, and A and B as defined above have two directions of
injection.
So by Shroeder Berstein, A and B are isomorphic.
I will use that isomorphism to define a function which extends any
non-empty finite subset of U_1 to a proper finite superset of
iteself. Ie, I will define a function f , so that for F a finite
non-empty subset of U_1, f(F) will be a finite subset of U_1
which is a proper superset of F.
So given F, a finite non-empty subset of U_1, we seek to define how
to extend it fintely. If F is even cardinality, consider the set of
all even positive length tuples of distinct elements of F. Given any
such tuple, we can delete its last element, obtaining an odd length
tuple of distinct F elements. Since F is even cardinality, any odd
length tuple of distinct elements enumerates a proper subset of F, and
so can be hit by an even length tuple of distinct elements with its
last element deleted.
So we have surjected the set of positive even length tuples of
distinct F elements onto the set of odd length tuples of distinct F
elements.
Also, if #F > 2, then odd length tuples of distinct F members of
length < #F - 2 are hit by at least two tuples when last elements are
deleted. Ie, there were two or more choices for the last element of
the even length tuple that was deleted to produce the target odd
length tuple.
So the positive even length tuples of distinct F members if a
finite set surjecting onto the odd length tuples of distinct elements,
where some odd tuples have > 1 size preimages.
We conclude there are strictly more positive even length tuples of
distinct F elements than odd length tuples of distinct F elements.
Above was assuming #F > 2. If #F = 2, there are 2 odd length
tuples and 4 positive even length tuples of distinct F elements, and
fortunately, 4 > 2, so the strict inequality holds here too.
So in all cases of #F even, consider the bijection from positive
even length tuples of distinct U_1 elements (ie A) going to the odd
tuples B. consider that : A -> B direction acting on the positive
even length tuples of distinct F elements. That injects into odd
length tuples, and we just saw there aren't enough odd length such
tuples of F elements. We conclude when we apply that : A -> B
injection to all the A elements with F coordinates, we must get some
tuples which contain at least some coordinates from outside F. Else
pigeon hole problems.
So in this case, define the new elements outside of F to be all U_1
elements appearing as coordinates anywhere in any tuple put out by
: A -> B applied to that set.
So f(F) will be defined to be F union those finitely many extra
elements.
Now to define f(F) if #F is odd. This is similar to the last,
with changes. I must prove that there are strictly more odd length
tuples of distinct F elements than positive even length tuples of
distinct F elements.
First some special cases. #F = 1. So there is one odd length
tuple, and no prositive length even tuples of distinct F elements.
1 > 0, so we are ok.
Next, #F = 3. There are 3 length 1 tuples, and 3*2 = 6 3-tuples
of distinct F elements. So there are 3 + 6 = 9 odd length tuples of
distinct F elements.
There are 3*2 = 6 2-tuples, so this is all the positive even
length tuples. 9 > 6, so ok.
Finally, suppose #F > 3 and #F odd. We consider all the odd
length tuples of length >1, of distinct F elements. For these, we
can delete the last coordinate, and obtain a positive even length
tuple. So we surject from this set to the positive even length tuples
over F.
I want to estimate how many more odd length >1 tuples of distinct F
elements there are than positive even lenght tuples. So consider all
the #F - 3 length tuples of dintinct F elements. (#F - 3 is
positive since we are presently in case #F > 3).
Each of these are hit by the deletion of last cordinate by exactly 3
elements, ie the 3 remaining choices of what extra element got
deleted.
So each #F - 3 length tuple is hit 3 times, so we know the odd > 1
length tuples exceed the posiotive even length tuples by at least 2 *
the number of #F - 3 length tuples.
This is an overcount by 2 * #F!/3! .
Now consider the 1-tuples of F. There are #F of these. These could
not be accounted for by the surjection of deleting last element,
because deleting the last coordinate from a 1-tuple does not leave an
even length tuple, which are the one we wanted to compare.
So using the deletion surjection to compare odd length tuples to
even length tuples, we overlooked #F many cases. But among the cases
we had, we overcounted by 2 * #F!/3!, which is strictly greater than
#F (since #F > 3).
So considering all odd length tuples of distinct F elements, we
still get strictly more than the positive even length tuples of
distinct F elements.
This was the desired claim.
So now consider the other direction of the bijection, ie consider
: B -> A carrying odd length tuples to evens.
Apply that to the tuples of F elements. We get positive even length
tuples back. There are fewer such tuples of F distinct F elements
than we started with, so as before by prigeon-hole some of the tuples
we got included coorinates outside of F. As before define f(F) to be
F union all such extra coordinates among all such bijection outputs
(opposite direction of bijection from last case) to that starting odd
length tuples from F.
So once more, we have defined f(F) to be a proper finite superset
of F, and a subset of U_1.
So f has shown how to properly finitely extend all finite sets
inside U_1.
Now pick some element u in U_1. Define a sequence F_0 = {u},
and F_i+1 = f(F_i) for i in omega.
We have defined a strictly growing tower of finite subsets of U_1.
Disjointify it, considering F_i+1 - F_i, and we get an omega
sequence of pairwise disjoint sets. Union the even ones of these,
getting an infinite set with infinite compliment, contra U_1
amorphous.
This contradiction from the bijection A <-> B used to define f.
So U_1 any amorphous set can make A,B as above giving an
example of bi-surjective non-isomorphic sets. We just don't
necessarily get this by the : B -> A direction failing, as the
previous example above shows.
So in general, considering U_1 amorphous, and regarding
injectibility in the two directions between A and B. The last result
says at least one direction of this must fail.
Strongly amorphous gives examples where both directions fail.
My amorphous example with injection : B >-> A above had that
direction work, so by the last result in that example : A >-> B must
fail. So that is an example where injections are possible exactly
from odds.
Is there an example with injectibility from evens but none from
odds? I don't know.
Also, earlier I wrote that it can argued strongly amorphous implies
eno injection either way. To see that, use one direction of the
definition of f above. Ie if we have an injection from odd tuples
to evens, we can do the part of the f definition above showing how to
extend odd f's, that part of the definition depended on exactly that
direction of injection. Similarly, injections from even tuples gives
a function extending even sets.
To make the tower I needed the extension method to handle all cases.
But if I have an extension method on exactly odd sets, by
considering odd sets containing the all parameters from the definition
of the method, I can still contradict strongly amorphous, ie the
extension method is defining relations contra strongly amorphous.
Similarly extending evens.
--
David Libert ah...@FreeNet.Carleton.CA
David Libert
Correcting some points from my last article, posted just a short
time ago.
In parent article
[1] David Libert Mar 16 '03 "Bi-surjectiveness"
http://mathforum.org/discuss/sci.math/m/490333/491228
ah...@freenet.carleton.ca (David Libert) writes:
[...]
> We conclude there are strictly more positive even length tuples of
> distinct F elements than odd length tuples of distinct F elements.
>
> Above was assuming #F > 2. If #F = 2, there are 2 odd length
> tuples and 4 positive even length tuples of distinct F elements, and
> fortunately, 4 > 2, so the strict inequality holds here too.
I wrote tuples of distinct F elements, which was correct, but I was
thinking all tuples, including repetitions. That's how I got 4.
Instead, tuples of distinct elements, I should have gotten 2.
Replacing 4 by 2 in "4 > 2" : Houston, we have a problem.
This was concerning the method f(F) of extending the finite set F,
how to find more U_1 members outside of F.
My method was, for #F even, to take all positive even length tuples
from F, apply the injection to those, obtaining odd tuples, and look
for new members among the coordinates of resutling odd tuples.
This method can break down for #F = 2, at the problem above. Namely
maybe the injection just deleted last member when applying to tuples
over F, so the method above just gets back F members.
So instead reorganize the larger proof to avoid this bad case.
There are a couple of ways to present this, which on closer
examination would be seen to be very similar. If we still want to
define f extending all sets F, make the definition of F depend on 3
fixed but arbitrary parameters for U_1 elements u0, u1 and u2. Then
to define f(F) apply the procedure above of applying the injection
to all inner tuples to F union {u0, u1, u2} instead of to F as
before. Then we are working with a set of size > 2, possibly even
now in the other case (odd) but get a superset of that as before,
which is still a superset of F.
Or else, use the old proof for f, and only claim it for sets of size
> 2, and then later build the tower starting with {u0, u1, u2}
instead from {u}.
I also used parts of that argument about injecting on tuples in
showing strongerly amorphous has no injections between A and B either
direction. That has similar adjustments as above, sometimes taking
more care to avoid moving between cases even/odd.
Again this can be phrased as changing the proof to show the original
claim about f, or changing the f claim and changing its applications.
[...]
Regarding the argument to define f(F), for F odd. I made it more
complicated than it needs to be.
I want to compare odd tuples to even tuples, showing there are more
odd ones. The method will be to use the surjection defined by
deleting last coordinate, to surject odds to evens.
I had the problem that this deletion takes 1-tuples out of the other
comparison set of positive even length tuples. So instead I just did
the surjection on odd tuples of length > 1.
I later argued that the inequality produced by the surjection
argument had a discrepancy larger than the overlooked cases.
But leaving off those cases was not a harm to my ultimate goal, that
had to be compensated by cancelling against other error terms, it was
a help. If I can use a subset of the odd tuples to surject onto even,
then that subset of odd tuples is already >= all the evens, so adding
in the skipped cases to the bigger side only makes it even bigger,
which is what I wanted anyway.
So actually, with the skipped cases helping instead of hurting, I
can simplify the surjection argument even more. I no longer need to
keep track that some elements have preimage > 1. I can just get a >=
from the surjection (instead of a > ) and rely on the 1-tuples to tip
the => back to a > .
The previous argument had #F = 1 and #F = 3 as special cases.
This was because I needed #F > 3 to get preimages > 1. But now I can
drop that, just have #F = 1 as the only special case.
So in other words, to show for F finite with #F odd, that there are
strictly more odd tuples of distinct F elements than even ones:
Special case #F = 1:
> First some special cases. #F = 1. So there is one odd length
> tuple, and no prositive length even tuples of distinct F elements.
> 1 > 0, so we are ok.
All other cases: surject the odd tuples of length > 1 onto all the
even tuples, by deleting last element. So without the 1-tuples, the
odd tuples are >= even tuples, and adding the 1-tuples back to the
count after the surjection, we get > .
--
David Libert ah...@FreeNet.Carleton.CA