0
$\begingroup$

I understand that a set A is at most countable if A is finite or countable.

I also understand that A is finite if A is equivalent to J(n) for some positive integer n and A is countable if A is equivalent to J, where J is the set consisting of all positive integers.

Following these definitions, is it possible for a set to be both finite and countable? (Presumably not since countable sets are equivalent to J, which happens to be infinite.)

Is it possible for a set to be finite but not countable? (Presumably always true, since countable sets are equivalent to J, which is infinite.)

Is it possible for a set to be countable and infinite? (Presumably always true, since countable sets are equivalent to J, which is infinite.)

Does it mean that finite sets are always at most countable and countable sets are also always at most countable, and finite sets are uncountable and countable sets are infinite?

$\endgroup$
  • $\begingroup$ Where do you find this definition of countable ? see for example en.wikipedia.org/wiki/Countable_set. A set is countable if it has a bijection with a subset of the natural numbers (which could be the whole set of natural numbers). $\endgroup$ – Tom Collinge Aug 7 '14 at 8:16
  • $\begingroup$ @TomCollinge Look at the second paragraph of that article. Some books don't count finite sets as countable. $\endgroup$ – zrbecker Aug 7 '14 at 8:31
  • $\begingroup$ @Danikar. Thanks, I'd never seen that definition (nor noticed it in the wiki article). $\endgroup$ – Tom Collinge Aug 7 '14 at 9:46
5
$\begingroup$

Is it possible for a set to be both finite and countable?

No. The set of natural numbers $\mathbb N$ (which you for some reason denote $J$) is countable, but not finite. Any other countable set which is countable has a bijection from it to $\mathbb N$, so if any other countable set was finite, $\mathbb N$ would be finite. And it's not.

Is it possible for a set to be finite but not countable?

Yes. This is always true. Finite sets are not countable by your definition. They are only "at most countable".

Is it possible for a set to be countable and infinite?

Obvioulsy, yes. $\mathbb N$ is one such example, and every other countable set as well.

Does it mean that finite sets are always at most countable and countable sets are also always at most countable, and finite sets are uncountable and countable sets are infinite?

That is exactly the same as what the definition

a set A is at most countable if A is finite or countable

is trying to say. The two statements (your last one and the starting definition) are completely equivalent.

$\endgroup$
  • $\begingroup$ What if you "twist" the definition a bit, like $$f\colon \mathbb{N}\to \{a,b,c\}, n \mapsto \begin{cases}a, & n \mod 3 \equiv 1\\ b, & n \mod 3 \equiv 2\\ c, & n \mod 3 \equiv 0 \end{cases}$$ Is then $\{a,b,c\}$ not both finite and countable with $J(n)=\left|\{a,b,c\}\right|=3$ and the function $f$? $\endgroup$ – monoid Aug 7 '14 at 7:45
  • 2
    $\begingroup$ $f$ is not bijective! $\endgroup$ – Ant Aug 7 '14 at 7:57
  • $\begingroup$ @monoid Two sets are equipotent ("of the same size") if ther exists a bijection between them. What you described is far from a bijection. $\endgroup$ – 5xum Aug 7 '14 at 8:05
  • 1
    $\begingroup$ When finite is separated from countable, we require uncountable to be infinite, or not at most countable. $\endgroup$ – Asaf Karagila Aug 7 '14 at 8:41
  • $\begingroup$ @AsafKaragila Thanks, did not know that. The German "countable" does not exclude the finite state. $\endgroup$ – monoid Aug 7 '14 at 13:34

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.