mm-1249
===
Subject: Planning in card shufßing
To my understanding I suppose a shufße of cards is a
probability
distribution on the permutation group of the cards. Given a
deck of
cards and a number of shufßes is there a method to \[CapitalThorn]nd a
combination
of those shufßes that can achieve a certain requirements, for
example: A full house on top of the deck with probability
greater than
a half.
===
Subject: Computational problem in symmetric group using GAP
By using GAP - http://www.gap-system.org/
How can i express a given element in a symmetric group as a
product of
certain \[CapitalThorn]xed elements in the same symmetric group, if
possible by
using GAP? Examples of real implementations (by GAP, or
Maple?) are
mostly welcomed!
===
Subject: How much lossless compression is possible in images?
Assuming ideal compression that removes every trace of
redundancy from
an image, how much lossless compression might really be
possible? I
know this is a dif\[CapitalThorn]cult question because so much depends on
image
content, but IÕm just trying to get an idea of how close
current
lossless compression methods are to the ideal. Visually
images seem to
be very highly redundant, although current lossless
algorithms only
manage about 50% compression. But assuming time and space
were not
constraints, how far could one theoretically go?
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Re: How much lossless compression is possible in
images?
posting-account=uMDgiw0AAAANoAxJOs_DnrtdjhRMBFah
> Assuming ideal compression that removes every trace of
redundancy
from
> an image, how much lossless compression might really be
possible? I
> know this is a dif\[CapitalThorn]cult question because so much depends on
image
> content, but IÕm just trying to get an idea of how close
current
> lossless compression methods are to the ideal. Visually
images seem
to
> be very highly redundant, although current lossless
algorithms only
> manage about 50% compression. But assuming time and space
were not
> constraints, how far could one theoretically go?
Time and space are not constraints? Okay then . . .
Fix some binary representation x of your image, and some
universal
Turing
machine U. Begin computations of U(0), U(1), U(00), U(01),
U(10), and
so
on up to U(smax) where smax encodes Print x and stop. After
BB(n)
steps
(where n is the number of computations youÕre running), all
the
computations
that eventually halt will have halted. Now look at the output
of all
the
computations, and pick the (lexigraphically) \[CapitalThorn]rst string s
such that
U(s)
halted leaving x on the tape.
The function BB() is known as the Busy Beaver function. For a
typical,
say
4 megabyte, image, youÕll have to run your computations for
about
BB(10^10^7)
steps. This number is kind of big, and just to compute it is
kind of
hard.
[And Jmes Hrris is kind of unlikely to prove FermtÕs Lst
Theorem.]
The length of the chosen, minimal s is known as the Kolmogorov
complexity of
x. It is the ultimate measure of how much information is
contained in
a
string, though it is kind of hard to compute in practice.
===
Subject: Re: How much lossless compression is possible in
images?
> Time and space are not constraints? Okay then . . .
> Fix some binary representation x of your image, and some
universal
> Turing
> machine U. Begin computations of U(0), U(1), U(00), U(01),
U(10), and
> so
> on up to U(smax) where smax encodes Print x and stop. After
BB(n)
> steps
> (where n is the number of computations youÕre running), \
all
the
> computations
> that eventually halt will have halted. Now look at the
output of all
> the
> computations, and pick the (lexigraphically) \[CapitalThorn]rst string s
such that
> U(s)
> halted leaving x on the tape.
> The function BB() is known as the Busy Beaver function. For
a typical,
> say
> 4 megabyte, image, youÕll have to run your computations \
for
about
> BB(10^10^7)
> steps. This number is kind of big, and just to compute it
is kind of
> hard.
> [And Jmes Hrris is kind of unlikely to prove FermtÕs Lst
Theorem.]
> The length of the chosen, minimal s is known as the
Kolmogorov
> complexity of
> x. It is the ultimate measure of how much information is
contained in
> string, though it is kind of hard to compute in practice.
So how much compression could you get?
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Re: How much lossless compression is possible in
images?
> Assuming ideal compression that removes every trace of
redundancy from
> an image, how much lossless compression might really be
possible? I
> know this is a dif\[CapitalThorn]cult question because so much depends on
image
> content, but IÕm just trying to get an idea of how close
current
> lossless compression methods are to the ideal. Visually
images seem to
> be very highly redundant, although current lossless
algorithms only
> manage about 50% compression. But assuming time and space
were not
> constraints, how far could one theoretically go?
> --
> Transpose hotmail and mxsmanic in my e-mail address to
reach me directly.
It depends totally on image content.
An image consisting of random pixels will not compress at all
(0%
compression) using a generic algorithm; an image consisting
of entirely one
colour will compress almost to zero (almost 100% compression).
A photos maximum compression will vary between 0% and 100%
depending upon
the amount of random detail in the photo.
===
Subject: Re: How much lossless compression is possible in
images?
...
> An image consisting of random pixels will not compress at
all (0%
> compression) using a generic algorithm; an image consisting
of entirely
one
> colour will compress almost to zero (almost 100%
compression).
If you use a generic algorithm it is pretty likely that an
image consisting
of random pixels will expand and not compress.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam,
nederland,
+31205924131
home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~dik/
===
Subject: Re: How much lossless compression is possible in
images?
> If you use a generic algorithm it is pretty likely that an
image
consisting
> of random pixels will expand and not compress.
Actually, the chance that a random image will become smaller
after
compression with any given algorithm is always 0.5. The
change that it
will become larger is thus also 0.5. Half of all random
images will be
smaller; the other half will be larger. This is true no
matter what
algorithm is used, as long as it is lossless (reversible).
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Re: How much lossless compression is possible in
images?
> It depends totally on image content.
> An image consisting of random pixels will not compress at
all (0%
> compression) using a generic algorithm; an image consisting
of entirely
one
> colour will compress almost to zero (almost 100%
compression).
> A photos maximum compression will vary between 0% and 100%
depending upon
> the amount of random detail in the photo.
My understanding has been that a Fourier transformation can
greatly
compress data, but that the best compression is achieved by
analyzing
and compressing the entire data set as a single unit, which is
impractical in real life because itÕs computationally very
dif\[CapitalThorn]cult to
analyze, say, an entire 400 MB of image data and produce a
single
transformation encompassing that entire \[CapitalThorn]le. If it were done,
though,
I presume it would be very compact indeed. Can anyone con\[CapitalThorn]rm
this?
I know that some existing systems also allow for a bit of
image-dependent customization, but that it often isnÕt
carried out
because of the overhead.
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Re: How much lossless compression is possible in
images?
<41b3ed05$0$9113$afc38c87@news.optusnet.com.au>
<f718r0l6iksda51uskrd5ie2dtfvjd35vs@4ax.com>
posting-account=Qiuj5AwAAACmGnmS12qcvqA9IXzD0s4L
gif uses run length encode
r r r r -> 4r
so its only suitable for a low color pallete
jpg fourier transforms the image, then uses run length encode
on that.
often the \[CapitalThorn]nal digits of each row are 0Õs, \
these are the high
frequencies (the detail) and compression just ignores some of
them.
if you only chop 0Õs you get lossless compression, if you \
chop
00002000030001000 it gets lossy.
quadtree is a recursive subdividing algorithm that could be
useful for
maps but never took off. i devised a composite quadtree gif
system.
the quadtree seperates the image into discernible simple
sections, and
the run length encode is tested at 360 different angles to
\[CapitalThorn]nd the
best compression. basically it searches for line segments,
suitable
for vector type graphics, stickmen.
what gets me is why they canÕt add a pollish function to \
jpeg
decompression, obviously a big single color area with a
border edge
around it is not meant to get ÔpixelatedÕ at the \
border.
apparently there is a fractal equation for every photo in
existence.
some amazing pictures of womens faces were constructed with
equations
(very high compression) if you can tailor the image somewhat.
and the
detail just keeps up as you zoom in..
computer games cheat, they store a library of tile bitmaps
and surface
everything, why download when you can put in a DVD of a
million
pictures and the computer just selects.
Herc
===
Subject: Re: How much lossless compression is possible in
images?
> gif uses run length encode
> r r r r -> 4r
Wrong. Gif uses LZW.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam,
nederland,
+31205924131
home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~dik/
===
Subject: Re: How much lossless compression is possible in
images?
> Assuming ideal compression that removes every trace of
redundancy from
> an image, how much lossless compression might really be
possible? I
> know this is a dif\[CapitalThorn]cult question because so much depends on
image
> content, but IÕm just trying to get an idea of how close
current
> lossless compression methods are to the ideal. Visually
images seem to
> be very highly redundant, although current lossless
algorithms only
> manage about 50% compression. But assuming time and space
were not
> constraints, how far could one theoretically go?
> --
> Transpose hotmail and mxsmanic in my e-mail address to
reach me
directly.
> It depends totally on image content.
> An image consisting of random pixels will not compress at
all (0%
> compression) using a generic algorithm; an image consisting
of entirely
one
> colour will compress almost to zero (almost 100%
compression).
I donÕt have the math at hand, but I believe that a truly
random image
would have at least some compressible areas. In a strange
sense, a
completely incompressible image would be as ordered as a
single color
image.
===
Subject: Re: How much lossless compression is possible in
images?
>> Assuming ideal compression that removes every trace of
redundancy from
>> an image, how much lossless compression might really be
possible? I
>> know this is a dif\[CapitalThorn]cult question because so much depends
on image
>> content, but IÕm just trying to get an idea of how close
current
>> lossless compression methods are to the ideal. Visually
images seem
to
>> be very highly redundant, although current lossless
algorithms only
>> manage about 50% compression. But assuming time and space
were not
>> constraints, how far could one theoretically go?
>>
>> --
>> Transpose hotmail and mxsmanic in my e-mail address to
reach me
>directly.
>> It depends totally on image content.
>> An image consisting of random pixels will not compress at
all (0%
>> compression) using a generic algorithm; an image
consisting of entirely
>one
>> colour will compress almost to zero (almost 100%
compression).
>I donÕt have the math at hand, but I believe that a truly
random image
>would have at least some compressible areas. In a strange
sense, a
>completely incompressible image would be as ordered as a
single color
image.
ThereÕs no such thing as an incompressible image, _until_ \
you
specify
what algorithm youÕre using. Given _any_ image I_0 there \
_is_
a
lossless compression algorithm that compresses I_0 to a
one-byte \[CapitalThorn]le:
def compress(I):
if I == I_0:
return a single 0 byte
else:
return a 1, followed by I.
I leave the decompressor as an exercise.
************************
David C. Ullrich
===
Subject: Re: How much lossless compression is possible in
images?
>> Assuming ideal compression that removes every trace of
redundancy from
>> an image, how much lossless compression might really be
possible? I
>> know this is a dif\[CapitalThorn]cult question because so much depends
on image
>> content, but IÕm just trying to get an idea of how close
current
>> lossless compression methods are to the ideal. Visually
images seem
to
>> be very highly redundant, although current lossless
algorithms only
>> manage about 50% compression. But assuming time and space
were not
>> constraints, how far could one theoretically go?
>>
>> --
>> Transpose hotmail and mxsmanic in my e-mail address to
reach me
> directly.
>> It depends totally on image content.
>> An image consisting of random pixels will not compress at
all (0%
>> compression) using a generic algorithm; an image
consisting of entirely
> one
>> colour will compress almost to zero (almost 100%
compression).
> I donÕt have the math at hand, but I believe that a truly
random
image
> would have at least some compressible areas. In a strange
sense, a
> completely incompressible image would be as ordered as a
single color
> image.
Well, you would be wrong. At least one de\[CapitalThorn]nition of random is
that an
image canÕt be compressed. I know of no \
de\[CapitalThorn]nition of random
which would
allow every or even most random images to have at least some
compressible
areas.
And what is completely incompressible image supposed to mean?
HereÕs a little mathematical titbit, which follows
immediately from the
pigeon hole principle:
The average image size (averaged across all possible images)
of images
compressed using lossless algorithms must be equal to or
greater than the
uncompressed image size.
Indeed, for all practical lossless compression algorithms,
the huge majority
of all all images are larger when compressed than they are
before
compression. Its just the tiny minority of images which get
smaller are
those that have characteristics often found in photos - such
as large areas
with only moderate colour variability.
===
Subject: Re: How much lossless compression is possible in
images?
> Well, you would be wrong. At least one de\[CapitalThorn]nition of random
is that an
> image canÕt be compressed.
More precisely perhaps, the average compression possible for
random
images approaches zero as the number of images approaches
in\[CapitalThorn]nity.
However, since a given random image may (unpredictably)
contain any
degree of redundancy, virtually all random images are
compressible to
some extent using some algorithms.
Put still another way, no algorithm exists (or can be
devised) that will
compress a random string of bits more than 50% of the time.
In fact, no
matter what the algorithm is, it will produce a shorter
output string
50% of the time, and a longer output string the other 50% of
the time.
> I know of no de\[CapitalThorn]nition of random which would
> allow every or even most random images to have at least
some compressible
> areas.
See above.
> The average image size (averaged across all possible
images) of images
> compressed using lossless algorithms must be equal to or
greater than the
> uncompressed image size.
Yes. Compression algorithms work only because all possible
images are
not equally probable. For every possible image that can be
compressed,
there exists some other image that will increase in size by
the same
amount after compression, if the compression is lossless
(reversible).
In real life, image data corresponding to pictorial
representations is
far more probable than random image data (even though the
number of
non-pictoral images possible vastly exceeds the number of
pictoral
images possible). So compression works.
> Indeed, for all practical lossless compression algorithms,
the huge
majority
> of all all images are larger when compressed than they are
before
> compression. Its just the tiny minority of images which get
smaller are
> those that have characteristics often found in photos -
such as large
areas
> with only moderate colour variability.
Yes. A different way of stating what IÕve said above.
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Re: How much lossless compression is possible in
images?
Originator: richard@cogsci.ed.ac.uk (Richard Tobin)
>> I donÕt have the math at hand, but I believe that a truly
random
image
>> would have at least some compressible areas.
>Well, you would be wrong. At least one de\[CapitalThorn]nition of random
is that an
>image canÕt be compressed. I know of no \
de\[CapitalThorn]nition of random
which
would
>allow every or even most random images to have at least some
compressible
>areas.
Suppose you choose some compression algorithm - simple
run-length
encoding of bytes for example. Suppose it uses a byte for the
length.
Any sequence of 3 or more equal bytes will be compressible.
Any
reasonably large image will have such a sequence in it, so it
will
have a part that can be compressed. (A large image that
didnÕt have
such a sequence would be most unlikely, if it really was
random.)
So itÕs true that suf\[CapitalThorn]ciently large random \
images will have
some
compressible areas.
This doesnÕt do you any good in practice, because you need \
to
distinguish the compressed areas from non-compressed areas
that just
happen to have the same values. You need extra bits for this,
so
you wonÕt end up with any compression overall.
>The average image size (averaged across all possible images)
of images
>compressed using lossless algorithms must be equal to or
greater than the
>uncompressed image size.
The unix compress program always produces a \[CapitalThorn]le which is the
same
size as the original or smaller, which it achieves by not
compressing
the \[CapitalThorn]le if compression would not make it smaller. However, it
appends .Z to the \[CapitalThorn]lename if it compresses it, and you have
to take
those extra bytes into acccount when determining the real
compression
ratio.
-- Richard
===
Subject: Re: How much lossless compression is possible in
images?
>>
>> Assuming ideal compression that removes every trace of
redundancy
from
>> an image, how much lossless compression might really be
possible? I
>> know this is a dif\[CapitalThorn]cult question because so much depends
on image
>> content, but IÕm just trying to get an idea of how close
current
>> lossless compression methods are to the ideal. Visually
images seem
to
>> be very highly redundant, although current lossless
algorithms only
>> manage about 50% compression. But assuming time and space
were not
>> constraints, how far could one theoretically go?
>>
>> --
>> Transpose hotmail and mxsmanic in my e-mail address to
reach me
> directly.
>>
>> It depends totally on image content.
>>
>> An image consisting of random pixels will not compress at
all (0%
>> compression) using a generic algorithm; an image
consisting of
entirely
> one
>> colour will compress almost to zero (almost 100%
compression).
> I donÕt have the math at hand, but I believe that a truly
random
image
> would have at least some compressible areas. In a strange
sense, a
> completely incompressible image would be as ordered as a
single color
> image.
> Well, you would be wrong. At least one de\[CapitalThorn]nition of random
is that
an
> image canÕt be compressed. I know of no \
de\[CapitalThorn]nition of random
which
would
> allow every or even most random images to have at least
some compressible
> areas.
> And what is completely incompressible image supposed to
mean?
How about an image consisting of random pixels [that] will
not compress
at
all?
===
Subject: Re: How much lossless compression is possible in
images?
> How about an image consisting of random pixels [that] will
not compress
at
> all?
It is always possible to devise an algorithm that will
compress any one
given image, no matter how random it may appear to be.
--
Transpose hotmail and mxsmanic in my e-mail address to reach
me directly.
===
Subject: Questions of Higher Order Derivatives; and their
Inverses
Can someone provide me with a better proof than this; somehow
I missed
this relation in undergraduate calculus:
(d^2s/dt^2)(dt/ds)^3 = -d^2t/ds^2
I differentiate the unit tangent vector, T =dr/ds, with
respect to t:
dT/dt = d(dr/ds)/dt
= d(dr/dt)(dt/ds)/dt
= (d^2r/dt^2)(dt/ds) + (d^2t/ds^2)(ds/dt)(dr/dt)
= (d^2r/ds^2)(ds/dt)
multiply by (dt/ds):
(dT/dt)(dt/ds) = d^2r/ds^2
= (d^2r/dt^2)(dt/ds)^2 + (d^2t/ds^2)(dr/dt)
(A)
In literature, in matrix form (stated without proof, easy
enough to
do), I \[CapitalThorn]nd:
| (ds/dt) (d^2s/dt^2)|
d^2r/ds^2 = | | * (dt/ds)^3
| (dr/dt) (d^r/dt^2)|
or, = (d^2r/dt^2)(dt/ds)^2 -
(dr/dt)(d^2s/dt^2)(dt/ds)^3 (B)
if Equation (A) = Equation (B)
then, (d^2s/dt^2)(dt/ds)^3 = -(d^2t/ds^2)
I extend it this way:
(ds/dt)(dt/ds)^2 = dt/ds
(d^2s/dt^2)(dt/ds)^3 = -d^2t/ds^2
(d^3s/dt^3)(dt/ds)^4 = d^3t/ds^3
(d^4s/dt^4)(dt/ds)^5 = -d^4t/ds^4
I also have a similar proof for:
(d^2r/dt^2)(dt/ds)^2 = (d^2r/ds^2)
But have not known of these simple relations; nor have been
able to
make a simple proof of it, using the de\[CapitalThorn]nition of
differentiation or
at least using:
Du^n/dx = [(1/n)u ^(n-1)]dx
I really donÕt have the necessary understanding of
differentials, and
differentiation, to prove the relations directly, or to even
ask the
proper questions, I guess; can someone help?
Charles
===
Subject: Re: topology 22
<\[CapitalThorn]Ksd.29098$zx1.2859@newssvr13.news.prodigy.com>
>>\[CapitalThorn]nd the subset W,X,Y,Z of real topology R
>>which satisfy (1),(2),(3),(4).
>>(without proof)
>>
>>(1) Y,Z is connected set
>>(2) Y in W in Z , Y in X in Z
> I donÕt get this, how can a subset of R can be in a subset
of R?
> The elements of a subset of R are numbers, arenÕt subsets
of R.
> This is a problem of the imprecise use of the word in.
Sloppy and confusing.
> A person might say the number 1 is in the interval [0, 2],
> and the same person might say the subset [1,2] is in the
> same interval. The OP should probably have used a different
> set of words.
How weird. Does ÔinÕ mean \
ÔsubsetÕ? That doesnÕt make \
sense.
===
Subject: Re: topology 22
>>\[CapitalThorn]nd the subset W,X,Y,Z of real topology R
>>which satisfy (1),(2),(3),(4).
>>(without proof)
>>
>>(1) Y,Z is connected set
>>(2) Y in W in Z , Y in X in Z
>
> I donÕt get this, how can a subset of R can be in a subset
of R?
> The elements of a subset of R are numbers, arenÕt subsets
of R.
> This is a problem of the imprecise use of the word in.
> Sloppy and confusing.
> A person might say the number 1 is in the interval [0, 2],
> and the same person might say the subset [1,2] is in the
> same interval. The OP should probably have used a different
> set of words.
> How weird. Does ÔinÕ mean \
ÔsubsetÕ? That doesnÕt make \
sense.
original problem is
\[CapitalThorn]nd the subset W,X,Y,Z of real topology R
which satisfy (1),(2),(3),(4).
(without proof)
(1) Y,Z is connected set
(2) Y C W C Z , Y C X C Z
(2) W is connected set
(4) X is not connected set
(symbol A C B = A is proper subset of B)
um.....(0,1) C (0,2) ....is this wrong ??
thank you very much for your advice.
===
Subject: Re: topology 22
> original problem is
> \[CapitalThorn]nd the subset W,X,Y,Z of real topology R
> which satisfy (1),(2),(3),(4).
> (without proof)
> (1) Y,Z is connected set
> (2) Y C W C Z , Y C X C Z
> (2) W is connected set
> (4) X is not connected set
> (symbol A C B = A is proper subset of B)
> um.....(0,1) C (0,2) ....is this wrong ??
> thank you very much for your advice.
And whats this real topology, do you mean euclidean topology
on real
numbers?
ItÕs quite easy.. since X contains a connected set then you
can easily
use the trick of X having two connected components. Example:
Y=(0,1), X=(0,1) union {2}
W=(0,2), Z=(0,3)
Jose Capco
===
Subject: Re: topology 22
<cp15dp$2jl$1@news.hananet.net>
>>\[CapitalThorn]nd the subset W,X,Y,Z of real topology R
>>which satisfy (1),(2),(3),(4).
>>
>>(1) Y,Z is connected set
>>(2) Y in W in Z , Y in X in Z
>
> I donÕt get this, how can a subset of R can be in a subset
of R?
> The elements of a subset of R are numbers, arenÕt subsets
of R.
>
> This is a problem of the imprecise use of the word in.
> Sloppy and confusing.
> A person might say the number 1 is in the interval [0, 2],
> and the same person might say the subset [1,2] is in the
> same interval. The OP should probably have used a different
> set of words.
>
> How weird. Does ÔinÕ mean \
ÔsubsetÕ? That doesnÕt make \
sense.
> original problem is
> \[CapitalThorn]nd the subset W,X,Y,Z of real topology R
> which satisfy (1),(2),(3),(4).
> (1) Y,Z is connected set
> (2) Y C W C Z , Y C X C Z
> (2) W is connected set
> (4) X is not connected set
> (symbol A C B = A is proper subset of B)
> um.....(0,1) C (0,2) ....is this wrong ??
Howver subset and proper subset symbols donÕt do well in
ascii.
A C E for example is a word. Some use < and <=, which is
very context sensitive and when talking both subset and
less than in same statement as for example
a < b ==> (b,r) < (a,r)
could be bothersome.
TeX uses subseteq and subset
However for ascii, subset and subsetneq would be clearer
for indeed proper subset means subset and /=.
I use subset and proper subset as need for
proper subset is infrequent.
ÔinÕ as Ôelement ofÕ \
is clear.
For a sequence, (x_n)_n within S can be more elucidating and
precise,
for (x_n)_n isnÕt a subset of S but only itÕs \
values, and
again
(x_n)_n not in S for itÕs not a element of S.
===
Subject: Re: SkolemÕs Paradox and why is math the way it is?
|I have a question about the universe of discourse, could you
please expand
|what you mean when you say that there are larger realms of
discourse than
set
|theory?
Well, partly I had in mind that there isnÕt just the one
system of
sets (the cumulative hierarchy). There are also the
non-well-founded
sets and the like. Restricting to just well-founded sets is a
way of
ensuring a certain kind of good behavior, but surely not
absolutely
necessary.
Also although there are often ways of representing
mathematical objects
as sets, itÕs somewhat arti\[CapitalThorn]cial to do so in \
many cases.
Meanwhile, there are constructions in category theory that
appear to
make sense, but are too big to be sets as they stand.
Keith Ramsay
===
Subject: Re: SkolemÕs Paradox and why is math the way it is?
> |I have a question about the universe of discourse, could
you please
expand
> |what you mean when you say that there are larger realms of
discourse than
set
> |theory?
> Well, partly I had in mind that there isnÕt just the one
system of
> sets (the cumulative hierarchy). There are also the
non-well-founded
> sets and the like. Restricting to just well-founded sets is
a way of
> ensuring a certain kind of good behavior, but surely not
absolutely
> necessary.
> Also although there are often ways of representing
mathematical objects
> as sets, itÕs somewhat arti\[CapitalThorn]cial to do so in \
many cases.
> Meanwhile, there are constructions in category theory that
appear to
> make sense, but are too big to be sets as they stand.
> Keith Ramsay
ThatÕs an interesting point about the cumulative hierarchy
and the
non-well-founded sets. Where I equated the cumulative
hierarchy with the
projectively completed ring of integers in the theory of
ubiquitous
ordinals,
then when I consider ubiquitous ordinals with no foundation
their ordinal
value
would not in the naive construction differ from their order
type in the
simple
case where A={A}. Thus they would all coincide with U, the
universal set,
as
ordinals, or there would be a lot of sets outside of the
cumulative
hierarchy,
the concept of which can be used to represent the integers as
mechanistic
sets.
Category theory, with its objects and arrows, or functions,
does not
seem to
be outside of the realm of discourse of set theory. Please
provide an
example or
to ZF of any abstraction of primary objects if applicable.
WhatÕs the point of a fundamental set theory if everything \
is
not a set?
People
often use ZF with classes, if they donÕt then they have to
stab out
their
\[CapitalThorn]gurative eyes every time they see the words collection of
all sets,
which
regenerate painfully. Then, when theyÕre using that, ZF with
classes,
say
class of all classes and their eardrums explode. Skolem. As
has
been
discussed in this and other recent threads, and rather
continuously for a
hundred
eternally, it can be easily seen that room for improvement in
foundations
exists.
There are a wide variety of logical theories, most using
damningly
self-reßexive
non-logical axioms, that plainly admit the universal set and
as well other
non-well-founded sets.
cumulative hierarchy as ubiquitous ordinals is that all of
the in\[CapitalThorn]nite
ordinals
are non-well-founded. That seems a decent naive resolution.
Then, you can
easily assume the sets are well-founded or not, and if so
then there are
ubiquitous naturals, else ordinals.
In\[CapitalThorn]nity: too big.
Ross F.
===
Subject: Re: SkolemÕs Paradox and why is math the way it is?
|> I didnÕt say anything about standards of proof, but since
you ask, we
|> do of course have standards. They are just informal, not
set by a \[CapitalThorn]xed
|> axiom system.
|
|But different axioms systems are different. For instance you
can have
|a non-well founded set theory, then you usually have
collection
|instead of repalcement, but in a normal set theory class a
proof of
|collection is required.
ItÕs a mistake, though, to assume that when people are using
two
different axiom systems, they are using them intending for the
sentences of the language to have two different
interpretations, one
for each axiom system. Sometimes they are only adding more or
less of the things that they believe to be true under one
given
interpretation.
ItÕs ordinarily impossible to capture oneÕs \
knowledge of
mathematics
in a formal system. If one believes that the axioms are true,
and that
the deductive rules are sound, then one normally believes
that they
are also consistent, but a system strong enough to capture a
personÕs
knowledge of mathematics presumably is strong enough for
GoedelÕs
incompleteness theorem to apply. So they believe the formal
system
to be consistent, but itÕs impossible to prove in the \
system.
Hence if I start working in ZFC+con(ZFC), itÕs fairly
unlikely that IÕm
doing so intending for the sentences IÕm working with to \
have
a
different meaning from what I intended when I was just
working with
ZFC. I merely added one more thing that I believe to be true
to the
axioms.
Keith Ramsay
===
Subject: Re: GCH vs. Axiom of Choice.
|Ah, I should have been more clear. L is a model (right?),
ItÕs a proper class of sets, the sets satisfying a certain
condition.
(Being constructible.) Another way to describe it is that
itÕs the
minimal model of ZF containing all the ordinals.
| ZF is an
|axiom system (right?). GCH is true for L (you said so in
your post
|right?). You also said that we prove that GCH is true for L?
But
|what do we need to prove it?
ZF is strong enough by itself to prove that GCH holds in L.
ZF is strong enough to prove that V=L holds in L, and that
V=L->GCH.
| For instance if we had to assume ZFC+GCH
|to prove it, then it wouldnÕt mean much IMO.
Heh, itÕs sort of amusing when to prove that some fact holds
true
when relativized to a model one needs to use the same fact not
relativized to the model. I can see how that might seem
underwhelming,
but itÕs not necessarily trivial or uninteresting. For
instance, one
had to prove that the axioms of ZF hold in L, too, and
obviously we
need to assume some of them in order to prove they hold in L.
| I assume that ZF can
|prove only limited things about L, since ZF is incomplete,
but if I
|add GCH to ZF then can ZF+GCH prove something new about L?
IÕm guessing it probably can, but I donÕt know \
of a good
example.
My guess is that some assumption intermediate between ZF and
ZF+V=L
is suf\[CapitalThorn]cient to prove (say) that aleph_1 is the same as
aleph_1
relative to L. Certainly V=L implies that!
On the other hand, there arenÕt any \[CapitalThorn]rst order \
properties of L
that can be proven in ZF+GCH but not in ZF. In fact, for an
arbitrary
sentence X in the language of ZF, the following are
equivalent:
(a) ZF |- (V=L->X)
(b) ZF + V=L |- X
(c) ZF |- L |= X.
(d) ZF + V=L |- L |= X
(a)->(b) is a case of the deduction theorem. (b)->(c) holds
because
itÕs a theorem of ZF that V=L relativized to L is true Given
a model
M of ZF, we can consider constructibility as relativized to
M. The
elements of M satisfying this relativized constructibility
form a
submodel L_M, which is another model of ZF. If we repeat this
process,
to get L_{L_M}, itÕs possible to prove that we \
donÕt shrink
the model
any; L_{L_M} = L_M. So L_M is a model of V=L, the axiom
stating that
every set is in L. So anything thatÕs a consequence of V=L
holds
relative to L. If X is a theorem of ZF+V=L, then that fact
can be
proven in ZF, and then applied to L.
(c)->(d) is obvious.
To prove (d)->(a), assume \[CapitalThorn]rst that (a) is false. By \
GoedelÕs
completeness theorem, there would exist a model of ZF+V=L+~X.
Suppose M is a model of ZF+V=L+~X. Since the L relativized to
M
is the same as M, we get that M |= ~(L|=X). Hence M is also a
model of ZF+V=L in which L|=X fails.
Since GCH is a consequence of V=L,
(cÕ) ZF + GCH |- L|= X
is also equivalent.
| How about
|ZF+(~GCH), can that also prove things about L?
Since ~GCH is so weak, I donÕt think there are many theorems
about
L in ZF+(~GCH) that arenÕt also theorems in ZF. We can \
deduce
from
~GCH the existence of sets not in L, of course.
| Do the truths of L
|vary depending on what other axioms L is de\[CapitalThorn]ned with? \
IÕm
trying to
|be more clear, but I apologize in advance if I failed again.
How would whether something is true of L depend on axioms?
Of course, what can be proven to be true of L from a set of
axioms
does depend on the axioms! IÕm not familiar with the \
details,
but I
gather that some large cardinal axioms (I think the existence
of a
measurable cardinal is strong enough) imply a relatively
detailed
account of the structure of L. Note that the existence of a
measurable cardinal is inconsistent with V=L.
This real 0# that is believed to be outside of L encodes some
of the
structure of L (if it exists).
Keith Ramsay
===
Subject: Re: Set Theory
|> |> As a result, people usually think one of two things,
either that
|> |> the continuum problem is hard, or that itÕs not a
problem
|> |> to solve. Platonists think of the problem as hard. \
ItÕs
a theorem
|> |> of ZFC that c=aleph_x for some ordinal x. A Platonist
would
|> |> (ordinarily at least) believe that, and think that we
just donÕt know
|> |> yet which ordinal x is, whether itÕs 1, 2, or \
something
else. On
|> |> the other hand, there are people who think that the
question is
|> |> somehow unde\[CapitalThorn]ned, and that itÕs \
meaningless to ask which
|> |> ordinal x really is.
|> |
|> |If the universe of discourse is the heirarchy of sets you
mentioned on
|> |another thread, then is x a speci\[CapitalThorn]c ordinal, or is it
still
unkown?
|> ItÕs a speci\[CapitalThorn]c ordinal, although we may not \
know whether
itÕs 1,
|> 2, 3, or something else.
|> The only way for it to make sense to say that the universe
of discourse
|> is indeed the cumulative hierarchy is to agree to at least
part of the
|> PlatonistsÕ position on it.
|
|Can you elaborate, IÕm donÕt even understand \
what you are
saying.
|Things like agree to at least PART seems vague to me.
Indeed, I was being a bit vague. The point is that lots of
the standard
philosophical positions opposed to Platonism would not agree
that it
makes sense to say that (we have decided) the cumulative
hierarchy is
our domain of discourse. The cumulative hierarchy is the
class of pure,
well-founded sets. I think thatÕs \[CapitalThorn]ne. But some \
people
consider it just
\[CapitalThorn]ctional.
The reason for the vagueness is that there are positions
differing both
from the ones treating it as a complete \[CapitalThorn]ction and Platonism.
It would
be possible for a constructivist, for example, to accept the
cumulative
hierarchy as a valid construction without buying into
Platonism.
| What do you
|have to do to consider that universe of discourse?
I \[CapitalThorn]nd this kind of how question hard to answer, because I
canÕt
tell what sort of answer youÕre looking for.
If we want to take the integers as our universe of discourse
(for
doing number theory, say), what do we have to do? In very
mundane
terms, we do what we did in elementary school-- learn to
count,
learn to do operations on them, perhaps learn mathematical
induction if weÕre lucky, and so on. At that point, we know
what
the integers are, to the extent that is needed to take them
to be
our universe of discourse in a more formal way.
For the cumulative hierarchy itÕs similar. We perhaps \
acquaint
ourselves with hereditarily \[CapitalThorn]nite sets {{},{{{}}}} something
like the way we got acquainted with integers. Then maybe we
choose
to suppose that the hereditarily \[CapitalThorn]nite sets can be regarded
as a
whole as a larger kind of set. We can de\[CapitalThorn]ne subsets of it,
families
of subsets, and so on. Eventually someone describes the
notion of
rank, and we ask how high in rank it makes sense to let sets
go.
The way you ask this kind of question makes me uneasy,
because I
keep getting the impression you are essentially expecting a
kind
of answer thatÕs actually impossible, without being able to
articulate
exactly what kind of expectation you have, so that we can
hold it
up to the light and show just why itÕs impossible to \
satisfy.
It relates to the boostrapping problem I mentioned months
back. ItÕs
dif\[CapitalThorn]cult to explain how it is possible to build a foundation
for
a subject without the foundation itself being arbitrary, or
itÕs
being built on top of a still more fundamental foundation
(which
then still needs to be explained).
In the case of the integers, I feel con\[CapitalThorn]dent that the
foundation
is quite okay, and that we know what the integers are even by
just
a very informal introduction to them.
| To me itÕs very
|confusing, like if you assume that fewer sets exist by
having GCH,
|then you get choice sets that donÕt exist in other \
versions,
is that
|because the sets that can lack a choice function are between
the
|cardinals omege, 2^ omega, 2^(2^omega), etc?
IÕm not surprised you \[CapitalThorn]nd it confusing, since I \
\[CapitalThorn]nd the
statement
of the question confusing!
It seems to me that youÕre imagining a mathematician \
changing
the
assumptions heÕs using, and this somehow going hand-in-hand
with
assuming a different class of sets as the domain of
discourse. These
two ideas *might* go through the mathematicianÕs mind
together, but
thereÕs no obvious relationship. To me, GCH is just another
one of
those conjectures thatÕs probably untrue, but whose
consequences
we could explore anyway.
Is what youÕre asking about a scenario where someone is
considering
a model M of ZF not satisfying GCH, and then shifts to
considering
a submodel N that is a model of ZF+GCH?
Keith Ramsay
===
Subject: A problem in convexity
IÕm stuck in this problem:
Let S be an in\[CapitalThorn]nite subset of the d-dimensional Euclidian
space and
let u be a
point in the interior of convex hull of S. Prove that one can
choose
2d points v1,...,v2d in S such that u lies in the interior of
convex
hull of v1,...,v2d.
Till now, I \[CapitalThorn]nd a way to prove the case when d=2, but \
canÕt
\[CapitalThorn]gure
out how to prove general cases.
Any comments are highly appreciated.
===
Subject: Re: A problem in convexity
> Let S be an in\[CapitalThorn]nite subset of the d-dimensional Euclidian
space and
> let u be a
> point in the interior of convex hull of S. Prove that one
can choose
> 2d points v1,...,v2d in S such that u lies in the interior
of convex
> hull of v1,...,v2d.
> Till now, I \[CapitalThorn]nd a way to prove the case when d=2, but \
canÕt
\[CapitalThorn]gure
> out how to prove general cases.
How did you get this problem? This problem is exciting.
The following is my solution. Many details are skipped or
compressed, because the solution is long.
= = = = Notations & De\[CapitalThorn]nitions = = = =
Let d be a natural number. (d = 1,2,3, ...)
R^d is the d-dim Euclidian space.
If S is a subset of R^d, we say
ch(S) = the convex hull of S,
int(S) = the interior of S,
|S| = the cardinality of S,
A /= B iff A is a subset of B.
U is always the set-union symbol, in this posting.
For example, U_{n in Z} (n, n+1) = R Z.
B(p;r) is the d-dim closed ball
with center p and of radius r > 0.
If p is a nonzero point in R^d, L(p) = { r p: r > 0 }.
If p_1, p_2, .. p_n are points in R^d, and L is a linear
m-dim subspace of R^d, q is a point in R^d,
and q+L contains the points p_1, ..., p_n, and m is
the minimal dimension possible such, then we say,
q+L is a plane generated by p_1, ..., p_n.
(Note that a plane is a subspace iff it contains 0.)
(Note that, in this de\[CapitalThorn]nition, planes need NOT be 2-dim.)
If p_1, p_2, ..., p_n are points in R^d, and if a_1, a_2,
..., a_n
are nonnegative real numbers whose sum is 1, and if a point q
satis\[CapitalThorn]es q = a_1 p_1 + a_2 p_2 + ... + a_n p_n, then
we say q is a 1-combination of p_1, p_2, ..., p_n .
= = = = Lemma 1 = = = =
[ Lemma 0 ]
If S is a subset of R^d, then
ch(S) = {all the 1-combinations of \[CapitalThorn]nitely many points of S \
}.
[ how to prove this ]
1. Show that the set on the right side is convex.
2. Show that every point in the set is in ch(S).
3. Then conclude the equality. //
[ Lemma 1/2 ]
Suppose P is a \[CapitalThorn]nite subset of R^d.
If q is a 1-combination of the points in P,
then q is a 1-combination of d+1 or fewer points in P.
[ how to prove this ]
Suppose p_1, p_2, ..., p_n are a smallest number of
points in P such that q is a 1-combination of p_1, ..., p_n.
And suppose n > d+1, then derive a contradiction using
the minimality of n. Then conclude n <= d+1. //
[ Lemma 1 ]
If S be a subset of R^d, then
ch(S) = U_{P/=S, |P|<=d+1} ch(P)
[ how to prove this ]
Use Lemma 0 and Lemma 1/2. //
[ Lemma 2 ]
Suppose O is a subset of R^d with nonempty interior.
Suppose {C_h : h in H} is a collection of convex subsets of
R^d such that O /= C_h for each h in H. (H can be any set)
If C_oo = U_{h in H} C_h,
then int(C_oo) = U_{h in H} int(C_h).
[ proof ]
U_{h in H} int(C_h) /= int( C_oo ) is obvious.
So, letÕs show
int(C_oo) /= U_{h in H} int(C_h).
There are u in R^d and s > 0, such that B(u;s) /= O.
Let u+v be an arbitrary point in int(C_oo).
Then for some t > 0, B(u+v;t) /= C_oo
For some r > 0, w = u+(1+r)v is in B(u+v;t), and so is in
C_oo, So w is in C_hÕ for some hÕ in H.
Since B(u;s) U {w} /= C_hÕ,
and since u+v is in int(ch( B(u;s) U {w} )),
u+v is in int(C_hÕ). //
= = = = a Theorem = = = =
[ a Theorem ]
Suppose S is a subset of R^d such that 0 is in int(ch(S)).
Then there is a subset T of S such that
0 is in int(ch(T)), |T|<=2d.
[ summary of proof ]
Two cases.
Case 1: S is \[CapitalThorn]nite.
In this case, suppose d>1, for the case d=1 is trivial.
There is nonzero u in R^d, such that every
(d-2)-dim plane generated by points
of S does not intersect L(+u) U L(-u).
Let D be the boundary of ch(S). D is a (d-1)-dim
surface surrounding the point 0.
L(+u) meets D at a point v_1.
There is a (d-1)-dim plane P_1 such that
v_1 is in P_1 and ch(S) is entirely contained in one of the
two regions cut out of R^d by P_1. (Informaly, P_1 is a plane
tangent to ch(S) at v_1. this P_1 may not be unique.)
Let E be the intersection of P_1 and S.
Now, think of P_1 as another (d-1)-dim Euclidean space,
E is inside that Euclidean space, and v_1 is in ch(E),
so by applying Lemma 1 to E as inside P_1, it follows that
there is subset T_1 of E such that v_1 is in ch(T_1) and
|T_1|<=(d-1)+1=d.
Because of how we have chosen u,
v_1 is not in the (P_1)-boundary of ch(T_1).
Therefore v_1 is in the (P_1)-interior of ch(T_1).
Same arguments for L(-u) gives v_2, P_2, T_2 and
v_2 is in P_2-interior of ch(T_2).
Therefore, 0, which is in ch{v_1, v_2}, is in interior of
ch(T_1 U T_2). And |T_1 U T_2| <= d+d = 2d.
So we have constructed T = T_1 U T_2, as desired.
Case 2: S is in\[CapitalThorn]nite.
Let {D_h : h in H} be the collection of all the sets of d+1
or fewer points in S.
Then, by Lemma 1, U_{h in H} ch(D_h) = ch(S).
Let P be a maximum-dim plane generated by
\[CapitalThorn]nitely many points in S.
Then P is generated by some \[CapitalThorn]nitely many points
q_1,q_2, ...,q_n in S.
This P, by the maximality of the dim(P), must contain
every point of S.
So, S /= P, and hence, ch(S) /= P.
But since S has nonempty interior, so does P.
Since every proper plane of R^d has empty interior,
P = R^d.
So, q_1,q_2, ...,q_n generates R^d. Therefore
ch {q_1, ..., q_n} has nonempty interior.
Let E_h = {q_1, ..., q_n} U D_h ,for each h.
Then U_{h in H} ch(E_h) = S.
ch{q_1, ... , q_n} /= ch(E_h) for each h.
So by applying Lemma 2 to {ch(E_h) | h in H}, we see
U_{h in H} int(ch(E_h)) = int(ch(S)).
So, 0 is in int(ch(E_hÕ)) for some hÕ .
Furthermore, E_hÕ is \[CapitalThorn]nite.
so we are now in Case 1 about E_hÕ . //
[ a equivalent form of the theorem ]
Suppose S is a subset of R^d such that
0 is in int(ch(S)), |S|>=2d.
then one can choose 2d distinct points p_1, ... p_2d
such that 0 is in int(ch({p_1, ... p_2d})) .
//
I hope a simple proof is somewhere.
- - -
Dae-jung Yoo (IGNJSA YOO) (Delete DELETE to reply by e-mail)
===
Subject: Re: A problem in convexity
>> Let S be an in\[CapitalThorn]nite subset of the d-dimensional Euclidian
space and
>> let u be a
>> point in the interior of convex hull of S. Prove that one
can choose
>> 2d points v1,...,v2d in S such that u lies in the interior
of convex
>> hull of v1,...,v2d.
>> Till now, I \[CapitalThorn]nd a way to prove the case when d=2, but
canÕt \[CapitalThorn]gure
>> out how to prove general cases.
>How did you get this problem? This problem is exciting.
>The following is my solution. Many details are skipped or
>compressed, because the solution is long.
...
>I hope a simple proof is somewhere.
See CaratheodoryÕs theorem.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
===
Subject: De\[CapitalThorn]nition of Entire Function
type=text/plain;
boundary=----=_NextPart_000_4439_01C4DB29.433F23D0
This is a multi-part message in MIME format.
------=_NextPart_000_4439_01C4DB29.433F23D0
Taken from MathWorld:
If a complex function is analytic at all \[CapitalThorn]nite points of the
complex
plane , then it is said to be entire
Since there are many reasonable 1-1 onto mappings of the
Complex Plane to
itself that map the point at in\[CapitalThorn]nity to a \[CapitalThorn]nite \
point (e.g.
1/z), is it
just historical that the de\[CapitalThorn]nition singles out the point at
in\[CapitalThorn]nity and
doesnÕt instead say
If a complex function is analytic except for one singularity,
then it
is ÔentireÕ?
Norm
------=_NextPart_000_4439_01C4DB29.433F23D0
name=eimg1183.gif
Content-Location: http://mathworld.wolfram.com/eimg1183.gif