Does counting make sense?

Question

The Bertrand Russells and Alfred Whiteheads of this world have written lengthy proofs that $1+1=2$, etc. (and one should hope their purpose was to illuminate some point about mathematical logic rather than to convince the public that $1+1$ really is $2$).

So suppose we regress to some point near the bottom of our epistemic edifice and ask this: suppose we count the members of a finite set and ascertain its cardinality, and then count them again in a different order. Must we get the same result? In proving that we must, we cannot use things not reasonably expected to have been established at that stage of the game. And if we don't always get the same result, then the whole concept of cardinality of a finite set makes no sense.

What is the state of present understanding of this question and its answers?

Answer 1

I do not know if this counts as a proof for you (I might be getting your question all wrong), but I guess it would be easy to formalize for a mathematician for any definition of counting or pairing). Start with the objects in a bag. Count them, and as you do put them in order on a labeled line, the line has two labels, the naturals (labels already there), and the identity of the object that lands there the first time you count (that you add the first time you count). Now every time you count you put each objects on the position that has its own label. You will always end up with the objects in their initial order and will reach always the same natural number label.

Answer 2

Suppose, toward a contradiction, that by counting the same finite set $S$ twice, you get two different results, say the two natural numbers $m<n$. So your counting has produced two bijections, one between $S$ and $\{1,2,\dots,m\}$ and one between $S$ and $\{1,2,\dots,n\}$. Composing the one bijection with the inverse of the other, you get a bijection from the set $\{1,2,\dots,n\}$ to a proper subset $\{1,2,\dots,m\}$. The crux of the proof is then to show, by induction on $n$, that there is no one-to-one map of $\{1,2,\dots,n\}$ into any proper subset of itself.

The basis of the induction, $n=0$, is trivial, as the empty set has no proper subset. For the induction step, assume the result for $n$ and suppose $f$ were a counterexample for $n+1$. Modifying $f$ slightly (changing just one or at most two values), you can arrange that $f(n+1)=n+1$. Then, being one-to-one, $f$ has to map $\{1,2,\dots,n\}$ into itself and therefore onto itself (by induction hypothesis). But then $f$ maps $\{1,2,\dots,n+1\}$ onto itself as well.

I've assumed here that a reasonable notion of natural number is available; that seems to be implicit in your reference to counting. It might, however, be useful to observe that the "meat" of the argument works even without natural numbers. Specifically, one can define finiteness by saying that a set $S$ is finite iff, whenever $X$ is a family of subsets of $S$ containing $\varnothing$ and $x\cup\{s\}\in X$ for all $x\in X$ and $s\in S$, then $S\in X$. (In other words, $S$ can be obtained from $\varnothing$ by repeatedly adjoining single elements.) With this definition, one can show, by essentially the same argument as above, that there is no one-to-one map from a finite set into a proper subset of itself.