Go Up |
Next Problems | 
Prev. Problems | 
Glossary |
Map
Problems: Infinity, Induction,
Reals
1. Use Dedekind's Theorem to show that the set of integers Z and the
interval of real numbers between 0 and 2, [0, 2], are both infinite (which is of course not
surprising).
2. Consider the set of numbers obtained by taking rational powers of rational
numbers. Is this set countable or uncountable ?
3. The collection of all polynomials with integer coefficients is countable. Prove
this by following these steps:
- Show that all polynomials of a fixed degree n (with integer coefficients) are
countable by using the above result on finite cross products.
- Show that all polynomials (with integer coefficients) are countable by writing that set
as a countable union of countable sets.
4. What is the cardinality of the open interval (-1, 1) ? How about the cardinality
of any open interval (a, b) ? Is the set R of all real numbers countable or
uncountable ?
5. Show that the set of countably infinite cross products of the set {0, 1} with
itself is not countable. In other words, the set consisting of all sequences (
,
,
,...), where each number 
is
either one or zero, is uncountable.
6. Is the set of all finite sequences of 0's and 1's countable or
uncountable ?
7. Use the Cantor-Bernstein theorem to prove the following:
- Q
and Z x Z have the same cardinality.
- R
and R x R have the same cardinality.
What is the cardinality of N x R ? How about Q x
Q ?
8. Show that the countable union of countable sets is countable.
9. Decide which of the statements below are true and which are false. If a
statement is false, provide a counterexample. If it is true, prove it.
- the union of two countable sets is countable
- the intersection of two countable sets is countable
- the union of any number of countable sets is countable
- the intersection of any number of countable sets is countable
10. Decide which of the statements below are true and which are false. If a
statement is false, provide a counterexample. If it is true, prove it.
- the union of two uncountable sets is uncountable
- the intersection of two uncountable sets is uncountable
- the union of any number of uncountable sets is uncountable
- the intersection of any number of uncountable sets is uncountable
11. Prove that any subset of a countable set is again countable.
12. Let S be the set of all function f that map N into
N. Show that S is uncountable.
13. For any given set S consider the relation r defined on the power set
P(S ) as follows:
- two subsets A and B of S are related if card(A) = card(B)
Is this relation an equivalence relation ? If S = R, then what are the
two equivalence classes defined by the above relation ?
14. If S = {1,2,3}, then what is P(S) (the power set of
S) ? What is the power set of the set S = {1, 2, 3, 4} ? How many elements does
the power set of S = {1, 2, 3, 4, 5, 6} have ? Prove in general that if S = {1, 2,
3, ..., n}, then card(P(S)) = 
.
15. Determine which of the following sets and their ordering relations are
partially ordered, ordered, or well-ordered:
- S
is any set. Define a 
b if a
= b
- S
is any set, and P(S) the power set of S.
Define A B if
A 
B
- S
is the set of real numbers between [0, 1]. Define a b if a is less than or equal to b (i.e. the 'usual'
interpretation of the symbol )
- S
is the set of real numbers between [0, 1]. Define a b if a is greater than or equal to b.
16. Which of the following sets are well-ordered ?
- The number systems N, Z, Q, or R ?
- The set of all rational numbers in [0, 1] ?
- The set of positive rational numbers whose denominator equals 3 ?
17. Use induction to prove the following statements:
- The sum of the first n positive integers is n (n+1) / 2.
- If a, b > 0, then
^n.gif)
+
for any positive integer n.
18. Use induction to prove Bernoulli's
inequality:
- If x -1 then
1 +
n x for all n
19. Try to use induction to prove that the sum of the first n square numbers is
equal to (n + 2)/3. (This induction proof should fail, since the statement is false - or is it
true ?)
20. Let S be the set of integers greater than 1. Define a relation on S by
declaring a b if b is divisible by a. Is S ordered ? Parially
Ordered ? Well-Ordered ?
21. Below are two recursive definitions, only one of which is valid. Which one is
the valid one?
- Let
= = 1 and define = 
+ 
for all n > 1.
- Let A be a subset of the natural number, and select the following subset
from the set A:
- = smallest element of A
- = smallest element of [ A
- {, , , ...,
} ]
22. The Fibonacci numbers are defined recursively as follows:
Then use induction to prove the following statements:
- the Fibonacci numbers are unbounded.
- the formula
holds for the Fibonacci numbers
23. Show that there is a unique function f from N to R
satisfying the formula
- h(1) = 3
- h(i) = sqrt( h(i-1) + 1) for i > 1
24. Show that there is no function f from N to R satisfying
the formula
- h(1) = 3
- h(i) = sqrt( h(i-1) - 1) for i > 1
25. Consider the recursion formula
- h(1) = 1
- h(2) = 2
- h(n) = [ h(n+1)]^2 - [h(n-1)]^2 for n > 1
This formula is not one to which the principle of recursive definition applies. Show that
nevertheless there does exist a function from N to R that satisfies this
formula by reformulating the recursion formula somewhat. Note that it may be necessary
to show that the function h is positive.
26. Consider the set S of all rational numbers strictly between 0 and 1.
- Find 5 different upper bounds for S
- Find the least upper bound for S.
- Is there any difference for the set [0, 1] ?
27. Consider the set of rational numbers {1, 1.4, 1.41, 1.414, 1.4142, ...}
converging to the square root of 2.
- What is the least upper bound of this set, if all we knew were the rational numbers?
- What is the least upper bound of this set, allowing real numbers ?
28. Show that the sum of a rational number and an irrational number is
irrational. What about the sum of two irrational numbers ? What about the product of two
irrational numbers?
29. Show that there exists a real number whose square is 3.
Go Up |
Next Problems | Prev. Problems | Glossary |
Map
(bgw)