New answers tagged

0

You're right that you overlooked something. If $p,q$ are jointly inconsistent, then it cannot be that $p \land (p \to q)$ is consistent, otherwise it would entail $p \land q$ by conjunction elimination and modus ponens, which is by assumption inconsistent. Therefore you cannot to derive a contradiction via Plantinga's method.


1

Here's an amusing way: Your contributions have quickened the completion of the wall by XXX minutes/hours/days. You can compute this based on the rates at which that one person and all the other people are contributing, but he/she won't be able to figure out the final goal without knowing the total rate of others' contribution. Presumably this is not ...


0

Actually you've a good skill that you can use to your advantage. I always think of mathematical theorems as having two parts, the logical part and the structural part. Your ability to systematically perform symbol-pushing (using valid inference rules of course) means that you'll have no trouble with the logical part, which is often half the problem solved. ...


0

My opinion is that in the ultimate form of understanding, "logical reasoning by means of syntactical rules" and "contentual reasoning" are the same thing. In the beginning, there is a disconnect. You see syntax, but have not yet learned the point. You have ideas about how the subject works, but have not yet learned how to apply those ideas to answer ...


0

For $n=0$, the result is clear. For positive integer $n$, since $n\geq 1$, it is concluded that $n\times n\geq n\times 1=n$. For negative integer $n$, since $n^2\geq 0$ and $n\leq 0$, the result is clear.


2

Your confusing stems from the way many articles about Godel's incompleteness theorems are extremely imprecise. Here is a proper definition. $\def\nn{\mathbb{N}}$ We say that a sentence $φ$ over a language $L$ is true in an $L$-structure $M$ iff $M \vDash φ$. For convenience, when $L$ is the language of arithmetic, we say that $φ$ is true iff $\nn \...


0

The problem is that your assumption is false, when $A$ is simply PA (due to Godel's incompleteness theorem) and so you can deduce everything. In particular, your hypothetical algorithm will both halt and not halt. On the other hand, you don't need your hypothetical algorithm at all, if all you want is to list out all theorems provable from $A$. Simply go ...


4

The statement "$n$th-order arithmetic is consistent" is expressible in first-order arithmetic, but not provable in $n$th-order arithmetic; and this is true for every $n$ (EDIT: and provable in $(n+1)$th order arithmetic, as per Carl's comment). We can similarly leap outside finite-order arithmetic in this way. A more natural example: The statement "There is ...


0

As is convenient in discussions of the completeness theorems, let's focus on the theory of arithmetic over the natural numbers. We have a well-defined notion of truth in the natural numbers under the usual arithmetic operations: e.g., the sentence $\forall i\cdot \exists a, b, c\cdot \ a > i \land a^2 + b^2 = c^2$ asserts the existence of arbitrarily ...


0

Question 1: Variables must be bound because we don't work with open sentences in proof systems, yet it is possible to assign a truth value to open sentences. The truth value of an open sentence $A$ with an free variable $x$ is true if and only if the value of its closure $\forall x A$ is true. Question 2: The difference between axiom 4 in FOL1 and FOL2 ...


0

Deductive reasoning has the soundness property, which states that "from true sentences and valid inference rules only true statements are derived", however it doesn't state that "from false statements and valid inference rules only false statements are derived", because soundness preserves only truth but not falsity. Therefore it is possible that you derive ...


0

Actually $$ \frac{1}{\sqrt{m+1}} \lt\ 2\sqrt {m+1} - 2\sqrt m \lt\ \frac{1}{\sqrt{m}}$$ because $$ 2\sqrt {m+1} - 2\sqrt m = \frac{2}{\sqrt {m+1} + \sqrt m} $$ and $$ \frac{1}{\sqrt{m+1}} \lt\ \frac{2}{\sqrt {m+1} + \sqrt m} \lt\ \frac{1}{\sqrt{m}}$$


-1

Assuming your formal system is consistent, Gödel shows there is a statement in that system whose interpretation is true but that is unprovable in the system. The statement is actually provable, but not in that system: you need the additional assumption that the system in consistent, and that is not provable in the system (unless the system happens to be ...


0

You didn't get the true proposition from the false one. It would be kind of like saying $2 < 1$ is not true but $1 < 3$ is true so $2 < 3$ is true. You didn't get it from $2 < 1 < 3$. It exists as its own statement.


1

This is essentially what you are doing: (a) $2 < 1$ is false. (b) $1 < 1000$ is true. From (a) and (b) we get $2 < 1 < 1000$ which is nonsense/false. We cut away the failing middle part and are left with $2 < 1000$ which is true.


1

The step is valid. Simplifying a little bit the case, we have to show that: if $\Gamma \vDash \mathcal C(d) \to \mathcal B$, then $\Gamma \vDash \mathcal C(z) \to \mathcal B$, provided that we have proved $\exists x \mathcal \ C(x)$. Assume not, i.e. that we have an interpretation $M$ with domain $D$ and a sequence $s$ such that : $M \vDash \...


2

What is actually important is the local property that every wff arises in exactly one of the ways $(\neg A)$ $(A\to B)$ $(A\lor B)$ $(A\land B)$ atomic formula, of such-and-such particular shapes themselves and within each group from only one combination of $A$ and $B$. This local property is crucial for being sure that we can define properties of ...


0

First, the easy answer is that any proposition which gives you a mixture of true and false as your result will be neither a tautology (which requires that the end result is always true) or a contradiction (which requires that the end result is always false.) So it is simple to give a counter-example: say,p, as Stefan suggested, or p implies q or ......lots. ...


0

This is Modus Tellens. By truth table we could be able to see that the row in both $\neg q$ and $p\rightarrow q$ columns we have True(T), then we can conclude that this argument is valid. The argument is valid.


0

With Natural Deduction, we need LEM or the equivalent DN, because the formula is not intuitionistically valid. 1) $B$ --- assumed [a] 2) $B \lor \lnot B$ --- by $\lor$-intro 3) $\lnot (B \lor \lnot B)$ --- assumed [b] 4) $\bot$ --- contradiction: 2) and 3) 5) $\lnot B$ --- by $\lnot$-intro, discharging [a] 6) $B \lor \lnot B$ --- by $\lor$-intro 7) $\...


2

The bottom line is that a statement cannot have unambiguous meaning unless you have a precise unambiguous way of interpreting (reading) it. Even in natural language almost all sentences have unambiguous grammatical structure and more or less clear semantic interpretation, which is not an accident, because otherwise it would fail to be a viable means of ...


0

$X \rightarrow Y$ is false if and only if $X$ is true and $Y$ is false. Thus, if $B$ is true, then $A \rightarrow B$ is true and your statement is true. On the other hand, if $B$ is false, then $B \rightarrow C$ is true and your statement is true. So the theorem is true. See also: https://en.wikipedia.org/wiki/Material_conditional#Truth_table In logical ...


1

If we didn't have unique readability, then the language would be useless - we wouldn't be able to say that a sentence is "true" or "false". We could have a sentence that was true under one reading, but not under the other. A formal language is to natural language what arithmetic is to counting - an abstraction that's supposed to make things clearer. Imagine ...


0

The answer you're probably looking for has been applied in programming languages for a long long time now. The basic idea is that in a program you can declare a new variable anywhere, and it is only visible in its scope, unless it is shadowed. So if you declare a new variable inside a for-loop it is only accessible within the for-loop and becomes ...


0

This is the maximum satisfiability problem (MAX-SAT): Source: A. Biere, M. Heule, H. van Maaren, Handbook of Satisfiability, IOS Press, 2009.


1

If the language has the symbols $\top$ (verum) and $\bot$ (falsum), they are $0$-ary conncetives and thus also formulas. If so, the definition of formula is [see: Dirk van Dalen, Logic and Structure (5th ed - 2013), page 57]: Definition 3.3.2 FORM [the set of formulas] is the smallest set $X$ with the properties: (i) $\bot$ [$\top $ is simply $...


1

In Set Theory an $n$-ary relation on a set $S$ is some (any) subset of $S^n.$ And an $n$-ary function on $S$ is a function from $S^n$ into $S.$ In Model Theory an $n$-ary relation and $n$-ary function symbols are arbitrary objects that are "interpreted" by a model $\mathbb M=(M,...)$ as $n$-ary relations and $n$-ary functions on $M.$ The "..." in $\mathbb ...


1

Just think of a relation as a collection of ordered $m$-tuples. Items $a1$, $a2$, ..., $am$ are related under the $m$-place relation R iff the tuple ($a1$, $a2$, ..., $am$) is in R. [they don't have to be related 'under some operation' to be related] For example, there is the 3-place relation which I will call $Pyth()$ : the numeric triplet ($a$,$b$,$c$) ...


2

They're symbols that are intended to denote such functions and relations; they're not functions or relations themselves.


1

Your grasp of these 'proof techniques' is roughly correct, though there are indeed clearer ways of understanding the difference between them. 'Indirect proofs' included not only 'proof by cases' but also 'proof by contradiction' and 'proof by contrapositive'. But I'll focus on the distinction between 'proof by cases' and 'proof without cases'. A 'proof by ...


1

You would need to specify your meta-system, before you can formalize a meta-theoretic statement. Conventionally logicians use some conservative extension of ZFC as their meta-system. Within ZFC one can consider any first-order language and collection of sentences (encoded in some way) over it, and ask whether there is a model, which is defined as a tuple ...


7

Use the definition of subset ($A\subseteq B$ if $x\in A$ implies $x\in B$) and the definition of intersection. Let $x\in X\cap Y$. Then $x\in X$ (and $x\in Y$) by the definition of intersection.


2

We show informally that there is an algorithm which will decide, on input a sentence $\varphi$ of our language, whether or not $\varphi$ is a theorem of $T$. We will assume that $T$ is finitely axiomatized. By the Completeness Theorem, $\varphi$ is a theorem of $T$ if and only if $\varphi$ is true in all models of $T$. Algorithm $1$ checks, one by one, ...


1

This answer relates to the following clarified question from the OP in comments: But how can we prove a statement is not self-referential? And even if we can, how can we prove a given statement is not some other type of statement (like self-referential) that also doesn't work under LEM (a new type that would should ban too)? Sounds like all we can do is ...


1

A "word" is many things. Consider this example: It is what it is. How many words are in that sentence? In one sense, there are five words: the first "it", the first "is", the "what", the second "it", and the second "is". So in that sense there are two "it"s, two "is"s, and one "what". In another sense, there are three words: "it", "is", and "what". ...


0

Pick two conditions, say, $k$ and $l$ where $k<l$. Then $k\implies k+1\implies...\implies l-1\implies l$, so $k\implies l$. Further, $l\implies l+1\implies ...\implies n-1 \implies n\implies 1\implies...\implies k$, so $l \implies k$. Thus, $k\iff l$ for any two conditions $k$ and $l$.


1

In my answer I'm assuming that you also have $0 \in A$ and that $A$ is a set of natural numbers. Otherwise as celtschk said in a comment your proof is invalid since it could be that $A$ contains things besides natural numbers. The logical flaws in your proof are: $\def\nn{\mathbb{N}}$ You claimed that $0 \in B$. This would require $0 \in A$ by definition, ...


3

Epstein is exposing an anti-platonist point of view; see page 2: There are other views of what propositions are. Some say that what is true or false is not the sentence, but the meaning or thought expressed by the sentence. Thus ‘Ralph is a dog’ is not a proposition; it expresses one, the very same one expressed by ‘Ralph is a domestic canine’. ...


1

As a child, I learned logic with the book "The Game of Logic", by Lewis Carroll. This does not use the modern symbols, but I think that it is a great book to introduce the basic concepts.


0

Yes, there has been an enormous amount of work on this. See the article Axiomatic Theories of Truth in the Stanford Encyclopedia of Philosophy for a starting point. As another answer points out, in mathematical logic we can often avoid the notion of "truth" simpliciter, and only talk about "truth in a model". This is not the case in philosophy, where the ...


3

In first-order logic one can make sense of what it means for a statement to be true with respect to some model. For example, there is a theory $T$ of groups, and a language of groups, and models of $T$ are groups. In any group $G$ one can ask whether a particular statement in the language of groups (for example, "for all $g, h$, it's true that $gh = hg$") is ...


1

The point is that in the meta-system you know whether or not a theory $T$ is consistent (otherwise the meta-system is too weak to be a useful meta-system). If it is consistent, then the collection of all provable sentences over $T$ is already the minimal set satisfying your constraints, so there is no reason to introduce your new notion since it is simply $\{...


-1

Let $ P(x) $ denote the property that $x$ is a pet in the house , and let $C(x)$ and $D(x)$ be the properties that $x$ is a cat or dog respectively, then your sentences translate to $$ \forall x (P(x) \to (C(x) \lor D(x)))$$ and $$ \to \exists y(P(y) \land(C(y) \lor D(y))) $$


1

For olympiads Number Theory this is a must-"Number Theory-Andrescu Titu"-https://blngcc.files.wordpress.com/2008/11/andreescu-andrica-problems-on-number-theory.pdf And for Geometry this one-"Coxeter-Geometry Revisited"-http://www.aproged.pt/biblioteca/geometryrevisited_coxetergreitzer.pdf I have another good book,but I have no idea if it's available ...


1

Your underlying question is philosophical, but that's fine; logic is just as much philosophy as it is mathematics. Let me state your question: How do we know that LEM is always valid? The only reasonable answer to this is that there is only one reality, and when we consider totally precise and unambiguous statements about this reality, it is ...


1

Edit: I actually read more of the source and see now that the author addressed this three paragraphs later " Viewed the other way around, to see that two non-identical terms are not the same, we just strip away occurrences of s from each term till one of the two terms becomes 0 and the other one is not 0. By the second axiom, these are not the same, and so ...


2

There is no error here. The book is asserting that these axioms are enough to determine whether any two particular natural numbers (of the form $s(s(\dots (s(0))\dots))$) are the same, as it explains after stating the definition. It is not attempting to write down every single true statement about the "same" relation. It is indeed true that the reverse ...


1

@Peter Smith wrote: So it is worth noting that e.g. John Corcoran can write "Three Logical Theories" as late as 1969 (Philosophy of Science, Vol. 36, No. 2 (Jun., 1969), pp. 153-177), finding it still novel and necessary to stress the distinctions between different types of logical theory. Here it is https://www.academia.edu/9855795/Three_logical_theories


2

In Resolution the "square" symbol : $\square$ is usually used to denote the empty clause, i.e. a contradiction. The empty clause is always false; thus, the symbol: $T \vDash \square$ means that the theory $T$ is unsatisfiable. If so, $KB ∧ B ⊭ \square$ must mean that the Knowledge base $KB$ plus the set of facts $B$ is satisfiable.


1

The sequence $(a_n)$ grows much faster than the Busy Beaver numbers. For example, not only the Busy Beaver sequence $BB(n)$ but also expressions like $BB(BB(n))$ and $\underbrace{BB(\cdots(BB(}_{n\text{ times}}n)))$ are definable in PA with formulas of length not much longer than the length of the smallest formula defining $n$ (in particular, with length ...



Top 50 recent answers are included