The induction tag has no usage guidance.
0
votes
2answers
132 views
Are Regularity schema and $\in$-induction schema equivalent in intuitionistic logic?
In posting "Does Regularity schema imply $\in$-induction when added to first order Zermelo set theor?"
the answer was that they are equivalent in classical first order logic with membership "$\in$".
...
1
vote
2answers
155 views
Does Regularity schema imply $\in$-induction when added to first order Zermelo set theory?
That $\in$-induction fails to be a theorem schema of first order Zermelo + Foundation (see here), then it appears that it is more eligible to replace axiom of Regularity (Foundation) by a Regularity ...
2
votes
1answer
237 views
Is $\in$-induction provable in first order Zermelo set theory?
Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail?
I asked this ...
2
votes
2answers
117 views
How to estimate a recursive inequality with an upper bound
The below is a simplification of part of a proof I'm working on, in numerical analysis. It is similar to a paper that I studied some months ago, for which I got some advice here on MathOverflow.
I ...
7
votes
1answer
191 views
Independent/Easy fraction of sentences over PA
Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
-1
votes
1answer
212 views
Towers of induced functions
Suppose $\mathbb{X}$ and $\mathbb{Y}$ are classes, and $f:\mathbb{X}\rightarrow\mathbb{Y}$. It seems like pretty standard course to consider an 'induced function' $f:\mathcal{P}\mathbb{X}\rightarrow\...
1
vote
0answers
130 views
Proving the existence of a sequence with recursive growth constraints
Fix $0 < c < 1/3$. Show that there exists a strictly increasing sequence $a_k > 0$, a sequence $b_k \geq 0$, and an infinite set $K \subseteq \mathbb{Z}_{>0}$ such that
\begin{align}\...
5
votes
4answers
461 views
Mathematical induction vis-a-vis primes
One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone ...
6
votes
1answer
350 views
Inductive Definitions in Category Theory
I'm trying to pin down a notion of inductive definability in category-theoretic terms.
The sorts of inductively defined sets (and classes) I'm most interested in are those that admit of induction and ...
2
votes
0answers
294 views
When must one strengthen one's induction hypothesis?
My questions are about the phenomenon that in order to prove a fact $\forall x \phi(x)$ by induction, sometimes straightforward induction "does not work" and instead one "must" use a "stronger" ...
19
votes
5answers
2k views
Is Cauchy induction used for proofs other than for AM–GM?
The proof by Cauchy induction of the arithmetic/geometric-mean inequality is well known. I am looking for a further theorem whose proof is much neater by this method than otherwise.
3
votes
1answer
250 views
Affine analog of the theory of sheets
In the study of adjoint orbits in a complex semi-simple lie algebra, there is a well known object known as a "sheet". These are the irreducible components of the union of orbits of the same dimension. ...
4
votes
0answers
115 views
Problem with a proof in Wellfounded trees in categories
I'm reading the paper Wellfounded trees in categories by Moerdijk and Palmgren. I'm having trouble understanding the proof of Theorem 7.2 (page 216), i.e. that in $\mathbf{ML}_{< \omega} \mathbf{W}$...
1
vote
0answers
47 views
A curious example envolving moment's convergence
Let $\{X_n\}$ be a random variable sequence and $X\sim N(0,\sigma)$. In general, the convergence $E(X_n^k) \stackrel{n}{\longrightarrow}E(X^k)$ doesn't implie that $E(X_n^{k+1}) \stackrel{n}{\...
3
votes
0answers
500 views
Two (strictly related) proofs by induction of inequalities
This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
17
votes
7answers
1k views
Unconventional types of induction
Induction is one of the most common tools is mathematics, and everybody knows the ordinary induction and the strong induction. However, in some proofs induction is applied in an unexpected and elegant ...
3
votes
2answers
462 views
notable inductive proofs relating to fractals
what are notable/ prominent inductive proofs relating to fractals?
the motivation for this question is:
fractals are very difficult mathematical objects to work with, and many problems/questions ...
3
votes
2answers
809 views
Neither Even Nor Odd Natural Numbers
Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement ...
36
votes
3answers
4k views
the following inequality is true，but I can't prove it
The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...
7
votes
1answer
536 views
ERA, PRA, PA, transfinite induction and equivalences
I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.
For instance I'm ...
2
votes
3answers
2k views
Why Does Induction Prove Multiplication is Commutative?
Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall z\bigr((Sx=...
7
votes
4answers
1k views
Examples of “exotic” induction
Next week I am going to teach two lessons on induction to very motivated students from high schools. At some point I would like to talk about ordered sets, well-ordered sets, and mention the fact that ...
5
votes
2answers
1k views
Homotopy Transfer Theorem for Differential Graded Associative Algebras
As in Algebra+Homotopy=Operad by Bruno Vallette, let $A$ with multiplication $\nu$ be a differential graded associative algebra equipped with degree +1 map $h$ and let $H$ be a chain complex such that ...
1
vote
0answers
121 views
Coinduction and corestriction are quasi-inverse equivalences for comodules?
I'm reading http://arxiv.org/abs/math/0310337.
There the following statement is given without proof:
Let $k$ be a field. Let $C$ be a counitary coaugmented coalgebra, i.e. there is $\eta: C\to k$ ...
0
votes
1answer
717 views
Maximum sum of 3 consecutive numbers in a permutation [closed]
Given that $X = \{0, 1, 2, ..., 7, 8, 9\}$, and $P$ is a permutation on $X$. Let $M(P)$ be the maximum sum of 3 consecutive elements. For example, if $P = (0, 2, 4, 1, 5, 7, 9, 3, 8, 6)$, then $M(P)$ ...
8
votes
2answers
860 views
Order statistics (e.g., minimum) of infinite collection of chi-square variates?
Hi everyone,
This is my first time here, so please let me know if I can clarify my question in any way (incl. formatting, tags, etc.). (And hopefully I can edit later!) I tried to find references, ...
17
votes
11answers
7k views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...
10
votes
3answers
2k views
Easier induction proofs by changing the parameter
When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof ...
4
votes
1answer
387 views
For which classes of functions this inverse function formula gives a closed form expression?
Lets consider this method of finding inverse function:
$$f^{-1}(x) = \sum_{k=0}^\infty A_k(x) \frac{(x-f(x))^k}{k!}$$
where coefficients $A_k(x)$ recursively defined as
$$\begin{cases} A_0(x)=x \\ ...
3
votes
2answers
1k views
How to restore the original formula from a binomial-like expansion?
I encountered with a recursive formula of the following kind:
$$A(0,x)=1$$
$$A(n,x)= \sum _{j=0}^{n-1} \binom{n-1}{j} A(n-j-1,x) \sum _{k=0}^{x-1} A(j,k)$$
The sum terms can be re-arranged so to ...
7
votes
1answer
781 views
Symmetric Proof that Product is Well-Founded
This is a fairly minor, technical question, but I'll toss it out in case someone has a good idea on it.
Suppose $(X,<_X)$ and $(Y,<_Y)$ are well-founded orderings (not necessarily linearly ...
34
votes
4answers
3k views
A principle of mathematical induction for partially ordered sets with infima?
Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old ...
4
votes
6answers
4k views
Proofs by induction [closed]
Background
I'm interested in the issue of "explanatory" mathematical proofs and would like to try to find out what intuitions mathematicians have about induction, because there seems to be some ...
