Question

Prove that if X and Y are disjoint countably infinite sets then X ∪ Y is countably infinity (can you please show the bijection from N->XUY clearly)

Answer #1

A formal proof would be something like this.

If X and Y are countable and disjoint sets, then there exist injective functions f and g from X and Y, respectively, to N.

Let C = X∪Y and define a function h : C→N as follows:

h(z) = 2f(z) , if z ∈ X

&, h(z) = 2g(z)+1 , if z ∈ Y

Then, if x≠y, we clearly have h(x)≠h(y) since if x,y∈X , this follows from the fact that f is injective (analogously for x,y∈Y) and if x∈X and y∈Y, we have that h(x) is even while h(y) is odd (analogously for x∈Y, y∈X). Hence h is an injective function from C to N and thus, by definition, C is countable.

a) Prove that the union between two countably infinite sets is a
countably infinite set.
b) Would the statement above hold if we instead started with an
infinite amount of countably infinite sets?
_________________________________________________
Thank you in advance!

Suppose A is an infinite set and B is countable and disjoint
from A. Prove that the union A U B is equivalent to A by defining a
bijection f: A ----> A U B.
Thus, adding a countably infinite set to an infinite set does
not increase its size.

(a) Let A and B be countably infinite sets. Decide whether the
following are true for all, some (but not all), or no such sets,
and give reasons for your answers. A ∪B is countably infinite A
∩B is countably infinite A\B is countably infinite, where A ∖ B =
{ x | x ∈ A ∧ X ∉ B }. (b) Let F be the set of all total unary
functions f : N → N...

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

Multiplicative Principle (in terms of sets): If X and Y are
ﬁnite sets, then |X ×Y| = |X||Y|. D) You are going to give a
careful proof of the multiplicative principle, as broken up into
two steps:
(i) Find a bijection
φ : <m + n>→<m>×<n> for any pair of natural
numbers m and n. Note that you must describe explicitly a function
and show it is a bijection.
(ii) Give a careful proof of the multiplicative principle by
explaining...

Prove that
Z
×{
0
,
1
,
2
,
3
}
is countably infinite by finding a bijection
f
:
Z
→
Z
×{
0
,
1
,
2
,
3
}
. (
Hint:
Consider the
division algorithm

Multiplicative Principle (in terms of sets): If X and Y are
ﬁnite sets, then |X ×Y| = |X||Y|.
D) You are going to give a careful proof of the multiplicative
principle, as broken up into two steps:
(i) Find a bijection
φ : <mn> → <m> × <n>
for any pair of natural numbers m and n. Note that you must
describe explicitly a function and show it is a bijection.
(ii) Give a careful proof of the multiplicative principle...

Which of the following sets are finite? countably infinite?
uncountable? Give reasons for your answers for each of the
following:
(a) {1\n :n ∈ Z\{0}};
(b)R\N;
(c){x ∈ N:|x−7|>|x|};
(d)2Z×3Z
Please answer questions in clear hand-writing and show me the
full process, thank you (Sometimes I get the answer which was
difficult to read).

Assume that X and Y are finite sets. Prove the following
statement:
If there is a bijection f:X→Y then|X|=|Y|.
Hint: Show that if f : X → Y is a surjection then |X| ≥ |Y| and if
f : X → Y is an injection then
|X| ≤ |Y |.

Problem 3 Countable and Uncountable Sets
(a) Show that there are uncountably infinite many real numbers
in the interval (0, 1). (Hint: Prove this by contradiction.
Specifically, (i) assume that there are countably infinite real
numbers in (0, 1) and denote them as x1, x2, x3, · · · ; (ii)
express each real number x1 between 0 and 1 in decimal expansion;
(iii) construct a number y whose digits are either 1 or 2. Can you
find a way...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 21 minutes ago

asked 25 minutes ago

asked 28 minutes ago

asked 33 minutes ago

asked 47 minutes ago

asked 49 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 3 hours ago