Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
If it is not infinite? Do you have any concrete problem? –  Michael Greinecker Apr 9 '12 at 14:40
2  
What kind of criterion are you looking for? Your question is far too general. –  user20266 Apr 9 '12 at 14:40
1  
That could depend on lots of things... –  Thomas Apr 9 '12 at 14:40
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. –  bgins Apr 9 '12 at 14:46
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). –  Michael Greinecker Apr 9 '12 at 15:02
show 3 more comments

3 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

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.

share|improve this answer
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. –  Asaf Karagila Apr 9 '12 at 23:25
add comment

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

share|improve this answer
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? –  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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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