Is this a correct proof?

LuisRodg · 2008-02-13 11:25:53

Today I had a quiz in my Discrete Mathematics class.

I managed to answer all the questions. There was one however that im unsure about.

The question was:

-------------------------------------
If A is a uncountably infinite set and A is a subset of B then prove that B is also a uncountably infinite set.
-------------------------------------

When i turned in my quiz the teacher lets us look at the solutions. The answer given was pretty simple. We assume that B is a countable set, therefore by the theorem that says that all subsets of countable sets are countable then since A is a subset B that means that A has to be a countable set as well. Contradiction to our assumption.

I didnt think of this so however I said this:

Since A is a uncountably infinite set then by Cantor's Diagonal Argument you can find an a-bar in the enumeration of the set A. Since A is a subset of B then you can find that same a-bar in the enumeration of B which proves that B is also a uncountably infinite set.

However, im unsure if what I said actually proves it?

mathsyperson · 2008-02-13 11:46:08

I'd say that's a satisfactory proof, although the given one is possibly easier.

Sort of maybe off-topic: I don't like how proofs often use contradiction unnecessarily.
You can use the contrapositive of the theorem used by the book to get the result directly.

If A is a subset of B, then B countable --> A countable.
Contrapositive: A not countable --> B not countable.
Done.

In fact, any proof by contradiction can be turned into a proof by contrapositive, and I find that often those are clearer.

LuisRodg · 2008-02-13 11:59:23

I understand what your saying perfectly.

I practically blanked out in the quiz and the proof that I gave was the only thin that came to mind.

Could the professor have a reason to object my proof and not give me any points? Im kind of worried.

Ricky · 2008-02-13 12:08:35

In fact, any proof by contradiction can be turned into a proof by contrapositive, and I find that often those are clearer.

Prove that the square root of 2 is irrational without contradiction. Prove that any set is connected without contradiction.

In analysis, there are so many cases that contradiction works better than a direct proof, and I've run into many where direct (with or without contrapositive) proofs are not straightforward, where as contradiction rolls right off your tounge.

My proof would probably have went something like this.

If B was not uncountable, then it must be finite or countable. The finite case is obvious, since A can't be. If B was countable, then we may enumerate it's elements. Therefore, A's elements form a subsequence of this which must also be enumerable. Contradiction.

mathsyperson · 2008-02-13 14:04:35

Proofs by contradiction go something like this:

A
Assume ¬B
Prove ¬B --> ¬A
Contradiction; ∴ B.

But since ¬B --> ¬A got proved in there, you could just go straight to the contrapositive of that and get the required statement without needing to make assumptions that turn out to be wrong.
No?

Ricky · 2008-02-13 14:29:34

No. Proof by contradiction goes:

Assume A and not B.
Prove that a false statement is true.
Contradiction, therefore A -> B.

In the case of the square root of two, you come to a conclusion that there is a common divisor between two numbers that are relatively prime. This has absolutely nothing to do with whether or not a number is rational or irrational (except that it is used in it's proof by contradiction).

LuisRodg · 2008-02-20 12:37:28

I just got my quiz back and she (teacher) marked my proof wrong. I asked her and she said I dont know what the sets are and that they could be anything so therefore I could not use the Cantor's Diagonal Argument?

That explanation made no sense to me and I felt it was sort of vague. What you guys think? Im kind of pissed.

TheDude · 2008-02-21 01:58:58

You assumed that the sets that you were working with were sets of numbers, but that is never explicitly stated in the question. They could be sets of words, or computer brands, or people. Therefore you can't use Cantor's Diagonal Argument, because it only works with sets of numbers.

Ricky · 2008-02-21 02:04:32

Your idea is correct, but your reasoning is wrong.

Since A is a uncountably infinite set then by definition of uncountable you can find an a-bar (i.e. element not in the listing) in any enumeration of the set A. Since A is a subset of B then you can find some element not in the listing in the enumeration of B which proves that B is also a uncountably infinite set.

This proof uses the same idea as Cantor's diagonal argument, but it's not because of Cantor's diagonal argument.

Ricky · 2008-02-21 02:09:18

TheDude wrote:

You assumed that the sets that you were working with were sets of numbers, but that is never explicitly stated in the question. They could be sets of words, or computer brands, or people. Therefore you can't use Cantor's Diagonal Argument, because it only works with sets of numbers.

That isn't entirely true, although right enough for this problem. You can, by the continuum hypothesis, set up a surjection between any uncountable set and the real numbers. Then you can carry Cantor's diagonal argument across the inverse of this function. Remember that it need not be 1-1, but "more" elements doesn't hurt you in this case. If you really wish to be explicit, use the axiom of choice to define an image of this function in the real numbers so that the function is 1-1.

Edited to add: By using the continuum hypothesis, I restrict myself to using only sets that we can construct in ZFC set theory. However this is where things get complicated, and very philosophical. It's best just to ignore the above.

LuisRodg · 2008-02-21 07:57:48

Ricky,

Your last post made no sense to me but I guess you were talking directly to TheDude.

I just want to know, was my teacher wrong in marking my proof wrong or you think I can go back to her and show her what you have to say? I basically dont care about the grade that much as knowing if my proof really proves it or not which in this post has been confusing. I know the proof by contradiction is by far the easiest but I just want to know if the one I did proves it which Ricky seems to imply it does?

Ricky · 2008-02-21 10:11:31

Like I said, the general idea is correct. But you used Cantor's diagonal argument as the reason behind your proof, which is wrong.

Math Is Fun Forum

#1 2008-02-13 11:25:53

Is this a correct proof?

#2 2008-02-13 11:46:08

Re: Is this a correct proof?

#3 2008-02-13 11:59:23

Re: Is this a correct proof?

#4 2008-02-13 12:08:35

Re: Is this a correct proof?

#5 2008-02-13 14:04:35

Re: Is this a correct proof?

#6 2008-02-13 14:29:34

Re: Is this a correct proof?

#7 2008-02-20 12:37:28

Re: Is this a correct proof?

#8 2008-02-21 01:58:58

Re: Is this a correct proof?

#9 2008-02-21 02:04:32

Re: Is this a correct proof?

#10 2008-02-21 02:09:18

Re: Is this a correct proof?

#11 2008-02-21 07:57:48

Re: Is this a correct proof?

#12 2008-02-21 10:11:31

Re: Is this a correct proof?

Board footer