Results 1 to 11 of 11

Math Help - Finite, Countable, or Uncountable?

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    [SOLVED] Countable or Uncountable?

    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.
    Last edited by SlipEternal; September 27th 2011 at 04:56 PM. Reason: It is solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Countable or Uncountable?

    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)
    Last edited by Swlabr; September 28th 2011 at 03:41 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Countable or Uncountable?

    Quote Originally Posted by SlipEternal View Post
    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!).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    Quote Originally Posted by Swlabr View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Countable or Uncountable?

    Quote Originally Posted by SlipEternal View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,397
    Thanks
    520

    Re: Countable or Uncountable?

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. countable & uncountable sets
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2010, 07:43 PM
  3. Replies: 2
    Last Post: November 11th 2010, 04:56 AM
  4. Replies: 4
    Last Post: October 11th 2008, 01:42 PM
  5. 5 Countable v. Uncountable Problems (Please help)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 7th 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum