Discrete Topology, Partitioning an Infinite Set
Pansy
"Let S be any infinite set. Show that requiring every infinite subset of S
to be open imposes the discrete topology on S."
[i.e. forces every set to be both open and closed]
Partial proof:
Let X be any subset of S. If X is infinite, then X is open by hypothesis.
If the complement S-X of X is infinite, then S-X is open, and therefore X is
also closed. If the S-X is finite, then X will be closed iff S-X is open.
It remains then to show that finite sets are open.
Let X be finite; then its complement S-X must be infinite (since S is
infinite). Thus S-X is open, and X is closed. All that needs to be shown
is that X is also open. The only way I've thought of to do this so far is
to assume that there exists a subset A of S such that both A and S-A are
infinite. (I'm stuck on the existence proof.)
If I have such an A, then both A and S-A are open because they're infinite.
(They're also both closed because their complements are open.) Because A is
already infinite, A(union)X must also be infinite. The same is true of
(S-A)(union)X. Both of these sets are open because they're infinite. The
intersection of two open sets is open. But the intersection of these two is
X. Thus any finite set X must be open.
The only thing I don't know how to do is construct A or prove such an A must
exist. Intuitively, it must be possible to divide an infinite set S into
two disjoint sets A and S-A which are both infinite. Any hints for proving
this? Also, I'm interested in a way to show that the finite set X above is
open without appealing to the existence of such an A and A-S pair.
Thanks for reading, and please post any responses, as I can't receive
e-mail.
Dave Seaman
>Let X be finite; then its complement S-X must be infinite (since S is
>infinite). Thus S-X is open, and X is closed. All that needs to be shown
>is that X is also open. The only way I've thought of to do this so far is
>to assume that there exists a subset A of S such that both A and S-A are
>infinite. (I'm stuck on the existence proof.)
If S is Dedekind-infinite (meaning it is equipollent to a proper subset
of itself), then it has a countable subset. Any countable set may be so
divided (think of odds and evens).
To prove that every infinite set is Dedekind-infinite, you need the axiom
of choice. Does the exercise allow you to assume that? Or perhaps
"infinite" is being used to mean "Dedekind-infinite"? The other common
meaning of "infinite" is "not equipollent to any natural number".
--
Dave Seaman dse...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.refuseandresist.org/mumia/021700amnesty.html>
David Libert
Dave Seaman (a...@seaman.cc.purdue.edu) writes:
> In article <v0Rc5.163$wi7....@news.pacbell.net>,
> Pansy <som...@somewhere.org> wrote:
>>Exercise 1-5 from Hocking and Young's _Topology_:
>
>>Let X be finite; then its complement S-X must be infinite (since S is
>>infinite). Thus S-X is open, and X is closed. All that needs to be shown
>>is that X is also open. The only way I've thought of to do this so far is
>>to assume that there exists a subset A of S such that both A and S-A are
>>infinite. (I'm stuck on the existence proof.)
>
> If S is Dedekind-infinite (meaning it is equipollent to a proper subset
> of itself), then it has a countable subset. Any countable set may be so
> divided (think of odds and evens).
>
> To prove that every infinite set is Dedekind-infinite, you need the axiom
> of choice. Does the exercise allow you to assume that? Or perhaps
> "infinite" is being used to mean "Dedekind-infinite"? The other common
> meaning of "infinite" is "not equipollent to any natural number".
As Dave notes, if S is Dedikind-infinite then the original question
can be solved. For example, to rephrase a proof, assuming a topology on
X has every set open, to show the topology is discrete it suffices to
show everey singleton set (ie one element set) is open, ie each singleton
is the intersection of two infinite sets. So as Dave says, from
Dedikind-infinite you can get disjoint infinite subsets, so union eavh
of these with the desired singleton.
ZFC (set theory with the Axiom of Choice) proves every infinite set is
Dedikind-infinite, so as Dave says this is an outright ZFC solution to
the original problem. Also, if the problem is read as supposing
Dedikind-infinite, then we have a ZF solution.
A set is defined to be Dedikind iff it is infinite and Dedikind-finite.
(Dedikind-finite: not Dedikind-infinite: ie not equipollent to a
proper subset of itself). So ZFC proves there are no Dedikind sets.
For B a subset of some set A, we define B is cofinite in A to mean
A - B is finite.
A set A is defined to be amorphous iff it is infinite and each subset
B of A is either finite or cofinite in A.
ZF (set theory without the Axiom of Choice) proves any amorphous set
is Dedikind. So ZFC proves there are no amorphous sets.
It is a known theorem that if ZF is consistent then there are models
of ZF + there exists an amorphous set.
Given any amorphous set A, form the topology on it of all infinite
sets and the empty set. For B1 and B2 infinite subsets of A, by the
amorphous property A-B1 and A-B2 are each finite. So
A-B1 union A-B2 is finite, ie A-(B1 ^ B2) is finite, so B1 ^ B2
is infinite.
So this shows the "topology" just defined has open sets closed under
finite intersection. Also the union of any collection of infinite sets
is infinite, so the "open" sets are closed under abritrary union as
required. A and {} are open, so we really do have a topology.
In this topology singletons are not open, so it is not the discrete
topology. So in this choiceless ZF model we have a counterexample to
the claim to be proved in the question.
This countereaxmple was based on having an amorphous set. Working
only with a Dedikind set is not enough to construct a direct
counterexample in the form above.
Namely, let D1 be a Dedikind set. Let D2 be an isomorphic copy of D1
which is disjoint from D1, for example D2 could be obtained by a
cartesian product of D1 with some singleton to make sure of
disjointness: D2 = D1 x {D1} would work, ie no ordered pair <x, D1>
could be a member of D1 by ZF having no circles of membership.
Define D = D1 union D2. Then D is still Dedikind: ie infinite
and Dedikind-finite. (The union of two Dedikind-finite sets is
Dedikind-finite).
D has two disjoint infinite subsets (D1 and D2). So D is not
amorphous. Also for {d} any singleton subset of D, {d} union D1
and {d} union D2 are two infinite subsets of D intersecting to {d}.
So any toplogy on D making all infinite sets open also has {d} open.
True for all {d} 's, so any such topology is discrete.
So D is Dedikind, but it can't be used to make a direct counterexample
to the basic claim.
This leaves open the possibility of other counterexamples constructed
from a Dedikind set, ie using sets of other than the basic Dedikind set.
I would conjecture this can't be done either. In fact I conjecture:
Conjecture: if ZF is consistent then there is a model of
ZF + there exists Dedikind sets + for every infinite set X every
topology on X making each infinite set open is the discrete topology.
Ie the conjecture above would be for every X in the model, not just
the Dedikind sets.
--
David Libert (ah...@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
Ed Hook
|> to be open imposes the discrete topology on S."
|> [i.e. forces every set to be both open and closed]
|> Partial proof:
|> Let X be any subset of S. If X is infinite, then X is open by hypothesis.
|> If the complement S-X of X is infinite, then S-X is open, and therefore X is
|> also closed. If the S-X is finite, then X will be closed iff S-X is open.
|> It remains then to show that finite sets are open.
|> infinite). Thus S-X is open, and X is closed. All that needs to be shown
|> is that X is also open. The only way I've thought of to do this so far is
|> to assume that there exists a subset A of S such that both A and S-A are
|> infinite. (I'm stuck on the existence proof.)
|> (They're also both closed because their complements are open.) Because A is
|> already infinite, A(union)X must also be infinite. The same is true of
|> (S-A)(union)X. Both of these sets are open because they're infinite. The
|> intersection of two open sets is open. But the intersection of these two is
|> X. Thus any finite set X must be open.
|> The only thing I don't know how to do is construct A or prove such an A must
|> exist. Intuitively, it must be possible to divide an infinite set S into
|> two disjoint sets A and S-A which are both infinite. Any hints for proving
|> this? Also, I'm interested in a way to show that the finite set X above is
|> open without appealing to the existence of such an A and A-S pair.
There have already been a couple of really
good responses to this, but maybe the
following is still worthwhile ...
I don't have Hocking & Young handy, but
(prior to this exercise) have they
proved the result that any infinite
set has a countable subset ?? (As you
may deduce from the posts by the two
Daves [Seaman and Renfro], this isn't
true in every version of set theory, but
you can also deduce that it _is_ true
for H & Y :-) Anyhow, given that result,
you can avoid your need for A as above
by making a small change in your proof.
Let C be a countable subset of S and
let p be any point in S. Without loss
of generality, you can assume that p
is not a point in C. Using any bijection
between C and N (the natural numbers),
write C as the union of disjoint
subsets C_0, C_1 (the first corresponding
to the even natural numbers, the second
to the odd). Then
{p} = (C_0 \cup {p}) \cap (C_1 \cup {p})
displays {p} as the intersection of two
open sets (open, because they're infinite)
and shows that {p} is itself open.
As I said, this is pretty much _your_
proof -- it just (slightly) finesses
the question of existence of your set
A ...
--
Ed Hook | Copula eam, se non posit
Computer Sciences Corporation | acceptera jocularum.
NAS, NASA Ames Research Center | All opinions herein expressed are
Internet: ho...@nas.nasa.gov | mine alone
Pansy
Dave Seaman <a...@seaman.cc.purdue.edu> wrote in message
news:8l0nrd$i...@seaman.cc.purdue.edu...
> In article <v0Rc5.163$wi7....@news.pacbell.net>,
> >infinite). Thus S-X is open, and X is closed. All that needs to be
shown
> >is that X is also open. The only way I've thought of to do this so far
is
> >to assume that there exists a subset A of S such that both A and S-A are
> >infinite. (I'm stuck on the existence proof.)
>
> of itself), then it has a countable subset. Any countable set may be so
> divided (think of odds and evens).
>
> To prove that every infinite set is Dedekind-infinite, you need the axiom
> of choice. Does the exercise allow you to assume that?
I don't know what is assumed in this context. This exercise is in section
1-4; at this point, Hocking and Young haven't explicitly defined "infinite
set". Section 1-9, "Some Theorems in Logic", presents the axiom of choice.
I had the feeling that partitioning an uncountably infinite set into two
infinite subsets would invoke the axiom of choice. I'm no set theoretician,
and I don't get too hung up over AC, but I like to know when I'm using it.
> Or perhaps
> "infinite" is being used to mean "Dedekind-infinite"? The other common
> meaning of "infinite" is "not equipollent to any natural number".
I cracked open Halmos' _Naive_Set_Theory_. He adopts the second definition
for infinite set. He then uses AC to prove that an infinite set S has a
subset equivalent to naturals (i.e. countably infinite subset), and as a
corollary shows that S is Dedekind-infinite. This is exactly as you noted
above.
It seems, then, that the most straightforward construction of the desired A
and S-A is as follows. S has a countably infinite subset (AC assumed!).
Index this set by the natural numbers. Put the even-indexed elements into
A. Then S-A is infinite because it contains the odd-indexed elements (an
infinite set) as a subset.
By the way, this exercise appears in section 1-4, "Basis and Subbasis of a
Topology". It's not clear what this has to do with bases. The infinite
subsets of S do _not_ satisfy the requirements of a basis for a topology on
S.
A collection {B_a) of subsets of S is defined to be a basis for a topology
in S provided that
(1) (union)(B_a) = S
(2) If p is a point of B_1(intersect)B_2, then there is an element B_3 of
{B_a} which contains p and which is itself contained in B_1(intersect)B_2.
There is no problem with (1) since S itself is infinite and is thus one of
the B_a.
However, (2) is not satisfied because two infinite sets can have a finite
intersection; in this case, the required B_3 does not exist if there are
only infinite sets in the {B_a}.
If anyone knows what Hocking and Young were getting at by putting this
exercise in the section on bases and subbases, I'd like to find out.
Thanks for your response!
Dave Seaman
Pansy <som...@somewhere.org> wrote:
>Dave Seaman <a...@seaman.cc.purdue.edu> wrote in message
>news:8l0nrd$i...@seaman.cc.purdue.edu...
>> To prove that every infinite set is Dedekind-infinite, you need the axiom
>> of choice. Does the exercise allow you to assume that?
>I don't know what is assumed in this context. This exercise is in section
>1-4; at this point, Hocking and Young haven't explicitly defined "infinite
>set". Section 1-9, "Some Theorems in Logic", presents the axiom of choice.
It could be that one of the points of the exercise was to get you
thinking about what an infinite set is.
>By the way, this exercise appears in section 1-4, "Basis and Subbasis of a
>Topology". It's not clear what this has to do with bases. The infinite
>subsets of S do _not_ satisfy the requirements of a basis for a topology on
>S.
Ok, that's one possibility eliminated. Did you try checking the other
one?
A collection of sets is called a subbase for a topology if the collection
of finite intersections of those sets forms a base for the topology. In
fact, it turns out that every collection of subsets of a set X is the
subbase for some topology on X.
The original question then becomes: consider the set of all (Dedekind-)
infinite subsets of S. Show that this collection is a subbase for the
discrete topology.
Herman Rubin
Dave Seaman <a...@seaman.cc.purdue.edu> wrote:
>In article <v0Rc5.163$wi7....@news.pacbell.net>,
>Pansy <som...@somewhere.org> wrote:
>>Exercise 1-5 from Hocking and Young's _Topology_:
>>Let X be finite; then its complement S-X must be infinite (since S is
>>infinite). Thus S-X is open, and X is closed. All that needs to be shown
>>is that X is also open. The only way I've thought of to do this so far is
>>to assume that there exists a subset A of S such that both A and S-A are
>>infinite. (I'm stuck on the existence proof.)
>If S is Dedekind-infinite (meaning it is equipollent to a proper subset
>of itself), then it has a countable subset. Any countable set may be so
>divided (think of odds and evens).
>To prove that every infinite set is Dedekind-infinite, you need the axiom
>of choice. Does the exercise allow you to assume that? Or perhaps
>"infinite" is being used to mean "Dedekind-infinite"? The other common
>meaning of "infinite" is "not equipollent to any natural number".
Most topology books allow more than that.
There are models of set theory in which there are sets which
are not equipollent to any natural number, but whose only
subsets are finite or cofinite. In such a set, having only
infinite sets and the empty set open is a topology.
--
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, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Pansy
> >By the way, this exercise appears in section 1-4, "Basis and Subbasis of
a
> >Topology". It's not clear what this has to do with bases. The infinite
> >subsets of S do _not_ satisfy the requirements of a basis for a topology
on
> >S.
>
> Ok, that's one possibility eliminated. Did you try checking the other
> one?
>
> A collection of sets is called a subbase for a topology if the collection
> of finite intersections of those sets forms a base for the topology. In
> fact, it turns out that every collection of subsets of a set X is the
> subbase for some topology on X.
OK, let B be the set of all finite intersections of infinite subsets of the
infinite set S. Clearly S itself is in B, so criterion (1) for a basis
(union of all elements of B must equal S) is met. If B_i and B_j are two
elements of S, then B_i(intersect)B_j is also in S. Criterion (2)
stipulates that if p is in the intersection of two elements B_i and B_j of
B, then there must be a third element B_k in B which contains p and is a
subset of B_i(intersect)B_j. So choosing B_k = B_i(intersect)B_j itself
meets this requirement.
True enough, then; B is a basis for a topology on S. The topology (open
sets on S) determined by B consists of all unions of elements of B. My job
is then to show that the singletons of S are open under this topology. This
amounts to asking whether every singleton s in S can be expressed as a
finite union of infinite subsets of S. Here is where this line of attack
converges with the one I outlined in my previous post -- in order to
construct such a finite union for a given singleton s, I still need to
partition S into two infinite sets, which has been demonstrated to require
AC. It seems that addressing the question of subbases and bases in the
context of this problem was extraneous (except in light of the fact that the
exercise appears in that section of the text!), but as a side-track it is
interesting in its own respect.
Thanks for taking the time to respond!
David Libert
My example below had D1 and D2 disjoint isomorphic Dedikind sets. In
fact isomorphic only arose so I could infer the existence of D1 and D2
from a single assumed Dedikind set. For the proof below it only matters
that D1 and D2 are disjoint and each Dedikind.
David Libert (ah...@FreeNet.Carleton.CA) writes:
>
> Define D = D1 union D2. Then D is still Dedikind: ie infinite
> and Dedikind-finite. (The union of two Dedikind-finite sets is
> Dedikind-finite).
>
> D has two disjoint infinite subsets (D1 and D2). So D is not
> amorphous. Also for {d} any singleton subset of D, {d} union D1
> and {d} union D2 are two infinite subsets of D intersecting to {d}.
> So any toplogy on D making all infinite sets open also has {d} open.
> True for all {d} 's, so any such topology is discrete.
All the proof of D having discrete topology needs is that D1 and D2
are disjoint infinite subsets of D.
So in fact this same proof works for any infinite set E which is assumed
non-amorphous. Ie suppose E is infinite and non-amorphous. So E has
some subset, call it D1, which is not finite and not cofinite in E. So
definining D2 = E-D1, D2 is also infinite and disjoint from D1.
So as above we can use D1 and D2 as disjoint infinite subsets of E to
make {d} union D1 and {d} union D2 be two infinite subsets of E
intersecting to {d}, for {d} arbitrary singelton subset of E. Hence any
topology on E making all infinite sets open is discrete, as required for
the orginal claim.
In my previous post I showed that an amorphous set has a topology
contradicting the claim. I have now shown non-amorphous sets satisfy
the claim.
So ZF proves for all sets X X satisfies the original claim <-> X is
non-amorphous. So ZF proves: the original claim <-> there are no
amorphous sets.
> So D is Dedikind, but it can't be used to make a direct counterexample
> to the basic claim.
>
> This leaves open the possibility of other counterexamples constructed
> from a Dedikind set, ie using sets of other than the basic Dedikind set.
>
> I would conjecture this can't be done either. In fact I conjecture:
>
> Conjecture: if ZF is consistent then there is a model of
> ZF + there exists Dedikind sets + for every infinite set X every
> topology on X making each infinite set open is the discrete topology.
>
> Ie the conjecture above would be for every X in the model, not just
> the Dedikind sets.
So by the above, this conjecture can be restated:
Conjecture: if ZF is consistent then there is a model of
ZF + there are Dedikind sets + there are no amorphous sets.
Regarding this, some months back there was a discussion in sci.math
about Sageev having constructed a ZF model in which there were
Dedikind sets and in which the Dedikind finite cardinals model PA.
(Dedikind finite cardinal: the cardinality of a Dedikind-finite set).
PA proves (for all n) (there exists m) [n = m+m or n = m+m+1].
So in Sageev's model, given any Dedikind set D, consider n = |D|, find
m, get two disjoint subsets of size m inside D. Since n is infinite
(by D Dedikind), either equation above gives m is infinite, so D
contains two infinite disjoint subsets, in other words D is not
amorphous.
So in Sageev's model, no Dedikind set is amorphous. But ZF proves
every amorphous set is Dedikind. So in Sageev's model, there are no
amorphous sets.
Sageev's model does have Dedikind sets, so Sageev's model is as
required in the conjecture above.
Sageev's construction was difficult, according to the sci.math
discussion. I would expect the conjecture above to have a simpler
construction.
Toward this, I posted on July 6 2000 to sci.logic "Cohen symmetric
choiceless ZF models" about methods of constructing choiceless ZF
models and related. One of these constructions was Fraenkel Mostowski
permutation models, models of ZFU, set theory with atoms rather than the
original ZF. These are easier than the Cohen symmetric ZF models.
I think I see how to make an FM model for the conjecture above.
Namely take atoms indexed by rational numbers: a_r for r rational.
Make a permutation group acting on these by permutations of rational
indices respecting the ordering on the rationals. Take a finite support
FM model over this group action on these atoms. (The terms are
explained in my other post).
It is direct to see N satisfies that A is Dedikind and not amorphous.
Namely Dedikind-infinite is equivalent over ZF to allowing an injection
of omega. Such an injection f : omega -> A can't have finite support,
otherwise permute elements of its range outside of the finite support.
On the other hand, the lower cut determined by a rational r has
support {r}, since the permutations respect the rational ordering. This
gives a subset of A refuting amorphous.
So N has a Dedikind set (A), and so far checking A to start no
amorphous set yet. I think I have a proof that there are no other
amorphous sets in N. So N would be a ZFU model supporting the ZFU
version of the conjecture above.
As I discussed in the previous article, Cohen's symmetric models is a
method of constructing ZF models having some similarity to FM models.
This suggests reworking the FM model to be a Cohen model. I can do this
as far as showing A is Dedikind and not amorphous. I don't yet see how
to show no other sets are amorphous.
As I mentioned last article, there is the Jech Sochar embedding
theorem, which can automatically do a limited amount of such transfers.
This does not seem to do enough for the job at hand though. It only
gives information about the resulting Cohen model up to some rank. To
see there are no amorphous sets we must know about all ranks.
So I still don't know a direct construction of the full ZF version of
the conjecture.
Bill Taylor
David Libert (ah...@FreeNet.Carleton.CA) writes:
> (The union of two Dedikind-finite sets is Dedikind-finite).
How do you prove this? (without some AC)
I've been turning it iver in my mind, but I seem to be too stupid.
Please help.
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Belief is the disease, knowledge the cure.
-------------------------------------------------------------------------------
Fred Galvin
> David Libert (ah...@FreeNet.Carleton.CA) writes:
>
> > (The union of two Dedikind-finite sets is Dedikind-finite).
>
> How do you prove this? (without some AC)
Suppose A and B are Dedekind-finite sets. If the union of A and B is
not Dedekind-finite, then it contains an infinite sequence of distinct
elements. But then some infinite subsequence of that sequence is
contained in A or B, contradicting the assumption that A and B are
Dedekind-finite. QED
David Libert
David Libert (ah...@FreeNet.Carleton.CA) writes:
>
> Conjecture: if ZF is consistent then there is a model of
> ZF + there are Dedikind sets + there are no amorphous sets.
>
> required in the conjecture above.
>
> Sageev's construction was difficult, according to the sci.math
> discussion. I would expect the conjecture above to have a simpler
> construction.
>
> Toward this, I posted on July 6 2000 to sci.logic "Cohen symmetric
> choiceless ZF models" about methods of constructing choiceless ZF
> models and related. One of these constructions was Fraenkel Mostowski
> permutation models, models of ZFU, set theory with atoms rather than the
> original ZF. These are easier than the Cohen symmetric ZF models.
>
> I think I see how to make an FM model for the conjecture above.
> Namely take atoms indexed by rational numbers: a_r for r rational.
> Make a permutation group acting on these by permutations of rational
> indices respecting the ordering on the rationals. Take a finite support
> FM model over this group action on these atoms. (The terms are
> explained in my other post).
>
> It is direct to see N satisfies that A is Dedikind and not amorphous.
> Namely Dedikind-infinite is equivalent over ZF to allowing an injection
> of omega. Such an injection f : omega -> A can't have finite support,
> otherwise permute elements of its range outside of the finite support.
>
> On the other hand, the lower cut determined by a rational r has
> support {r}, since the permutations respect the rational ordering. This
That should be support {a_r}.
> gives a subset of A refuting amorphous.
>
> So N has a Dedikind set (A), and so far checking A to start no
> amorphous set yet. I think I have a proof that there are no other
> amorphous sets in N. So N would be a ZFU model supporting the ZFU
> version of the conjecture above.
>
> As I discussed in the previous article, Cohen's symmetric models is a
> method of constructing ZF models having some similarity to FM models.
> This suggests reworking the FM model to be a Cohen model. I can do this
> as far as showing A is Dedikind and not amorphous. I don't yet see how
> to show no other sets are amorphous.
I think I have since seen how to do this last part. Earlier I did not
have any particular stumbling block, I just felt overwhelmed at
"Cohenizing" the previous FM model. Since then I realized this seems to
be a standard such argument.
There are some analogies to what I have in mind and Cohen's first
construction like this. There is an FM model to make an amorphous set
of atoms: namely a finite support model over a countable set of atoms
a_i for i in omega, with group action the full permutation group on
those atoms. So in the invariant FM model the countability of the atoms
is lost, ie any omega listing of atoms is not invariant and so excluded
from the symmetric model.
Cohen's first ~AC model was a Cohen symmetric reworking of this FM
model. Namely for each FM atom make a label a_i, i in omega. Make a
label for a the set of all these atoms. Also, for each orginal atom a_i
make countably many labels a_i,j as j varies over omega, to enumerate
the members of a_i. Make a group action: a is always fixed, the a_i 's
permute arbitrarily among themselves, the a_i,j 's permute consistently
with the a_i 's to preserve membership, with extra permutations allowed
among the j's, such permutation of j's depending on i.
Then Cohen reals are attached with finite support to all a_i,j 's.
The finite support notion for the Cohen symmetric model is finite
support among all the labels: equivalently finite support among the
bottom level labels: a_i,j 's.
The original FM model depended on permutations among the original
atoms a_i, reflecting the similarity of these atoms to each other. In
the Cohen version, there are to be corresponding permutations, to also
reflect corresponding similarities of the a_i 's. A complication in the
Cohen version is the forcing construction introduces differences among
the a_i 's by specifying membership information about the Cohen reals
a_i,j below the a_i 's. But the point is, any bounded stage of the
construction only specifies finitely much such membership information.
So for example adding at a bounded stage differences between a_i1,j1 and
a_i2,j1 does not make an essential difference between a_i1 and a_i2.
The exact identity of j1 as a subindex below a_i1 is meaningless as
compared to j1 below a_i2, because the group action has the extra layer
of permutations of j 's. So at a bounded stage a_i1 and a_i2 can still
be viewed as similar by considering a_i1,j1 to correspond to some other
a_i2,j2 rather than a_i2,j1. It is impossible by these considerations
to force a definitive difference between a_i1 and a_i2 at a bounded
stage of the construction. Combined with the other properties of the
forcing construction this is enough to mimic the original FM permutation
arguments.
So to rephrase again, the original FM model depended on similarites
among its atoms a_i, to allow permutation arguments and show certain
kinds of things could not be in the FM model because they can't be
sufficiently invariant. A ZF model can't have such similarity among its
sets as a ZFU model has among its atoms (no automorphisms). In Cohen's
symmetric models, it is the forcing that adds the extra structure to
make this final ZF dissimilarity. So the Cohen reworking of an FM
construction does not attach the forcing directly to the original FM
atoms a_i, but instead introduces a new layer of labels below: a_i,j,
and a new layer of group action on this layer specifically. This
insulates the a_i corresponding to the FM atoms from the assymmetries
forcing adds.
That is the background of the amorphous set construction as an FM
model and as a Cohen symmteric model.
Returing now to the Dedikind sets + no amorphous sets construction,
we had the FM model based on atoms a_r for r rational. (A different
set of atoms and group action than that discussed above with a_i 's).
The Cohen version will have labels a_r for r rational. We add new
labels a_r,j r rational, j in omega enumerating the members of the
respective a_r,j. The group action will permute the a_r among
themselves by rational order preserving permutation of indices, and
will permute a_r,j 's by consistently permuting r 's as from the
a_r 's and extra full permutation of omega on the j's, depending on r.
Add Cohen reals by finite support for each a_r,j. Take the finite
support Cohen symmetric model on this group action.
Then I think the arguments for everything non-amorphous from the FM
model (the arguments I have never written out) carry over in the
forcing context this way.
If this is all correct it says (modulo ZF consistent) that assuming
only over ZF that there are Dedikind sets is not enough for any
mathematical argument of any sort of counterexample to the original
topological claim.
Torkel Franzen
> Suppose A and B are Dedekind-finite sets. If the union of A and B is
> not Dedekind-finite, then it contains an infinite sequence of distinct
> elements.
It does?
Fred Galvin
Oh, did I get that wrong? Damn it, I used to know some basic set
theory, but it looks like I've lost it. All right, what's wrong with
the following argument. By definition, a Dedekind-finite set is a set
which is not equinumerous with any of its proper subsets. If X is not
Dedekind-finite, then X is equinumerous with some proper subset of
itself. Choose a proper subset Y of X which is equinumerous with X, a
bijection f:X-->Y, and an element x in X\Y. Then x, f(x), f(f(x)), ...
is an infinite sequence of distinct elements of X. What am I missing?
Torkel Franzen
>By definition, a Dedekind-finite set is a set
>which is not equinumerous with any of its proper subsets. If X is not
>Dedekind-finite, then X is equinumerous with some proper subset of
>itself. Choose a proper subset Y of X which is equinumerous with X, a
>bijection f:X-->Y, and an element x in X\Y. Then x, f(x), f(f(x)), ...
>is an infinite sequence of distinct elements of X. What am I
>missing?
Nothing at all! It was I who somehow got it into my head that
dependent choice was needed here, but I was thinking of the
proof, irrelevant in this context, that an infinite set is Dedekind
infinite.
Bill Taylor
|> Dedekind-finite, then X is equinumerous with some proper subset of
|> itself. Choose a proper subset Y of X which is equinumerous with X,
|> a bijection f:X-->Y, and an element x in X\Y. Then x, f(x), f(f(x)), ...
|> is an infinite sequence of distinct elements of X.
Aha! Very nice; very simple. So this little lemma, that every Ded-inf set has
a sequence of distinct elements in it, is what Torkel & I were both missing.
Now I don't feel quite so stupid, to be in such auspicious company.
As the converse is equally simple, indeed even simpler, it seems that a set
is Dedekind-infinite IFF it contains a subsequence of distincts.
Never knew that before. It makes Dedekind-(in)finiteness much simpler to think
about. In another thread, (or was it this same one?), someone was talking
about "amorphous" sets. These were Dedekind-finite but Cantor-infinite.
i.e. they had no bijection with any n, but no injection from N. Hmmm.
Amorphous indeed! No wonder most of us want to keep DC at least.
It strikes me now that there is (maybe) yet *another* degree of amorphousness.
It may be that a set has *no* injection from N into it, but still *does* have
a surjection *onto* N. That would be Dedekind-finite, but still somewhat
more infinite than merely Cantor-infinite.
Yikes!
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
N = 1 ==> P = NP
-------------------------------------------------------------------------------
Fred Galvin
> As the converse is equally simple, indeed even simpler, it seems
> that a set is Dedekind-infinite IFF it contains a subsequence of
> distincts.
Yes. That's how people usually think of Dedekind-infinite cardinals:
they are cardinals that are greater-than-or-equal-to omega, whereas
ordinary infinite cardinals are merely not-less-than omega.
> Never knew that before. It makes Dedekind-(in)finiteness much
> simpler to think about. In another thread, (or was it this same
> one?), someone was talking about "amorphous" sets. These were
> Dedekind-finite but Cantor-infinite. i.e. they had no bijection
> with any n, but no injection from N. Hmmm. Amorphous indeed! No
> wonder most of us want to keep DC at least.
>
> It strikes me now that there is (maybe) yet *another* degree of
> amorphousness. It may be that a set has *no* injection from N into
> it, but still *does* have a surjection *onto* N. That would be
> Dedekind-finite, but still somewhat more infinite than merely
> Cantor-infinite.
Such things can be. It's consistent with ZF that there is an infinite
set X such that P(X) is Dedekind-finite. On the other hand, there
certainly is a surjection from P(X) to N: map the n-element subsets of
X to n. Of course, P(P(X)) must be Dedekind-infinite.
Herman Rubin
Bill Taylor <mat...@math.canterbury.ac.nz> wrote:
.................
In another thread, (or was it this same one?), someone was talking
>about "amorphous" sets. These were Dedekind-finite but Cantor-infinite.
>i.e. they had no bijection with any n, but no injection from N.
This is not enough for amorphous. They need to have no
decomposition into two infinite sets.
David Libert
> On 27 Jul 2000, Bill Taylor wrote:
>
>> As the converse is equally simple, indeed even simpler, it seems
>> that a set is Dedekind-infinite IFF it contains a subsequence of
>> distincts.
>
> Yes. That's how people usually think of Dedekind-infinite cardinals:
> they are cardinals that are greater-than-or-equal-to omega, whereas
> ordinary infinite cardinals are merely not-less-than omega.
>
>> Never knew that before. It makes Dedekind-(in)finiteness much
>> one?), someone was talking about "amorphous" sets. These were
>> Dedekind-finite but Cantor-infinite. i.e. they had no bijection
>> with any n, but no injection from N.
This above just defined Dedekind sets: infinite but
Dedekind-finite. As Herman Rubin mentioned recently, amorphous has a
different definition: a set A is amorphous iff A is infinite and
every subset of A is either finite or cofinite in A. Equivalently, a
set A is non-amorphous iff A contains two disjoint infinite subsets.
>> Hmmm. Amorphous indeed! No
>> wonder most of us want to keep DC at least.
>>
>> It strikes me now that there is (maybe) yet *another* degree of
>> amorphousness. It may be that a set has *no* injection from N into
>> it, but still *does* have a surjection *onto* N. That would be
>> Dedekind-finite, but still somewhat more infinite than merely
>> Cantor-infinite.
>
> Such things can be. It's consistent with ZF that there is an infinite
> set X such that P(X) is Dedekind-finite. On the other hand, there
> certainly is a surjection from P(X) to N: map the n-element subsets of
> X to n. Of course, P(P(X)) must be Dedekind-infinite.
This is an interesting line to consider: P(X) being
Dedekind-finite, or equivalently for X infinite as just mentioned,
P(X) being Dedekind.
First I will review some relations of amorphous to Dedekind from my
recent posts, and then comment further on P(X) Dedekind.
I previously menitoned Con(ZF) -> Con(ZF + there is an amorphous
set). This was Cohen's first choiceless model in _Set Theory and the
Continuum Hypothesis_ .
I mentioned before without proof that ZF proves for all sets A
if A is amorphous than A is Dedekind. This follows from Fred's note
about the injection of omega into a Dedekind-infinite set. Ie given a
Dedekind-infinite set, inject omega, consider the range of this on
evens and odds, obtaining two disjoint infinite subsets, refuting
amorphous. So taking contrapositive, amorphous -> Dedekind finite.
The other clause of both "amorphous" and "Dedekind" is being infinite,
so that just carries through.
I mentioned before, the disjoint union of two Dedekind sets is
Dedekind and not amorphous, so ZF proves if there is a Dedekind set
then there is a Dedekind non-amorphous set.
I had a couple of recent posts noting without details my recent
proof Con(ZF) -> Con(ZF + there are Dedekind sets + there is no
amorphous set) .
So amorphous -> Dedekind but the reverse can fail on a case by case
basis and also as a general existence claim.
Turning now to the question of P(X) Dedekind for infinite X, I have
found ZF proofs of the following:
for all A P(A) is non-amorphous
for all A if A is amorphous then P(A) is Dedekind
for all A if P(A) is Dedekind then A is Dedekind.
Also, my basic ZF model construction above of Dedekind sets with no
amorphous sets, the basic Dedekind set D1 first constructed into the
model has P(D1) Dedekind. So it is possible to have D1 Dedekind and
non-amorphous with P(D1) Dedekind. So the implication above
P(A) Dedekind -> A Dedekind can't be improved to P(A) Dedekind -> A
amorphous.
So by D1 a non-amorphous Dedekind set can have Dedekind powerset.
On the other hand, another of Cohen's basic models was the most
extreme failure of AC possible: an omega sequence of two element sets
having no choice function.
In fact Cohen's example has the stronger property that the only
choice functions on subsets of his example are on finite subsets of
his countable set. Another fact which will simplify definitions in a
moment is two element sets enumerated at distinct locations in the
omega sequence are disjoint from each other.
This implies that D2 = the union of all Cohen's countably many two
element sets is Dedekind. Ie if D2 were Dedekind-infinite, an
injection of omega into D2 would give a choice function on infinitly
many two element sets by picking the member first enumerated by the
injection.
Cohen's original omega sequence of two element sets is an injection
of omega into P(D2), so P(D2) is Dedekind-infinite, ie P(D2) is not
Dedekind.
So D1 and D2 are each Dedekind sets, but P(D1) is Dedekind and
P(D2) is not. These arose from different Cohen symmetric models, but
the constructions can be combined with no conflict, so we can even get
a single ZF model with sets D1 and D2 as above in the same model.