Is the Axiom of Choice Necessary to Well-Order Finite Sets?

[Csharp]

Hi,

I want to show that there exists a well ordering for every finite set.

(I know if you add axiom of choice you can prove this theorem for infinite sets too but I think the finite sets do not need axiom of choice to become well ordered)

 

[Deveno]

Have you tried using induction on the cardinality of the set?

 

[Csharp]

Good idea.

Suppose that k is well ordered.

k+1= k U {k}

First of all I'll define an ordering on k+1.
If s and t are both in k then I use the ordering from k.
If one of s and t is k then k>s.

Suppose that S is a nonempty subset of k+1.
Then if it doesn't contain k it has a lowest member.
If it contains k then S-{k} has a lowest member which is also lower than k itself.

 

[Evgeny.Makarov]

I want to show that there exists a well ordering for every finite set.

Every total order on a finite set is a well-ordering.

 

[blue_raver22]

Hello,

You are correct, the axiom of choice is not necessary to prove the existence of a well ordering for finite sets. In fact, the well ordering principle is one of the fundamental axioms of set theory, and it guarantees the existence of a well ordering for any set, finite or infinite.

To prove the existence of a well ordering for finite sets, we can use mathematical induction. First, we show that the empty set is well ordered by default. Then, we assume that any set with n elements is well ordered, and we show that any set with n+1 elements is also well ordered. This can be done by constructing a well ordering for the set with n+1 elements from the well ordering of the set with n elements.

Therefore, we can conclude that every finite set has a well ordering, without needing to invoke the axiom of choice. However, as you mentioned, for infinite sets, the axiom of choice is needed to guarantee the existence of a well ordering.

I hope this helps clarify the concept of well ordering for finite sets. Thank you for your question.