New answers tagged

1

The assumption is not discharged on line 5.   This is merely a redundant repetition of line 3.   That is okay, however it is redundant and repeated. Line 7 is the statement that line 4 and 6 are contradictory. $A, \neg A\vdash \bot$ .   The assumption is not yet discharged; though it is set up. The assumption is discharged on line 8 with &...


1

When you make an assumption, you're creating a mini universe in which the assumption is true. In that universe, you can reference the assumption as much as you want, just like you can reference premises and other statements as much as you like throughout the proof. Then, when you have done everything you need to with the assumption - either you've reached a ...


2

In response to a comment you made on Aravind's answer, you are absolutely allowed to go from $n$ to $n+1$, that is not where the problem in your proof is. However, your proof is still not working completely. What you have done is taken an arbitrary tree on $n$ vertices, which by your induction hypothesis has $n-1$ edges. You now form a new tree, (not an ...


2

Your induction proof is incorrect; the way induction works is (for example): Suppose we have a sequence $P(1),P(2),\ldots$ of statements and we wish to prove that $P(n)$ is true for all natural numbers $n$. After proving some base cases, say $P(1),\ldots,P(k)$, we consider an arbitrary $n>k$ and prove $P(n)$ assuming that the statements $P(1),P(2),\ldots,...


1

I'd like to add an aspect to your question, that hasn't been touched by any of the other answers thus far: Evidence plays a significant role in current day mathematics. Vectornaut already mentioned one example of this. Let me provide another, that has a different kind of flavour to it. I'd like to talk about large cardinals, but before I do so, let me ...


7

If you're a 20th-century sort of scientist, you might describe "evidence" for a hypothesis as a valiant but unsuccessful attempt to falsify it—to prove it wrong by showing that it implies something false. For example, say it's the early 1800s, and you want to test the hypothesis H that Fresnel's wave model accurately describes the behavior of light. You ...


5

Evidence is information that tends to indicate that a proposition is more likely to be true, whereas a proof demonstrates conclusively that the proposition is true. As such, yes a proof is evidence but evidence is not necessarily a proof, so you cannot use the terms synonymously. BTW, for this reason the old saw that absence of evidence is not evidence ...


0

Theorem: Suppose you have a set $P \subseteq \mathbb N$ where $\mathbb N = \{1, 2, 3, \dots\}$, with the following two properties $1 \in P$. If $n \in P$, then $n+1 \in P$. Then $P = \mathbb N$. Mathematical induction goes like this. Suppose you have some property. $p(n)$ that you want to prove is true for all natural numbers, $n$. Let $P = \{n \in \...


0

That doesn't quite work. I think this is a misunderstanding on how induction works. So for regular induction as you said what we do is: Prove the statement holds for some integer $k$ Prove that the statement holds for $n+1$ if it holds for $n$ Now this works because since the statement holds for $k$ it would then hold for $k+1$ and then since the ...


0

I know of one book that contains 256 proofs of the Pythagoran theorem. Wikipedia claims that several hundred proofs of the law of quadratic reciprocity have been found. I am sure that there are limits. Especially within a strictly formal logical/mathematical system. But I don't think that the answer is simple.


0

Let's not get into formal proofs. I don't think that is what you or your instructor are talking about. The picture above can be used to prove that the angle bisctor at $A$ intersects side $\overline{BC}$ in such a way that $\dfrac{AB}{BE} = \dfrac{AC}{CE}$. The proof involves showing that $\triangle AEC \sim \triangle DEB$ and showing that $\triangle ABD$ ...


14

Proposition: Every real number is less than $1,000,000$. Evidence: The proposition seems to hold for all numbers in my test set $\{1,2,3,\ldots,100\}$.


28

In mathematics, "evidence" is weaker than "proof". Mathematicians use the words "proof" and "evidence" differently from the sciences. When we speak of a "proof" that something is true, we mean an irrefutable line of logical implications. When we speak of "evidence" that something is true, we typically mean indications (like many worked out examples or ...


47

Hypothesis: $n^2-n+41$ is prime, for all natural $n$. Evidence: True for $n=1, 2, 3,\ldots, 40$. That seems persuasive, but for $n=41$ the hypothesis is false. In general, science typically uses inductive reasoning, i.e. noticing a pattern and claiming it continues forever. An improvement is the scientific method, i.e. noticing a pattern, making a ...


0

In an empty universe, every $\forall$ becomes true and every $\exists$ become false. So you can just split any theorem into two cases, one case assumes the universe is empty and one case does not. In the case where the universe is empty, everything is reducible to propositional logic. In the case where the universe is not empty, you are back to your ...


0

[Edit: This post was due to a misreading of ooooooo's system, which required that all free variables on the right of the sequent are in the set of variables on the left (like mine, so it's embarrassing that I missed it). That prevents my second step from going through. However, my intuition does not tell me whether his system is sound or not, but he will ...


0

Does the following proposal work? Please tell me what you think about the following modification of the calculus given in the question. If you find some mistakes, please tell me. The solution is a sound dealing with free variables. Definition. A sequent is an expression of the form $[V]\ \Gamma\vdash\phi$ where $V$ is a finite set of variables, $\Gamma$...


2

The easiest (and in my opinion cleanest) way to do this is to augment the context. In the sequent calculus you presented, you have the left-hand of the sequent being a set $Γ$ of formulae. Instead of that, you need to have set of sentences $S$ for axioms and a context chain $Q$. $Q$ is an ordered list, each item being either a conditional context or a ...


0

If you do the foundations of logic so that variant statements are identified (in my terminology I say they are the same as formulas because they in some sense have the same form), then all the generalization rules you need are those guaranteeing that $\forall x A$ is the infimum of the set of formulas $[t/x]A$, where $t$ ranges over the set of terms. I.e., ...


1

My intuition is that propositions without free variables are fully general, while a proposition with a free variable $x$ is a statement about a specific thing named $x$. For example, $\forall x : \text{IsRed}(x)$ means "everything is red", but $\text{IsRed(x)}$ means "the thing called $x$ is red". So suppose we already derived $\text{IsRound}(x) \vdash \...


3

Example Let $\Gamma$ the set of first-order Peano axioms: no variables free. 1) $\Gamma \vdash \exists x (x = 0)$ --- easily provable 2) $\Gamma, x=0 \vdash x=0$ --- obvious 3) $\Gamma \vdash x=0$ --- from 1) and 2) by $\exists$-elim : wrong ! 4) $\Gamma \vdash \forall x (x=0)$ --- from 3) by $\forall$-intro, 1) $\Gamma, x=0 \vdash x = 0$ 2) $\...


0

Instead of induction, rather following a similar argument to what you had, we get: $$x \in \left(\bigcup_{i\in I}B_i\right)^c \iff x \notin \bigcup_{i \in I}B_i\iff \forall i, x \notin B_i \iff \forall i, x \in B_i^c \iff x \in \bigcap_{i \in I}B_i^c $$ Even if you had an induction proof, I believe this is better because it holds for arbitrary set $I$ ...


0

Hint: "$x$ is not in all $B_i$" is equivalent to "there is some $i$ such that $x$ is not in $B_i$".


1

$\def\imp{\rightarrow}$Whoever wrote the 'solution' you ask about is wrong. The negation of a statement in first-order logic is always the statement that says exactly the opposite, so the negation of $p \imp q$ is always $p \land \neg q$. But for your second example: Take any $x,y \in \mathbb{Z}$. Prove that if $xy$ is odd, then $x$ and $y$ are odd. ...


3

The negation of of $p \rightarrow q$ is just $ p \wedge \neg q$ Thus the negation of $p\rightarrow(q \wedge r)$ is $p\wedge \neg (q \wedge r) $ In words this says that: The statement that it is false that $p$ implies that both $q$ and $r$ are true is equivalent to the statement that $p$ is true and one of $q$ and $r$ is false. The contrapositive of an ...


1

First, note that (II) is redundant since it's a theorem of the system (without using (I)). Here's a proof: $\big( A(x) \rightarrow B \big) \rightarrow \Big( \forall x A(x) \rightarrow \big( A(x) \rightarrow B \big) \Big) \qquad Ax1$ $\bigg( \big( A(x) \rightarrow B \big) \rightarrow \Big( \forall x A(x) \rightarrow \big( A(x) \rightarrow B \big) \Big) \...


0

Yes, the difference is exactly that the second statement is weaker than the first. $$\begin{array}{l}\forall x (A(x)\to B) ~\to~ (\exists x~A(x) ~\to~ B)\\(\exists x~A(x) ~\to~ B) ~\to~ (\forall x~A(x)~\to~B)\\\hline \forall x(A(x)~\to~B)~\to~(\forall x~A(x)~\to~B) \end{array}$$ Or in your tiny universe: $$\begin{array}{l}((A_1\to B)\wedge (A_2\to B)) ~\...


2

For each degree two vertex, if there exist a Hamiltonian cycle, will contain the two edges adjacent to the vertex. Since there are $k+1$ vertices of degree two of which none are adjacent, that means there will be $2k+2$ edges you must choose, but a Hamiltonian cycle in a graph of $2k+1$ vertices cannot have that many edges.


2

The question about generalized induction has been dealt with in the answer by Noah Schweber. Here is a quick non-induction proof of the desired inequality. Note that it works under conditions substantially more general than the conditions in the OP. For fixed exponent $x$, consider the function $f(t)=t^x$. Then by the Mean Value Theorem we have $$\frac{f(n)-...


3

While this can indeed be done, your described approach certainly isn't enough - here's a counterexample! Let $P(x_1, . . . , x_n)$ be the statement $$"x_1=x_2=...=x_n."$$ Then $P(1, . . . , 1)$ is true, and $P(x_1, . . . , x_n)$ implies $P(x_1+1, . . . , x_n+1)$, but clearly $P$ is not true in general. What's going on is that this scheme fails to take into ...


1

You have already gotten some good answers, I thought I could add something more of use which is not really an answer, but maybe good if you find differential entropy to be a strange concept. Since we can not store a real or continuous number exactly, entropy for continuous distributions conceptually mean something different than entropy for discrete ...


2

Notice that $\ln(\color{blue}{\sqrt{\color{black}{x}}}) = \ln(x^{\color{blue}{\frac{1}{2}}}) = \color{blue}{\frac{1}{2}}\ln(x)$ for all $x > 0$. Using this identity, let us re-write the maximum entropy, $\frac{1}{2} + \ln(\sqrt{2\pi}\sigma)$, as follows: $$ \begin{align} \frac{1}{2} + \ln(\sqrt{2\pi}\sigma) &= \frac{1}{2} + \ln(\color{blue}{\sqrt{\...


2

For continuous distribution like Normal/Gaussian we compute the differential entropy. You can find the derivation here http://www.biopsychology.org/norwich/isp/chap8.pdf For more info on differential entropy I recommend the book "Elements of Information Theory" by Cover and Thomas.


0

Expand into factorial polynomials and sum the telescoping series. $$\begin{align}\sum_{k=1}^nk(k+4)&=\sum_{k=1}^n\left[k(k+1)+3k\right]\\ &=\sum_{k=1}^n\left[\frac13k(k+1)(k+2)+\frac32k(k+1)-\frac13(k-1)k(k+1)-\frac32k(k-1)\right]\\ &=\frac13n(n+1)(n+2)+\frac32n(n+1)-\frac13(0)(1)(2)-\frac32(1)(0)\\ &=\frac16n(n+1)(2n+4+9)=\frac16n(n+1)(2n+13)...


0

Induction is usually straight forward: 1) n = 1 Does $1*5 = \frac 16*1*(1+1)*(2*1 + 13)$? Yep $5 = \frac 16 2*15 = 5$. So that's the initial step. 2) Suppose true for $n = k$ Does $1*5 + ..... + k(k+4) + (k+1)(k+5) = $ $\frac 16*k(k+1)(2k + 13) + (k+1)(k+5) = \frac 16*(k+1)(k+2)(2(k+1) + 13)$ $=\frac 16(k+1)(k+2)(2k + 15)$? So does $\frac 16*k(k+1)(...


2

A proof without induction: $$ \sum_{k=1}^{n}k(k+4)=\sum_{k=1}^{n}k^2+4\sum_{k=1}^{n}k= \frac{n(n+1)(2n+1)}{6}+4\cdot\frac{n(n+1)}{2} =\frac{n(n+1)}{6}(2n+13) $$


0

With induction, you want to prove a base case and then show that if it works for step $n$ then it also works for step $n+1$. If both of those things are true then you're done! Base case, $n=1$: $$ 1(1+4) = \frac{1}{6}1(1+1)(2(1)+13) $$ $$ 5 = 5 $$ Inductive step: We want to show $$ 1 \times 5 + ... + (n+1)((n+1)+4) = \frac{1}{6}(n+1)((n+1)+1)(2(n+1)+13)...


1

$$1 \times 5+2\times6+3\times7 +\cdots +n(n + 4) = $$ $$=\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}4i=\frac{n(n+1)(2n+1)}{6}+4\frac{n(n+1)}{2}$$


7

Base Case: For $n = 1$, we have: $$ 1 \times 5 = 5 = \frac{1}{6}(1)(1 + 1)(2(1) + 13) $$ which works. Inductive Hypothesis: Assume that the claim holds for $n' = n - 1$, where $n \geq 2$. It remains to show that the claim holds for $n' = n$. Indeed, observe that: \begin{align*} &1 \times 5 +\cdots + n(n + 4) & \\ &= [1 \times 5 + \cdots + (n - ...


2

[This is a partial answer, but I decided to post it anyway since no one else has answered for a long time now. Very interesting question by the way!] Note that if $T = PA + \neg Con(PA)$, then $T \vdash \neg Con(T)$ and hence $T_2$ is inconsistent and proves everything, so your hierarchy collapses. So it's not enough just to assume that $T$ contains $PA$. I ...


0

Like MathematicianByMistake I also feel that the word "rigorous" doesn't really capture the distinction you're drawing, but I can't discern your intent well enough to offer a substitute. My guess is that you really mean "quantitative", in the sense that you are concerned not just with the existence of $\delta$ but in knowing the largest possible value of $\...



Top 50 recent answers are included