24.118: Paradox and Infinity PS 1: Suggested solutions

October 16, 2001

1.

(5 pts)

There is no one correct solution to the problem, but here are some thoughts on the matter. The situation considered from a physical point of view. The scenario described is actually physically impossible, since an infinite amount of energy would be needed to turn the bulb on infinitely many times (each time, it takes some constant minimum of energy to turn on the bulb; what decreases is the extra time–after coming on–that the bulb is shining). So suspend the actual laws of physics. If we consider the scenario in a setting in which the laws of nature are different (suppose there is an infinite amount of enery around that could be expended on the task), the lamp may be either on or off at t = 1, which depends on the particular laws of nature that hold in this counterfactual situation. It may be on (Law: ‘Every bulb that has shone infinitely many times shines on forever’), off (Law: ‘A bulb that has shone infinitely many times remains dark forever’) or indeterminate (Law: ‘A bulb that has shone infinitely many times may either be on or off’. Admittedly, none of these laws strike us as very plausible, but they are at least logically possible laws or follow from logically possible laws). So if we consider the situation from a (possible) physical point of view, we cannot say anything concrete about the state of the lamp—it just depends on what the laws are in the imagined situation.

The situation considered from a mathematical point of view. In a mathematical setting, all the information given is the state of the lamp at points arbitrarily close to 1, but we lack information about the lamps’ state at t = 1. But not only is it a matter of us not knowing what the state of the lamp is at time t=1: The state of the lamp is a function of the time t. Represent ‘on’ by ‘1’ and ‘off’ by ‘0’. The function, call it ‘f’, has been defined so that

f(1/2) = 1, f(3/4) = 0, f(7/8) = 1, f(15/16) = 0

(If you want, fill in the gaps: The value of f at t for 1/2 ≤ t < 3/4 is 1, etc.) But this function is not defined for the argument 1. So it is indeterminate what the value of f is at 1, or rather: It has no value at 1.

The situation here differs in an important respect from the scenario that underlies the various versions of Zeno’s paradox: In (most of) these, the relevant series of states converges to a unique state. For instance, as we move towards the door in ever decreasing steps, we get closer and closer to the door, that is, as t (the time-variable) approaches 1, we apprach the state of being at the door. In the case of the lamp, as t approaches 1, the series of states of the lamp does not converge to a unique state.

2.

(5 pts each)

A function from a set A to a set B is mapping that assigns exactly one member of B to each element of A. A function f from A to B is 1-1 if for every element b in B there is at most one element a in A such that f assigns b to a (usually written as: f(a) = b). Put differently, if f is 1-1, then it assigns to every element of A its own element of B. A function f from A to B is onto if for every element b in B there is at least one element a in A such that f assigns b to a (f(a) = b). Put differently, if f is onto, then it ‘uses’ up all of B. In general, if set A has α many elements and B has β many elements, then there are β^{α} many functions from A to B. Writing them out is (if α, β are both finite) straightforward but can be rather tedious (as I’m sure you discovered for yourself). Therefore, I won’t go through all of them.

(a) There are 2^{2} many functions from B to B. In this case the functions that are 1 − 1 are also onto:

(i) f(Al)=Al f(Bruce)=Bruce

This can also be written as: f = {⟨Al,Al⟩, ⟨Bruce,Bruce⟩}

(ii) f(Al)=Bruce f(Bruce)=Al This can also be written as: f = {⟨Al,Bruce⟩, ⟨Bruce,Al⟩}

The remaining two functions are neither 1 − 1 nor onto:

(i) f(Al)=Al f(Bruce)=Al

(ii) f(Al)=Bruce f(Bruce)=Bruce

(b) There are 3^{2} many functions from B to G. The following are 1 − 1 (no two elements of A get mapped to the same element in B):

(i) f(Al)=Xochitl f(Bruce)=Yolanda

(ii) f(Al)=Xochitl f(Bruce)=Zaida

(iii) f(Al)=Yolanda f(Bruce)=Xochitl

(iv) f(Al)=Yolanda f(Bruce)=Zaida

(v) f(Al)=Zaida f(Bruce)=Xochitl

(vi) f(Al)=Zaida f(Bruce)=Yolanda There are no onto functions from B to G because there are not enough elements in B to map one to each element of G.

(c) There are 2^{3} functions from G to B. None of them are 1 − 1 because B does not have enough elements. All but two of the functions are onto (the two that aren’t are the one that maps all elements of G to Al and the one that maps all elements of G to Bruce.

(d) There are 3^{3} functions from G to itself. Of these, 6 are both 1 − 1 and onto.

3.

(5 pts each)

(a) There are 9^{2} functions from B to C. None of these are onto (C has too many elements). All but nine of the functions are 1 − 1 (namely the nine that map both elements of B to the same element of G).

(b) There are 2^{9} functions from C to B. None of these are 1 − 1 (C has too many elements). All but two of these are onto (namely the two functions that map all elements of C to only one of the elements of B).

4.

(5 pts)

Let

α = #{f|f : N → R}

be the number of functions from the natural numbers to the reals and

β = #{f|f : R → N}

the number of functions from the real numbers to the naturals. Computing α is straightforward: By definition of cardinal exponentiation (p2 of the handout) α is the number of real numbers (2^{ℵ_{0}}) raised to the number of natural numbers (ℵ_{0}), i.e. α = (2^{ℵ_{0}})^{ℵ_{0}}. Further, by one of the exponentiation rules, we get that

α = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{(ℵ_{0}×ℵ_{0})}

So, since ℵ_{0} × ℵ_{0} = ℵ_{0}, we get

α = #{f|f : N → R} = 2^{ℵ_{0}}

Next, we need to determine, how many functions there are from the reals to the naturals. First, note that there are at least 2^{(2^{ℵ_{0}})} of them because every set S of reals can be represented by a function from reals to naturals. For a set S of reals define f_{S}, the characteristic function of S (as it was called in class), as follows:

f(r) = 1 iff r ∈ S
f(r) = 0 iff r ∉ S

Since there are 2^{(2^{ℵ_{0}})} sets of reals, there are 2^{(2^{ℵ_{0}})} many characteristic functions, so there are at least 2^{(2^{ℵ_{0}})} many functions from reals to naturals.

Next, determine how many functions from reals to naturals there are at most. Note that each function f from reals to naturals can be represented by a collection of pairs of reals and naturals: For each such function f we have

fmaps real r_{1}to natural n_{1}
fmaps real r_{2}to natural n_{2}
…

(and so on for every real r)

As we saw in class, each real can be coded as an infinite sequence of naturals:

r ↦ ⟨n_{1}, n_{2}, n_{3}, …, n_{m}, …⟩

In order to represent the fact that function f maps real r to natural n, we can use the infinite sequence

s = ⟨n, n_{1}, n_{2}, n_{3}, …, n_{m}, …⟩

However, s just represents another real number. A single function from reals to naturals can thus be represented as a collection of reals. But that means that there can be no more functions from the reals to the naturals than there are sets of reals, i.e. 2^{(2^{ℵ_{0}})} many! So we have 2^{(2^{ℵ_{0}})} ≤ β ≤ 2^{(2^{ℵ_{0}})}. Then the Schröder-Berstein Theorem allows us to conclude that β = 2^{(2^{ℵ_{0}})}.

By Cantor’s theorem, 2^{ℵ_{0}} < 2^{(2^{ℵ_{0}})}, so we conclude that α < β.