Re: Definition of Axiom of Choice?

From: KRamsay (kramsay_at_aol.com)
Date: 09/08/04 

Date: 08 Sep 2004 06:48:48 GMT

In article <1e068d95.0409071500.52fed1e1@posting.google.com>,
ntspam2@netscape.net (Nathan) writes:
|This ranking is not uncontroversial; I'm sure different people have
|different favorite equivalents for AC. My favorite is:
|
|Given any two sets, there exists a surjection of one onto the other.

Given any two *nonempty* sets. There is no surjection from {} to {0}
or from {0} to {}.

|I think it's called Cardinal Trichotomy, but someone will surely
|correct me if I'm wrong.

It's similar, but not quite the same thing.

I think in the absence of AC, cardinality is usually defined in
terms of injections, not surjections. Cantor defines it essentially
this way. He defines equal cardinality in terms of one-to-one
correspondence, and then defines the cardinality of A to be less than
that of B if there is a subset of B equivalent to A but not vice-versa.

The fact that if there exists a surjection from B to A, then there
exists an injection from A to B, is a relatively minor variation on
the axiom of choice. On the other hand, the fact that if there is an
injection from A to B, and A is nonempty, then there is a surjection
from B to A is just the law of excluded middle. (Send elements in the
image of A to the unique elements they came from; send the other
elements of B to some given element of A.) So it's easier to see that
cardinal trichotomy implies the version you like than to go the other
way.

I believe cardinal trichotomy as usually stated also bundles in the
Cantor-Bernstein theorem. Once we know that either there is an
injection from A to B or from B to A, we get three cases. The fact
that in the case where injections in both directions exist, there is
a bijection (and hence |A|=|B|) is the Cantor-Bernstein theorem.

|My intuition of the way sets should behave
|forces me to accept this formulation of the axiom. In this it is far
|superior to either Zorn's Lemma or the Well-Ordering Theorem,
|although they are certainly much more useful for proving theorems.

I'm not sure whether to like or dislike this intuition! I'm amused
by it in any case.

The only proofs I've heard of that pass between Cardinals being
ordered and the axiom of choice go by way of well-ordering. If
cardinals are linearly ordered, then they all have to fit into the
ordering of the alephs, i.e. the cardinalities of ordinal numbers,
or equivalently of well-orderable sets. This can be shown to imply
they are well-ordered. Conversely, if every set is well-orderable,
that shows its cardinality belongs to the linear ordering of the
alephs.

Without assuming choice, there is the concept of the Hartog's
ordinal of a set, the smallest ordinal without an injection to
the set. I don't know how far the theory of cardinals in the
absence of choice has been developed. I suppose people working
with determinacy need some knowledge of this, don't they? In a
model of the axiom of determinacy (which might be a submodel of
the real universe, hence relevant to it) the axiom of choice fails.

Without assuming the law of excluded middle, there are still two
partial orders given by injections and surjections between sets.
I don't know whether anyone has put serious effort into that theory
at all.

Keith Ramsay

Relevant Pages

  • Re: Z-Cardinality
    ... Cantors definitions are biased to equality. ... Cardinality didn't come all from nothing, it was defined for fullfill a ... In a sense that if set A have as many members as set B then they are ... injection from B to A without having equal z-cardinalities. ...
    (sci.math)
  • Re: an important set theory post
    ... set of natural numbers, to has cardinality 2^aleph_0. ... I believe the fact that there is no injection from this ... salvaging non-constructive mathematics for constructive ... prove constructively that the set of well-orderings on a ...
    (sci.math)
  • Re: About Cardinality and Set Size:
    ... Frege's definition of cardinality of x is that card x ... card x = card y if there exist an injection from x ... many members a set has, ... Five basic intuitive notions about numerousity of ...
    (sci.math)
  • Re: About Cardinality and Set Size:
    ... Frege's definition of cardinality of x is that card x ... card x = card y if there exist an injection from x ... many members a set has, ... Five basic intuitive notions about numerousity of ...
    (sci.math)
  • Re: Set Theory-Axiom of Congruence.
    ... > sets is always greater than the cardinality of any proper subset of it. ... "axiom" can easily be proven. ... The inclusion map is an injection from a ...
    (sci.math)
Loading