# Tag Info

0

Actually, you don't need to use Contradiction Theorem! The following is a derivation of the formula $\lnot\exists x \, P(x) \to \forall x \, \lnot P(x)$ in first-order natural deduction without using the rules RAA (reductio ad absurdum) and EFQ (ex falso quodlibet): This means that the formula $\lnot \exists x \, P(x) \to \forall x \, \lnot P(x)$ is ...

0

$\quad\big(\exists x\; P(x) \big)\to Q \\\Updownarrow(\text{Use Implication Equivalence}) \\\quad \\\Updownarrow(\text{Use Quantifier Dual Negation}) \\\quad \\\Updownarrow(\text{Use Distribution of Universal over Disjunction; since$x$is not free in$Q$}) \\\quad \\\Updownarrow(\text{Use Implication equivalence}) \\\quad\forall x\;\big(P(x)\to Q\big)$

0

Your derivation is absolutely correct! There is no need for EFQ, the rules $\lor_I$ ($\lor$-introduction) and $\to_I$ ($\to$-introduction) that you have used in your derivation are sufficient to prove $P \to (Q \lor P)$. Remark: This means that $P \to (Q \lor P)$ is provable not only in classical and intuitionistic logic, but also in minimal logic.

-3

In proving programs correct ,some assertions are made of the format {P} Code {Q} where P and Q are Per and post conditions respectively. For example: { x is even } x = x+1 { x is even } Here pre condition and post condition are shown, by using these we can easily check our programs correctness.

3

Your first question has a simple answer — this ternary connective does the trick: $$\triangleright(A,B,C):=(A\Rightarrow(B\land C)).$$ In terms of this connective, we can define $$A\Rightarrow B:=\triangleright(A,A,B)$$ and then $$A\land B:=\triangleright(A\Rightarrow A,A,B).$$ Clearly, $\{\triangleright\}$ and $\{\Rightarrow,\land\}$ are ...

1

Revised edition We have to see : Saul Kripke, Semantical Analysis of Intuitionistic Logic I (1965), page 97-on, and : Melvin Fitting, Intuitionistic logic, Model theory and Forcing (1969), page 28-on. According to Kripke's explanation [page 99] : To assert $\lnot A$ intuitionistically in the situation $H$, we need to know at $H$ not only that ...

0

Computation-free approach: the condition $n \equiv 3 \pmod{6}$ implies $n^2 \equiv 9 \pmod{36}$, which is exactly what we need.

1

You’re missing part of the definition of a wqo: it must be a quasi-order, meaning that it must be reflexive and transitive. Equivalently, $\preceq$ is a wqo on $A$ iff it is a well-founded quasi-order with no infinite antichain. This means that a partial order with an infinite antichain is not a wqo even if it’s well-founded. For example, the order $\preceq$ ...

2

It means $\Gamma\vdash (\phi \Rightarrow \psi)$. The alternative reading, $$(\Gamma\vdash \phi) \Rightarrow \psi \tag{*}$$ is a conceptual mess: $\Gamma\vdash \phi$ is a statement of the metatheory, $\psi$ a formula of the theory, and (*) seems to be a formula of the theory — or wants to be one, or something — but it isn't. Re the reverse implication part ...

1

Assume $2^k\geq k^2$. Then $2^{k+1}\geq 2k^2$. If you can show $2k^2\geq (k+1)^2=k^2+2k+1$ for $k\geq 4$, you are done. $2k^2\geq k^2+2k+1$ iff $0\geq -k^2+2k+1$, which is true for $k\geq 4$ (parabola opening downward with largest root $<4$).

1

To prove the induction step, you first need to show $\phi_n\rightarrow \phi_1$. In your proof you directly used it but that would be incorrect you have to prove it although the proof is simple: $\phi_n\rightarrow \phi_{n+1}$ and $\phi_{n+1}\rightarrow \phi_1$ implies $\phi_n\rightarrow \phi_1$. Now we can use our induction hypothesis to conclude that ...

2

What $n\equiv3 \pmod6$ means is that $\exists k\in \mathbb{Z}$ such that $n=6k+3$. We need to prove that $36\mid(n^2+27)$ so plugging in $6k+3$ for $n$ we get $$(6k+3)^2+27=36k^2+36k+36$$ This is divisible by $36$.

2

Hint: You actually don't know that $n$ doesn't divide $6,$ for example $n=3$ satisfies your assumption. However you do know that there is an integer $k$ for which $n=6k+3.$ Now substitute that into $n^2+27$ and expand, and see what it looks like.

6

$x (1-x) = \frac 14 - (x - \frac 12)^2 \le \frac 14$ holds for all $x \in \mathbb R$. (Alternatively, use the GM-AM inequality, or visualize $y = x(1-x)$ as a parabola with vertex at $(\frac 12, \frac 14)$.) Then from $$a(1-b) \cdot b (1-c) \cdot c (1-a) = a(1-a) \cdot b (1-b) \cdot c (1-c) \le \frac 14 \cdot \frac 14 \cdot \frac 14$$ it follows that at ...

0

Hint: show the sum $a(1-b) + b(1-c) + c(1-a) \leq 3/4$.

1

Using analysis: define $f(x)=x^3+x$. Since $f'(x)=3x^2+1>0$, the function is strictly increasing, hence, injective, and the result follows.

0

If you have calculus, you can conclude this is impossible as follows, since $lim_{x, y \to \infty}x^2+xy+y^2=\infty$, there is a point where the minima is achieved. This point has vanishing partial derivatives, thus $\partial_x(x^2+xy+y^2)=2x+y=0$ and likewise $2y+x=0$, so $x=-2y=4x$ so $x=0$ and likewise $y=0$, so $x=y=0$, and we have a contridiction since ...

5

$$a^3+a=b^3+b\iff a^3-b^3=b-a$$ $$\iff (a-b)\left(a^2+ab+b^2\right)=b-a$$ If $a=b$, then we're done. For contradiction, assume $a\neq b$. Then $a-b\neq 0$ and we can divide both sides by $a-b$: $$a^2+ab+b^2=-1\iff 4a^2+4ab+4b^2=-4$$ $$\iff (2a+b)^2+3b^2=-4,$$ contradiction, because $(2a+b)^2+3b^2\ge 0$ for all $a,b\in\Bbb R$.

0

I use Polish notation. The formation rules run: All lower case letters of the Latin alphabet, and 0 qualify as well-formed formulas (wffs). If $\alpha$ and $\beta$ qualify as wffs, then so do N$\alpha$, C$\alpha$$\beta, K\alpha$$\beta$, and A$\alpha$$\beta. The axiom schemes are: CAppp a law of Clavius CpKpp a law of K-tautology introduction CpApq ... 2 You can prove$$\psi\land \chi \to \psi\land\chi$$by going through (\psi\land\chi)\land(\psi\land\chi). Now apply rule 10 to get$$ \psi \to (\chi\to\psi\land\chi) $$Then your assumed derivations of \psi and \chi, plus modus ponens twice concludes \psi\land \chi. 0 24=7.2+5.2....25=5.5....26=5.1+7.3....27=7.1+5.4....28=4.7....Now if n>29 we have n=5 x+y where y\in \{24,25,26,27,28\} and x\in Z^+. Since y=5A+7B for some non-negative integers A,B, we have n=5(A+x)+7 B. 2 Actually, it is possible using induction. Notice that 1 = 3\times 5 - 2\times 7 = -4\times 5 + 3\times 7. So, suppose that n\ge 24, with n = 5p + 7q for p,q\in\mathbb{N}. Then you just have to show that we can pick (p,q) such that either$$q\ge 2$$so that we can add 3\times 5 - 2\times 7 and get n+1 = 5(p+3) + 7(q-2), or that$$p\ge 4$$so ... 1 Yes, your intuition is correct. The precise way to formulate (and prove) your claim is that the principle of induction is equivalent to the well-ordering principle or$\mathbb N$, namely that every non-empty subset of the naturals has a smallest element. The proof is not at all hard. 2 Yes, if you prove something by showing that a minimal counterexample would necessarily lead to an even smaller counterexample (and so, contradiction), that is the same thing as the induction principle. Often the same proof can easily be framed as an induction proof or as a minimal counterexample proof. However, it does also happen that one of the two is a ... 2$(n+1)^3-(n+1)$comes from the expression$n^3-n$when you replace$n$with$n+1$. This is the induction step - to show that$(n+1)^3-(n+1)$is divisable by$3$if we assume that$n^3-n$is. Here the following happens:$n^3-n$is divisable by$3$(by the inductive assumption),$3n^2$is divisable,$3n$is divisable, therefore, their sum$n^3-n+3n^2+3n$is ... 3$P(n+1)$is the statement that$(n+1)^3 - (n+1)$is divisible by 3. Just fill in$n+1$in$P(n)$. So you have to simplify this expression first. The equality between 2 and 3 is just algebra (you write$2n$from the second term as$3n - n$, which is true for all$n$). Why would you do this? Because you want to use your assumption that$P(n)$is true, which ... 1 Induction is in fact the way to do this; we induct on the number of elements in the set. The empty set is trivially well-ordered; any set containing exactly one real is well-ordered (if the set is$\{x\}$, the order is$x \leq x$, and that's a well-order). Now, suppose we have a set$\{ r_1, r_2, \dots, r_n \}$, which are in ascending order. What is it for ... 2 Your answer is good. If there was the added condition that$f$is continuous at$x=0$, then you could conclude that$f$is decreasing on all of$\mathbb R$. You'd only have to prove that$f(y)>f(0)$when$y<0\$.

Top 50 recent answers are included