Hot answers tagged

16

It's actually vastly easier to view proofs as trees in this context, so I'll do that. Generally, an "infinitely long proof" is more accurately a well-founded infinitely-branching tree (or something morally equivalent) - the idea being that we're working in some infinitary logic (or some logic of similar nature) where the basic deductive steps might involve ...


6

What about $p\lor q$? Since $q$ is false (by assumption) and $p$ is false (since $p\implies q$ and $q$ is false), $p\lor q$ is false. And if $r$ is true (as you acknowledged) but $p\lor q$ is false, then $r\implies(p\lor q)$ is false.


6

One: take $\{\varphi\}$ where $\varphi$ is a tautology (so deducible from $\emptyset$). If you don't like that, two: let $\varphi$ be any sentence at all, and consider $\{\varphi, \varphi\wedge(\varphi\vee\varphi)\}$. Or more generally any pair of distinct yet logically equivalent sentences. (Note that that's the only way you can get a set of size two with ...


5

Nope they're not the same. In general, the meaning changes when permuting different quantifiers (however $(\forall x\in A)(\forall y\in B)$ and $(\forall y\in B)(\forall x\in A)$ are the same, and same holds for $\exists$). To see why the two statements you gave have different meanings, start by translating them to English: the first one says "For every ...


5

Yup that's correct, with the exception that you should say "There exists an integer $n\ge 2$" instead of $n>2$. Edit: You pointed out in comments that $n=2$ satisfies the given statement. Your solution however is still not the negation of the given statement, rather a statement logically equivalent to the given statement in $(\mathbb N,+,\times)$. ...


5

Call $X = \{n \in \mathbb{N}| n < 0\}$ (yes, the negative natural numbers!). You can prove from the axioms of the natural numbers that there is no natural number $n$ such that $n+1=0$. So if $n<0$, then $n+1<1$ and $n+1\neq 0$, so $n+1 < 0$. So if $\exists n \in X$ then $X$ is infinite!


5

No, we cannot. For example, take $\mathcal{C}$ to be the class of all finite structures in our language, let $\varphi_n$ be the sentence asserting that there exist at least $n$ elements in the universe - that is, $\varphi_n$ is the sentence $$\exists x_1,..., x_n(\bigwedge_{1\le i<j\le n}\neg x_i=x_j),$$ which is clearly first-order - and let $\Sigma=\{\...


5

No we are not sure. So what? “Problems worthy of attack prove their worth by fighting back.” ― Piet Hein, Grooks 1


4

These two statements do not mean the same thing. Let $A,B = \mathbb{N}$. The first statement is true: for any $x \in \mathbb{N}$ we can take $y=x+1$. The second statement is false; there is no upper bound for the natural numbers.


4

Example: let $A=B= \mathbb R$ and $" \le "$ be the usual order on $ \mathbb R.$ If $x \in A$, then $y:=x+1 \in B$ and $x \le y.$ Hence we have $(\forall x \in A)(\exists y \in B)(x \le y)$. But $(\exists y \in B)(\forall x \in A)(x \le y)$ means that $ \mathbb R$ is bounded from above.


4

Here's a proof of the statement I created with openlogicproject.org. A good general practice when you want to prove things with implication like $A\to B$ is to assume $A$ as a hypothesis and see if you can prove $B$ from it. If so, then you can infer the implication.


3

Theoretically you can of course instantiate the variable with any variable-free terms, but in practice it makes sense to stick with terms that only use constants that already exist in its branch. This is because if you ever obtain an open branch every non-literal has either been decomposed, or is a universal that has been instantiated with every constant ...


3

Notice that the inductive step, like any inductive proof, assumes that 'The statement holds for $k$' .... i.e. (in this case) that with $k$ blue-eyed islanders, none of them leaves before day $k$, but they do all leave on day $k$. So, at this point we indeed don't know that it is true, but rather we just assume that it is true, and see what follows. Well, ...


3

The fact that there is a comma between "If berries are ripe along the trail" and the following phrase usually means that the sentence should be read as "If berries are ripe along the trail, then hiking is safe if and only if grizzly bears have not been seen in the area", where the consequent of the conditional is the whole sentence after "then". So, ...


3

If $p$ is not true, so $r$ is true. So, $q$ is true, because either $p$ or $q$ ($p\lor q$) is true when $r$ is.


3

$0$. If the set is empty, there is nothing to remove.


3

As you correctly say, you start your tableau with $\neg \Diamond(p \lor \neg p), 0\\ \Box \neg (p \lor \neg p), 0$ And that's where it already ends: In order to continue by disassembling $\Box$, you'd need to have a $0$-accessible world $1$ in your branch, $0r1$. This is what the rule in Priest's book states: $\Box A, i\\ irj\\ \downarrow\\ A, j$ ...


3

For starters, you could prove Peano's Fifth Axiom, a.k.a. the Axiom of Induction.


3

If $f(x)$ is continuous and differentiable, then, on a small enough scale it can be approximately a line. In which case $f(x+\delta) \approx f(x) + \delta f'(x)$ for small $\delta$ We could also invoke the mean value theorem. There exists a $c\in (a,b)$ such that $f'(c) = \frac {f(b) - f(a)}{b-a}$


3

How do these two interpretations relate to each-other? Going in the details would require a course in type theory, if you want to deepen your knowledge of the subject you should search reference on the Curry-Howard isomorphism. An intuitive not too precise explanation of the relation between these interpretations is the following. Generally to every ...


3

The "domain" is the class of all sets if you are working in the first-order theory of ZFC. Indeed, notation like $\forall x\in \mathbb R.P(x)$ in a set-theoretic context, is usually defined as shorthand for $\forall x.x\in\mathbb R \Rightarrow P(x)$. Here, again, the $\forall x$ is quantifying over every individual in our first-order theory. For ZFC, that ...


2

In the language of my first order logic text, $x,y,z$ are individual variables, not propositional variables. They don't represent truth values, they are merely arguments for the predicate variables that do return truth values. Perhaps it's clearer to write the sentence without the infix inequality symbols: $$\exists x,y,\neg(\neg Lxy\vee\exists z(Lxz\...


2

This question was recently asked and answered on MathOverflow. The result you're looking for is Proposition 4.3.28 in Marker's Model Theory: An Introduction.


2

$A=B=(0,1)$ is a counterexample.


2

You are right. In a more general sense: For every $x$, $A$ happens is negated by: There is an $x$ for which $A$ does not happen Therefore: For every $x$, there is $y$ such that $P(x,y)$ is true Is negated by: There is an $x$ such that $P(x,y)$ is false for every possible $y$


2

I assume statement 3) is supposed to be the conclusion? As such, this is called the Fallacy of Denying the Antecedent In this fallacy you typically go from $a \rightarrow b$ and $\neg a$ to $\neg b$, but it is easily understood that going from $\neg a \rightarrow \neg b$ and $a$ to $b$ is the same idea: you deny/oppose the antecedent (the 'íf'part of the ...


2

As Scientifica mentions in their answer, translating the logical statement to a sentence helps. If you can simplify the sentence towards more natural language, do so. Moreover, it is often instructive to to consider a special case. And even better, combine the two and write sentences about a special case. If $A=B=\mathbb N$, then the statements are: $(∀x∈A)...


2

All you are really using is the fact that if a number $x$ happens to be $0$ then $ax=0$ for every value of $a$. You can then apply that to show $x_n/2^m = 0$.


2

First, assume $p$ is true. Than $p \rightarrow q$ together with $p$ true forces $q$ to be true. Now assume $p$ is false so that $\lnot p$ is true. Then $\lnot p \rightarrow r$ forces $r$ to be true, which in turn (via $r \rightarrow (p \lor q)$) forces $p \lor q$ to be true. But in this branch of the analysis we're assuming that $p$ is false. If $p$ is ...


2

I understand we assume $q$ is false. Then in order for $p\to q$ to be true, $p$ must also be false. Then, in order for $(\lnot p) \to r $ to be true, $r$ must be true because $p$ is already false, so negating it would have it be true; thus $r$ must be true. But I don't understand the last one. $ r \to (p \lor q)$, we know $r$ is true, but what ...


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