Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

4
votes
2answers
393 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
2
votes
1answer
683 views

Is saying 'This statement is true' a logically valid statement?

I understand how 'This statement is false' is not logically valid, but what about 'This statement is true'? I've always heard self-referential statements are not logically sound, but I can't really ...
1
vote
1answer
35 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y \...
0
votes
2answers
84 views

Show that $ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $ is, in general, NOT a theorem.

Show that $$ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $$ is, in general, NOT a theorem. My answer: First, I got the abstraction of the formula which is $ p \rightarrow A \lor q$ then ...
1
vote
1answer
113 views

Do all contradictory statements entail something self-referential?

"The house is all blue(B), and the house is all white(W)" Those statements are, ostensibly, not of the form p ⋀ ¬p. However, they do seem to entail p ⋀ ¬p. For example "The house is all blue" entails ...
1
vote
1answer
33 views

Can covering be done on two elements?

The covering rule is: $$B \bullet (B+C) = B$$ and $$B+(B \bullet C)=B$$ So does it follow from this rule that: $$B \bullet A \bullet \bar{C} + B \bullet D \bullet\bar{F} = B \bullet (A\bullet\bar{C}+D\...
2
votes
1answer
1k views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
1
vote
2answers
96 views

How to find the Equivalence class for a given set?

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and I'...
3
votes
2answers
170 views

If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
2
votes
2answers
101 views

What does it mean for a set of sentences $\mathcal{T}$ to “secure” a set of sentences $\Delta$?

I know the standard interpretation is: $\mathcal{T}$ secures $\Delta$ iff every interpretation that makes all members of $\mathcal{T}$ true makes at least one member of $\Delta$ true. ...
0
votes
1answer
78 views

Give an equational proof $ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$

Give an equational proof $$ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$$ I don't know where to start. Maybe I could start with $ (\forall x)(A \...
3
votes
2answers
223 views

Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
1
vote
1answer
146 views

First order logic tableaux with multiple quantifiers

I find very confusing to understand how combined qualifiers might expand on a tableaux. While for $\exists x\ p(x)$, I would just create a new term, a, and for $\forall x\ p(x)$ I would use an ...
3
votes
3answers
258 views

General Strategy for Derivations in Propositional Logic

In Propositional Logic, one is often tasked with showing that some particular formula is a theorem of a given deductive system, i.e. $\emptyset \vdash \psi$. These formulas can look very simple and ...
1
vote
1answer
75 views

What exactly does $\vdash_T G_T \leftrightarrow \lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ mean?

To me this translates to: $G_T$ is provable in $T$ if and only if there doesn't exist a $y$ such that $y$ is a witness to the provability of $\ulcorner G_T \urcorner$. But I'm not entirely sure what ...
1
vote
1answer
48 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la Curry,...
2
votes
2answers
80 views

Give a Hilbert-style proof $ \vdash ( x=y \rightarrow y = x) $

Give a Hilbert-style proof $$ \vdash ( x=y \rightarrow y = x) $$ I don't know where to start. I thought maybe I can use Ax5 (Identity axiom) $ x = x $ as a starting point. See George Tourlakis, ...
3
votes
1answer
70 views

Give an equational proof $ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $

Give an equational proof $$ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $$ What I tried $(\exists x)(A \lor B)$ Applying Definition of $\exists$ $\lnot (\forall x)\...
51
votes
8answers
5k views

Is it possible that “A counter-example exists but it cannot be found”

Then otherwise the sentence "It is not possible for someone to find a counter-example" would be a proof. I mean, are there some hypotheses that are false but the counter-example is somewhere we ...
0
votes
1answer
97 views

Implication or Bidirectional in “x is a Prime”

I have a question regarding First Order Logic. I have to express the property "x is a Prime" in First Order logic. So far I have the following solution: $\forall x\;Prime(x) \leftrightarrow \neg \...
0
votes
1answer
45 views

Why $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology?

Let $c$ be a new constant symbol in the language. Then $[\forall x \neg \alpha \rightarrow \neg \alpha^{x}_{c}] \longrightarrow [\alpha^{x}_{c} \rightarrow \exists x \alpha]$ is a tautology. This ...
1
vote
1answer
63 views

Give an equational proof $ \vdash (p \lor \lnot r) \rightarrow (p \lor q) \equiv \lnot q \rightarrow (r \lor p)$

Give an equational proof $$ \vdash (p \lor \lnot r) \rightarrow (p \lor q) \equiv \lnot q \rightarrow (r \lor p)$$ What I tried $(p \lor \lnot r) \rightarrow (p \lor q)$ Applying De morgan ...
0
votes
0answers
61 views

Poisson process: Has my book used a necessary condition, when it should have used a sufficient condition?

My book says that if we know that if we are viewing a poisson process with length $t$, and know that $n$ events happened in that interval, than the time that any of those events happened is uniformly ...
3
votes
1answer
152 views

Equivalence of Deductive System $L_0$ and the Sequent Calculus

Let $\mathcal{L}_0=\mathcal{L}[\{\neg, \rightarrow\}]$. Define the system $L_0$ as follows: An axiom of $L_0$ is any formula of $\mathcal{L}_0$ of the form (A1) $(\alpha \rightarrow ( \beta \...
4
votes
1answer
116 views

In Whitehead and Russell's PM, are overlapping ranges of significance necessarily identical?

In Principia Mathematica summary of ✳63 In virtue of ✳20.8, we have $\vdash : \phi a ∨ \sim\phi a . ⊃ . \hat{x}(\phi x \vee \sim \phi x ) =t‘a$ i.e. if "$\phi a$" is significant, then ...
1
vote
2answers
85 views

Construct the truth table?

Any body help me .. How to solve this? (i) $(p\land q)\to (p \leftrightarrow (q \lor r))$ (ii) $(p \leftrightarrow q) \leftrightarrow ((p\land q) \lor (\neg q \land \neg p))$ (iii) $(...
2
votes
2answers
454 views

How to write negation of statements?

How to write negation of following statements in words? ...
1
vote
1answer
175 views

Why exactly are NAND and NOR the only universal binary logic functions?

We know there are 16 possible binary logic functions: ...
2
votes
0answers
122 views

Simplify Product of Sums

Similar question to: Boolean Algebra - Product of Sums I was given a truth table and asked to give the sums-of-products and the product-of-sums expressions. I reduced the sums-of-products ...
3
votes
6answers
919 views

Question about the Continuum Hypothesis

The Continuum Hypothesis hypothesises There is no set whose cardinality is strictly between that of the integers and the real numbers. Clearly this is either true or false - there either exists ...
1
vote
1answer
417 views

How does one avoid circular reasoning? [closed]

How can you be reasonably assured that you are not engaging in circular reasoning when you invoke a theorem, lemma, etc.? For instance, what if you accidentally "prove" a theorem using a consequence ...
-3
votes
1answer
68 views

Give an equational proof $ \vdash p \land (q \equiv p) \equiv p \land q $

Give an equational proof of $$ \vdash p \land (q \equiv p) \equiv p \land q $$ How can I give equational proof for this formula ? See George Tourlakis, Mathematical Logic (2008) or this post for a ...
1
vote
1answer
117 views

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema?

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema ? If you think 'yes', then give a proof. If you think 'no', construct a counter model ...
1
vote
1answer
306 views

What is “Standardizing variables” in the procedure of converting First Order Logic to CNF?

What is meant by the step "Standardize variables" in the procedure of converting First Order Logic to CNF? The 6 all steps can be listed as, ...
1
vote
1answer
295 views

Converting statements with term 'only' and 'any' to predicate logic

How to convert following statement into predicate logic? 1)"Only dogs are mammals" 2)"Any dog is a mammal" Is there a difference between "Any dog is a mammal" ...
6
votes
2answers
235 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
1
vote
1answer
292 views

Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...
1
vote
1answer
465 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that $(...
2
votes
2answers
478 views

What is the formal proof for distributive law, from the other side of the equation?

How does one prove that (P ∨ Q) ∧ (P ∨ R) ⊢ P ∨ (Q ∧ R) Is this a well formed proof? ...
0
votes
6answers
97 views

Why is this contrapostive assumed to be true?

I have a problem with the following logical deduction: $ incabal(Darren) \implies incabal(Martyna) $ This would read, "If Darren is in the cabal, then so is Martyna." Later in the homework we ...
-1
votes
1answer
35 views

Logic and consistency

This is a past exam questions, and I was wondering if my thinking was correct If it is satisfiable, it is consistent We can construct a truth table and verify if there exist a truth value it is ...
2
votes
3answers
208 views

Construct XNOR with only OR gates

Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
0
votes
1answer
422 views

How can I tell if an infinite truth tree is valid?

I read that truth trees are not the best way of searching for an interpretation because in some cases, the tree will always be infinite even when there is an interpretation (with a finite domain) that ...
1
vote
1answer
141 views

Prove $\vdash (\lnot B \rightarrow \lnot A) \rightarrow (( \lnot B \rightarrow A) \rightarrow B)$

Give a hilbert style proof $$ \vdash (\lnot B \rightarrow \lnot A) \rightarrow (( \lnot B \rightarrow A) \rightarrow B)$$ How could I prove it ? When I apply deduction theorem, do I take $ ((\lnot ...
0
votes
1answer
48 views

Applying substitutions on formulae in logic

Do the following substitutions. If undefined, explain why. $ (p \land \top \equiv r)[\bot := r] $ $((\forall x)(\forall y)(\forall z)(g(x,y) = z))[z := f(x) = y ]$ $(p \rightarrow q \land \bot)[p := ...
3
votes
1answer
4k views

Using a truth table to determine if valid or invalid

I have some questions like if $P$ then $Q, P$ therefor $Q$ for example, how can you tell from writing your truth table if therefor $Q$ is valid or invalid? I mean I know its true because Modus Ponens ...
3
votes
2answers
83 views

Reductio Ad Absurdum Question

I've been stuck on this question (which uses RAA). Was wondering if somebody could help me to make sense of it? $$\{\neg (\phi \leftrightarrow \psi )\} \vdash ((\neg \phi )\leftrightarrow \psi )$$ ...
0
votes
1answer
73 views

Write theorem conditions concisely

Let $Z$ be a set, $x$ be some object. Let the following statements hold (for some logical formulas $P,P_1,\dots,P_n$ and some logical formula $Q$): $\forall z\in Z:(P(x) \Leftrightarrow Q(x,z))$ $(...
0
votes
2answers
127 views

Definition nested and unnested first order formulas

What's the definition of nested and unnested formulas in a first order language? I came across the term in a model theory book i'm reading, and I can't seem to find it defined there, or in my brief ...
0
votes
1answer
76 views

Logic, need help to find out what that abbreviations means

My native language is Portuguese, so I'll translate the question. Note that I haven't found relative content to that question on my language, but I found out that one of the abbreviations means Main ...