# Tag Info

2

Start with the list of all $2^n$ vectors of length $n$ of $+1$s and $-1$s. Someone changes some of the entries to $0$. Show that there is always a non-empty collection of rows which sums to the zero vector. This looks like the perfect case for induction (on $n$), but the two proofs I'm aware of don't use induction; induction just doesn't seem to help here.

4

1) For all relatively prime positive integers $a$ and $m$ there is a prime number in the arithmetic progression $a$, $a+m$, $a+2m$, $a+3m,\dots$ Of course the general theorem is that there are infinitely many primes in each such progression, but the way I stated it by quantifying over all $a$ and $m$ is equivalent to the general version; for beginners I ...

2

For all n, there is no m such that m < n < m+1.

2

Theorem: For all $n\in \mathbb{N}$, $$n^2 + 1 \geq 2n.$$ Easy to prove by just observing that $(x-1)^2 \geq 0$ for all $x\in \mathbb{R}$. Not only is this way quicker than writing out a proof by induction, but it works for all real numbers, not just natural numbers. So you have an easier proof of a stronger result!

3

There's the classic example that $$1 + 2 + \ldots + n = \dfrac{n(n+1)}{2},$$ which can be proved without induction using Gauss's trick, or the geometric argument involving a rectangular grid. In a similar vein, showing $${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k} \quad \text{for } 1 \le k \le n - 1$$ has a really straightforward ...

0

You have not died every day since you were born.

-1

One good example of such a sequence is a prime number generating sequence related to the Ulam spiral: $N^2 - N + 41$. Tt generates prime numbers when N = any integer from 0 to 40 inclusive, but obviously fails at 41, returning the result of 41^2. The solutions form a diagonal line on an Ulam spiral that starts at 41 Here is a Youtube video by Numberphile ...

6

There is a whole family of examples similar to the proposition that $n^3-n$ is divisible by $6$ for each natural number $n$. Proof by induction isn’t hard, but it’s certainly unnecessarily complicated.

0

The book Fabian, Habala, Hájek, Montesinos, Zizler: Banach Space Theory, The Basis for Linear and Nonlinear Analysis (CMS Books in Mathematics) has many exercises at the end of each chapter. It does not have solutions, but most of the exercises come with some hint (in some cases rather detailed). Google Books link, DOI: 10.1007/978-1-4419-7515-7 This book ...

0

As a fellow undergraduate, I'm working my way through the book Introduction to Abstract Algebra (4th Edition) by W. Keith Nicholson. The book contains all of the areas of Algebra you mentioned and more, and there are a plethora of problems for each of the sections on Group Theory, Ring Theory, Field Theory, Galois Theory, and so on. Each section has ...

3

For all $n \in \mathbb{N}$, $\frac{n}{n+1} < 1$. The slick algebraic proof of this would be $\frac{n}{n+1} = 1 - \frac{1}{n+1} < 1$ since $\frac{1}{n+1}>0$ for all $n \in \mathbb{N}$. Induction would be much messier...

1

There is a counterintuitive counterexample from the theory of inverse problems of a non-measurable conductivity on a disc that is not distinguishable from a homogeneous one w/boundary circle electrical measurements. It involves a function $f(r):[0,1]\rightarrow R^+$, such that $f(r^n)=f(r)$ for all natural numbers $n$. The construction of such a function ...

3

It seems like Stephen Abbott's Understanding Analysis is just what you are looking for. From page vii of the Preface: Each chapter begins with the discussion of some motivating examples and open questions. The tone in these discussions is intentionally informal, and full use is made of familiar functions and results from calculus. The idea is to freely ...

0

We have the well known sum \begin{equation*} 1+x+x^2+\cdots =\frac{1}{1-x}. \end{equation*} Setting $x=e^{i\theta},~0<\theta<2\pi~(x\neq 1)$ gives \begin{equation*} 1+e^{i\theta}+e^{2i\theta}+\cdots =(1-e^{i\theta})^{-1}=\frac{1}{2}+\frac{1}{2}i\cot(\frac{1}{2}\theta). \end{equation*} Equating the real parts we see that \begin{equation*} ...

1

Regarding the development of the idea of mathematical "structure" during the '30s, and thus independently from the "mainstream" structuralism, I suggest you the book : Leo Corry, Modern Algebra and the Rise of Mathematical Structures (1996), and the Review by R.Reed, and the paper : Leo Corry, Mathematical Structures from Hilbert to Bourbaki.

0

Here's a proof using transfinite induction, which I think is close to the one provided by Borel. Unfortunately, this proof assumes the Axiom of Choice. Suppose there is a collection $\mathcal{U}$ of open intervals which covers $[0,1]$ but no finite subcollection of it covers $[0,1]$. Let $\kappa$ be a cardinal greater than $|\mathbb{R}|$. For each ordinal ...

0

I haven't worked out details. But presumably you could model a modern computer (at the level of electrical circuits, transistors, etc), using ordinary differential equations. If you include an infinitely long magnetic tape (which would require either an infinite dimensional ODE, or a PDE), then you have constructed a Turing machine. And hey presto, you ...

-1

If you can read Chinese or have some friends help to translate, my blog is the best choice (http://blog.sina.com.cn/strongart), you can find a lot of pure math notes and teaching videos: commutative algebras(1-30, 1-13+) functional analysis and operator algebras(1-60) and so on. They are all made by myself. I wish someone reposts them to Youtube or ...

0

The notion of equivalence is relative to the theory. It is important to note that some of the equivalences cited above are not correct if you do not assume Archimedes axiom. For example, in Dehn's semi-euclidean plane, the sum of angles of any triangle is $\pi$ but the axiom of parallels fails: https://en.wikipedia.org/wiki/Dehn_plane Also, Hartshorne ...

6

I think: This answer on MathOverflow is relevant. This paper is pointing out the counterexample. This paper is mending the original statement. The theorem is in algebra, and is about whether the $\lim^1$ functor vanishes on Mittag-Leffler sequences in abelian categories satisfying certain axioms. In order to correct the mistake, the author had to add a ...

15

With a strict enough definition of "non-foundational mathematics" I think the answer is probably "no" (although I would be very interested in seeing potential examples.) However, this shouldn't make mathematicians working on such mathematics feel safe about using unrestricted comprehension. The reason is that it's not always clear a priori what mathematics ...

7

The whole idea of using set theory as a foundational theory is that you want a theory that if you believe is consistent, the rest of mathematics is consistent. Naive set theory is inconsistent. So you can't really continue, you cannot trust it to give you the rest of mathematics. And it is not important that you "don't seem to appeal to the paradoxes". ...

4

Well, I wouldn't trust a building whose structure was shown to be flawed. Note that it isn't a suspicion, it is a certainty. But I know what you mean by your question... consider the following "proof" (taken from another question at MSE): Theorem: Let $K$ be a field, then $K$ has an algebraic closure $\bar{K}$ (i.e an algebraic extension that is ...

1

By transfinite induction, I will show that every countable ordinal $\alpha$ there is a set of rationals $S_\alpha\subseteq (0,1)$ which has order type $\alpha$. Then we will have $\omega_1$ clearly distinct sets of rationals. For $S_0$ we can (indeed, we have to) take an empty set. For set $S_{\alpha+1}$ we can take $\frac{1}{2}S_\alpha\cup\{\frac{1}{2}\}$, ...

2

Define $f : \mathbb{R} \to \mathcal{P}(\mathbb{Q})$ as $f(x) = (-\infty, x) \cap \mathbb{Q}$. It is injective, so $|\mathbb{R}| \leqslant |\mathcal{P}(\mathbb{Q})|.$

1

Follows directly by Cantor's Theorem. (Note that you asked a proof that $\mathcal{P}(\mathbb{Q})$ is uncountable, not that its cardinality is the same of $\mathbb{R}$)

2

For each real number $x$ pick a strictly increasing sequence $x_n$ of rationals converging to $x$. Then $$f(x)=\{ x_n| n \}$$ is a one to one function from $\mathbb R$ to $P(Q)$. As $\mathbb R$ is uncountable....

0

Here is one I found myself (those are complete prime factorizations): \begin{align}38&=\textbf {2}\cdot 19\\ 38\, 111&=\textbf{23}\cdot \color{#0bc}{1657}\\ 38\, 111\, 111 &=\textbf{233}\cdot \color{#0bc}{163567}\\ 38\, 111\, 111\, 111 &=\textbf{2333}\cdot 31\cdot 526957\\ 38\, 111\, 111\, 111\, 111 ... 5 One problem which I like is the Bridge of Konigsberg problem. The challenge is to find a path that crosses each bridge exactly once. It was eventually proved to be impossible by Euler and is considered one of the early applications of graph theory. http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg 8 This answer takes a bit of background, but I think it's worth it. Please bear with me! If you already have the necessary background, you can skip to the last section for the punch line. The surface of a sweet bun and the surface of a doughnut are both examples of two-dimensional manifolds: geometric spaces that look like planes from close up. An ant ... 3 It's impossible to define mathematics in a way that satisfies all mathematicians. This is likely not the answer you're after, but it stroke me when I first heard of it because definitions in mathematics are both exact and omnipresent, and I was not suspecting that providing a universal definition of mathematics itself could be such an intractable problem. ... 0 Find a solution, x \in \mathbb{R} to the equation x+1=x.​ 4 There exists a set of Wang tiles for which it is undecidable whether they can tile the entire plane. Wang tiles are nice and geometric and easily described, but you can encode each Turing machine so that the machine halts if and only if the tiles can't tile the entire plane. 5 Constructing an algorithm to solve any Diophantine equation has been proven to be equivalent to solving the halting problem, as is computing the Kolmogorov complexity (optimal compression size) of any given input, for any given universal description language. In general I think what you're looking for is either problems that are proven to be equivalent to ... 13 It is impossible to find a rational number whose square is 2. 1 As stated by JJacquelin, your example is wrong. However, the following theorem is impossible to solve with just the axioms of Zermelo–Fraenkel set theory: the Cartesian product of a collection of non-empty sets is non-empty. This led to the famous Axiom of choice being introduced (in another form) by Zermelo to address the issue. Previously, the axiom ... 3 << about the impossibility of trisecting an angle using compass and straight edge and its fascinating to see such a deceptively easy problem that is impossible to solve >> This statement is false. Since it is now proved that "trisecting an angle using compass and straight edge is impossible", the problem is solved. So, the problem was not impossible ... 13 The proof that demonstrates the impossibility of trisecting an angle uses Galois theory. Galois theory can also be used to show that certain polygons cannot be constructed with compass and straightedge, and was originally used to show that, in general, polynomials of degree \geq 5 are not solvable. To be specific, an n-gon is constructible via ... 3 Take a look at this project http://www.formulae.org It is open source, it is about math and it is partially documented. There are several sources for documentation: the developer's guide (LaTeX, partially), the front-end user´s guide (LaTeX, starting), the API reference (JavaDoc, partially) and expression dictionary (online wiki, partially) 5 See the papers of: Dusart 2010 Axler 2013 Axler 2014 Büthe 2014 Kotnick 2008 Schoenfeld 1976 For the nth prime upper bound, Axler 2013 viii Korollar G is best when n \ge 8009824. Dusart 2010 page 2 is best from 688383 to 8009823. Below that, either Dusart 2010 page 7, Dusart 1999 page 14, Robin 1983 or tweak the values since this is a limited ... 3 In the nineteenth century expressing the antiderivative of an elementary function as an elementary function was an open problem. Nowadays, Risch algorithm, which can be run on machines, decides whether such operation can be done and, if so, yields a version of the correct result. I cannot speak for past mathematicians, but I think this is a useful tool. ... 7 I would say that computing the Fourier coefficients of a tamed function is a triviality today even at an engineering math 101 level. Ph. Davis and R. Hersh tell the long and painful story of Fourier series. I quote from their book: "Fourier didn't know Euler had already done this, so he did it over. And Fourier, like Bernoulli and Euler before him, ... 5 This sum-of-squares theorem of Fermat may qualify as an example: An odd prime p is expressible as the sum of squares x^2+y^2 if and only if p\equiv 1 \text{ mod } 4. You can read this Wikipedia article (as of the most recent update to this answer) to see the difference in mental effort in the original proof by Euler, as opposed to a modern ... 6 That there exist transcendental numbers. This was fist shown by Liouville, who proved that Liouville's number:\sum_{i=0}^\infty10^{-i!}is transcendental. The "modern" proof would be due to Cantor: There are countably many algebraic numbers and uncountably many reals. Therefore there exists a transcendental number. Proving that Liouville's number ... 1 Proofs that \sqrt{2} is irrational. I know (at least) four, and there are lists of many more. I could go on, but would be a bore, so I'll let someone else have the floor. 1 \mathbb{R}[i] \simeq \mathbb{C} The first isomorphism theorem is what allows you to say \mathbb{R}[x]/(x^2+1) \simeq \mathbb{R}[i] which is just \mathbb{C}. We identify the kernel of \phi:p(x) \to p(x) \mod (x^2 + 1) with the ring setting x^2 + 1 = 0. This is a very powerful idea, leading to the notion of algebraic variety Brouwer Fixed Point ... 0 Einstein was an amateur violinist who would give recitals at Princeton, with his friend Casadesus playing the piano. After having met Einstein, composer Bohuslav Martinů wrote Five Madrigal Stanzas, which he dedicated to him. The violin part was tailored to Einstein's limited abilities. When he was asked how Einstein performed it, the composer's answer would ... 7 First Isomorphism Theorem examples First Isomorphism Theorem (FIT) applies in different contexts: Groups, Rings, Vector Spaces, Lie Algebras and other structures. As follows, examples for the first three. Three Group Isomorphisms Let us consider GL_2(\Bbb F_3): the group of 2\times 2 invertible matrices with coefficients in \Bbb F_3 which is the ... 1 One of the most worth-mentioning identities may probably be Carl Friedrich Gauss's compution of cos(2pi/17): \begin{align} \cos(\frac{2\pi}{17})&= \frac1{16}[-1+\sqrt{17} + \sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}-\sqrt{34-2\sqrt{17}}-2\sqrt{34+2\sqrt{17}}}]\\ \end{align} which has a significant role in regular heptadecagon construction. 2\int_0^1\frac{x^4(1-x)^4}{1+x^2}=\frac{22}{7}-\pi It's interesting how something so bizarre on the left hand side yields the tiniest of errors in one of the most famous approximations of $\pi$.

Top 50 recent answers are included