conjecture - every non-singleton has a dearrangement
MoeBlee
d is a dearrangment of S <-> (d is a permutaion of S & Ax(x in S -> d
(x) not= x))
I'm wondering whether in ZC set theory without the axiom of regularity
(i.e., just extensionality, separation, pairing, union, power set,
infinity, and choice) it is a theorem (and thus how to prove) that for
all S, if S is not a singleton, then there is a dearrangement of S.
It's easy to prove that if S is countable and not a singleton, then S
has a dearrangement, but my various attempts to prove the general case
have not been successful (or maybe it doesn't hold in the general
case?).
MoeBlee
William Elliot
> Definition:
>
> d is a dearrangment of S <-> (d is a permutaion of S & Ax(x in S -> d
> (x) not= x))
>
> I'm wondering whether in ZC set theory without the axiom of regularity
> (i.e., just extensionality, separation, pairing, union, power set,
> infinity, and choice) it is a theorem (and thus how to prove) that for
> all S, if S is not a singleton, then there is a dearrangement of S.
>
There's even a rearrangement of the empty set.
> It's easy to prove that if S is countable and not a singleton, then S
> has a dearrangement, but my various attempts to prove the general case
> have not been successful (or maybe it doesn't hold in the general
> case?).
>
If S = { s_r | r in R }, then
p(s_r) = s_(r+1) is a rearrangement of S.
If S is infinite or if S is finite and even (including 0),
then there's two disjoint equinumerous sets A,B with S = A \/ B.
Let f be a bijection from A to B. Then
p(s) = f(s) if s in A
= f^-1(s) if s in B
is a rearrangement of S.
If S is non-singleton and odd
then some distinct a,b,c in S, even E with
S = { a,b,c } \/ E. A rearrangement of S is
a -> b; b -> c; c -> a and a rearrangement of E.
Herbert Newman
> If S is infinite [...] then there [are] two disjoint
> equinumerous sets A, B with S = A u B.
Proof?
Herb
MoeBlee
Cardinal arithmetic: card(S) = card(S)+card(S).
But every set S is 1-1 with some set S* disjoint from S.
So take card(S) = card(S_1)+card(S_2), with {S, S_1, S_2} pairwise
disjoint.
So S is 1-1 with S_1 u S_2.
So let f be a bijection from S1 u S2 onto S.
So S = (f "S_1) u range(f "S1).
MoeBlee
MoeBlee
This is the only part I need:
> If S is infinite or if S is finite and even (including 0),
> then there's two disjoint equinumerous sets A,B with S = A \/ B.
Okay.
> Let f be a bijection from A to B.
Okay.
> Then
>
> p(s) = f(s) if s in A
> = f^-1(s) if s in B
> is a rearrangement of S.
(I'm using 'dearrangement' since 'rearrangement' appears elsewhere
with a different meaning.)
I don't see how you conclude that p is a dearrangement.
MoeBlee
MoeBlee
> On Jul 6, 10:35 pm, William Elliot <ma...@rdrop.remove.com> wrote:
>
> This is the only part I need:
>
> > If S is infinite or if S is finite and even (including 0),
P.S., I meant I only need to consider S infinite (moreover we can
narrow to S uncountable), since I've already done countable (countably
infinite and finite).
MoeBlee
MoeBlee
> I don't see how you conclude that p is a dearrangement.
No, wait, nevermind, I do see it. Since A and B are disjoint, f(s) ~=
s, and f^-1(s) ~= s.
Very simple, nice. Thanks.
MoeBlee
Herbert Newman
>>> If S is infinite [...] then there [are] two disjoint
>>> equinumerous sets A, B with S = A u B.
>>
>> Proof?
>>
> Cardinal arithmetic: card(S) = card(S) + card(S).
Accepted.
> But every set S is 1-1 with some set S* disjoint from S.
Could you show that in detail? (Proof?)
If we had the axiom of regularity this would be easy:
Let S* = {<S, s> : s e S}.
Clearly there cant be an element <S, s> (with s e S) in S, since this would
violate regularity.
How can we show this without regularity?
Now...
Let's assume this CAN be shown in ZFC-Regularity. Then from S we would get
S* with S ~ S* and S n S* = {}, and from S* we would get S** with S* ~ S**
and S* n S** = {}.
Then
card(S) = card(S*) + card(S**).
with S* n S** = {}, and S* ~ S**.
> So S is 1-1 with S* u S**.
Ok.
> So let f be a bijection from S* u S** onto S.
> So S = f[S*] u f[S**].
And of course f[S*] n f[S**] = {}, and f[S*] ~ f[S**].
Then we would have shown (taking A = S* and B = S**):
If S is infinite then there are two disjoint
equinumerous sets A, B with S = A u B.
Ok.
The rest is easy. Since A ~ B, there's a bijection f from A onto B. (Then
f^-1 is a bijection from B onto A.)
Now define f': S --> S with
f' = f u f^-1.
f' is the dearrangment you were looking for. (Easy!)
Herb
P.S. Actually I already had devised a proof along these lines, but didn't
know how to prove "Elliot's theorem". (There's still a small "gap" in my
book. See above.)
Herbert Newman
Ooops... 2 typos/thinkos corrected:
>> So let f be a bijection from S* u S** onto S.
>> So S = f[S*] u f[S**].
>>
> And of course f[S*] n f[S**] = {}, and f[S*] ~ f[S**].
>
> Then we would have shown (taking A = f[S*] and B = f[S**]):
> ~~~ ~~~
> If S is infinite then there are two disjoint
> equinumerous sets A, B with S = A u B.
>
Herb
Herbert Newman
>> ... every set S is 1-1 with some set S* disjoint from S.
>>
> Could you show that in detail? (Proof?)
>
> If we had the axiom of regularity this would be easy:
>
> Let S* = {<S, s> : s e S}.
>
> Clearly there cant be an element <S, s> (with s e S) in S, since this would
> violate regularity.
>
> How can we show this without regularity?
Ah, an idea: we can SKIP this step and go directly for S* and S**:
Let's define
S* = {<0, s> : s e S}
and
S** = {<1, s> : s e S}.
Then S ~ S* and S ~ S**, and hence S* ~ S**; and S* n S** = {}. (Right?)
> Then
> card(S) = card(S*) + card(S**).
>
> with S* n S** = {}, and S* ~ S**.
>
>> So S is 1-1 with S* u S**.
>
> Ok.
>
>> So let f be a bijection from S* u S** onto S.
>> So S = f[S*] u f[S**].
>
> And of course f[S*] n f[S**] = {}, and f[S*] ~ f[S**].
>
> Then we would have shown (taking A = f[S*] and B = f[S**]):
>
> If S is infinite then there are two disjoint
> equinumerous sets A, B with S = A u B.
>
> Ok.
>
> The rest is easy. Since A ~ B, there's a bijection f from A onto B. (Then
> f^-1 is a bijection from B onto A.)
>
> Now define f': S --> S with
>
> f' = f u f^-1.
>
> f' is the dearrangment you were looking for. (Easy!)
>
> Actually I already had devised a proof along these lines, but didn't
> know how to prove "Elliot's theorem".
Thanx for that great question.
Herb
MoeBlee
> On Tue, 7 Jul 2009 11:28:25 -0700 (PDT) MoeBlee wrote:
> > But every set S is 1-1 with some set S* disjoint from S.
> How can we show this without regularity?
['x' stands for Cartesian.]
Let z not in range(S). Then Sx{z} is disjoint from S. (Proof idea by
Ullrich.)
I suspect your approaches don't work without invoking regularity.
MoeBlee
William Elliot
there's some bijection
f:S -> Sx{0} \/ Sx{1}
Take A = f^-1(Sx{0}), B = f^-1(Sx{1})
Herbert Newman
>>>
>>> But every set S is 1-1 with some set S* disjoint from S.
>>>
>> How can we show this without regularity?
>>
> ['x' stands for Cartesian.]
>
> Let z not in range(S). Then S x {z} is disjoint from S. (Proof idea by
> Ullrich.)
Great, thanks.
> I suspect your approaches don't work without invoking regularity.
You mean
>> Let's define
>>
>> S* = {<0, s> : s e S}
>> and
>> S** = {<1, s> : s e S}.
?
Hmmm, I'd say S* is a set of pairs the first component of which is 0 and
S** is a set of pairs the first component of which is 1. Since 0 =/= 1,
all pairs in S* should differ from the pairs in S**, hence S* n S** = {}
(no matter of the "structure" of S, i.e. the sets s in S), no?
Moreover (of course): S ~ S* and S ~ S**, hence S* ~ S**. ;-)
Herb
Herbert Newman
Right, thanks, William. :-)
Herb
Herbert Newman
>> Let's define
>>
>> S* = {<0, s> : s e S}
>> and
>> S** = {<1, s> : s e S}.
>>
>> Then
>> card(S) = card(S*) + card(S**).
>>
>> with S* n S** = {}, and S* ~ S**.
>>
>>> So S is 1-1 with S* u S**.
>>
>> Ok.
>>
>>> So let f be a bijection from S* u S** onto S.
>>> So S = f[S*] u f[S**].
>>
>> And of course f[S*] n f[S**] = {}, and f[S*] ~ f[S**].
>>
>> Then we would have shown (taking A = f[S*] and B = f[S**]):
>>
>> If S is infinite then there are two disjoint
>> equinumerous sets A, B with S = A u B.
>>
See William Elliot's lates reply. :-)
Herb
Herbert Newman
> Moe:
>>
>> I suspect your approaches don't work without invoking regularity.
>>
> You mean
>
> | Let's define
> |
> | S* = {<0, s> : s e S}
> | and
> | S** = {<1, s> : s e S}.
>
> ?
>
> Hmmm, I'd say S* is a set of pairs the first component of which is 0 and
> S** is a set of pairs the first component of which is 1. Since 0 =/= 1,
> all pairs in S* should differ from the pairs in S**, hence S* n S** = {}
> (no matter of the "structure" of S, i.e. the sets s in S), no?
>
> Moreover (of course): S ~ S* and S ~ S**, hence S* ~ S**. ;-)
See William Elliot's latest reply. :-)
Herb
P.S. I's funny, I really had exactly the same proof idea as William, I just
couldn't figure out how to prove the crucial step:
If S is infinite then there are two disjoint
equinumerous sets A, B with S = A u B.
:-)
Daryl McCullough
For an infinite set S, we have
|S| + |S| = |S|
|S| x |S| = |S|
I know the proofs of these in the case that S is countable,
but I don't immediately see how those proofs generalize to
uncountable S. Does the proof require the axiom of choice?
--
Daryl McCullough
Ithaca, NY
Frederick Williams
> For an infinite set S, we have
> |S| + |S| = |S|
> |S| x |S| = |S|
>
> I know the proofs of these in the case that S is countable,
> but I don't immediately see how those proofs generalize to
> uncountable S. Does the proof require the axiom of choice?
|S| x |S| = |S| is equivalent to AxCh.
--
Which of the seven heavens / Was responsible her smile /
Wouldn't be sure but attested / That, whoever it was, a god /
Worth kneeling-to for a while / Had tabernacled and rested.
MoeBlee
> Does the proof require the axiom of choice?
Yes.
MoeBlee
MoeBlee
> >> S* = {<0, s> : s e S}
Without regularity, how do you prove S* is disjoint from S?
> >> and
> >> S** = {<1, s> : s e S}.
> Hmmm, I'd say S* is a set of pairs the first component of which is 0 and
> S** is a set of pairs the first component of which is 1. Since 0 =/= 1,
> all pairs in S* should differ from the pairs in S**, hence S* n S** = {}
Of course, but that was not at question. What was at question was to
show (without regularity) that there is a set disjoint from S
(equinumerous with S, of course). Finding two sets both equinumerous
with S and disjoint from each other is not a problem. The question was
to finding some set equinumerous with S and disjoint from S itself.
Without the axiom of regularity, we can't just assume that {0}xS or {1}
xS are disjoint from S, though of course they are disjoint from each
other.
Ullrich's solution works:
Sx{z} is disjoint from S when z is not in the range of S.
MoeBlee
MoeBlee
P.S. Wanna up the ante on this, Daryl, and prove that every
uncountable set has a dearrangement, without using choice (or
regularity)?
I'm GUESSING it can't be done.
MoeBlee
Herbert Newman
> On Jul 8, 2:46�am, Herbert Newman <nomail@invalid> wrote:
>
>>>> � � � �S* = {<0, s> : s e S}
>
> Without regularity, how do you prove S* is disjoint from S?
It seems that you didn't read my argument very carefully. I wrote (quote
from 2 consecutive posts):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>> If S is infinite [...] then there [are] two disjoint
>>> equinumerous sets A, B with S = A u B.
>>
>> Proof?
>>
> Cardinal arithmetic: card(S) = card(S) + card(S). [Moe]
Accepted.
> But every set S is 1-1 with some set S* disjoint from S. [Moe]
Could you show that in detail? (Proof?)
_If_ we had the axiom of regularity [then] this would be easy [of course]:
Let S* = {<S, s> : s e S}.
Clearly there can't be an element <S, s> (with s e S) in S, since this
would violate regularity.
How can we show this without regularity?
~~~~~~
~~~~~~
Ah, an idea: we can SKIP this step and go directly for S* and S**:
Let's define
S* = {<0, s> : s e S}
and
S** = {<1, s> : s e S}.
Then S ~ S* and S ~ S**, and hence S* ~ S**; and S* n S** = {}.
~~~~~~
~~~~~~
Then
card(S) = card(S*) + card(S**).
with S* n S** = {}, and S* ~ S**.
> So S is 1-1 with S* u S**.
Ok.
> So let f be a bijection from S* u S** onto S.
> So S = f[S*] u f[S**].
And of course f[S*] n f[S**] = {}, and f[S*] ~ f[S**].
Then we would [indeed] have shown (taking A = f[S*] and B = f[S**]):
If S is infinite then there are two disjoint
equinumerous sets A, B with S = A u B.
Ok.
The rest is easy. Since A ~ B, there's a bijection f from A onto B. (Then
f^-1 is a bijection from B onto A.)
Now define f': S --> S with
f' = f u f^-1.
f' is the dearrangment you were looking for. (Easy!)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Then YOU wrote:
> I suspect your approaches don't work without invoking regularity.
And I replied:
> You mean
>
> | Let's define
> |
> | S* = {<0, s> : s e S}
> | and
> | S** = {<1, s> : s e S}.
>
> ?
>
> Hmmm, I'd say S* is a set of pairs the first component of which is 0 and
> S** is a set of pairs the first component of which is 1. Since 0 =/= 1,
> all pairs in S* should differ from the pairs in S**, hence S* n S** = {}
> (no matter of the "structure" of S, i.e. the sets s in S), no?
>
> Moreover (of course): S ~ S* and S ~ S**, hence S* ~ S**.
You should try to read more carefully what I actually wrote, Moe, before
replying to my posts.
Herb
MoeBlee
> It seems that you didn't read my argument very carefully.
No, I did.
But I think I see the misunderstanding (for which I do not blame you):
When I said that I doubted that your approach would work, I was not
referring to the final theorem about derangemetns but rather to the
intermediary question you had raised about showing a set equinumerous
with, but disjoint, from S. That is, my comment was as to that
question onto itself; I did not mean to imply that that question could
not be bypassed en route to proving the theorem about derangements.
MoeBlee
Herbert Newman
Hi Moe!
> But I think I see the misunderstanding (for which I do not blame you):
> When I said that I doubted that your
>
> approach
>
> would work, I was not referring to the final theorem about derangements
> but rather to the intermediary question you had raised about showing a
> set equinumerous with, but disjoint, from S.
I see, I guess, it's the plural form that led me astray: you actually wrote
"approaches" in your original reply.
> That is, my comment was as to that question onto itself ...
I see. Right, David Ullrich's approach would answer my question concerning
that problem.
As usual I have learned something addressing one of your questions. :-)
(Besides Ullrich's method there's the nice/simple approach concerning
"Elliot's theorem".)
Herb
MoeBlee
> As usual I have learned something addressing one of your questions.
I'm happy to hear that.
I have a followup theorem that I'll post when I get a less distracted
to minute: The derangement problem only occurred to me on the way to
trying to prove yet another theorem. I think my proof of this next
theorem is some nice clear thinking, but I wouldn't be surprised that
it has an even simpler proof.
MoeBlee
MoeBlee
> I have a followup theorem
Derangements came up because I wanted to use them to prove an Enderton
exercise (in ZC set theory without regularity and with "card(x)=card
(y) <-> x equinumnerous with y"):
Show if k is an infinite cardinal, then k! = 2^k:
['P' stands for 'the power set of' ; 'N' stands for 'the identity
function on'; 'X' stands for the binary Cartesian product.]
By prior considerations, we have k! =< k^k = 2^k.
So it remains to show 2^k =< k!.
First, it is easy to show that k! is infinite.
Then let:
F = {f | f: k->2}
S = {s | s is a permutation of k}
E = {p in Pk | card(p) ≠ 1}
B = {f in F | card({x in k | f(x) = 1}) ≠ 1}
C = {f in F | card({x in k | f(x) = 1}) = 1}
R = {<p d> | p in E & d is a derangement of p},
which exists as described, since it is a subset of E X P(kXk).
By choice, let D be a function and a subset of R and dom(D) = dom(R) =
E.
So D: E->S such that for all p in E, we have D(p) is a derangement of
p.
Note that F = BuC.
Let H: B->S by
H(f) = N{x in k | f(x) = 0} u D({x in k | f(x) = 1}).
H is 1-1.
Let T: C->k by
T(f) = the_x(x in k & f(x) = 1).
Let z be some member of k.
Let G: C->S by
G(f) = (N{x in k | f(x) = 0}\{<T(f) T(f)> <z z>}) u {<T(f) z> <z T(f)
>}.
G is 1-1.
So card(B) =< k!
and card(C) =< k!.
So card(B)+card(C) =< k!+k! = k!.
and card(B)+card(C) = card(F) = 2^k.
So 2^k =< k!.
So 2^k = k!.
MoeBlee
MoeBlee
> G(f) = (N{x in k | f(x) = 0}\{<T(f) T(f)> <z z>}) u {<T(f) z> <z T(f)>}.
>
> G is 1-1.
There's no significance to the line spacing there; just a typo.
MoeBlee
MoeBlee
Darn, the spacing got messed up. I hope this displays better:
> N{x in k | f(x) = 0}\{<T(f) T(f)> <z z>} u {<T(f) z> <z T(f)>}.