Tag Info

New answers tagged

3

Hypothesis: "$n$ is a positive integer" Conclusion: "the sum $1+2+\cdots+n$ equals $\frac{n(n+1)}{2}$" and the given statement is: if hypothesis then conclusion.


0

Actually, you swapped it. The hypothesis is what you already know what is true. The conclusion is what you want to prove. Then: hypothesis: The $n$ items are the first $n$ positive integers. conclusion: Their sum is $n(n+1)/2$.


1

I think a lot of theorems could be stated in such a way as to fulfil the requirements, e.g., $x^n+y^n=z^n$ has a solution in positive integers if and only if $n\le2$; the Riemann zeta function has infinitely many zeros with real part $s$ if and only if $s=1/2$ (OK, the "only if" part may not be a theorem just yet); there is a sporadic simple group of order ...


2

Every statement can be proved or disproved. If $\varphi$ is a statement which is always true (e.g. $\forall x(x=x)$), then it is always provable, if its negation is always provable -- then $\varphi$ is always disprovable. Otherwise, $\{\varphi\}$ proves $\varphi$ and $\{\lnot\varphi\}$ disproves $\varphi$. So every statement is either always true, or ...


1

I would not step to the esoteric or psychological level here. Let me introduce an easy example of two obviously equivalent statements: $\forall x Rx$ holds if and only if $(\exists x Px \lor \forall x\neg Px)\rightarrow \forall x Rx$, so $$\forall x Rx \leftrightarrow((\exists x Px \lor \forall x\neg Px)\rightarrow \forall x Rx)$$ is a tautology. But see ...


4

See the Wikipedia pages List of statements undecidable in ZFC and List of undecidable problems. Note that the lists are different in flavor, e.g. compare Independence and Undecidable problem. Other examples of statements whos truth can't be determined are wrong ones. Also note that "theorem" is a technical term in the context of formal logic and here I would ...


0

Remember that: $(a\implies b) \equiv (\neg a \lor b)$ Hence: $\therefore \neg (a\implies b) \equiv (a \land \neg b)$ The counter example of the implication is an event where $a$ happens and not $b$. ${\begin{array}{|c|c|c|c|}\hline a & b & a\to b & a \land \neg b \\ \hline\hline F & F & T & F \\\hline F & T & T & F \\ ...


2

You can disprove the statement $a \implies \sim b$ using a counterexample if you can find one. However, this does not prove the statement $a \implies b$. This is because the negation of $a \implies \sim b$ isn't $a \implies b$. Recall that the negation of an implication is not an implication. $\sim (a \implies b) \equiv a \wedge \sim b$. In words, this ...


3

Instead of having both $A$, $B$, $a$ and $b$, let's make some of them $p$ and $q$. Also, since you're talking about counterexamples, there must be a quantifier somewhere, so I guess you actually mean something like $$ A \equiv \forall x\,(p(x)\to q(x)) $$ $$ B \equiv \forall x\,(p(x)\to \neg q(x)) $$ Having a counterexample to $A$ means that we have a ...


1

Fermat's Little Theorem was originally proved by Euler in 1736 by proving the more general case $a^{\phi(n)} \equiv 1\pmod{n}$. However, today's typical proof of Fermat's Little Theorem is proved using abstract algebra, which provides a proof simpler and more direct than Euler's proof. Source: http://en.wikipedia.org/wiki/Fermats_little_theorem


3

Are there any nice examples of "old" complicated proofs that become much simpler after new math is discovered years later ? Yes. Ruffini proved that quintics and higher polynomials cannot be solved by radicals in the general case, as is the case for those of inferior degree. Though there was nothing mathematically wrong with his proof, it did have the ...


0

There is hope that techniques developed in classifying saturated fusion systems will yield results in group theory that will streamline the classification of finite simple groups.


0

I'd say this proof is more easily understood if you generalize it by replacing $\bot$ with an arbitrary proposition $C$: $$\left((A\Rightarrow C)\land (B\Rightarrow C)\right)\Rightarrow \left((A\lor B)\Rightarrow C\right)$$ But this is just the elimination rule for $\lor$ in disguise in natural deduction: $$\underline{\Gamma\vdash A\lor B \quad ...


0

Assuming I understand it correctly, computer science (denotational semantics?) deals with this by using total functions to represent partial functions. We define a distinguished element $\bot$ meaning undefined (usually pronounced "bottom"). Given a partial function $f:A \nrightarrow B$ we can represent it with a total function $f^{\prime}:A \rightarrow ...


1

I'm not sure to understand the statement of your problem; so I try to interpret it as : Consider a theory $T$ in first order logic, and a formula $C$ such that all formulae in $T$ nor $C$ contain $\exists$. Does always exist a proof of $C$ from $T$ that do not invoke $∃$-introduction? I do not know if you are considering specifically natural deduction, ...


0

In classical logic, you can trivially proof the low of the excluded middle (it is an axiom). However, in intuitionistic (no law of excluded middle) predicate logic, you can only proof this for certain types of formulas, e.g. quantifier-free ones. So yes, there should be statements which do not have a constructive proof. Example: $\vdash \forall x P(x) \lor ...


6

About the final sentence: If the Goedel number, in some model, of a proof of a contradiction were a standard natural number, then it would encode an actual proof of a contradiction. But there is no actual proof of a contradiction in $T$ because, by hypothesis, $T$ has a model. About assuming that $T$ has a nonstandard model: That assumption could be ...


0

Well, I guess that "particular property" is just a placeholder for the properties that follow in the same Wikipedia page: Expressive Completeness Functional Completeness Semantical Completeness Strong Completeness Refutation-Completeness ... The definition must, in my opinion, be understood with respect to the section that follows. To my knowledge, ...



Top 50 recent answers are included