
Re: Some Questions about Infinite Sets
Posted:
May 13, 2011 2:33 PM


On May 13, 4:16 am, jbriggs444 <jbriggs...@gmail.com> wrote: > On May 12, 5:49 am, Han de Bruijn <umum...@gmail.com> wrote: > > I suppose this method must be well known. I'm curious about a name and > > a reference, eventually. > It's called the Inverse Function Rule. The term was coined > by Tony Orlow.
Yes, TO first came up with the IFR, and now HdB is posting something similar to it.
Bringing this back to the Katz paper, we see that the closest Katz comes to the IFR is his OUTPACING principle:
"Definition 6.1.1. x outpaces y just in case the restriction of x to any sufficiently large initial segment of N is larger than the corresponding restriction of y, that is, iff:
EnAm(m > n ? x[m] > y[m])
Notice that the size comparison between the two restricted sets will always agree with the comparison of their normal cardinalities since all initial segments of N are finite. We employ this notion to state a sufficient condition for one set of natural numbers to be larger than another:
OUTPACING. If x outpaces y, then x > y.
The general motivation behind this principle should be familiar. We extrapolate from well understood finite cases to puzzling infinite cases." (Katz, page 83)
The main difference between IFR and OUTPACING is that the latter merely compares pairs of sets, while the former seeks to give a _name_ to each equivalence class (like log(aleph_0)).
> A more general notion is "asymptotic density".
Katz shows the relationship between his OUTPACING and density in the following:
"Theorem 6.3.4. Suppose that both x and y converge in z. Then, if rho(x, z) < rho(y, z), y outpaces x." (Katz, page 95)
Here Katz uses rho(x,y) to denote the density of x in y. The usual asympotic density is rho(x,N) or just rho(x).
> Neither gives rise to a total ordering on the "set size" of > the subsets of the naturals.
Yes, even Katz admits as much:
"[x > y iff x outpaces y] conflicts with CS, for outpacing is not a quasilinear or dering. For example, neither [2n] nor [2n + 1] outpaces the other since each initial segment {0, . . . , 2n + 1} of N contains n evens and n odds. But the two are discernible under outpacing, since [2n] outpaces [2n + 2] while [2n + 1] does not." (Katz, page 84)

