Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is well known that certain properties of infinite sets can only be shown using (some form of) the axiom of choice. I'm reading some introductory lectures about ZFC and I was wondering if there are any properties of finite sets that only hold under AC.

share|cite|improve this question
    
In the formulation of AC, where we choose an element from each set $S_{i}, (i \in I)$, the cardinality of each $S_i$ does not matter. The axiom of choice is only necessary when the index $I$ is infinite. – basket Feb 16 at 8:49
3  
The statement, that every finite set of sets has a choice function is actually a theorem of $\mathsf{ZF}$. – Stefan Perko Feb 16 at 8:49
    
2  
As stated, this question is pretty vague. Let's say there is some set $X$ that cannot be well-ordered. Then $\{X\}$ is a finite set with the property that its unique element cannot be well-ordered... However, this property is ultimately about an infinite set, namely $X$. If we restrict ourself to hereditarily finite sets, then there are no such examples. Since the set of all hereditarily finite sets admits a definable well-order. – Stefan Feb 16 at 8:52

There are two remarks that may be relevant here.

(1) This depends on what you mean by "finite sets". Even for (infinite setts of) pairs the axiom of choice is does not follow from ZF if one looks at an infinite collection. This is popularly known as the "pairs of socks" version of AC which is one of the weakest ones.

(2) If you mean that the family of sets itself is finite, then AC can be proved in ZF by induction, i.e., it is automatic, but this is only true if your background logic is classical. For intuitionistic logic, the axiom of choice can be very powerful even for finite sets. For example, there is a theorem that the axiom of choice implies the law of excluded middle; in this sense the introduction of AC "defeats" the intuitionistic logic and turns the situation into a classical one.

share|cite|improve this answer

The usual properties of finite sets are still true without the axiom of choice.

  1. If $A$ is a finite set, then every function $f\colon A\to A$ is injective iff it is surjecitve iff it is bijective.

  2. If $A$ is a finite set of non-empty sets, then there is a choice function from $A$.

  3. If $A$ is a finite set, then every partial order on $A$ has a maximal element; every two linear orders on $A$ are isomorphic; etc.

  4. The power set of a finite set is finite, and a subset of a finite set is finite.

All these proofs don't use the axiom of choice at all. However the axiom of choice comes into play at two points:

  1. You have an infinite family of finite sets. Then you might need the axiom of choice in order to say something. But this is because we left the realm of finite sets, the family of sets is now infinite.

  2. There are characterizations of finiteness which are not necessarily true anymore. There might be an infinite set $A$ such that every $f\colon A\to A$ is injective if and only if it is bijective, and so on.

    So now there are several notions of finiteness. The term "finite" in choiceless contexts usually means a set which is in bijection with a bounded set of natural numbers. And we can talk about finiteness using Dedekind's characterization with injective functions (as above), and there is a whole spectrum in between.

share|cite|improve this answer
    
I'm bracing myself for the answer being above me, but why say "in bijection with a bounded set of natural numbers" rather than "in bijection with a natural number"? Are there models of ZF that have bounded sets of natural numbers not in bijection with any natural number? – Steve Jessop Feb 16 at 14:19
    
Steve, at this level it is often the case that people don't entirely think of the natural numbers as sets. So you can say proper initial segment, you can say bounded subset, or you can say a finite ordinal or a natural number. It's all the same even without choice. – Asaf Karagila Feb 16 at 14:30
1  
Ah, OK. Thanks. You had me worried for a minute there ;-) – Steve Jessop Feb 16 at 14:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.