Reference no: EM132381022
The Size of Sets Problems -
Problem 1 - According to Definition 4.4, a set X is enumerable iff X = ∅ or there is a surjective f : Z+ → X. It is also possible to define "enumerable set" precisely by: a set is enumerable iff there is an injective function g : X → Z+. Show that the definitions are equivalent, i.e., show that there is an injective function g : X → Z+ iff either X = ∅ or there is a surjective f : Z+ → X.
Problem 2 - Define an enumeration of the positive squares 4, 9, 16, . . .
Problem 3 - Show that if X and Y are enumerable, so is X U Y.
Problem 4 - Show by induction on n that if X1, X2, . . . , Xn are all enumerable, so is X1 U . . . U Xn.
Problem 5 - Give an enumeration of the set of all positive rational numbers. (A positive rational number is one that can be written as a fraction n/m with n,m ∈ Z+).
Problem 6 - Show that Q is enumerable. (A rational number is one that can be written as a fraction z/m with z ∈ Z, m ∈ Z+).
Problem 7 - Define an enumeration of B*.
Problem 8 - Recall from your introductory logic course that each possible truth table expresses a truth function. In other words, the truth functions are all functions from Bk → B for some k. Prove that the set of all truth functions is enumerable.
Problem 9 - Show that the set of all finite subsets of an arbitrary infinite enumerable set is enumerable.
Problem 10 - A set of positive integers is said to be cofinite iff it is the complement of a finite set of positive integers. Let I be the set that contains all the finite and cofinite sets of positive integers. Show that I is enumerable.
Problem 11 - Show that the enumerable union of enumerable sets is enumerable. That is, whenever X1, X2, . . . are sets, and each Xi is enumerable, then the union Ui=1∞ Xi of all of them is also enumerable.
Problem 12 - Let f : X x Y → Z+ be an arbitrary pairing function. Show that the inverse of f is an enumeration of X x Y.
Problem 13 - Specify a function that encodes N3.
Problem 14 - Show that ρ(N) is non-enumerable by a diagonal argument.
Problem 15 - Show that the set of functions f : Z+ → Z+ is non-enumerable by an explicit diagonal argument. That is, show that if f1, f2, . . . , is a list of functions and each fi : Z+ → Z+, then there is some f- : Z+ → Z+ not on this list.
Problem 16 - Show that if there is an injective function g : Y → X, and Y is non-enumerable, then so is X. Do this by showing how you can use g to turn an enumeration of X into one of Y.
Problem 17 - Show that the set of all sets of pairs of positive integers is non-enumerable by a reduction argument.
Problem 18 - Show that Nω, the set of infinite sequences of natural numbers, is non-enumerable by a reduction argument.
Problem 19 - Let P be the set of functions from the set of positive integers to the set {0}, and let Q be the set of partial functions from the set of positive integers to the set f0g. Show that P is enumerable and Q is not. (Hint: reduce the problem of enumerating Bω to enumerating Q).
Problem 20 - Let S be the set of all surjective functions from the set of positive integers to the set {0,1}, i.e., S consists of all surjective f : Z+ → B. Show that S is non-enumerable.
Problem 21 - Show that the set R of all real numbers is non-enumerable.
Problem 22 - Show that if X is equinumerous with U and and Y is equinumerous with V, and the intersections X ∩ Y and U ∩ V are empty, then the unions X U Y and U U V are equinumerous.
Problem 23 - Show that if X is infinite and enumerable, then it is equinumerous with the positive integers Z+.
Problem 24 - Show that there cannot be an injective function g : ρ(X) → X, for any set X. Hint: Suppose g : ρ(X) → X is injective. Then for each x ∈ X there is at most one Y ⊆ X such that g(Y) = x. Define a set Y such that for every x ∈ X, g(Y-) ≠ x.