Finite, Countable, or Uncountable?

**SlipEternal** · September 27th 2011, 09:01 AM

Let $f: \mathcal{P}(\mathbb{N}) \to \mathcal{P}(\mathbb{N})$ define the function $f(A)=\bigcup_{B\subset A, B\text{ is finite}, B\ne\emptyset}{\left\{\sum_{b\in B}{b}\right\}}$ (Forgive me for not knowing how to format that better, but I hope it is clear what it is doing).

An example:
$f(\{1,2\})=\{1,2,3\}$

Consider the set:
$I=\left\{X \in \mathcal{P}(\mathbb{N})|card\left(f^-1(X)\right)>1\right\}$

Is $I$ countable, or uncountable?
It is at least countable because
$f(\mathbb{N})=\mathbb{N}$ and $f(\{2^n|n=0,1,2,...\})=\mathbb{N}$
$f(2\mathbb{N})=2\mathbb{N}$ and $f(\{2^n|n=1,2,...\})=2\mathbb{N}$
And this can be continued for each natural number, implying at least countably infinite. I don't know how to show uncountably infinite.

**SlipEternal** · September 27th 2011, 04:45 PM

Never mind. Uncountably infinite is actually really easy to show.
$\text{Let }X\in I$
$\text{Let }X=\{x_1,x_2,x_3,...\}$
$x_1,x_2\in f^{-1}(X)$ by virtue of the fact that they cannot be obtained by the sum of anything larger, so they must be in any preimage.
Let $a_1\text{ be the index for }x_{a_1}=x_1+x_2$
By the same logic, for all $i<n, x_i \in f^{-1}(X)$
Now, either $x_{a_1}\in f^{-1}(X)$ or not.
Let $b_1\text{ be the smallest index }x_{b_1} \notin f(\{x_1,x_2,x_{a_1}\})$ . It must be that $x_{b_1}\in f^{-1}(X)$ because we have exhausted the sums of the smallest two elements, as well as the sum of a potentially 3rd smallest with that of the first two.
Now, let $x_{a_2}=x_1+x_2+x_{b_1}$ . Either $x_{a_2} \in f^{-1}(X)$ or not.

This process can continue ad infinitum producing a binary sequence, each one representing a distinct member of $I$ . This maps bijectively with reals, and so my set $I$ is uncountable.

I realize I need a little more rigor to fully justify it, but the intuition is there, and that is good enough for now.

**SlipEternal** · September 28th 2011, 01:16 AM

Oops, my mistake. Like I said, the intuition was there, but I hadn't fully justified my answer. My sloppy work above was actually an initial understanding that a set may have uncountably many preimages, which is not the same thing at all (and I failed to show that, as well). Instead, starting again:

Consider some $X \in I$ . Because it has multiple preimages, and each preimage is a subset of $X$ , it is natural to wonder about the intersection of all preimages of $X$ . With some work, likely involving combinatorial methods, I can likely show that the intersection of all preimages is one of the preimages of $X$ . This would allow me to use something like Zorn's Lemma, which would imply a minimal set that can generate my set $X$ . (Possibly I don't even need Zorn's Lemma. I haven't thought about the specifics enough). Anyway, there exists a set of integers that are extraneous (adding them or removing them from the preimage will not effect the image. Now, at this point, I will need to introduce some notion of topology in order to proceed, as my current idea needs either sequential or covering compactness. This will allow me to show that there exists some finite number of elements that are variable (changing those variables changes the entire problem. However, once the problem is changed, there are only a countable number of ways that they can change because any sequence of changes to the set has a subsequence that converges to the same set as the original sequence. Therefore, there are a countable union of countable configurations which yield distinct sets in $I$ . So, it turns out it is countable, not uncountable.

Again, the intuition is there, just not the rigor.

**Swlabr** · September 28th 2011, 02:45 AM

It is interesting. Everything hinges on the cardinality of your set $A$ . If $A$ is allowed to be infinite then $I$ is uncountable, while if it can only be finite then $I$ is countable. The latter is equivalent to proving that countably generated groups/algebras etc. are countable.

Note that it doesn't make sense for the set $A$ to be infinite - infinite sums cannot happen! I mean, what would they sum too?

Anyway,

To prove that taking infinitely sized $A$ gives you an uncountable set, let $A=\{p^{n_p}; p\text{ prime }, n_p>0 \text{ fixed for given }p\}$ . Note that there are countable many choices for each $n_p$ , and no two $p^{n_p}$ if your set give you the same element of your set. Thus, there are $|\mathbb{N}|^{|\mathbb{N}|}$ choices for this set $A$ , each of which is a different element of $\mathcal{P}(\mathbb{N})$ . Thus, $|I|>|\mathbb{N}|^{|\mathbb{N}|}$ .

Of course, you should probably find explicit injections between the set of possibilities for $A$ and $\mathcal{P}(\mathbb{N})$ . But this isn't too hard.

Now, if you take $A$ to be finite then there are countably many sets of size $j$ for a given $j\in \mathbb{N}$ . Thus, write $w_{i, j}$ for the $i^{th}$ set of size $j$ . Therefore, $I$ is countable ( $w_{i, j}\mapsto 2^i3^j$ yields an injection from $I$ to $\mathbb{N}$ , so assuming the axiom of choice we are done)

**SlipEternal** · September 28th 2011, 03:40 AM

$A$ is not a valid element of $I$ . Counting the number of possible sets for $A$ has absolutely no relationship whatsoever to the number of sets in $I$ .

Here is why:
Assume $n_p=1$ for all $p$ . Thus, $2,3,5,7,11,... \in A$ . However, because $10=2+3+5 \notin A, f^{-1}(A)=\emptyset, card(\emptyset)=0<1$ . Therefore, $A \notin I$ . So, you just counted an uncountable number of sets, none of which are elements of $I$ . Examples of infinite sets in $I$ are $\mathbb{N}$ where $f(\mathbb{N})=\mathbb{N}, f(\{2^n|n=0,1,2,...\})=\mathbb{N}$ . Therefore, $I\text{ is nonempty}$ . And, by the reason given in my last post, it is actually countable, as I indicated. The reason is subtle. You must first assume that you have an actual element of $I$ before trying to show that the number of possible elements of $I$ are uncountable. I assume that I have one such infinite set.

So, here's an examples. Let's assume that I have one of these infinite sets, $X \in I$ . Assume that for two of its preimages, one contains the natural number $x$ and the other does not. (If each had equivalent containments, then they would be the same set, and therefore, contradict the notion that $X$ had multiple preimages, therefore some $x$ may be found. Let the minimal two elements of $X$ be $x_1,x_2$ . The function $f$ guarantees that $x_1+x, x_2+x, x_1+x_2+x \in X$ . However, one of the preimages does not include $x$ , which implies that there must exist some other subsets whose sums are equal to those three elements. Keep in mind that we are dealing with some subset of natural numbers, so our sums only get larger. Not only that, but we are dealing with infinite sets, so we have an infinite number of finite subsets to sum up, and all of these sums are in $X$ . When calculating these sums, it is worthwhile to calculate them in order of how large they are. $x_1+x_2$ are by definition the smallest elements of $X$ . Therefore, they cannot be the sum of any other elements. If they are in $X$ , it is because they are in EVERY preimage of $X$ . If your numbers are too far apart, then $X$ will have a single distinct preimage.

For example: $A=\{3^n|n=0,1,2,3,...\}$ . Its elements look like this: $\{1,3,9,27,...\}$ .
$f(A)=\{1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,.. .\}$ . Now, for any preimage of $f(A)$ , it must contain $1,3$ . The only way for them to be in $f(A)$ is if their preimage contains them. If $4 \in f^{-1}(f(A))$ , then $1+4=5 \in f(f^{-1}(f(A)))$ , which is not in $f(A)$ , so 4 cannot be in its preimage. Continuing on, you can discover that the ONLY set that can be its preimage is $A$ itself. Therefore, the cardinality of its preimage is 1. This is NOT a valid set in $I$ .

So, my construction of beginning with a set in $I$ is NOT assuming a countable set in the first place. It assumes that I have an arbitrary element of $I$ and makes use of the properties of what it means to be in $I$ to arrive at the conclusion that $I$ must be countable.

**Swlabr** · September 28th 2011, 03:42 AM

Originally Posted by SlipEternal

$A$ is not a valid element of $I$ . Counting the number of possible sets for $A$ has absolutely no relationship whatsoever to the number of sets in $I$ .

Here is why:
Assume $n_p=1$ for all $p$ . Thus, $2,3,5,7,11,... \in A$ . However, because $10=2+3+5 \notin A, f^{-1}(A)=\emptyset, card(\emptyset)=0<1$ . Therefore, $A \notin I$ . So, you just counted an uncountable number of sets, none of which are elements of $I$ . Examples of infinite sets in $I$ are $\mathbb{N}$ where $f(\mathbb{N})=\mathbb{N}, f(\{2^n|n=0,1,2,...\})=\mathbb{N}$ . Therefore, $I\text{ is nonempty}$ . And, by the reason given in my last post, it is actually countable, as I indicated. The reason is subtle. You must first assume that you have an actual element of $I$ before trying to show that the number of possible elements of $I$ are uncountable. I assume that I have one such infinite set.

So, here's an examples. Let's assume that I have one of these infinite sets, $X \in I$ . Assume that for two of its preimages, one contains the point $x$ and the other does not. (If each had equivalent containments, then they would be the same set, and therefore, contradict the notion that $X$ had multiple preimages, therefore some $x$ may be found. Let the minimal two elements of $X$ be $x_1,x_2$ . The function $f$ guarantees that $x_1+x, x_2+x, x_1+x_2+x \in X$ . However, one of the preimages does not include $x$ , which implies that there must exist some other subsets whose sums are equal to those three elements. Keep in mind that we are dealing with some subset of natural numbers, so our sums only get larger. Not only that, but we are dealing with infinite sets, so we have an infinite number of finite subsets to sum up, and all of these sums are in $X$ . When calculating these sums, it is worthwhile to calculate them in order of how large they are. $x_1+x_2$ are by definition the smallest elements of $X$ . Therefore, they cannot be the sum of any other elements. If they are in $X$ , it is because they are in EVERY preimage of $X$ . If your numbers are too far apart, then $X$ will have a single distinct preimage.

For example: $A=\{3^n|n=0,1,2,3,...\}$ . Its elements look like this: $\{1,3,9,27,...\}$ .
$f(A)=\{1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,.. .\}$ . Now, for any preimage of $f(A)$ , it must contain $1,3$ . The only way for them to be in $f(A)$ is if their preimage contains them. If $4 \in f^{-1}(f(A))$ , then $1+4=5 \in f(f^{-1}(f(A)))$ , which is not in $f(A)$ , so 4 cannot be in its preimage. Continuing on, you can discover that the ONLY set that can be its preimage is $A$ itself. Therefore, the cardinality of its preimage is 1. This is NOT a valid set in $I$ .

So, my construction of beginning with a set in $I$ is NOT assuming a countable set in the first place. It assumes that I have an arbitrary element of $I$ and makes use of the properties of what it means to be in $I$ to arrive at the conclusion that $I$ must be countable.

You might want to re-read my post - I've edited it to make what I was saying a bit clearer (just before you posted this!).

**SlipEternal** · September 28th 2011, 03:46 AM

Originally Posted by Swlabr

You might want to re-read my post - I've edited it to make what I was saying a bit clearer (just before you posted this!).

Ah, thank you. Yes, that is a good point. Infinite sums are not possible. However, if you read my definition of $f$ , it makes sure that every subset it sums is finite. So, $f(X)$ is well defined for any infinite set of natural numbers $X$ .

**Swlabr** · September 28th 2011, 04:12 AM

Originally Posted by SlipEternal

Ah, thank you. Yes, that is a good point. Infinite sums are not possible. However, if you read my definition of $f$ , it makes sure that every subset it sums is finite. So, $f(X)$ is well defined for any infinite set of natural numbers $X$ .

Ah yes, sorry, not sure why I missed that!

**SlipEternal** · September 28th 2011, 04:23 AM

Perhaps I should include that I have already proven without coming to the forum that there are an uncountable number of sets who preimage is empty, and an uncountable number of sets who preimage is non-empty. I'm now trying to distinguish between preimages that are distinct and preimages that are non-distinct. By my current way of thinking, there are only countably many sets with more than one preimage and an uncountable number of sets with a distinct preimage. For the purposes that I plan to use it, an intuitive understanding is all I will need. I don't need a rigorous proof. I'm more interested in application of this than in actually proving anything. In fact, I doubt I would be capable of proving it. It is like assuming the Goldbach Conjecture to be true because it so intuitively seems true. That's all I need. So, for my purposes, this problem is solved.

I am still interested in it. So, if you want to discuss it further, I am very interested in doing so!

**SlipEternal** · September 28th 2011, 10:36 AM

Ok, I have been thinking about this a little bit more, and I think I can extend the concept a bit to make my position a little more rigorous.

As mentioned, $\mathbb{N}$ has multiple preimages. Additionally, for any $k \in \mathbb{N}, k\mathbb{N}$ also has multiple preimages.

Now, $f(2\mathbb{N}\cup\{n\}), n\text{ is odd}, n>1$ all have multiple preimages

In general, any infinite set of natural numbers that has multiple preimages follows the same pattern. It is some subset of $k\mathbb{N}$ union with some finite number of natural numbers, take $f$ of that set, and you wind up with a set that has multiple preimages (namely, in the section of the set that is multiples, you may remove one of the multiples in the preimage, but it will still appear in the image.)

Even if that construction is not exhaustive, it seems like every construction is simply a countable collection of sets. And countable unions of countable sets are countable.

Now, if $f$ were extended to $\mathcal{P}(\mathbb{Z})$ to itself, the number of sets with multiple preimages would be uncountable.

For example:
Given any binary sequence, $a_n=0\text{ or }1$ .
Let $A_{a_n}=\left\{10^n,-10^n|a_n=1, n=0,1,2,...\right\}$
The set $f(A_{a_n})$ has two preimages:
$A_{a_n}\text{ and }A_{a_n}\cup\{0\}$
But, if $f$ were defined on the domain $\mathcal{P}(\mathbb{Z}\backslash \{0\})$ , then the number of sets with multiple preimages would likely be countable again.

**SlipEternal** · September 28th 2011, 03:29 PM

I apologize and retract my statement. It turns out that the only case I've found to yield uncountable results is the one case I initially dismissed: the finite case!

Given any binary sequence, $a_n=0\text{ or }1$ .
Let $A_{a_n}=\left\{10^{5n}|a_n=1, n \in \mathbb{N}\right\}\cup\left(\[100\]\backslash\{8,12\}\right)$
And let $B_{a_n}=\left\{10^{5n}|a_n=1, n \in \mathbb{N}\right\}\cup\left(\[100\]\backslash\{20\}\right)$

Turns out, $f\left(A_{a_n}\right)=f\left(B_{a_n}\right)$ , thus there are uncountably many sets with more than one preimage.

Thread: Finite, Countable, or Uncountable?

LinkBack

Thread Tools

Display

[SOLVED] Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Re: Countable or Uncountable?

Similar Math Help Forum Discussions

Prove a countable Cartesian product of countable sets is uncountable

countable & uncountable sets

|all finite sentences| (countable alphabet) = countable, right?

[SOLVED] Uncountable: A is a countable subset of an uncountable set X, prove X \ A un

5 Countable v. Uncountable Problems (Please help)

Search Tags