1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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
    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

    User Avatar
    2017 Award

    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

    User Avatar
    2017 Award

    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

    User Avatar
    2017 Award

    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
    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

    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

    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

    User Avatar
    2017 Award

    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
    Nothing. That is the right counterexample.
     
  18. Apr 27, 2016 #17
    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
    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##.
     
  22. Apr 27, 2016 #21
    Right!
     
  23. Apr 27, 2016 #22

    TheDemx27

    User Avatar
    Gold Member

    For number six, the fact that there is a counterexample is especially counter-intuitive. I'd like to see that one solved.
    edit: oh wait it has been...
     
  24. Apr 27, 2016 #23

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    I'm curious for 10. :oldsmile:
     
  25. Apr 27, 2016 #24
    It just did. It's actually a pet peeve of mine. I see a lot of people writing
    [tex]\int \frac{1}{x}dx = \log|x| + C[/tex]
    while this is completely incorrect. The most general primitive of ##1/x## is not ##\log|x| + C##, but rahter
    [tex]\log|x|+ \left\{\begin{array}{l} C_1 ~\text{if}~x<0\\ C_2 ~\text{if}~x>0 \end{array}\right.[/tex]
    Where is the issue? The usual statement for ##6## comes from the mean-value theorem which only holds for connected domains (i.e. intervals). It does not hold when the domain of the function is not an interval, like the maximal domain for ##1/x##.

    I really don't get why calculus books don't pay attention to this and even make errors against it. You'd think it's harmless, but I've seen a number of threads here by people who were confused by something that is essentially this.
     
  26. Apr 27, 2016 #25
    Oh wow, I never knew that this "problem" exists. Never thought about it to be honest and indeed the calculus book I used (Adams) did that if i'm not mistaken.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted