Question

Prove that if A is a countable subset of an uncountable set B, then B \ A is uncountable.

Answer 1

one idea
if two sets X, Y are countable, then so is \(X\cup Y\)

Answer 2

I would only be using one countable set, though, A. Like....maybe I'm just dumb and don't get the hint, lol.

Answer 3

\[A\cup( B-A)=B\]

Answer 4

Just in general, or in specific to this situation?

Answer 5

that is always the case

Answer 6

to spell it out, it would be a proof by contradiction
if \(A\) and \(A-B\) were both countable, then
\[A\cup (B-A)=B\] would be countable, but it is not by assumption

Answer 7

When you write A - B, is that the same thing as the notation I've been given? A - B = A\B? I know I don't know as much about this as I should, so I'm sorry I'm making you give so many hints, lol.

So how do we have A - B flip to B - A when we add in a union?

Answer 8

i had to write it that way because i could not figure out how to write B\A in latex

Answer 9

but they are the same

Answer 10

Ah, okay, lol. So A and A-B flips to AU(B-A) ? I guess I'm trying to understand that connection first.

Answer 11

Maybe if I type something finite out:
A = {1, 2, 3, 4, 5}
B = {1, 2, 5, 6, 7, 8}
B \ A = {6, 7, 8}
A U (B\A) = {1, 2, 3, 4, 5, 6, 7, 8} ?? What am I misunderstanding? x_x

Answer 12

would a contrapositive be simpler to deal with?

Answer 13

Prove that if A is a countable subset of an uncountable set B, then B \ A is uncountable.

contrP

Prove that
if B \ A is countable.
then A is an uncountable subset of a countable set B

Answer 14

prove or disprove ...

Answer 15

Okay, so you had to negate all 3 parts to do the contrapositive.

Answer 16

not sure if my contrP is contraP enough ...

Answer 17

What do you mean?

Answer 18

i mean im not confident in my attempt at a contraP to determine if its the actual contraP :)

Answer 19

Lol, I see. Well....So assuming B\A is countable. That means there exists a bijection from (B\A) to the natural numbers? Or can I actually say B\A = N?

Answer 20

wish i knew, at the moment its just an attempt to see if its more provable ... since we know that a contraP has the same truth value as the original statement.

Answer 21

if B/A is countable there is one to one correspondence to N yes

Answer 22

Yeah, at least that's one thing I know ^_^ I guess I wouldve thought the contrapositive would be if B\A is countable, then A is an uncountable subset of the uncountable set B. I wouldnt have thought that the B part would be negated.

Answer 23

B/A is not equal to n, but there exists some function f that maps B/A to N

Answer 24

So however I prove this. I need to come up with a function?

Answer 25

no, its simply assumed to be true for the contraP stab at it.

Answer 26

So regardless of the proof method, no function is needed?

Answer 27

correct. its implied by the nature of the conjecture. its true by hypothesis. and we either reach a contradiction, an absurdity, or a factuality

Answer 28

And having both parts of the if statement being negated would be correct? I want to say A is an uncountable subset of a countable set B? Because yeah, I would have initially thought that it'd be A is an uncountable subset of an uncountable set B

Answer 29

that part i cant say for sure ... just havent had the practice

A is a countable subset of an uncountable set B

A is an UNcountable subset of ... B seems fair to me.

Answer 30

the Z mods are countable sets of Z/Zn

Answer 31

if we want to give this contraP some bite, we can focus on them .... but then we dont have a general case, but it may give us some insight into the abstract

Answer 32

but then B is not an uncountable set .. lol so many twists and turnd to proofings

Answer 33

No worries ^_^ And alright, that would have been my thought. If I don't need a function, then I suppose that helps my thought process. From my notes, it looks like if you have an uncountable subset of another set, then that set is also uncountable. Not that it helps, lol.

Wait, though, Z mod would include 0 and 0 isnt an element of N. Does that matter? Maybe we can use something like Zp? But then I think I might be confusing group ideas with set ideas.

Answer 34

Z/Z3 is the set {0,1,2} Z mod3, the set of equivalence classes that are the remainders blah blah

Answer 35

ive forgotten most of the group theory stuff i learnt in college.

Answer 36

Yeah, Im working with group theory now, so I was thinking Zp, p being prime numbers. But then I think that assumed under multiplication, so thats throwing in a group idea. I'll brb, though, gotta switch computers :)

Answer 37

Prove that if A is a countable subset of an uncountable set B, then B \ A is uncountable.

we are dealing with sets here, not groups.

let B be the set of real numbers, and A be the set of integers. What does the set R/Z look like?

Answer 38

Yeah, I know, I was just trying to think along the modulo idea, just my idea was a group, so no go. When you put R/Z, which notation is that? Seems like there are many notations for the same thing, so not sure which is which all the time

Answer 39

its notation dealing with homomorphisms i believe. R mod Z

Answer 40

homomorphism is prolly the wrong term .. isomorphism maybe?

Answer 41

Okay, so modulo, gotcha. Yeah, if you had a homomorphism it'd be one-to-one for sure. R mod Z is definitely a new idea, though, definitely more used to finite, Z mod 8 or something, hehe. I don't think isomorphism would be necessary. Part of isomorphism requires two groups have the same order, so yeah. Lol, I feel like I'm making this infinitely more complicated than it needs to be.

Answer 42

pfft, im the one prolly making it complicated :) satellites method most likely suffices, but i cant vouch for it since i cant say that i understand it.

Answer 43

I still enjoy the discussion if nothing else xD

Answer 44

X is countable
Y is countable
therefore \(X\cup Y\) is countable
you can prove that if you like, but it is more or less obvious

Answer 45

if you take A union B\A you definitely get B

Answer 46

*If A is a subset of B*

Answer 47

so if A and B\A are countable, so is B
but by assumption B is not countable
therefore neither is B\A

Answer 48

Yeah, I was typing that up x_x I saw it after you said that. I don't know why I didnt catch on at first. Didn't intend to make you just give me the answer, sorry about that :(

Answer 49

your participation rate in the conversation merited a little more guidance :)

Answer 50

Alright x_x I mean, no matter what I will have to do this on my own during exams. I mean, for some reason when he posted that the second time I understood, it just didnt hit me at first. Oh well. I hope I didnt annoy him too much, hehe. Well, I got one more I'll post. Thanks to everyone :)

Answer 51

good luck ;)