Math Is Fun Forum

Kazy

Member

Registered: 2006-01-24

Posts: 37

Need help with proofs

I need to prove:

a) Prove that if S is any finite set of real numbers, then the Z U S (integers Union S) is countably infinite.

b) Let A, B, C, D be subsets of a universal set U. Suppose that A ≈ B and C ≈ D. Prove that A X C ≈ B X D (cartesian products)

c) Let A and B be sets contained in a universal set U. Suppose there exists an injection f: A -> B. Prove that if A is countably infinite, then B is countable.

For A, I'm thinking Z U *anything* is countably infinite since Z is infinite. I'm not sure if thats all I have to say, or even really how to make that a formal proof. For B and C I don't even know where to begin.

Can anyone help me out? Thanks!

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need help with proofs

For A, I'm thinking Z U *anything* is countably infinite since Z is infinite. I'm not sure if thats all I have to say, or even really how to make that a formal proof. For B and C I don't even know where to begin.

Not true.  Z U R is not countable.  Z U [0, 1] isn't either.  In fact, Z U anything uncountable isn't countable.  But Z U anything countable is countable.

You have the map from Z to Z f(x) = x, the identity map.  Obviously, this is 1-1 and onto.  So Z has the same cardinality as Z (duh!).

But we can use this function to map Z U S to Z.  Let |S| = n.  Now we use n as an offset.  Since S is finite, S can be represented by the set {s_x : x ≤ n, x in N}.  So we can then have the function:

f(x) = {s_x if x ≤ n} or {x if x > n}

Which you can show is 1-1 and onto, and thus, Z U S is the same size as Z, and so Z U S is countably infinite.

For b, are you allowed to state the |A x B| = |A| * |B|?

For c, you know tha tf is 1-1.  From this, you can show that |A| >= |B|.  And from this, you can say that if A is countably infinte, since B contains less elements, either B is countably infinite or finite (all finite sets are countable).

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."