# Tag Info

33

The busy beaver function $BB(n)$ is (informally) an upper bound on the amount of time a computer of size $n$ can compute without going into an infinite loop. It increases much more quickly than does Ackermann's function; so much so that it can't be computed at all. In fact, it increases more quickly than any function that can be computed. The busy beaver ...

15

The definition of equicardinal is that there exists a bijection between the sets. You are trying to define "not equicardinal" as "there exists a bijection between one set and a strict subset of another". This definition is not a good one, as all Dedekind infinite sets (such as $\mathbb{Z}, \mathbb{R}$) have the property that they are bijective with strict ...

9

Fast-growing functions appear a lot in proof theory. For example Goodstein's theorem states that the Goodstein function (defined in the link) can not be proved total in Peano arithmetic because it grows too fast. Harvey Friedman conducts some research on this side. There is, for example, a finite version of Kruskal's tree -theorem. The TREE function is a ...

7

You are correct. If I know what you are saying, you are right that it wouldn't matter. The factored form is $(x+3)(x-3)(x^2+3x-1)$.

6

Seems perfectly possible to me. Take $F = \mathbb R$, $a=0$ and $\displaystyle f(x)=\exp\left(-\frac{1}{x^2}\right)\sin\left(\frac{1}{x}\right)$ (with $f(0)=0)$. If I'm not mistaken, $f$ even verifies $f^{(n)}(0)=0$ for all $n \in \Bbb N$.

6

Rule of thumb: if the current year shows up in a problem, it is probably a red herring. Second rule of thumb: looking for a pattern will help you decide what to prove. $$f(1) + f(2) = 4 f(2) \implies f(2) = \frac{f(1)}{3}$$ $$f(1) + \frac{f(1)}{3} + f(3) = 9 f(3) \implies f(3) = \frac{f(1)}{6}$$ $$f(1) + \frac{f(1)}{3} + \frac{f(1)}{6} + f(4) = 16 f(4) ... 5 Consider A=\{3,7\}, B=\{3,7,9001\} and f defined by f(3):=3 f(7):=7. As long as g maps 3 back to 3 and 7 back to 7, the function g\circ f will be the identity on A, while there are two options to where g may map 9001 to. 5 As far as I know, there isn't. The concept of a "non-surjective and non-injective function" just doesn't generally arise often enough to need a special term. 5 As mentioned by others as well, the statement is that A\sim B \Leftrightarrow \exists \phi:A\leftrightarrow B (i.e., A and B are of the same cardinality if there exists a bijection between A and B) That is not to say that all maps between them must be bijective, just that there must be at least one such map. Consider A=\mathbb{N} and ... 5 Only statement (c) is true. Hint: if f is continuous and strictly increasing, it has a continuous (left-)inverse f^{-1}. Consider f^{-1} \circ f \circ g. Counterexamples, in no particular order: f(x) = x, g(x) is discontinuous f is increasing but discontinuous, g is a constant function f is increasing but discontinuous, g(x) = x ... 4 I think the fundamental error here is a mistaken notion of what the Pigeonhole Principle is. Nowhere in the Wikipedia page cited in the question does it say there is any rule over which hole each pigeon may go into. As is evident from some comments on other answers the argument in the question is based on the misconception that the Pigeonhole Principle ... 4$$f(x)=\int \sin^2{x}dx=\int\dfrac{1-\cos{(2x)}}{2}=\dfrac{x}{2}-\dfrac{\sin{2x}}{4}+C$$since$$f(\dfrac{\pi}{2})=\dfrac{\pi}{4}\Longrightarrow C=0$$4 I'ts not "exponential" in the sense of the derivative being proportional to the value, no. It does, however, have "exponential growth", in the sense that there's a constant C with$$ |f(x)| \ge C u^x $$for large enough x and for some u > 1. In computer science, such functions are sometimes sloppily called 'exponential', even though they could ... 4$$n^2f(n)-(n-1)^2f(n-1)=f(n)\\(n^2-1)f(n)=(n-1)^2f(n-1)\\f(n)=\frac{(n-1)}{n+1}f(n-1)=\frac{n-1}{n+1}\cdot\frac{n-2}{n}f(n-2)=\cdots=\frac{(n-1)!}{(n+1)\cdot n\cdots4\cdot3}f(1)=\frac{2}{n(n+1)}f(1)\\f(2013)=\frac{2}{2013\cdot 2014}\cdot2014=\frac{2}{2013}$$4 This equality is equivalent to this statement: There is an integer n strictly between \log_2(t+1) and \log_2(t+2) And this is the same as t+1< 2^n<t+2 This happens if and only if \lceil t+1\rceil  is a power of 2 and t\notin\Bbb Z. 4 Many times we know from context that the solution of a problem will necessarily have certain continuity properties (e.g. physics laws may imply that). However, "apparent" singularities may be introduced as artifacts of the solution methods employed. In such case we can safely remove these apparent singularities. This can be done quite spectacularly in ... 3$$\int_{-1}^1f(x)dx=\int_{-1}^0f(x)dx+\int_0^1f(x)dx$$By the ranges of definition, this$$=\int_{-1}^0x\ dx+\int_0^1 x^2\ dx$$3 If k \leqslant \sqrt{N}, then \lfloor N/\lfloor N/k\rfloor\rfloor = k, since, letting m = \lfloor N/k\rfloor, we have$$mk\leqslant N < (m+1)k = mk + k \leqslant mk + m = m(k+1),$$so that gives you \lfloor \sqrt{N}\rfloor values. And the values of \lfloor N/k\rfloor for k \leqslant \lfloor \sqrt{N}\rfloor are all different, since ... 3 The actual problem is that what you wrote there are not the functions, but just two terms varying by a certain parameter. In order to call those a function, you have to define the domain, which would look like this:$$f: \mathbb{R}\setminus\{2, 4\}\rightarrow \mathbb{R}, x \mapsto f(x) := \frac{(x-2)(x-3)}{(x-2)(x-4)}\\ g: \mathbb{R}\rightarrow \mathbb{R}, ...

3

There is an informal concept of "function", which says that a function is any correspondence (itself an informal term) that assigns one definite output value to each input value of the function. This informal concept has various formalizations, depending on the precise use one has for it. The set-based concept of a function as a set of ordered pairs such ...

3

Your question has nothing to do with group theory; the fact that inverse functions are necessarily bijective is a matter of set theory. And if you know, as a suppose, that in order to have an inverse function, a function $f$ must be bijective, it is pretty obvious that the inverse $f^{-1}$ will always be bijective. After all the requirement for an inverse is ...

2

The set $A$ is connected. Suppose that $\lim_{n\to\infty}f(x_n)=a$, $\lim_{n\to\infty}f(y_n)=b$ and $a<b$. Since $f$ is continuous, given any $c\in(a,b)$, by the intermediate value theorem you will be able to construct a sequence $z_n\to\infty$ such that $\lim_{n\to\infty}f(z_n)=c$.

2

They are not. You can only say they assume the same values in the intersection of their domains, that is: $$f|_{D(f) \cap D(g)} = g|_{D(f) \cap D(g)}.$$ This answer assumes the definition: two functions $f:A \to B$ and $g:C \to D$ are equal if: $A = B$, $C = D$ and $f(x) = g(x)$ for all $x \in A = C$.

2

Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,\ldots\,$. Therefore all pairs of rationals can be arranged in a table $$\def\p#1#2{(r_{#1},r_{#2})} \matrix{\p11&\p12&\p13&\cdots\cr \p21&\p22&\p23&\cdots\cr \p31&\p32&\p33&\cdots\cr ... 2 This answer is specifically about the Pigeonhole Principle, unlike some other answers which have been about infinity. A correct use of the Pigeonhole Principle requires the following: I define what my pigeonholes and pigeons are. The cardinality of the pigeons must be strictly larger than the cardinality of the pigeonholes. My nemesis assigns pigeons to ... 2 Since nobody decided to give a formal answer, I will try to give mine according to your comments. There's no equinumerous function or bijective set. There are equinumerous sets and bijective functions. Equinumerous sets are sets for which at least a bijection (bijective function) exists. Set A and B are equinumerous, if there exists a one-to-one and onto ... 2 On a different matter -- it does not (even remotely) grow as fast as the Busy-Beaver function, but there exist results saying that a general family of properties of graphs can be \varepsilon-tested in \phi(\varepsilon) queries to the graph [GGR98], where \phi(\varepsilon) is of the form$$2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}} where the dots hide a ...

2

Yes, you are thinking correctly. $(f+g)(1) := f(1)+g(1)$ $(f-g)(5) := f(5)-g(5)$ $(f/g)(-3) := f(-3)/g(-3)$ $(fg)(5) := f(5)g(5)$ Other than this, is just looking at the drawing. After squinting my eyes a bit, I found no mistakes in your work. You're on the right track. Good studies.

2

Hint for the first part (injectivity): Both $2a - 1$ and $2b - 1$ are positive.

2

So let $f(a)=f(b)$. Since $f(n_{odd})\le0$ if $n_{odd}$ is an odd natural number and $f(n_{even})>0$ if $n_{even}$ is an even natural number, we must have that if: $f(a)=f(b)$ Then either a and b are both even or both odd. With that in mind, we first consider a and b both even: $(-1)^a(2a-1)=(-1)^b(2b-1)$ $(2a-1)=(2b-1)$ $a=b$ And then a and b odd: ...

Only top voted, non community-wiki answers of a minimum length are eligible