Your most counterintuitive yet simple math problem

[Loren Booda]

Do you all think that fundamental, visualizable math relations have mostly been considered?

 

[Hurkyl]

The existence of [a continuous] bijection would mean that [0, 1] and [0, 1]² are homeomorphic, which isn't true.

Is that obvious? I know that there are continuous bijections which aren't homeomorphisms (e.g. |X| --> X for any space X that is not given the discrete topology)...

 

[dvs]

Is that obvious? I know that there are continuous bijections which aren't homeomorphisms (e.g. |X| --> X for any space X that is not given the discrete topology)...

A continuous bijection from a compact space onto a Hausdorff space is automatically a homeomorphism.

 

[enigmahunter]

The "http://en.wikipedia.org/wiki/Continuum_hypothesis" " is my choice.

"There is no set whose size is strictly between that of the integers and that of the real numbers."

It is an interesting problem and considered as a fact, even though it cannot be proved or disproved in ZFC.

 

[Count Iblis]

Suppose you simulate a world in which mathematicians and physicists live on a huge computer. Then everything in that world will be discrete and countable. Nevertheless the virtual mathematicians and physicists will likely still invent uncountable sets, real numbers, Axiom of Choice, etc. and pretend that it applies to their world.

 

[csprof2000]

"Suppose you simulate a world in which mathematicians and physicists live on a huge computer. Then everything in that world will be discrete and countable. Nevertheless the virtual mathematicians and physicists will likely still invent uncountable sets, real numbers, Axiom of Choice, etc. and pretend that it applies to their world. "

And then when people said that the real world was really only 2-D and made of discrete bits and pieces, the mathematicians and physicists would say something like "Perhaps your experience is limited" or something. Then the mathematicians would continue proving there are numbers that don't have any value you can name and physicists would keep letting all functions equal the first term in their Taylor expansions.

Seriously, though... Set theory in general (particularly that which applies to infinite sets) seems dangerously close to being more mysticism than logic. I don't like it and, thankfully, computer scientists don't have to.

 

[Hurkyl]

Seriously, though... Set theory in general (particularly that which applies to infinite sets) seems dangerously close to being more mysticism than logic.

Then you need to learn more about logic.

I don't like it and, thankfully, computer scientists don't have to.

You're joking, right? How exactly do you plan to study the theory of computation if you can't talk about languages (or worse, classes of languages)? How do you plan to study generic programming if you don't allow type variables? How do you plan on discussing the semantics of types like java.math.BigInteger? How do you plan on doing asymptotic analysis without calculus?

 

[csprof2000]

We have the luxury of using potential, rather than actual, infinities in computer science. It's called constructive mathematics. Go read a book before you pretend to know things.

I don't think anybody has a problem admitting that there is no largest integer. Likewise, who could pretend to be able to list all the reals between 0 and 1? Still, there's no reason to linger on such things as a theory of infinities... unless that's what you like.

 

[Hurkyl]

We have the luxury of using potential, rather than actual, infinities in computer science. It's called constructive mathematics. Go read a book before you pretend to know things.

Before your retort, did it even cross your mind that maybe, just maybe, I have some clue what I'm talking about? Whether you call them "potential" or "actual", you're still doing set theory with infinite sets.

And really, I disagree with the judgement you're using potential infinities. e.g. if sets are expressed either through enumerating its elements via a Turing machine, or a calculation of its membership relation via a Turing machine... the Turing machine serves as a complete description of the set.

But really, at this point, we run into the problem that "actually infinite" and "potentially infinite" aren't (to my knowledge) well-defined notions, so there isn't really any substance to such a debate.

 

[Vanadium 50]

For me it was understanding that there are more reals in (0,1) than all rationals

Related to that - nearly all numbers are normal, yet there are very few - perhaps zero - concrete examples of one.

 

[csprof2000]

Hmmm...

If there were zero concrete examples of a normal number, would you still say they exist?

The ancients didn't believe in proof by contradiction. If somebody knows why people started believing in it, I'd love to know. Was it Aristotle? That seems too early. But I really don't have any idea.

I think that any mathematical object that can be shown to exist but which also has no concrete example is the most counterintuitive thing in mathematics. Most of the rest... some probability aside... is usually straightforward, if with some hindsight.

 

[Hurkyl]

The ancients didn't believe in proof by contradiction.

I would love to see a reference for that claim.

If somebody knows why people started believing in it, I'd love to know. Was it Aristotle?

http://planetmath.org/encyclopedia/ReductioAdAbsurdum.html cites Aristotle citing Euclid's use of RAA, so at least as far back as that.

If there were zero concrete examples of a normal number, would you still say they exist?

Logically, one would say a normal number exists if and only if one could prove the statement

\exists x \in \mathbb{R} : x \text{\ is normal}

(and it is a theorem of real analysis in classical logic)

 

[daniel_i_l]

I'm not sure what one this is called but consider the following trivial question:
You are given a family with two children, one of them is a girl, what are the chances that the other one is a girl? The answer is of course 1/3.
Now consider a similar problem:
You are given a family with two children, one of them is a girl named Florida (a very rare name), what are the chances that the other one is a girl? The answer in this case approaches 1/2 as the popularity of the name Florida approaches 0. (to see why this is write down all the possibilities)
It amazes me that knowing the name of one girl changes the chances that the other one will also be a girl.

 

[CRGreathouse]

So Hurkyl cited PlanetMath's citation of Aristotle citing Euclid's use of RAA?

 

[Tac-Tics]

"Suppose you simulate a world in which mathematicians and physicists live on a huge computer. Then everything in that world will be discrete and countable.

This reminds me of a quote by Einstein:

"God does not care about our mathematical difficulties. He integrates empirically."

Probably not fully applicable to the conversation, but I always thought it was a neat idea when considering what would otherwise be infinitely time-consuming integration.

Nevertheless the virtual mathematicians and physicists will likely still invent uncountable sets, real numbers, Axiom of Choice, etc. and pretend that it applies to their world. "

This seems like a realness fallacy. I don't know the proper name for it, but claiming that some things are more "real" than others because they are better understood or more classical. For example, some people think that "infinity" isn't real and zero is, because distances in the real world can be measured to be zero, but not infinity. But the fallacy is in that both are just an abstraction. If you have a loop, for example, and follow it in a circle, measuring how long you travel before you find the end, there IS no value to satisfy how long you've gone, so infinity, in some sense, is completely legitimate.

Mathematicians have created the notions of the real numbers because they are more useful in many instances than rationals. If we stick to rationals, then the number of allowed angles we can measure is crippled, as a triangle with a typical rational angle leads to an irrationally long hypotenuse. And the loss of the least upper bound property is death of many useful phenomenon. For example, you can have a continuous rational function which assumes both positive and negative values, but which has no zeroes.

The axiom of choice is just plain handy, and it doesn't matter if it reflects reality, because it makes life easier.

Then the mathematicians would continue proving there are numbers that don't have any value you can name and physicists would keep letting all functions equal the first term in their Taylor expansions.

Mathematicians solve problems faster than the real world can provide. Physicists need to know the answers faster than they can prove them. It works out for both teams.

Seriously, though... Set theory in general (particularly that which applies to infinite sets) seems dangerously close to being more mysticism than logic. I don't like it and, thankfully, computer scientists don't have to.

Perhaps if you haven't, you should read Godel Escher Bach. If you do, you should re-read it. If you assume only fundamentals of logic and peano's axioms of integers, you get a system which every bit as set theory does. Even if your formal system doesn't allow for functions, sets, or cardinality literally, you can easily write a computer program that can translate sentences back and forth between an axiomatic set theory and any other logical system, like Hofstadter's Typographical Number Theory (TNT). Once you have a way to translate sentences like that, you're in trouble, because you have problem your system to have the same logical power as the other. In other words, the infinite mysteries of the integers ARE the mysticism of set theory.

 

[Hurkyl]

If there were zero concrete examples of a normal number, would you still say they exist?

It just struck me; there's an interesting variation on this. In the arithmetic of complex numbers^*, there are two solutions to the polynomial equation x^2 + 1 = 0... however, neither one can actually be constructed!

(The reason is symmetry; any condition expressed using the elementary notions of arithmetic that is satisfied by a is also satisfied by the complex conjugate of a)

Of course, particular models of the complex numbers could provide an external construction for such roots. (e.g. building the complex numbers out of R², or as a quotient of R[x]) But such constructions cannot be carried out in a purely arithmetic fashion, and require properties specific to the ambient theory and construction of the specific model.


*: Of course, the theory could be formulated in other ways that don't have this property; e.g. one could provide an explicit constant symbol that is axiomatically defined to be a solution to x^2 + 1 = 0, in which case it is trivial to construct a solution

 

[Doodle Bob]

Seriously, though... Set theory in general (particularly that which applies to infinite sets) seems dangerously close to being more mysticism than logic. I don't like it and, thankfully, computer scientists don't have to.

Seriously, though, brick-layers also don't generally have to know and understand set theory, but that's not a particularly high mark of honor for the field of masonry.

Why you feel the need to denigrate a field just because you don't understand it very well, is beyond me.

 

[Vid]

My friend just sent me a proof that given any function from R->R if you tell me every value except at x_o, there is a strategy to guess the value with probability 1.

 

[adriank]

That sounds interesting. Do you mind posting it?

 

[daniel_i_l]

My friend just sent me a proof that given any function from R->R if you tell me every value except at x_o, there is a strategy to guess the value with probability 1.

Even if the function isn't continuous?

 

[jostpuur]

A feminist claim: As is known, women are more loyal to their partners than men are. So on average, men have more sexual relationships than women have.

 

[adriank]

In general, for any function f \colon \mathbb{R} \to \mathbb{R} whose value is known everywhere except x_0, the remaining value could be anything. However, if the function was continuous, then there is only one possibility for f(x_0). This generalizes by the theorem below.

Theorem. Let X and Y be topological spaces, with Y Hausdorff. Let x_0 be a limit point of X, and let f \colon X \to Y and g \colon X \to Y be functions continuous at x_0 such that f(x) = g(x) for all x \ne x_0 in some neighborhood U of x_0. Then f(x_0) = g(x_0).

Proof. Suppose f(x_0) \ne g(x_0). Then since Y is Hausdorff, there exist disjoint open sets V_1, V_2 \subseteq Y such that f(x_0) \in V_1 and g(x_0) \in V_2. Since both f and g are continuous at x_0, there exist open sets W_1, W_2 \subseteq X containing x_0 such that f(W_1) \subseteq V_1 and g(W_2) \subseteq V_2. Let W = U \cap W_1 \cap W_2; this set is open and it contains x_0. Thus it contains some point x \ne x_0, since x_0 is a limit point of X; we have f(x) = g(x). But f(W) \subseteq V_1 and g(W) \subseteq V_2, so f(W) and g(W) are disjoint, contradicting f(x) = g(x).

 

[Vid]

No the function doesn't have to be continuous.

Let f:R->R be any function. No constraints except that its a function. Tell me every value of f except at x_o. Now, we take the set of all functions from R->R and define an equivalence relation where f~g if f and g differ at finitely many points. Take any member g from the equivalence class of f. Since f and g differ on a set of measure zero, f(x_o) = g(x_o) with probability 1.

Of course the fact that we can choose g relies on the axiom of choice.
:D

 

[CRGreathouse]

Since f and g differ on a set of measure zero, f(x_o) = g(x_o) with probability 1.

I'd think that at a random point x, f(x) = g(x) with probability 1, but that wouldn't day anything about f(x_0) = g(x_0). Otherwise consider where f(x) = 1 for x = 0 and 0 otherwise, and g is uniformly 0. The probability that they agree on a random point is 1; the probability that they agree at x = 0 is 0.

This reminds me of a paper I read a few years ago, with a title along the lines of 'using the Axiom of Choice to see the future', which discussed similar techniques (as I recall!) to take a glance at a time epsilon in the future.

 

[Vid]

Except we don't know anything about g except that it differs from f on a set of measure zero. Sure you could construct a counterexample, but it doesn't change the fact that if I have two functions that differ on a set of measure zero the probability that f(x_o) = g(x_o) is 1 for any x_o. Something happening with probability one isn't the same as something always happening.

 

[tim_lou]

a counterintuitive piece of math... well, i read something about continuum hypothesis, and it says that it is proved that it cannot be proved or disproved based on the ZFC set theory. Isn't that weird?!

Also, any set can be well ordered by axiom of choice. And everything about the minimal uncountable (well-ordered) set.

 

[adriank]

No the function doesn't have to be continuous.

Let f:R->R be any function. No constraints except that its a function. Tell me every value of f except at x_o. Now, we take the set of all functions from R->R and define an equivalence relation where f~g if f and g differ at finitely many points. Take any member g from the equivalence class of f. Since f and g differ on a set of measure zero, f(x_o) = g(x_o) with probability 1.

Of course the fact that we can choose g relies on the axiom of choice.
:D

Quite interesting. I'm a little sceptical about that, but I'll think about it some more.

 

[Hurkyl]

Since f and g differ on a set of measure zero, f(x_o) = g(x_o) with probability 1.

Why? This certainly doesn't follow from anything you said previously, because this is the first time you even mention probability. You never bother to specify what probability distribution you're using either... (nor what the outcomes and events are)

 

[adriank]

Alright, here's a specific example showing that the proof doesn't work.

Say you have two functions f and h that differ only at x₀; then f ~ h. Choose any member g from [f] = [h]; by your argument, f(x₀) = g(x₀) with probability 1, and h(x₀) = g(x₀) with probability 1. But these are disjoint events, so that is absurd.

 

[CRGreathouse]

Alright, here's a specific example showing that the proof doesn't work.

Say you have two functions f and h that differ only at x₀; then f ~ h. Choose any member g from [f] = [h]; by your argument, f(x₀) = g(x₀) with probability 1, and h(x₀) = g(x₀) with probability 1. But these are disjoint events, so that is absurd.

Heh, I said the same thing in post #54.