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 X₁, X₂, . . . , X_n are all enumerable, so is X₁ U . . . U X_n.

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 B^k → 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 X₁, X₂, . . . are sets, and each X_i is enumerable, then the union U_i=1^∞ X_i 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 N³.

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 f₁, f₂, . . . , is a list of functions and each f_i : 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.