Followup about injecting tuples of amorphous set
David Libert
[0] David Libert June 14 '03
"Amorphous set with injection distinct tuples evens to odds"
http://mathforum.org/discuss/sci.math/t/515533
which I have lost as a live article. Some corrections, and a
simplification of the main proof.
> This article is answering a left over question from the two previous articles
>
> [1] David Libert Mar 16 '03 "Re: "Bi-surjectiveness""
> http://mathforum.org/discuss/sci.math/m/490333/491228
>
> [2] David Libert Mar 17 '03 "Re: "Bi-surjectiveness""
> http://mathforum.org/discuss/sci.math/m/490333/491250
>
> In the base of that thread
>
> [3] Mar 14-17 '03 13 articles "Re: "Bi-surjectiveness""
> http://mathforum.org/discuss/sci.math/m/490333
That is a bad URL for [3].
Corrected [3] URL : http://mathforum.org/discuss/sci.math/t/490333
> the original poster Rolf Bardeli asked whether two sets A and B
> having surjections must be isomorphic, and related questions. Various
> articles in [3] noted ZFC proves bi-surjective sets are isomorphic.
Ie: A and B having both directions of surjections between them.
> In the parent article of [1], Herman Rubin noted that for U_1
> amorphous the sets A the set of positive even length tuples of
> distinct U_1 elements and B the set of odd length tuples of distinct
> U_1 elements are bi-surjective but non-isomorphic.
>
> The two surjections are obtained by projection by deleting last
> coordinate.
Except deleting last coordinate from the singleton tuples in B would
send them to the empty tuple, which is not a member of A = *positive*
even length tuples of distinct U_1 members. So the surjection
: B ->> A should be defined to send singelton tuples to some fixed
A element, same for all singletons, and to delete last coordinate on
all non-singleton tuples in B. The last clause is enough to get all
of A in the range.
So such surjections are not purely definable, because they depend on
picking an A member. But they are definable from finitely many
parameters for U_1 members (the coordinates of the picked A member),
and this is enough to apply Separation in the FM model and get the
surjection is a member of the FM model.
> [1] followed up Herman's article, noting in more detail why A and B
> are non-isomorphic. [2] added a technical correction to [1].
>
> [1]-[2] proved that for such A,B, at least one direction of
> injectibility between them must fail. [1]-[2] also gave two Fraenkel
> Mostoski ZF models with alternate example of such A,B, (ie the
> respective A,B defined over alternate examples of U_1 's), one
> example where both directions of injectibility failed, and a second
> example where B could inject into A (ie odds to evens). Hence, by
> the previous result, in this second example A can't inject into B.
>
> [1] raised but did not answer the question of whether there could be
> another example with A injecting into B (ie evens into odds).
>
> The new result of this present article is a Fraenkel Mostowski ZF
> model with an amorphous U_1 with A injecting into B (ie evens to
> odds), answering affirmatively that question from [1].
>
> The construction method below, to do this, is similar to the
> construction of an amorphous set with a group structure from
>
> [4] David Libert Feb 3 '03 "Re: Group Structure on any set"
> http://mathforum.org/discuss/sci.math/a/m/478403/479486
>
> Let V be a vector space with countable basis over the field of
> scalars Z/2. I will make a Fraenkel Mostowski ZF model, with set of
> atoms corresponding to the members of V. The permutation group on the
> atoms will be the automorphism group of V as a Z/2 vector space, with
> the usual action of that group. The FM model will be finite support.
>
> We will be considering V+, the non-0 elements of V, as a set
> inside the FM model.
Since the proof below takes a tuple <v1, ... , vn> from the target
set and considers the subspace generated by {v1, ... , vn}, I
thought I better not play with fire and fall into some degenerate
case, so I worked with V+ to make all the vi 's non-zero to be sure I
really had a non-null subspace.
But no problem. The tuple in question of length n is picked with n
positive even, so even if the zero vector is included, it won't be the
only vector, so the generated space is non-null, and everything else
goes through, with one further adjustment.
Below, I wanted the superset I generated of {v1, ... vn} to be an
odd sized set. Since originally that set was the
subspace - {zero-vector}, I arranged the subspace to be even so this
set is odd.
In the revised version, with zero-vector possibily in {v1, ... vn},
I will just use the subspace itself instead of
subspace - {zero-vector}. So we need the subspace odd instead of
even. So change V from being a vector space over Z/2 to being over
Z/3. (Or indeed over any odd finite field, Z/p p odd prime, or
others).
Anyway, the proof will continue, using V instead of V+, with the
underlying field (for definateness in exposition now) Z/3, with those
other adjustments outlined below coming. So reading on in the quote,
let V+ now = V, and replace Z/2 by Z/3.
> Given any finite subset F of V+, we can consider the subspace of V
> this generates, also a finite set since Z/2 is finite. Given any pair
> of vectors outside of that subspace, we can find an automorphism of V
> fixing the subspace and sending one such vector to the other. This is
> enough to get V+ is amorphous in the FM model. (A similar argument was
> mentioned in [4]).
>
> The vector space structure of V is respected by the automorphism
> group, hence it has empty support in the FM construction, so it makes
> it into the FM model.
>
> I will use that vector space structure to define in the FM model an
> injection : A >-> B ie positive even length tuples of distincts into
> odd length tuples of distincts.
>
> So suppose <v1, v2, ... , vn> is a tuple of distinct V+ members,
> with n positive even. I seek to define the associated odd length
> tuple of distinct V+ members.
>
> Consider the subspace generated by {v1, ... vn}. We define a basis
> for this subspace from the <v1, ... , vn> tuple, using the tuple
> ordering between coordinates to do so. (Ie tuples in permuted order
> of each other can get different bases this way). Namely work through
> v1, v2 , ... vn in turn, throwing into the growing basis any element
> not in the span of the part of this basis previously added.
>
> We obtain a basis of m elements, for some m : 1 <= m <= n . Using
> that basis, we can associate each non-0 vector in the the subspace
> generated by {v1, ... vn} an m-tuple of Z/2 elements, ie the
> coordinates of the vector realtive to this basis.
Note that the coordinate tuple depends on having the basis elements
in some order, to correspond to the tuple order of the coordinates.
The previous paragraph actually defined more than a basis, it defined
an ordered basis, ie the ordering from the original tuple. This
ordering is being used to get the tuple of coordinates.
> We can linearly order the set of such m-tuples, lexicographically on
> a linear ordering on Z/2.
Ie, the lexicographic ordering depends on the tuple ordering of
coordinates, so traces back to the defined ordering on the basis.
> {v1, ... , vn} is a subset of that subspace, indeed of the non-0
> part of that subspace. The subspace has size 2^m (m basis vectors
> over Z/2), an even number. So removing the 0 vector, the non-0 part
> of the subspace is odd size. That odd sized set is a superset of the
> starting even sized set {v1, ... , vn}, so the inclusion is proper.
In revision, we make {v1, ... , vn} a subset of the entire
subspace, which is now size 3^m (m positive), hence odd, so again the
inclusion is proper.
The rest continues as before:
> So we can find the least element of the non-0 part of the subspace,
> according to the linear ordering we defined, which is not a member of
> {v1, ... , vn}, such must exist by the properness result.
>
> We have found a way to definably pick a member of V+ outside of
> {v1, ... , vn}, definable using only the vector space structure on V,
> which is available in the FM model.
>
> Letting vn+1 be the V+ member so selected, we map <v1, ... , vn>
> to <v1, ... , vn, vn+1>, ie append vn+1, so mapping the even
> length tuple <v1, ... vn> to an odd length tuple.
>
> The inverse of this map is just by deleting last coordinate, so this
> map is injective.
>
> So V+ is the desired amorphous U_1 with A >-> B.
It is simpler to not muck around with the zero-vector as a special case.
--
David Libert ah...@FreeNet.Carleton.CA