Question

In: Advanced Math

Let f be a one-to-one function from A into b with B countable. Prove that A...

Let f be a one-to-one function from A into b with B countable. Prove that A is countable.

Section on Cardinality

Solutions

Expert Solution

Since is countable, we can enumerate its elements as . We now enumerate as follows. Let be the smallest integer such that . Then for a unique (because is one-to-one). We define .

Suppose that , and that we have defined in . Let be the smallest integer such that . Then for a unique (because is one-to-one). We define .

By induction, we have defined for all integer .

We claim that unless . Proof: Let . Then we may assume that . Then where is the smallest integer such that . Since , we know that . Thus, .

Finally, we claim that . Proof: If not, say and . Then . But this is impossible because by construction of , every element corresponds to a unique . Hence, .

This shows that is countable.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

TOPOLOGY Let f : X → Y be a function. Prove that f is one-to-one and...

TOPOLOGY Let f : X → Y be a function. Prove that f is one-to-one and onto if and only if f[A^c] = (f[A])^c for every subset A of X. (prove both directions)

1) a) Prove that the union of two countable sets is countable. b) Prove that the...

1) a) Prove that the union of two countable sets is countable. b) Prove that the union of a finite collection of countable sets is countable.

Let f: A ->B and g:B -> A be functions. Prove that if fog is one-to-one...

Let f: A ->B and g:B -> A be functions. Prove that if fog is one-to-one and gof is onto, then f is a bijection.

4. Let a < b and f be monotone on [a, b]. Prove that f is...

4. Let a < b and f be monotone on [a, b]. Prove that f is Riemann integrable on [a, b].

Let f : R → R be a function. (a) Prove that f is continuous on...

Let f : R → R be a function. (a) Prove that f is continuous on R if and only if, for every open set U ⊆ R, the preimage f −1 (U) = {x ∈ R : f(x) ∈ U} is open. (b) Use part (a) to prove that if f is continuous on R, its zero set Z(f) = {x ∈ R : f(x) = 0} is closed.

Prove the following: (a) Let A be a ring and B be a field. Let f...

Prove the following: (a) Let A be a ring and B be a field. Let f : A → B be a surjective homomorphism from A to B. Then ker(f) is a maximal ideal. (b) If A/J is a field, then J is a maximal ideal.

9. Let f be continuous on [a, b]. Prove that F(x) := sup f([x, b]) is...

9. Let f be continuous on [a, b]. Prove that F(x) := sup f([x, b]) is continuous on [a, b]

Prove that if f is a bounded function on a bounded interval [a,b] and f is...

Prove that if f is a bounded function on a bounded interval [a,b] and f is continuous except at finitely many points in [a,b], then f is integrable on [a,b]. Hint: Use interval additivity, and an induction argument on the number of discontinuities.

Let f be a continuous function on [a, b] which is differentiable on (a,b). Then f...

Let f be a continuous function on [a, b] which is differentiable on (a,b). Then f is non-decreasing on [a,b] if and only if f′(x) ≥ 0 for all x ∈ (a,b), while if f is non-increasing on [a,b] if and only if f′(x) ≤ 0 for all x ∈ (a, b). can you please prove this theorem? thank you!

Prove 1. Let f : A→ B and g : B → C . If g...

Prove 1. Let f : A→ B and g : B → C . If g 。 f is one-to-one, then f is one-to-one. 2. Equivalence of sets is an equivalence relation (you may use other theorems without stating them for this one).

Subjects