Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**Kazy****Member**- Registered: 2006-01-24
- Posts: 37

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!

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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..."

Offline

Pages: **1**