Forming one set from another
Michael Stemper
create C' from C by replacing every element of C that is in (C int D)
with a unique element that is not in (C union D)?
As a step in a proof, can I just say "form C' from C ...", or do I
need to invoke Choice, or do I actually need to show that this step
is possible?
--
Michael F. Stemper
#include <Standard_Disclaimer>
The FAQ for rec.arts.sf.written is at:
http://www.geocities.com/evelynleeper/sf-written
Please read it before posting.
Arturo Magidin
wrote:
> Given two countably infinite sets, C and D, is it always possible to
> create C' from C by replacing every element of C that is in (C int D)
> with a unique element that is not in (C union D)?
Given any set X, there is always a set x that is not in X (Proof: let
x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
x not in x --> x in x); this does not require the Axoim of
Foundation).
So let x be a set that is not in \/(\/(C\/D)). Then take
C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
To see that no element of (C/\D x {x}) lies in C \/ D, suppose that
(a,x) is in C\/D, with a in C/\D. That means that {{a},{a,x}} is an
element of C\/D, hence {a,x} is an element of \/(C\/D), hence x is in
\/(\/(C\/D)); but this contradicts the choice of x. Hence (C/\D x {x})
is disjoint from (C\/D), as desired.
> As a step in a proof, can I just say "form C' from C ...", or do I
> need to invoke Choice, or do I actually need to show that this step
> is possible?
You don't need to invoke choice (or Foundation; or even Replacement,
which might seem like the sort of thing you might need here). It is
usually clear that this sort of thing (what one might call
"disjointizing") can always be done by taking direct products with
appropriate singletons. I always think of it as "painting" elements of
sets a particular color in order to be able to distinguish them. So
usually you could just say what property you want C' to have, provided
you are able to provide a proof that such a thing can be done when
requested. The usual trick of doing something like I did above
generally works.
--
Arturo Magidin
Michael Stemper
>On Dec 1, 7:35=A0am, mstem...@walkabout.empros.com (Michael Stemper) wrote:
>> Given two countably infinite sets, C and D, is it always possible to
>> create C' from C by replacing every element of C that is in (C int D)
>> with a unique element that is not in (C union D)?
>
>Given any set X, there is always a set x that is not in X (Proof: let
>x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
>x not in x --> x in x);
It looks like some kind of diagonalization, but I'll have to take
it home and write it down on paper to be sure that I understand it.
>So let x be a set that is not in \/(\/(C\/D)). Then take
>
>C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
The first "x" in this expression is intended to be the cross-product
operator, nicht wahr?
>To see that no element of (C/\D x {x}) lies in C \/ D, suppose that
>(a,x) is in C\/D, with a in C/\D. That means that {{a},{a,x}} is an
>element of C\/D, hence {a,x} is an element of \/(C\/D), hence x is in
>\/(\/(C\/D)); but this contradicts the choice of x. Hence (C/\D x {x})
>is disjoint from (C\/D), as desired.
Actually, this looks as if it might be a more robust variant of
something that I tried early on. I ended up rejecting what I had,
which was basically something along the lines of "replace all c in
C&D with (c,0)", if I recall correctly. I ended up throwing it out
when I realized that C&D might include c, (c,0), ((c,0),0), uzw.
Then, I started floundering around, trying to find a way to select
elements that would be guaranteed non-duplicates. After I spend
some serious time with your response, I hope to understand it. I
don't think that I could have come up with it, though.
>> As a step in a proof, can I just say "form C' from C ...", or do I
>> need to invoke Choice, or do I actually need to show that this step
>> is possible?
>
>You don't need to invoke choice (or Foundation; or even Replacement,
>which might seem like the sort of thing you might need here). It is
>usually clear that this sort of thing (what one might call
>"disjointizing")
I like this word -- it conveys exactly what I was attempting to do.
In fact, I'm willing to bet that you can read between the lines and
work out what I want to use this result to prove, can't you?
> can always be done by taking direct products with
>appropriate singletons.
Choosing the singleton could be tough. Or, maybe after I understand
what you've said, it'll be child's play.
Thanks, as always.
--
Michael F. Stemper
#include <Standard_Disclaimer>
This sentence no verb.
Arturo Magidin
wrote:
> In article <d6425703-5980-4953-86c7-32b23729c...@m16g2000yqc.googlegroups.com>, Arturo Magidin <magi...@member.ams.org> writes:
>
> >On Dec 1, 7:35=A0am, mstem...@walkabout.empros.com (Michael Stemper) wrote:
> >> Given two countably infinite sets, C and D, is it always possible to
> >> create C' from C by replacing every element of C that is in (C int D)
> >> with a unique element that is not in (C union D)?
>
> >Given any set X, there is always a set x that is not in X (Proof: let
> >x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
> >x not in x --> x in x);
>
> It looks like some kind of diagonalization, but I'll have to take
> it home and write it down on paper to be sure that I understand it.
Yes; it's very similar to the 'diagonal set' in the proof of Cantor's
Theorem (which would be {y in X : y not in f(y)}). It's really just an
artifice to show that given any set, there is always a set that is not
an element of it. It only requires the Axiom of Separation.
> >So let x be a set that is not in \/(\/(C\/D)). Then take
>
> >C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
>
> The first "x" in this expression is intended to be the cross-product
> operator, nicht wahr?
Yes; sorry for using x and not y for the element...
> >To see that no element of (C/\D x {x}) lies in C \/ D, suppose that
> >(a,x) is in C\/D, with a in C/\D. That means that {{a},{a,x}} is an
> >element of C\/D, hence {a,x} is an element of \/(C\/D), hence x is in
> >\/(\/(C\/D)); but this contradicts the choice of x. Hence (C/\D x {x})
> >is disjoint from (C\/D), as desired.
>
> Actually, this looks as if it might be a more robust variant of
> something that I tried early on. I ended up rejecting what I had,
> which was basically something along the lines of "replace all c in
> C&D with (c,0)", if I recall correctly. I ended up throwing it out
> when I realized that C&D might include c, (c,0), ((c,0),0), uzw.
Exactly.
> Then, I started floundering around, trying to find a way to select
> elements that would be guaranteed non-duplicates. After I spend
> some serious time with your response, I hope to understand it. I
> don't think that I could have come up with it, though.
>
> >> As a step in a proof, can I just say "form C' from C ...", or do I
> >> need to invoke Choice, or do I actually need to show that this step
> >> is possible?
>
> >You don't need to invoke choice (or Foundation; or even Replacement,
> >which might seem like the sort of thing you might need here). It is
> >usually clear that this sort of thing (what one might call
> >"disjointizing")
>
> I like this word -- it conveys exactly what I was attempting to do.
> In fact, I'm willing to bet that you can read between the lines and
> work out what I want to use this result to prove, can't you?
If you are aiming for a definition of "cardinality of a sum", that is,
you want to take a set C of cardinality kappa, a set D of cardinality
lambda, and use them to defie "kappa+lambda", the usual way is to do
this by considering Cx{1} and Dx{2}; Cx{1} is clearly bijectable with
C, Dx{2} bijectable with D, and Cx{1} /\ Dx{2} = emptyset. So one
defines kappa+lambda as the cardinality of (Cx{1}) \/ (Dx{2}). No need
to much around with C/\D. This amounts to taking C and "painting every
element of C the color blue", then "painting every element of D the
color red" to ensure that the elements of C and of D are now pairwise
distinct...
Regards,
--
Arturo Magidin
Tim Little
> Given two countably infinite sets, C and D, is it always possible to
> create C' from C by replacing every element of C that is in (C int D)
> with a unique element that is not in (C union D)?
Yes. For example, for each x in C /\ D you could replace it with
{x, C\/D}. Some form of the axiom of regularity is required for this
particular replacement to work, but other forms may be possible
without it.
> As a step in a proof, can I just say "form C' from C ...", or do I
> need to invoke Choice, or do I actually need to show that this step
> is possible?
The only time you should ever omit any demonstration in a proof is
when you know that the readers should be able to fill in the missing
formal details themselves. If you have doubts yourself, then it
doesn't belong in your proof.
- Tim
Arturo Magidin
> On Dec 1, 7:35 am, mstem...@walkabout.empros.com (Michael Stemper)
> wrote:
>
> > Given two countably infinite sets, C and D, is it always possible to
> > create C' from C by replacing every element of C that is in (C int D)
> > with a unique element that is not in (C union D)?
>
> Given any set X, there is always a set x that is not in X (Proof: let
> x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
> x not in x --> x in x); this does not require the Axoim of
> Foundation).
>
> So let x be a set that is not in \/(\/(C\/D)). Then take
>
> C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
A possibly simpler replacement is to first consider the set:
A = { y | there exists z such that (z,y) in C\/D }
(that is, all things that are second coordinates of an ordered pair in
C or in D). It is not hard to show that this is in fact a set using
appropriate unions and power sets. Then let w be something not in A.
You can then take
C' = (C - (C/\D)) \/ ( (C/\D) x {w} ).
If you had z in (C/\D)x{w} that is also in C\/D, then z = (r,w) for
some r in C/\D, but this would mean that (r,w) is in C\/D, which means
that w is in A, which contradicts that we picked w to be something not
in A.
--
Arturo Magidin
Michael Stemper
>On Dec 1, 7:35=A0am, mstem...@walkabout.empros.com (Michael Stemper) wrote:
>> Given two countably infinite sets, C and D, is it always possible to
>> create C' from C by replacing every element of C that is in (C int D)
>> with a unique element that is not in (C union D)?
>
>Given any set X, there is always a set x that is not in X (Proof: let
>x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
>x not in x --> x in x); this does not require the Axoim of
>Foundation).
>
>So let x be a set that is not in \/(\/(C\/D)). Then take
>
>C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
Let's see if I'm doing this right.
Let C = { 1, (2,0), 4 } and D = { 1, 2, (0,3) }
Then C\/D = { 1, 2, 4, (2,0), (0,3) }
= { 1, 2, 4, { {2}, {2,0} }, { {0}, {0,3} } }
\/(C\/D) = { 1, 2, 4, {2}, {2,0}, {0}, {0,3} }
\/(\/(C\/D)) = { 0, 1, 2, 3, 4 }
Is this right?
It seems that there is an implicit limitation on the levels of
abstraction in this formulation. Ordered pairs are to be replaced
by their definitions as sets, but the naturals aren't. Is my
understanding correct?
--
Michael F. Stemper
#include <Standard_Disclaimer>
2 + 2 = 5, for sufficiently large values of 2
Michael Stemper
>On Dec 1, 1:03=A0pm, mstem...@walkabout.empros.com (Michael Stemper) wrote:
>> >On Dec 1, 7:35=3DA0am, mstem...@walkabout.empros.com (Michael Stemper) wrote:
>> >> Given two countably infinite sets, C and D, is it always possible to
>> >> create C' from C by replacing every element of C that is in (C int D)
>> >> with a unique element that is not in (C union D)?
>> Actually, this looks as if it might be a more robust variant of
>> something that I tried early on. I ended up rejecting what I had,
>> which was basically something along the lines of "replace all c in
>> C&D with (c,0)", if I recall correctly. I ended up throwing it out
>> when I realized that C&D might include c, (c,0), ((c,0),0), uzw.
>> I like this word -- it conveys exactly what I was attempting to do.
>> In fact, I'm willing to bet that you can read between the lines and
>> work out what I want to use this result to prove, can't you?
>
>If you are aiming for a definition of "cardinality of a sum", that is,
You flatter me. :-> I was just trying to start from my proof that
the union of two disjoint countably infinite sets was countably infinite
and generalize it to the case where the two sets weren't necessarily
disjoint.
However, while playing around with your suggestion, it occurred to me
that I could form bijections between the even naturals and one of the
sets and the odd naturals with the other, which gives me a surjection
to the union, hence |CUD| <= |N|. Since |N| <= |C|, Schroder-Bernstein
says |CUD| = |N| and Bob's your uncle. Much cleaner.
Learning happens in strange ways.
>you want to take a set C of cardinality kappa, a set D of cardinality
>lambda, and use them to defie "kappa+lambda", the usual way is to do
>this by considering Cx{1} and Dx{2}; Cx{1} is clearly bijectable with
>C, Dx{2} bijectable with D, and Cx{1} /\ Dx{2} =3D emptyset.
This is also cleaner than what I was doing, as well as simpler to
understand. Thanks!
--
Michael F. Stemper
#include <Standard_Disclaimer>
Michael Stemper
This was a case like the apocryphal story of the guy giving a lecture
and saying, "it is obvious that ...". He stops, thinks, puts down the
chalk (old story), and heads to his office. An hour later he reappears
and says, "I was right. It is obvious."
--
Michael F. Stemper
#include <Standard_Disclaimer>
The Qurqirish Dragon
wrote:
I think that this depends on the universe the sets are derived from.
If the universe is countable, then it is possible the set of all
elements not in (C union D) is finite, with smaller cardinality than
(C int D). The most trivial example would be if C were the set of
elements in the universe. Then the set of elements not in (C union D)
is empty, and (C int D) = D, and there is no way to construct C'
If the universe is not countable, then it is always possible (as shown
in other parts of this thread).
Arturo Magidin
wrote:
> In article <d6425703-5980-4953-86c7-32b23729c...@m16g2000yqc.googlegroups.com>, Arturo Magidin <magi...@member.ams.org> writes:
>
> >On Dec 1, 7:35=A0am, mstem...@walkabout.empros.com (Michael Stemper) wrote:
> >> Given two countably infinite sets, C and D, is it always possible to
> >> create C' from C by replacing every element of C that is in (C int D)
> >> with a unique element that is not in (C union D)?
>
> >Given any set X, there is always a set x that is not in X (Proof: let
> >x = {y in X : y not in y}; if x in X, then (x in x --> x not in x; and
> >x not in x --> x in x); this does not require the Axoim of
> >Foundation).
>
> >So let x be a set that is not in \/(\/(C\/D)). Then take
>
> >C' = (C - (C /\ D)) \/ ( (C/\D) x {x}).
>
> Let's see if I'm doing this right.
First, you might want to look at my later simplification. It is much
easier to consider the set of "second coordinates of any ordered pair
that my be in C\/D", and take x to be an element not in that set.
That said...
> Let C = { 1, (2,0), 4 } and D = { 1, 2, (0,3) }
>
> Then C\/D = { 1, 2, 4, (2,0), (0,3) }
> = { 1, 2, 4, { {2}, {2,0} }, { {0}, {0,3} } }
>
> \/(C\/D) = { 1, 2, 4, {2}, {2,0}, {0}, {0,3} }
> \/(\/(C\/D)) = { 0, 1, 2, 3, 4 }
>
> Is this right?
Not quite; if X is a set, then \/X = {y | exists z (y in z and z in
X)}. That is: the result of taking the union of the elements of X.
So if C\/D = {1 2, 4, (2,0), (0,3)}, then
\/(C\/D) would be
1 \/ 2 \/ 4 \/ (2,0) \/ (0,3) =
{0} \/ {0,1} \/ {0,1,2,3} \/ {{2}, {2,0}} \/ {{0},{0,3}} =
= {0, 1, 2, 3, {2}, {2,0}, {0}, {0,3}}.
Then, \/(\/(C\/D)) =
0 \/ 1 \/ 2 \/ 3 \/ {2} \/ {2,0} \/ {0} \/ {0,3} =
{} \/ {0} \/ {0,1} \/ {0,1,2} \/ {2} \/ {2,0} \/ {0} \/ {0,3} =
{0, 1, 2, 3}.
The point is that among the elements in that set are 0 and 3, that is,
the set contains {y | there exists x such that (x,y) is in C\/D}.
If you were to take \/(\/(\/(C\/D))) you would get {0,1,2}.
> It seems that there is an implicit limitation on the levels of
> abstraction in this formulation. Ordered pairs are to be replaced
> by their definitions as sets, but the naturals aren't. Is my
> understanding correct?
No; the naturals are expanded as well. What we are doing is
considering the set as a family (which it is in usual ZF, since there
are no ur-elements; a family is a set all of whose elements are sets)
and taking the union of that family.
--
Arturo Magidin