0
$\begingroup$

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

  • 1
    If it is not infinite? Do you have any concrete problem?2012-04-09
  • 2
    What kind of criterion are you looking for? Your question is far too general.2012-04-09
  • 1
    That could depend on lots of things...2012-04-09
  • 1
    You need to show that there exists no bijection between $A$ and $B$2012-04-09
  • 1
    Along the lines of what J.D. said, you can show that there is no injection from B to A, or no surjection from A to B.2012-04-09
  • 2
    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.2012-04-09
  • 0
    Sorry, 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?)2012-04-09
  • 2
    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).2012-04-09

3 Answers 3

0

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

  • 2
    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?2012-04-09
  • 0
    Yes you are right, this makes no sense.2012-04-10
4

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.

  • 1
    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.2012-04-09
1

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.

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.