Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge Micromass' big counterexample challenge

  1. Apr 27, 2016 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I adore counterexamples. They're one of the most beautiful things about math: a clevery found ugly counterexample to a plausible claim. Below I have listed 10 statements about basic analysis which are all false. Your job is to find the correct counterexample. Some are easy, some are not so easy. Here are the rules:

    • For a counterexample to count, the answer must not only be correct, but a detailed argumentation must also be given as to why it is a counterexample.
    • Any use of outside sources is allowed, but do not look up the question directly. For example, it is ok to go check analysis books, but it is not allowed to google the exact question.
    • If you previously encountered this statement and remember the solution, then you cannot participate in this particular statement.
    • All mathematical methods are allowed.
    Here you go:

    1. SOLVED BY Samy_A Any open set ##G## such that ##\mathbb{Q}\subseteq G\subseteq \mathbb{R}## has either ##G=\mathbb{Q}## or ##G=\mathbb{R}##.
    2. SOLVED BY ResrupRL Every symmetric matrix in ##\mathcal{M}_n(\mathbb{C})## is diagonalizable for each ##n##
    3. SOLVED BY stevendaryl Every ##C^1## function ##f:\mathbb{R}\rightarrow \mathbb{R}## that is square-integrable, that is ##\int_{-\infty}^{+\infty} |f(x)|^2 dx <+\infty##, has ##\lim_{x\rightarrow +\infty} f(x) = 0##.
    4. SOLVED BY andrewkirk There is no infinitely differentiable function ##f:\mathbb{R}\rightarrow \mathbb{R}## such that ##f(x) = 0## if and only if ##x\in \{1/n~\vert~n\in \mathbb{N}\}\cup\{0\}##.
    5. SOLVED BY ProfuselyQuarky Every derivative of a differentiable function is continuous.
    6. SOLVED BY Samy_A For any ##A\subseteq \mathbb{R}## open holds that if ##f^\prime(x) = g^\prime(x)## for each ##x\in A##, then there is some ##C\in \mathbb{R}## such that ##f(x) = g(x) + C##.
    7. SOLVED BY fresh_42 If ##(a_n)_n## is a sequence such that for each positive integer ##p## holds that ##\lim_{n\rightarrow +\infty} a_{n+p} - a_n = 0##, then ##a_n## converges.
    8. SOLVED BY jbriggs444 There is no function ##f:\mathbb{R}\rightarrow \mathbb{R}## whose graph is dense in ##\mathbb{R}^2##.
    9. SOLVED BY andrewkirk If ##f:\mathbb{R}^2\rightarrow \mathbb{R}## is a function such that ##\lim_{(x,y)\rightarrow (0,0)} f(x,y)## exists and is finite, then both ##\lim_{x\rightarrow 0}\lim_{y\rightarrow 0} f(x,y)## and ##\lim_{y\rightarrow 0}\lim_{x\rightarrow 0} f(x,y)## exist and are finite.
    10. SOLVED BY andrewkirk If ##A## and ##B## are connected subsets of ##[0,1]\times [0,1]## such that ##(0,0),(1,1)\in A## and ##(1,0), (0,1)\in B##, then ##A## and ##B## intersect.
    Thank you all for participating! I hope some of these statements were surprising to some of you and I hope some of you have fun with this! Don't hesitate to post any feedback in the thread!

    I will give the source of each statement after the correct answer has been given.
     
    Last edited: Apr 27, 2016
  2. jcsd
  3. Apr 27, 2016 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Nice, some I know, some not.

    Let me try 1:
    Any open set ##G## such that ##\mathbb{Q}\subseteq G\subseteq \mathbb{R}## has either ##G=\mathbb{Q}## or ##G=\mathbb{R}##.
    Set ##\mathbb{Q} = \{ q_1,q_2,q_3, ...\}##
    Let's build an open set ##G## such that ##\mathbb{Q}\subseteq G## that can be written as ##G=\cup ]q_n-\epsilon_n,q_n+\epsilon_n[##.
    ##\mathbb{Q}\subseteq G## is trivially true. That ##G## is open is also trivial, as ##G## is the union of open sets.
    Also, any open interval in ##\mathbb R## will contain irrational numbers, so that ##\mathbb{Q} \neq G##.

    Now, we don't want ##G=\mathbb{R}##.
    So let's build the ##\epsilon_n## such that some chosen non rational number is not in ##G##.
    ##\pi## is not a rational number.
    Set ##\displaystyle \epsilon_n=\frac{1}{2}\min_{m \leq n} |\pi -q_m|##.
    Clearly ##\epsilon_n>0##. Also ##\pi \notin ]q_n-\epsilon_n,q_n+\epsilon_n[##, since ##|\pi- q_n| \geq 2\epsilon_n \gt \epsilon_n## (and this for all ##n##).
    Hence ##\pi \notin G##.

    EDIT: I think my definition of the ##\epsilon_n## is too complicated.
    ##\displaystyle \epsilon_n=\frac{1}{2}|\pi -q_n|## would also work.
     
    Last edited: Apr 27, 2016
  4. Apr 27, 2016 #3

    fresh_42

    Staff: Mentor

    The polite feedback: Great examples and at first glimpse rather tough ones.
    The philosophical feedback: Do not take any obvious claims for granted unless proven (esp. in topology).
    The optimist's feedback: An entertaining Alzheimer prophylaxis.
    The pessimist's feedback: Hell, am I stupid.
    The humorous feedback: You've had a topologist for breakfast, haven't you?
    The practical feedback: I'm afraid of typing in one of those counterexamples even if I had found them.
    The hairsplitter's feedback: I assume (0,0) denotes a point in the plane and not an open interval.
    The personal feedback: Those things drive me crazy since I'm strongly attracted to find them out. If it only weren't such a time and paper killer.
    The micromass' feedback: I know there is a solution. (ref. to the integral in Roman numbers)
    The PF standard feedback: Wouldn't this be a hilarious insight?
     
  5. Apr 27, 2016 #4

    fresh_42

    Staff: Mentor

    Can't it be that ##\pi \in ]q_m - ε_m, q_m+ε_m [## for some ##m ≠ n##? One can find a rational number at each distance to ##\pi##.
     
  6. Apr 27, 2016 #5

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand what ##n## is in your question.

    But I've been somewhat sloppy, let me rewrite it.

    Any open set ##G## such that ##\mathbb{Q}\subseteq G\subseteq \mathbb{R}## has either ##G=\mathbb{Q}## or ##G=\mathbb{R}##.
    Set ##\mathbb{Q} = \{ q_1,q_2,q_3, ...\}##
    Let's build an open set ##G## such that ##\mathbb{Q}\subseteq G## that can be written as ##G=\cup ]q_n-\epsilon_n,q_n+\epsilon_n[##.
    ##\mathbb{Q}\subseteq G## is trivially true. That ##G## is open is also trivial, as ##G## is the union of open sets.
    Also, any open interval in ##\mathbb R## will contain irrational numbers, so that ##\mathbb{Q} \neq G##.

    Now, we don't want ##G=\mathbb{R}##.
    So let's build the ##(\epsilon_n)_n## such that some chosen non rational number is not in ##G##.
    ##\pi## is not a rational number.
    ##\forall n \geq 1##, set ##\displaystyle \epsilon_n=\frac{1}{2}|\pi -q_n|##
    ##\forall n \geq 1##, clearly ##\epsilon_n>0##.
    Also, ##\forall n \geq 1##, ##\pi \notin ]q_n-\epsilon_n,q_n+\epsilon_n[##, since ##|\pi- q_n| = 2\epsilon_n > \epsilon_n##. Hence ##\pi \notin G##.
     
  7. Apr 27, 2016 #6

    fresh_42

    Staff: Mentor

    Thanks. The ∀ quantor makes it clear. I was distrait by the minimum which made me somehow "fix" the n. Sorry. Nice solution. Do you have any idea about the square problem?
     
  8. Apr 27, 2016 #7

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    Maybe I'm thinking #1 is easier than it actually is, but why not something as simple as ##G=(-\infty , \pi)\cup(\pi,\infty)##? In other words, ##G = \mathbb{R}/\{\pi\}##. It's open because it's a union of open sets. Since ##\mathbb{Q} \subset \mathbb{R}## and the only number in ##\mathbb{R}## which is excluded from ##G## (that is, ##\pi##) is irrational (proof not included :wink:), the second definition shows that ##\mathbb{Q} \subseteq G##. Since irrational numbers like ##2\pi## are in ##G##, ##G \neq \mathbb{Q}##. Since ##\pi \in \mathbb{R}## is explicitly excluded from ##G##, ##G \neq \mathbb{R}##. Is there something wrong with this example?
     
  9. Apr 27, 2016 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No, this is the easiest example, but Samy_A's example works too and he was first, so the credits go to him :smile:
     
  10. Apr 27, 2016 #9

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    No.
    I have a guess, but I will put it in a spoiler so as to not distract or wrongfoot people who want to try it.
    Maybe the Topologist's sine curve can be used to build a counterexample.
     
  11. Apr 27, 2016 #10

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Of course!
     
  12. Apr 27, 2016 #11

    ProfuselyQuarky

    User Avatar
    Gold Member
    2016 Award

    That's me :frown: I've got a killer counterexample for #5 but heck no way am I going to post it here.
     
  13. Apr 27, 2016 #12

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    Absolutely. I just wanted to make sure I wasn't missing something fundamental.
     
  14. Apr 27, 2016 #13

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Why is that?
     
  15. Apr 27, 2016 #14

    ProfuselyQuarky

    User Avatar
    Gold Member
    2016 Award

    Reason #1: I’ve got like 10 minutes before leaving for my foreign language class and I stink at LaTeX, so it’ll take me a long while to figure out how to type it all up. It would take even longer to scan my scratch paper and upload it.

    Reason #2: I’m 99.9% sure my counterexample is legitimate, but my fear is always “I probably missed something and so it’s probably wrong and someone will probably point out the mistake in a sarcastic way that’s meant to be funny but I'll take the wrong way and won’t find it funny”

    And now, I shall log off . . .
     
  16. Apr 27, 2016 #15

    fresh_42

    Staff: Mentor

    7. ##a_n = \sum_{k=1}^{k=n} \frac{1}{k}##. But I have the same difficulty as TeethWhitener. What am I missing?
     
  17. Apr 27, 2016 #16

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Nothing. That is the right counterexample.
     
  18. Apr 27, 2016 #17

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Come on, post it!
     
  19. Apr 27, 2016 #18

    jbriggs444

    User Avatar
    Science Advisor

    Consider the set of canonical decimal expansions such that the first set of n digits after the decimal are arbitrary, the next n digits are all zero and the remaining digits are all non-zero for some strictly positive integer n. For any given decimal it is easy to decide whether it is of this form. Further, for any number of this form, there is only one value of n for which the constraint will hold. It is clear that reals with canonical decimals of this form are dense in the reals.

    Consider the trailing non-zero digits in decimals of this form. This is an infinite string of digits in the range 1-9 and can be used to arbitrarily encode information of one's choice. The remainder of the challenge is simply dotting the i's and crossing the t's.

    Let the first digit encode a sign. 1 => +1. 2 => -1. 3-9 => 0. Call this ##S##.

    Let the second digit encode a sign on the exponent. 1 => +1, 2 => -1. 3-9 => zero. Call this ##s##

    Let the next digits encode an exponent. 9 = end of sub-string, subtract 1 from each of the intervening digits to produce the octal expansion of a non-negative integer. If there is no 9 in the string, the exponent is taken as zero. If a 9 appears immediately, the exponent is taken as zero. Call this ##e##

    Subtract 1 from each of the remaining digits to produce the base nine fraction with the radix point assumed to the left of the first digit. If there are no remaining digits (e.g. if the trailing non-zero digits have no 9) then this mantissa is taken as zero. Call it ##m##.

    Let f(x) = x if the canonical decimal expansion of x fails to take the requisite form.
    Let f(x) = ##Sm\cdot9^{se}## if the canonical decimal expansion of x does take the requisite form.

    For any given (x,y) pair and any given tolerance it is clear that we can find infinitely many base 9 floating point values within that tolerance of y. And it is also clear that we can find infinitely many reals within the tolerance of x with canonical decimal expansions that encode such a base 9 floating point value. Which is to say that the graph of f is dense in R^2.
     
    Last edited: Apr 27, 2016
  20. Apr 27, 2016 #19

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Very beautiful solution!

    As an alternative, every function ##f:\mathbb{R}\rightarrow \mathbb{R}## which satisfies ##f(x+y) = f(x) + f(y)## but is not linear/continuous/Lebesgue measurable/of the form ##f(x) = \alpha x## (these four are equivalent), has a graph dense in ##\mathbb{R}^2##.
    Source: Herrlich "Axiom of Choice" Chapter 5.1
     
  21. Apr 27, 2016 #20

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Not sure I interpret this correctly, but anyway.
    ##A=]0,1[\cup ]2,3[##.
    ##f: A \to \mathbb R: x \mapsto x##
    ##g: A \to \mathbb R: x \mapsto x## for ##x \in ]0,1[##, ##x \mapsto x + 1 ## for ##x \in ]2,3[##.
    ##\forall x\in A: f'(x)=g'(x)=1##, but obviously there is no ##C\in \mathbb{R}## such that ##f(x) = g(x) + C##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Micromass' big counterexample challenge
Loading...