|
|
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
quasi-linear 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)
|
|
