Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Division without the axiom of choice
Replies: 10   Last Post: Jan 12, 2013 4:51 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Paul

Posts: 411
Registered: 7/12/10
Re: Division without the axiom of choice
Posted: Jan 12, 2013 3:40 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.