# Tag Info

45

Write the axioms of number theory as $P^-+\mathrm{Ind}$, where $P^-$ is the ordered semiring axioms (no induction), and $Ind$ is the axiom (scheme) of induction. Then a theorem requires some induction if it is not provable by $P^-$ alone - that is, if we can find a model of $P^-$ in which the theorem is not true. (This is Goedel's completeness theorem.) So ...

23

Here is a "proof" of a famous identity by Ramanujan: $$\sqrt{1+\sqrt{1+2\sqrt{1+3{\sqrt{1+4\sqrt{\dots}}}}}}=2.$$ Claim: Let us prove this more general result for all $n\geq 0$: $$\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{\ldots}}}}}=n+1.$$ Base case: When $n=0$, we have $\sqrt{1+0\sqrt{\dots}}=0+1$, and this is true. Inductive step: Assume ...

8

Claim: For every $n\in\mathbb{Z^+}$, if $x,y\in\mathbb{Z^+}$ with $\max(x,y)=n$, then $x=y$. Base case: Suppose that $n=1$. If $\max(x,y)=1$ and $x,y\in\mathbb{Z^+}$, then $x=1$ and $y=1$. Inductive step: Let $k\in\mathbb{Z^+}$. Assume that whenever $\max(x,y)=k$ and $x,y\in\mathbb{Z^+}$, then $x=y$. Now let $\max(x,y)=k+1$, where $x,y\in\mathbb{Z^+}$. ...

7

A nice example from the area of computer science would be John C. Reynolds "Polymorphism is not set-theoretic" (available here: https://hal.inria.fr/inria-00076261/document). The point is that second-order $\lambda$-calculus does not have set-theoretic models (there is a rather natural definition in the paper of what it means to be "set-theoretic"). The ...

6

Does the following standard proof of the Brouwer fixed point theorem for the two-dimensional disk $D$ count? Theorem. Any continuous map $f : D \to D$ has a fixed point. Proof. If $f$ had no fixed point, the map $g : D \to \partial D$ given by $g(x) = \partial D \cap ($ray from $f(x)$ to $x)$ would be a retraction of $D$ onto $\partial D$, that is, $g ... 6 Here is a collection of Flawed Induction Proofs. 6 Here is one published by Knuth. Claim: $$\underbrace{\frac1{1\cdot2}+\frac1{2\cdot3}+\ldots}_{n\text{ terms}}=\frac32-\frac1n$$ Base case: For$n=1$, we have$\frac32-\frac11=\frac1{1\cdot2}$Inductive step: $$\left(\frac1{1\cdot2}+\ldots+\frac1{(n-1)\cdot n}\right)+\frac1{n\cdot(n+1)}=\frac32-\frac1n+\frac1{n\cdot(n+1)}$$ ... 6 One example is Sylver's Coinage played like so: Player's alternate selecting positive integers ($1, 2, 3, 4\dots$). The rule is that no number is allowed to be expressed as sum (with possible duplicates) of the previous. For example, say$\{4, 8, 5, 7\}$($8$would have had to been said before$4$) was previously said. Then$6$could be said, but$14$could ... 4 One example is the ring game, which is defined here - in essence, the game (or a slight variant thereon) can be described as: Start with a Noetherian ring$R$. At each turn, replace$R$with a quotient thereof. If a player can make no legal moves (i.e.$R$is a field, thus has no proper quotients). One can notice that if we play this on$\mathbb Z$, ... 4 Here are two proofs that both involve recognizing that a big category is the ind- or pro-category of a smaller category, and then proving something about the smaller category to get it for the bigger category. Theorem: The Pontryagin dual$\text{Hom}(A, S^1)$of a torsion abelian group$A$is a profinite abelian group and vice versa; these two maps are ... 4 Here is one example, very classical probably. I hope it counts for your purposes! Proposition. The fundamental group of a topological group$(G,\ast,e)$is abelian. Proof. The fundamental group$\pi_{1}$is a functor from topological spaces to groups which preserves products, so that it sends group objects into group objects. A topological group is a ... 4 How about the following: Given collections$\{a_i\}$and$\{b_i\}$of real numbers, then for all$n$:$\sum_{i=1}^n a_i + \sum_{i=1}^nb_i=\sum_{i=1}^n(a_i+b_i)$. If that is what you are looking for then I'm sure you can come up with millions of other such examples. 3 The Baire Category Theorem is equivalent to the Axiom of Dependent Choice, and therefore you would not expect to be able to find what you call a neat proof. It may if course not be exactly what you are looking for, precisely because induction alone is not enough to prove the theorem. 2 For each non-negative integer$n$, let$S(n)$be the statement$S(n) : n=0.$Claim: Every non-negative integer is equal to$0$. Base case:$S(0)$is clearly true. Inductive step: Fix some$k\geq 0$and assume that$S(0),\ldots, S(k)$are true. To prove that$S(k+1)$is true, observe that$S(k)$says$k=0$and$S(1)$says$1=0$; hence, we have that ... 2 Let me provide a few references about the$p$-Laplace operator. Some open problems concerning$p$-Laplacian are listed in Abstracts of Mini-Workshop "The p-Laplacian Operator and Applications", 2013, on the pages 476-480. (Problem 3 about Nodal line of second$p$-eigenfunction is explained also here, p. 10.) Other open problems like a unique continuation ... 2 Claim: For every non-negative integer$n, 5n=0$. Base case:$5\cdot 0=0$. Inductive step: Suppose that$5j=0$for all non-negative integers$j$with$0\leq j\leq k$. Write$k+1=i+j$, where$i$and$j$are natural numbers less than$k+1$(I am considering the natural numbers to include$0$). By the induction hypothesis,$5(k+1)=5(i+j)=5i+5j=0+0=0$. Flaw: ... 2 Higman's game$^*$Using finite words on a fixed finite alphabet, two players take turns, in each turn specifying a word that contains no already-specified word as a subsequence. The game terminates when a player (declared the loser) is unable to specify a word, and the other player is declared the winner. By Higman's Lemma, every such game must eventually ... 2 The Hydra problem can be converted in a game with several players. The first player chooses the hydra. Players take turns cutting heads. 1 A ring$R$with exactly two non-maximal ideals,$\{0\}$and$R$, is either a local ring that's not a field or a product of two fields. 1 A commutative ring is connected (no nontrivial idempotents) iff$\{0\}$and$R$are the only finitely generated idempotent ideals. Near misses: A commutative ring is semisimple iff$R$is the only essential ideal. A commutative ring has trivial Jacobson radical if$\{0\}$is the only superfluous ideal. A commutative ring is reduced iff$\{0\}$is the ... 1 Finite groups: The cyclic groups; the dihedral groups; the symmetric groups; the alternating groups; the quaternion group. 1 Graph Theory: the complete graphs; the complete bipartite graphs; trees; the Petersen graph. 1 The Jacobson radical. Take a noncommutative ring$R$with 1. Any left ideal is either contained in another or is maximal. The elements common to all maximal left ideals, i.e. $$J = \bigcap_i M_i,$$ is a group in two ways: It is an abelian group because it is an ideal (inherits group additivity from$R$, pretty obvious). It is group under circle ... 1 You might be interested in "Uncle Petros and Goldbach's Conjecture", a 1992 novel by Greek author Apostolos Doxiadis. This book has got a good story, and also discusses mathematical problems and some recent history of mathematics. http://www.amazon.co.uk/gp/aw/d/0571205119/ref=redir_mdp_mobile/278-8223441-9186456 1 I don't know if this fits as an answer, but I think that Michael Barr's existence of free groups is a nice application of some basic category theory. 1 You can prove the Poincare Lemma by reducing categorically/homotopy-theoretically to the case of a point. Proof: (re-)state the Poincare lemma (every closed form on a contractible subdomain of$\mathbb{R}^n\$ is exact) as a statement about De Rham cohomology, and prove that the De Rham cohomology functor sends homotopy equivalences to isomorphisms. I seem to ...

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