# Does counting make sense?

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?

• If you want to be formal, you probably want to give a formal definition of what it means to "count" a set in a certain order.
– anon
Commented Jul 7, 2014 at 22:50
• But sometimes the question of what is the right way to be formal is part of the question. Commented Jul 7, 2014 at 23:02
• If you believe induction is "true" in an epistemological sense, then it should be the same result. Since we can prove this by induction. So the real question is whether or not induction is a valid principle. This question is not foundational, as it is philosophical. But I feel it might be at the edge of reasonable topics for this website, if not perhaps after that edge. Commented Jul 8, 2014 at 4:42
• Looking at this from (a sort of) anthropic principle: if counting doesn't make sense, you will find mathematicians up in arm to insert in an axiom to ensure that it does. This fall under the same category as question like "does number 0 exist" or "why real line is connected": these properties are what we know intuitively and expect them to be true in our system, so if they are not, axioms will be added to ensure they are, because we build axioms to ensure they are true.
– Gina
Commented Jul 8, 2014 at 6:42
• I do not agree with your statement : "their purpose was to illuminate some point about mathematical logic rather than to convince the public that 1+1 really is 2". Their purpose was to prove that all of existing (one century ago) mathematics can be "rewritten" and proved starting from a basic "formalized" language with only some (few) axioms regarding which they hoped to convince (themselves and) the readers about their "logical" nature (i.e. a priori and evident). The philosophical project as failed; the mathematical achievement is remarkable. Commented Jul 8, 2014 at 12:24

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.

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.