# When is a subset of a countable set finite?

Suppose I have a countable set B, and a subset of it called A. I would like to know when is A finite.

From the comments: B is an infinite set. I know that B is equivalent to the natural numbers so every subset of B is either countable (when there exists a bijection between A and B) or A is a finite set (when? - Does it happens if there is no bijection from A to B?) – JanosAudron 10 mins ago

-
If it is not infinite? Do you have any concrete problem? – Michael Greinecker Apr 9 '12 at 14:40
What kind of criterion are you looking for? Your question is far too general. – user20266 Apr 9 '12 at 14:40
That could depend on lots of things... – Thomas Apr 9 '12 at 14:40
Certainly when $B$ is finite. Otherwise, it completely depends on $A$. For example, any countable set $B$ can be put in bijection with $\mathbb{N}$. Which subsets $A$ of $\mathbb{N}$ are finite? One characterization is that $A$ must be bounded, i.e. have a finite maximal element. So in general, if $\phi:B\to\mathbb{N}$ is a bijection, then $A\subset B$ is finite iff $\phi(A)$ is bounded. – bgins Apr 9 '12 at 14:46
Yes. Because any set in bijection to an infinite set is infinite. For $A$ to be infinite, it suffices for there to be a surjection from $A$ onto $B$ or a injection from $B$ into $A$ (the first requires some form of choice). – Michael Greinecker Apr 9 '12 at 15:02

Recall that if $S\subseteq\mathbb N$ then $S$ is finite if and only if $S$ is bounded, namely there is some $k\in\mathbb N$ such that for every $n\in S$ we have $n<k$.

We can use transfer this property to $B$. If $B$ is finite, well $A$ has to be finite. However if $B$ is infinite then there is a function $f\colon\mathbb N\to B$ which is a bijection, we can therefore write $b_n=f(n)$, and therefore $B=\{b_n\mid n\in\mathbb N\}$.

Now $A\subseteq B$ is finite if and only if there is some $k\in\mathbb N$ such that if $b_n\in A$ then $n<k$.

-

There are many definitions of finitude. Consider the following, due to Dedekind:

A set $A$ is finite iff there is no bijection between $A$ and any proper subset $B \subset A$.

Then there is also this definition from Tarski's 1924 paper:

A set $A$ is finite iff every nonempty family of its subsets has a minimal element.

Finally, and perhaps most obviously for your purposes, a set $A$ is finite just in case there is a bijection between $A$ and an initial segment of the natural numbers.

-
Normally we say that a set is finite if it is bijectible with a finite von Neumann ordinal. While Tarski's definition really does coincide with our notion of finite, the equivalence of Dedekind's definition requires a small piece of the axiom of choice. If one changes Tarski's definition to "...every chain has a maximal element" then one again reaches a point where the axiom of choice is needed. To compensate the axiom of choice we can use the power set operation, though. $A$ is finite if and only if $P(P(A))$ is Dedekind-finite. – Asaf Karagila Apr 9 '12 at 23:25

Equip $B$ with the discrete topology. Then a subset $A$ is finite if and only if it is compact in this topology.

-
But how would you define compact? The cleanest definition would be "Every open cover have a finite subcover" in which case you run into a circular definition because what is a finite subcover? – Asaf Karagila Apr 9 '12 at 23:22
Yes you are right, this makes no sense. – Mustafa Gokhan Benli Apr 10 '12 at 19:24