Uncountable: A is a countable subset of an uncountable set X, prove X \ A uncountable

  • #1
Statement to prove:
If A is a countable subset of an uncountable set X, prove
that X \ A (or "X remove A" or "X - A") is uncountable.

My work so far:
Let A be a countable subset of an uncountable set X.
(N denotes the set of all naturals)
So A is equivalent to N (or "A ~ N") by the definition of countable.
X is not equivalent to N since X is uncountable.
Assume X \ A is countable. That is (X \ A) ~ N. Thus there is a bijection from (X \ A) to N. However since X is uncountable it is not guaranteed there is an n in N such that there is an x in X that maps to n. And so X \ A is uncountable.

I know that proof is incomplete and may even be completely off :|
I am really struggling in this class (Intro to Real Analysis) and feel as if it will be my GPA-killer (but I don't want it to be!). I'm having a hard time with the countable/uncountable concepts we covered last week.

Any help is greatly appreciated! Thank you for your time.
 

Answers and Replies

  • #2
655
3


If both A and X\A were countable, what would that imply about the countability of X = A union X\A?
 
  • #3
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132


"Thus there is a bijection from (X \ A) to N. However since X is uncountable it is not guaranteed there is an n in N such that there is an x in X that maps to n. And so X \ A is uncountable"
Not bad at all, but you need to develop precision and what you need to prove.
Here, I think your intuition was sort of correct (namely that IF X/A were countable, that would entail that all of X would be countable, something you know is forbidden)

You are struggling, but in your case, you are moving upwards, whatever you might feel right now.
:smile:
 
  • #4


If both A and X\A were countable, what would that imply about the countability of X = A union X\A?
*light goes on in head* I think I see it now:
Okay, I think I got it (thanks to your help!):

My proof would be:

Let A be a countable subset of an uncountable set X. Assume X \ A is countable.
A union X \ A = X which is countable because the union of two countable sets is countable. BUT, this is a contradiction to the assumption that X is uncountable. Therefore, X \ A is uncountable. QED.

Did I get it? :D
 
  • #5
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132


*light goes on in head* I think I see it now:
Okay, I think I got it (thanks to your help!):

My proof would be:

Let A be a countable subset of an uncountable set X. Assume X \ A is countable.
A union X \ A = X which is countable because the union of two countable sets is countable. BUT, this is a contradiction to the assumption that X is uncountable. Therefore, X \ A is uncountable. QED.

Did I get it? :D
Yes.
 
  • #6


"Thus there is a bijection from (X \ A) to N. However since X is uncountable it is not guaranteed there is an n in N such that there is an x in X that maps to n. And so X \ A is uncountable"
Not bad at all, but you need to develop precision and what you need to prove.
Here, I think your intuition was sort of correct (namely that IF X/A were countable, that would entail that all of X would be countable, something you know is forbidden)

You are struggling, but in your case, you are moving upwards, whatever you might feel right now.
:smile:

Thanks for the encouraging note :) My professor did give a list of tips that to prove something uncountable we'd need a contradiction and so we would first assume it countable. Thanks to everyone's helps/tips, I'm slowly getting the hang of this.
This forum rocks and is a tremendous lifesaver! :) Thanks, everyone!
 
  • #7

Related Threads on Uncountable: A is a countable subset of an uncountable set X, prove X \ A uncountable

  • Last Post
Replies
1
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
12
Views
16K
Replies
1
Views
2K
Replies
1
Views
12K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
3K
Replies
2
Views
2K
  • Last Post
Replies
12
Views
9K
Top