Paul
Posts:
258
Registered:
7/12/10
|
|
Re: Division without the axiom of choice
Posted:
Jan 12, 2013 3:40 AM
|
|
On Saturday, January 12, 2013 1:18:40 AM UTC, Butch Malahide wrote:
> On Jan 11, 2:01 pm, pepste...@gmail.com wrote:
>
> > On Friday, January 11, 2013 12:59:39 AM UTC, Butch Malahide wrote:
>
> > > On Jan 10, 4:15 am, pepste...@gmail.com wrote:
>
> > > > Let A and B be sets. Assume ZF without assuming choice. Then, for all [positive] integers n, I believe (correct me if I'm wrong) that, if n x A is equipotent to n x B, then A is equipotent to B.
>
> >
>
> > > Yes, that is correct. More generally, it is proved in ZF that, for any
>
> > > cardinals a and b, and any nonzero finite cardinal (i.e. natural
>
> > > number) n, the inequality na <= nb implies a <= b. (This implies the
>
> > > proposition you asked about, in view of the well known fact that a = b
>
> > > <-> a <= b & b <= a.)
>
> >
>
> > > > There's a famous Conway/Doyle paper which proves this for n = 2 and n = 3.
>
> > > > However, it doesn't seem rigorous or clear and I have trouble understanding it.
>
> >
>
> > > I don't know the Conway/Doyle paper, and I don't know a proof for n =
>
> > > 3. A proof for n = 2 has been posted in this newsgroup:
>
> >
>
> > >http://groups.google.com/group/sci.math/msg/1e65b64fee74fe07?hl=en
>
> >
>
> > > > Does anyone know a more axiomatic treatment? (I don't have access to a university, and I'm not in the market for maths purchases, so only free references would be helpful.)
>
> >
>
> > > The following summary and references are cribbed and paraphrased from
>
> > > p. 174 of Waclaw Sierpinski's book Cardinal and Ordinal Numbers,
>
> > > second edition revised, Warszawa, 1965. The theorems are theorems of
>
> > > ZF (standard set theory without the axiom of choice); m and n are
>
> > > arbitrary cardinals (i.e., if they are infinite, they are not
>
> > > necessarily alephs); k is a natural number. The theorems you are
>
> > > interested in are:
>
> >
>
> > > THEOREM 1. If km = kn then m = n.
>
> >
>
> > > THEOREM 2. If km <= kn then m <= n. [TYPO CORRECTED]
>
> >
>
> > > F. Bernstein, Untersuchungen aus der Mengenlehre, Math. Annalen 61
>
> > > (1905), 117-155. [Proves Theorem 1 for k = 2 and outlines a proof for
>
> > > general k.]
>
> >
>
> > > W. Sierpinski, Sur l'egalite 2m = 2n pour les nombres cardinaux, Fund.
>
> > > Math. 3 (1922), 1-16. [Another proof of Theorem 1 for k = 2.]
>
> >
>
> > > W. Sierpinski, Sur l'implication (2m <= 2n) -> (m <= n) pour les
>
> > > nombres cardinaux, Fund. Math. 34 (1947), 148-154. [Proof of Theorem 2
>
> > > for k = 2.]
>
> >
>
> > > A. Tarski, Cancellation laws in the arithmetic of cardinals, Fund.
>
> > > Math. 36 (1949), 77-92. [Proof of Theorem 2 in general.]
>
> >
>
> > > I guess Tarski's 1949 paper has what you're looking for. I don't know
>
> > > if it's available as a free etext; I'm inclined to doubt it, but I
>
> > > haven't looked. On the other hand, I bet your local public library can
>
> > > get you a copy at nominal cost by interlibrary loan.
>
> >
>
> > Thank you for this very helpful reply. I'm afraid that I'm not convinced by the proof for the case n = 2 on > the other thread. I suppose I could try to fill in the details but I do this type of maths for enjoyment,
>
> > and I enjoy the process of reading through complete proofs more than I enjoy working out the details.
>
>
>
> > So what are these missing details I'm referring to? The answer is that it doesn't seem at all transparent
>
> > to me that, in the infinite case, almost all the horses get matched at some finite stage. (The finite case > is fine).
>
>
>
> Looks like one detail to me. Let me try to explain that one to you, so
>
> you can enjoy the proof.
>
>
>
> Hmm. The statement "[k]eep doing this until either all horses have
>
> been paired off, or else you are left with just one horse" might be
>
> ambiguous. I can see how someone might take it to meen that, after a
>
> FINITE number of steps, all or all but one of the horses will have
>
> been matched. No, the process is supposed to continue as long as
>
> necessary, an infinite number of steps if that's what it takes. The
>
> claim is that, when the process has run to completion, there will be
>
> at most one unmatched horse (in each connected component). That is,
>
> each horse (with at most one exception) gets matched after some finite
>
> number of steps, but that number varies from one horse to another, and
>
> is not necessarily bounded.
>
>
>
> Assume for a contradiction that two or more horses (in the same
>
> component) remain unmatched after an infinite sequence of steps. Call
>
> one of them Admiral, and call his nearest unmatched neighbor Biscuit.
>
> Every horse between Admiral and Biscuit got matched at some finite
>
> stage. Since there were only a finite number of horses between A and B
>
> to start with, there was some finite stage when *all* horses between A
>
> and B had been matched. (So A and B are horses of opposite colors,
>
> because there were initially an even number of horses between them.)
>
> Now it's clear that, after at most 4 more steps, A and B would have
>
> been matched with each other, unless one of them got matched with
>
> another horse first. Q.E.D.?
>
>
>
> An easy modification of this argument shows that 2m <= 2n implies m <=
>
> n.
Thanks, Fred.
This is a much clearer exposition than the Conway/Doyle one in www.math.dartmouth.edu/~doyle/docs/three/three.pdf and I now completely understand the proof. It might be worthwhile submitting your argument for publication (I'm guessing that it's your proof or your exposition).
Initially I missed the induction argument at the end of your most recent post.
However, I did get one thing right initially. When I said "The answer is that it doesn't seem at all transparent to me that, in the infinite case, almost all the horses get matched at some finite stage," I meant that it didn't seem transparent to me that almost all horses have the property that they get matched at a finite stage. I did not mean to imply that I believed that some finite stage existed at which point almost all the horses were matched.
Anyway, all is clear now which makes me happier.
Thanks again,
Paul
|
|
