Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
2answers
19 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 ...
3
votes
1answer
31 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
1answer
40 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
26 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 ...
1
vote
2answers
70 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 ...
0
votes
1answer
34 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 ...
2
votes
2answers
32 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
39 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 ...
0
votes
0answers
16 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 ...
2
votes
2answers
41 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
29 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 ...
31
votes
7answers
3k 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
40 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 ...
1
vote
1answer
22 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 ...
1
vote
0answers
31 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
39 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
70 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
52 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
1answer
56 views

How to write negation of statements? [on hold]

How to write negation of following statements in words? ...
1
vote
1answer
37 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
37 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
591 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
63 views

How does one avoid circular reasoning? [on hold]

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
45 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
41 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 ...
0
votes
1answer
26 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
33 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" ...
4
votes
2answers
110 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
60 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 ...
0
votes
0answers
36 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
29 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
55 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 ...
2
votes
3answers
48 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
73 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 ...
0
votes
1answer
51 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
31 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
170 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
60 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
0answers
33 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
31 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
65 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 ...
3
votes
3answers
149 views

Limited completeness and restricted quantifiers

Let $L$ be a first order language with no constant or operation symbols. $L$ also has a relation symbol $R$ of arity $2$. Let $T$ be a Godelian set of formulas. Let $Q^1,Q^2$ be two formulas. The only ...
2
votes
1answer
63 views

$\textbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence. I ...
-1
votes
1answer
21 views

a question on time, distance, speed [on hold]

Everyday, Victor starts at 3.00 pm from his home to pick up his son from school. They reach their house at 5.00 pm. One day school was over at 3.00 pm. Victor, not aware of this, started from home as ...
4
votes
0answers
89 views

Combinatorial packages of N items [[How many distinct Boolean Expressions can be made using N variables]]

Using just the AND operator, the number of distinct packages that can be built from a set of size $n$, is simply $2^n$. If one adds the operators OR and XOR, how many packages can be built? That is, ...
0
votes
1answer
27 views

Use the auxiliary variable metatheorem to proof

Use the auxiliary variable metatheorem to show that $$ \vdash (\exists x)(A \land B \land C) \rightarrow (\exists x)(A \rightarrow C \rightarrow B)$$ My answer : By using the deduction theorem we ...
2
votes
1answer
50 views

Proving the propositional tableau sound and complete

There is something fundamental that stops me from understanding the proofs for the propositional tableau. (1) soundness proves that all theorems that can be proved are valid (2) completeness proves ...
0
votes
1answer
40 views

Natural deductive Logic [closed]

Let $R$ be a binary relation. Then a. $R$ is reflexive iff $(x)Rxx$ b. $R$ is serial iff $(x)(\exists y)Rxy$ c. $R$ is Euclidean iff $(x)(y)(z)((Rxy \land Rxz) \rightarrow Ryz)$ d. $R$ is ...
1
vote
2answers
70 views

Does generalization of axioms apply also to theorems?

In Enderton's book "A Mathematical Introduction to Logic" (second edition), he includes six axiom groups, and allows also for a generalization of those axioms such that if $\Psi$ is an axiom then ...
0
votes
1answer
20 views

four digit numbers that have at least one of their digits repeated

The number of four digit telephone numbers that have at least one of their digits repeated is A. 9000 B. 4464 C. 4000 D. 3986