prove that if a set A is countably infinite and B is a superset of A,...

prove that if a set A is countably infinite and B is a superset of A, then prove that B is infinite

Solutions

Expert Solution

Define , for any , where is the set of all natural numbers.

Recall that a set S is called a finite set if there exists , be such there is a bijection between S and and a set is called an infinite set if it is not finite.

Also recall if denotes the cardinality of a set then, , for all n. and for any two sets M and N if there exists an injective map , the we will have .

A set is called countable infinite if there is a bijection between the set and .
Given that , where is countable infinite. To show B is an infinite set.

Proof by contradiction method. Let's assume by contrary that B is a finite set. Then by definition we can find , such that B is bijection with Since , there is an injective map from A to B, Thus we get an injective map from A to Let f be the bijectiion between A and , then , is also a bijective, and A to , is an injective, thus by composing we get an injective map from , thus this means , which is a contradiction. Hence B is an infinite set.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Prove that a subset of a countably infinite set is finite or countably infinite

Prove: If A is an uncountable set, then it has both uncountable and countably infinite subsets.

1.) Prove that Z+, the set of positive integers, can be expressed as a countably infinite...

1.) Prove that Z+, the set of positive integers, can be expressed as a countably infinite union of disjoint countably infinite sets. 2.) Let A and B be two sets. Suppose that A and B are both countably infinite sets. Prove that there is a one-to-one correspondence between A and B. Please show all steps. Thank you! (I rate all answered questions)

Let A be an infinite set and let B ⊆ A be a subset. Prove: (a)...

Let A be an infinite set and let B ⊆ A be a subset. Prove: (a) Assume A has a denumerable subset, show that A is equivalent to a proper subset of A. (b) Show that if A is denumerable and B is infinite then B is equivalent to A.

5. For each set below, say whether it is finite, countably infinite, or uncountable. Justify your...

5. For each set below, say whether it is finite, countably infinite, or uncountable. Justify your answer in each case, giving a brief reason rather than an actual proof. a. The points along the circumference of a unit circle. (Uncountable because across the unit circle because points are one-to-one correspondence to real numbers) so they are uncountable b. The carbon atoms in a single page of the textbook. ("Finite", since we are able to count the number of atoms in...

Prove the product of a compact space and a countably paracompact space is countably paracompact.

Prove Theorem 29.9 (Cantor). There are countably many algebraic numbers.In this project, you will prove this...

Prove Theorem 29.9 (Cantor). There are countably many algebraic numbers.In this project, you will prove this theorem.

2. (a) Prove that U45 is generated by the set {14,28}. (b) Prove that the additive...

2. (a) Prove that U45 is generated by the set {14,28}. (b) Prove that the additive group Z×Z is generated by the set S={(3,1),(−2,−1),(4,3)}. Please be thorough step by step with details, please.

(a) Prove that there are no degenerate bound states in an infinite (−∞ < x <...

(a) Prove that there are no degenerate bound states in an infinite (−∞ < x < ∞) one-dimensional space. That is, if ψ1(x) and ψ2(x) are two bound-state solutions of − (h^2/2m) (d^2ψ dx^2) + V (x)ψ = Eψ for the same energy E, it will necessarily follow that ψ2 = Cψ1, where C is just a constant (linear dependence). Bound-state solutions should of course vanish at x → ±∞. (b) Imagine now that our particle is restricted to move...

a. Prove that y=sin(x) is a subspace of R^2 b. Prove that a set of 2x2...

a. Prove that y=sin(x) is a subspace of R^2 b. Prove that a set of 2x2 non invertible matrices a subspace of all 2x2 matrices

Subjects