0
$\begingroup$

Quick question:

I understand that finite sets are equivalent to $J_n$ for some n $\in$ N, and that countable sets are equivalent to N. Also, either of these is true if and only if an injective map f : A $\rightarrow$ N exists or if and only if a surjective map g : N $\rightarrow$ A exists.

Also, the proof that $J_n$ is NOT equivalent to N goes:

Define $J_n = \{1,2,\ldots,n\}$ and consider the mapping h : $J_n \rightarrow$ N. Observe that h(j) $\le \sum_{i=1}^nh(i)$ for all $j \in J_n$, so it follows h is not onto. Hence, $J_n \subset$ N.

Is it valid to claim $\bigcup_{A \in F}(A) \sim N$ can be shown, when A is finite for all A $\in$ F and F is countable, by recursively declaring the bijection:

k : $\bigcup_{i=1}^m(A) \rightarrow$ $J_n$ until m and n diverge toward infinity.

This would imply that as n gets large enough through summation, $J_n \sim N$ if and only if the $\bigcup_{i=1}^\infty(A)$ is countable.

$\endgroup$
4
  • $\begingroup$ Is this just intuitively true? $\endgroup$ Commented Sep 22, 2014 at 1:16
  • $\begingroup$ I understand everything before the question, but what do you mean by $J_n\sim N$ as $n$ diverges toward infinity? $\endgroup$ Commented Sep 22, 2014 at 1:19
  • $\begingroup$ I mean, because $J_n \subset$ N, by increasing n we also increase the cardinality of $J_n$. If n diverges, will $J_n$ be equipotent to N (under the conditions I listed...otherwise the union might become uncountable)? $\endgroup$ Commented Sep 22, 2014 at 1:24
  • $\begingroup$ It should be "for all $j\in J_n$" rather than "for all $j\in\mathbb N$". $\endgroup$ Commented Sep 22, 2014 at 1:38

1 Answer 1

Reset to default
1
$\begingroup$

$A$ is a countable set iff there exists an injection $f: A \rightarrow \mathbb N$. So all finite sets are countable; but not all countable sets are finite.

Your attempt at proving that $J_n$ is "NOT equivalent to" $\mathbb N$ has a flaw. You correctly note that $J_n$ is a proper subset of $\mathbb N$. (Of course, we could just as easily prove this via: $n+1 \notin J_n$ and $n+1 \in \mathbb N$, therefore $J_n$ is a proper subset of $\mathbb N$).

But so what? Let $E$ be the set of even naturals. It's obvious that $E$ is a proper subset of $\mathbb N$; but that doesn't mean we can conclude that $E$ is a finite set!

To prove that a set is finite depends on what your definition of 'finite' is. The usual definition is that for some $n \in \mathbb N$, there exists a bijection $f : A \rightarrow J_n$; where $J_n = \{i \in \mathbb N: i \leq n\}$ and by that definition, the trivial function $f(x) = x$ shows that $J_n$ must always be finite; we don't need anything fancier than that.

As to your claim, your assertion is ill-defined.

What do you mean, for an arbitrary $A \in F$ where $F$ is a countable set of finite sets, by $\bigcup_{i=1}^m(A)$? If $A$ is the set $\{7\}$ and $m=3$, what set are we unioning when $i=2$? Is $m$ supposed to depend of $A$ in some way, or is $A$ supposed to depend of $i$ or $m$ in some way?

When you have answered that, what exactly do you mean by "until $m$ and $n$ diverge to infinity"? I presume that $m$ and $n$ are both elements of $\mathbb N$; and I note that $\mathbb N \notin \mathbb N$. How do the words "infinity" and "diverge" fit into this picture?

To help focus your enquiry, the thing I might suggest is this:

Let $F$ be a countable set of finite sets $\{A_i\}$.

To keep from being sloppy, I will first note that since $F$ is countable, there is an injective function $q: F \rightarrow \mathbb N$. Now $q(F)$ is a subset of the naturals, and therefore there is some unique $a \in F$ such that $q(a)$ is minimal in $q(F)$ (assuming that every set of naturals has a unique least element... obvious of course, but must previously be proven!!).

So call that minimal $a$ to be $A_1$; now $q(F) - \{A_1\}$ is either empty, or it has a minimal element which we will call $A_2$. Et cetera! So whether $F$ is finite or not, I can give some meaning to $A_i \in F$.

Now, your claim seems to want to be: if $F = \{A_i\}$ is a countable collection of finite sets, and for all $n \in \mathbb N$, there exists $m \in \mathbb N$ such that there exists a surjection $f : \bigcup_{i=1}^m A_i \rightarrow J_n$, then exists a bijection $g: F \rightarrow \mathbb N$.

And that, my friend, can be proven!

$\endgroup$
6
  • $\begingroup$ I see what you mean. That said, I believe I edited my question accordingly. I'm interested in the transition from when every set A $\in$ F is finite where F is countable. What is the notation when you take $\bigcup_{A \in F}$(A)? $\endgroup$ Commented Sep 22, 2014 at 1:43
  • $\begingroup$ You are still assuming that if $A$ is a proper subset of $\mathbb N$, then $A$ is not equinumerous with $\mathbb N$. That is incorrect. $\endgroup$ Commented Sep 22, 2014 at 1:45
  • $\begingroup$ Whoops, I deleted something. I meant to include that one should assume every A in the family F is finite. $\endgroup$ Commented Sep 22, 2014 at 1:46
  • $\begingroup$ Chas: Can you rephrase/remove paragraph 3? The OP does not actually define a function $h$; for arbitrary functions $J_n\to\Bbb N$ the statement is true. The error is simply that E draws a weak conclusion from the statement. (The conclusion is not strong enough to prove $J_n\not\sim\Bbb N$, but the statement is.) $\endgroup$ Commented Sep 22, 2014 at 1:47
  • $\begingroup$ Thank you for the recent edit Chas Brown. Though my question is more: "Is what I said valid?" $\endgroup$ Commented Sep 22, 2014 at 1:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.