Let the cardinal number of N, the set of all natural numbers, be א0. Prove that...

Let the cardinal number of N, the set of all natural numbers, be א0. Prove that the product set N × N = {(m,n);m ∈ N,n ∈ N} has the same cardinal number. Further prove that Q+, the set of all positive rational numbers, has the cardinal number N_0.

Hint: You may use the formula 2^(m−1)(2n − 1) to define a function from N × N to N, see the third example on page 214 of the textbook.

Solutions

Expert Solution

milcah answered 1 year ago

Next > < Previous

Related Solutions

Let S be a set of n numbers. Let X be the set of all subsets...

Let S be a set of n numbers. Let X be the set of all subsets of S of size k, and let Y be the set of all ordered k-tuples (s1, s2, , sk) such that s1 < s2 < < sk. That is, X = {{s1, s2, , sk} | si S and all si's are distinct}, and Y = {(s1, s2, , sk) | si S and s1 < s2 < < sk}. (a) Define a one-to-one correspondence f : X → Y. Explain...

Let x, y be integers, and n be a natural number. Prove that x ^(2n) −...

Let x, y be integers, and n be a natural number. Prove that x ^(2n) − y ^(2n) is divisible by x + y

Let S be the set of all natural numbers that are describable in English words using...

Let S be the set of all natural numbers that are describable in English words using no more than 50 characters (so, 240 is in S since we can describe it as “two hundred forty”, which requires fewer than 50 characters). Assuming that we are allowed to use only the 27 standard characters (the 26 letters of the alphabet and the space character), show that there are only finitely many numbers contained in S. (In fact, perhaps you can show...

Prove That For All Natural Numbers A > 1 And B > 1, If A Divides...

Prove That For All Natural Numbers A > 1 And B > 1, If A Divides B Then A Does Not Divide B+1 (prove by contradiction)

A triangular number is the sum of the n natural numbers from 1 to n. For...

A triangular number is the sum of the n natural numbers from 1 to n. For example: The triangular number for 3 is 1 + 2 + 3 = 6 The triangular number for 7 is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 Write a program segment (using a loop), that calculates and then prints the integer n and its triangular number.

1. Prove that given n + 1 natural numbers, there are always two of them such...

1. Prove that given n + 1 natural numbers, there are always two of them such that their difference is a multiple of n. 2. Prove that there is a natural number composed with the digits 0 and 5 and divisible by 2018. both questions can be solved using pigeonhole principle.

2. Let D be a relation on the natural numbers N deﬁned by D = {(m,n)...

2. Let D be a relation on the natural numbers N deﬁned by D = {(m,n) : m | n} (i.e., D(m,n) is true when n is divisible by m. For this problem, you’ll be proving that D is a partial order. This means that you’ll need to prove that it is reﬂexive, anti-symmetric, and transitive. (a) Prove that D is reﬂexive. (Yes, you already did this problem on one of the minihomework assignments. You don’t have to redo the...

Let N(n) be the number of all partitions of [n] with no singleton blocks. And let...

Let N(n) be the number of all partitions of [n] with no singleton blocks. And let A(n) be the number of all partitions of [n] with at least one singleton block. Prove that for all n ≥ 1, N(n+1) = A(n). Hint: try to give (even an informal) bijective argument.

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1....

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1. Prove that there is a natural number k such that n divides ((m^k) − 1).

5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set...

5. Let n = 60, not a product of distinct prime numbers. Let Bn= the set of all positive divisors of n. Define addition and multiplication to be lcm and gcd as well. Now show that Bn cannot consist of a Boolean algebra under those two operators. Hint: Find the 0 and 1 elements first. Now find an element of Bn whose complement cannot be found to satisfy both equalities, no matter how we define the complement operator.

Subjects