37
$\begingroup$

Cantor defined countable sets as

A set is countable if there exists an injective function from the set to the set of natural numbers.

Still today countability is almost always defined in Cantor's words. Are the natural numbers really necessary to define countability. Most mathematicians admit that set theory is still a rich subject to study without getting into the conception of numbers. And I believe that the notion of countability is more fundamental than the set of natural numbers itself. Hence I wonder is it possible to define countability without referring the natural numbers?

Let $A$ be a set and let $S:A\rightarrow A$ be a successor function which is characterised by the following properties.

  1. Two different elements in $A$ can not have same successor.

  2. The successor of an element should not be its ancestor.

Shall I define countable sets as below?

A set is countable if there exists a successor function as characterised above.

$\endgroup$
  • 11
    $\begingroup$ for the set $\mathbb R$ isn't the function $S(x)=x+1$ a successor function? $\endgroup$ – lulu Mar 12 '17 at 11:41
  • 5
    $\begingroup$ Well, $\mathbb N$ seems pretty fundamental to me. I don't see any way to dodge it that doesn't just end up being a just a way to disguise it. Doesn't mean there isn't a way, of course. $\endgroup$ – lulu Mar 12 '17 at 11:48
  • 8
    $\begingroup$ "And I believe that the notion of countability is more fundamental than the set of natural numbers itself." Out of curiosity, why do you believe that? I certainly think the exact opposite. $\endgroup$ – Noah Schweber Mar 12 '17 at 15:34
  • 1
    $\begingroup$ @Noah Schweber The literal meaning of count or countability must be ignored. I don't know whether current mathematical definition for countability is rooted in that literal meaning. If that meaning is ignored then my belief may have some sense. $\endgroup$ – Durgadass S Mar 12 '17 at 15:54
  • 7
    $\begingroup$ @DurgadassS I guess I still don't understand - why do you expect countability to be more natural than the natural numbers? What property of countability stands out? I'm just curious where you're coming from in this regard. That is - what is your interest in this question motivated by in the first place? $\endgroup$ – Noah Schweber Mar 12 '17 at 15:56
68
$\begingroup$

Yes. You can. Depending on the available tools.

  1. A set $A$ is countable if and only if whenever $B\subseteq A$ and $|B|<|A|$, then $B$ is finite. If you want countable to refer only to infinite sets, then you can also add that there is a proper subset of $A$ which is equipotent with $A$.

    Now, you might argue that finiteness depend on the natural numbers, but don't worry, Tarski got you covered: $X$ is finite if and only if the partial order $(\mathcal P(X),\subseteq)$ is well-founded.

  2. A set $A$ is countable if and only if it can be linearly ordered such that every proper initial segment is finite. Again, if you are only interested in infinite sets, add the requirement that there is no maximal element.

| cite | improve this answer | |
$\endgroup$
  • 20
    $\begingroup$ Interestingly, this whole thing doesn't even require the axiom of choice! $\endgroup$ – Asaf Karagila Mar 12 '17 at 11:52
  • $\begingroup$ Using this definition, is it possible to prove $\mathbb{R}$ is uncountable? If so can you give some links to such proofs $\endgroup$ – Durgadass S Mar 12 '17 at 13:53
  • 2
    $\begingroup$ Why wouldn't you? You asked for equivalent definitions of countability which do not presuppose some notion of natural numbers. But the definition are still equivalent. More importantly, though, is how do you define the real numbers without the natural numbers? $\endgroup$ – Asaf Karagila Mar 12 '17 at 13:54
  • 2
    $\begingroup$ @Francis: No, you can prove without choice that $\aleph_0$ is the only infinite cardinal which is minimal. I never claimed, in that definition, that it is the minimum. $\endgroup$ – Asaf Karagila Mar 12 '17 at 18:37
  • 1
    $\begingroup$ @Martin: Well, this is a nifty little thing about the natural numbers, it is the unique linear order which is without a maximum, but every proper initial segment is finite. Once you establish that a finite set has no self injections which are not bijections, you immediately get a unique matching between elements based on the cardinality of the initial segments they define. This is essentially the same argument you'd use "normally", only here we hide the natural numbers as "finite cardinalities" without being too specific about them. $\endgroup$ – Asaf Karagila Mar 12 '17 at 21:06
27
$\begingroup$

Two sets are equipotent iff there is a bijection between them.

A set is finite iff it admits a total ordering in which every nonempty subset has a least element and a greatest element; otherwise it is infinite.

(Alternatively, a set $A$ is infinite iff the set $\mathcal P(\mathcal P(A))$ is equipotent to a proper subset of itself.)

A set is countable (finite or countably infinite) iff all of its infinite subsets are equipotent.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm sure this is a stupid question, but -- why do you need to invoke $\mathcal P$? I'd have thought that a set is infinite if and only if it is equipotent to some proper subset of itself. $\endgroup$ – ruakh Mar 13 '17 at 1:11
  • $\begingroup$ Ah, that makes sense -- thanks! $\endgroup$ – ruakh Mar 13 '17 at 2:18
  • 1
    $\begingroup$ Aw, I liked the $\mathcal P(\mathcal P(X))$ characterization ... $\endgroup$ – hmakholm left over Monica Mar 13 '17 at 12:50
  • $\begingroup$ @bof Wouldn't it be even simpler to say that X is infinite iff X can be injected to a strict subset of itself (e.g. X minus a singleton)? $\endgroup$ – Alexandre Halm Mar 14 '17 at 12:57
  • 1
    $\begingroup$ @AlexandreHalm Yes, but I wanted to avoid using the Axiom of Choice. You need AC to prove that every infinite set can be injected to a proper subset of itself. However you don't need AC to prove that the second power set $\mathcal P(\mathcal P(X))$ of an infinite set $X$ can be injected to a proper subset of itself. $\endgroup$ – bof Mar 14 '17 at 21:44
12
$\begingroup$

No that does not work. Even if you add a condition that there is an element (representing $0$) that is not the successor of anything), the definition would still claim that, for example $$ (\mathbb R \setminus \mathbb Z) \cup \mathbb N $$ is countable, just by defining "successor" as the usual $x\mapsto x+1$.


What modern (since the early 1900s) set theory actually does does not depend directly on the natural numbers:

  1. A set $A$ is called inductive iff $\varnothing \in x$, and for every $x\in A$ it holds that $x\cup\{x\}\in A$ too.

  2. There's an explicit axiom of set theory promising that at least one inductive set exists.

  3. The intersection of all inductive sets is called $\omega$.

  4. A set is called "countable" if it is in bijective correspondence with (some subset of) $\omega$.

It turns out that the elements of $\omega$ are good candidates for representing the natural numbers within set theory, so usually we end up defining $\mathbb N$ to be an alternative name for $\omega$ -- but countability does not actually depend of the number-ness of $\omega$'s elements. (It doesn't care about arithmetic, for example).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I agree that $\omega$ represents $\mathbb{N}$ and $\mathbb{N}$ acts as a name for $\omega$. And I know that the pure set theoretic construction of $\mathbb{N}$ exists. Actually what I am intended to ask is "Is it possible to define countability without such creatures even though they are pure set theoretic". For example defining order relation (as a consequence defining ordered set) without referring order-able numbers (or the set theoretic equivalence of such order-able numbers). $\endgroup$ – Durgadass S Mar 12 '17 at 12:15
  • $\begingroup$ @DurgadassS: I think bof's answer is a good response to that. $\endgroup$ – hmakholm left over Monica Mar 12 '17 at 12:25
3
$\begingroup$

A set $S$ is countable iff $S$ injects into every set $T$ that non-surjectively injects into $T$.

Basically, $S$ is countable iff $S$ is no larger than every infinite set.

A set is countable if there exists a successor function as characterised above.

Henning Makholm already explained why this is wrong, but I wish to point out that it is because you did not get an equivalence. If a set is countable then there exists a successor function like you said, but the converse does not hold.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand your point. Also my characterisation is incomplete (or wrong). The question actually is whether it is possible to characterise such a function. If the name "successor" bothers then lets call it something like "counter function". $\endgroup$ – Durgadass S Mar 13 '17 at 17:35
  • $\begingroup$ @DurgadassS: Hmm if you're asking about characterizing the successor function then it is a vastly different question as compared to defining countable. My answer provides a definition of countable, and it is only incidental that any successor-like operator on $T$ would be a non-surjective injection from $T$ into itself. $\endgroup$ – user21820 Mar 13 '17 at 17:53
  • $\begingroup$ Yes I now realise the vast difference. However it seems this question is of significant interest and I don't disturb it. $\endgroup$ – Durgadass S Mar 13 '17 at 18:00
  • $\begingroup$ Wait, how is this different than what bof and I wrote? $\endgroup$ – Asaf Karagila Mar 13 '17 at 22:09
  • $\begingroup$ @AsafKaragila: Um my answer is definitely different from bof's, since his/hers is essentially "$S$ is countable iff every pair of infinite subsets of $S$ can be put in bijection." Secondly, both of your answers involve the use of linear orderings, which is not used in my answer. Also it's a more succinct definition, to a certain extent. =) $\endgroup$ – user21820 Mar 14 '17 at 2:42
1
$\begingroup$

If you're working in a constructive theory, then the concepts of denumerable (countable) and recursively enumerable (semidecidable) precisely coincide, so you can avoid direct reference to the natural numbers that way.

Certainly, if a set is recursively (computably) enumerable, then it is countable. A simple counting algorithm that outputs the members of the set can be used to demonstrate this fact. This works even in a classical setting, of course.

Now, if a set is countable, then the construction (in some formal system) of its characteristic function provides an algorithm for deciding the set, by the Curry-Howard correspondence. Thus the set is recursive. (The Curry-Howard correspondence, by virtue of being an isomorphism, can be used to show the converse too, but I wanted to show that the converse holds even in a classical theory, as per above.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please explain the downvote: don't just drive by! $\endgroup$ – Noldorin Mar 13 '17 at 3:41
  • 1
    $\begingroup$ +1 but can you give an example of such a theory or framework? I've never heard of such a thing, though it sounds interesting. $\endgroup$ – goblin Mar 13 '17 at 3:59
  • 6
    $\begingroup$ I am unsure how one would develop the theory of recursive enumerability without mentioning natural numbers at no point. Would you mind giving some more details? $\endgroup$ – Wojowu Mar 13 '17 at 5:21
  • $\begingroup$ @goblin, Well, any constructive system should do the job, I believe. Specifically, intuitionistic logic. $\endgroup$ – Noldorin Mar 13 '17 at 18:09
  • 2
    $\begingroup$ If you are dealing with Turing machines, I would argue natural numbers, or for that matter integers, come in when defining this computation model because of the tape. As for lambda calculus, I would agree natural numbers don't sneak in in any obvious way. $\endgroup$ – Wojowu Mar 13 '17 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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