Questions about 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)

0
votes
1answer
18 views

What is a theory and what is its extension

As I understand, a theory is a set of sentences which are closed under some notion of deduction (i.e., applying deduction rules to the sentences of a theorem does not produce any new sentences) ...
0
votes
0answers
5 views

is 2nd criterion of inference satisfied for the restrictions on rules governing quantifiers

these two criteria are mentioned in patrick suppes book- intro to logic. then to account for criterion 1 , some rules of restrictions on quantifiers are given. But about criterion 2, how do we know ...
0
votes
1answer
14 views

is criterion of eliminability and criterion of non creativity independent

In introduction to logic by Patrick suppes, in Theory of definition 2 criteria are given, criterion of eliminability and criterion of non creativity. So if any formula is eliminable it should also be ...
0
votes
1answer
27 views

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable It gives the hint to use $x \in \mathbb{N} \leftrightarrow \exists x_0 \exists x_1 \exists x_2 \exists x_3(x \equiv x_0 \cdot x_0 \wedge x_1 ...
0
votes
0answers
14 views

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

show the set of valid second-order $\emptyset$-sentences is not R-enumerable this would have the empty symbol set i.e. $S = \emptyset$ so it would be sentences that are universally or existentially ...
1
vote
2answers
30 views

where to begin with mathematical logic- text suggestions

My name is battlefrisk and I intend to pursue a career in either operations research or artificial intelligence. I have only taken a single class on logic, and I am considering buying a text on the ...
1
vote
1answer
32 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
2
votes
2answers
63 views

Why is the implication “If pigs could fly, I'd be king” a true implication? [duplicate]

Let $P$ = "Pigs can fly" and $Q$ = "I'm king". Apparently, there's a rule stating that $P \implies Q$ is true, if $P$ is false. In this example, $P$ is indeed false, because pigs cannot fly. But how ...
2
votes
0answers
23 views

Probabilistic Logic

I was wondering if there is any system of logic that has been worked out that explicitly uses probabilistic notions at its foundation. It would include ideas like as a first principle, all statements ...
1
vote
0answers
19 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all ...
2
votes
1answer
64 views

for all $x$, $P(x)$ implies there exists $x$, $P(x)$?

$$\begin{align*} \big[\forall x\,P(x)\to\exists x\,P(x)\big]&\iff\left[\big(\neg\forall x\,P(x)\big)\lor\exists x\,P(x)\right]\\ &\iff\exists x\,\neg P(x)\lor\exists x\,P(x)\;, \end{align*}$$ ...
7
votes
0answers
90 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
1
vote
1answer
74 views

When two theorems are equivalent? [Formal definition]

I understand that two mathematical statements (theorems) are equivalent when one can prove any of the statements by using the other one. Is there a formalism for such a description?
1
vote
1answer
47 views

Identify the type of fallacy

"Mohan is a student and he is hardworking. Therefore, all students are hardworking." Is the fallacy committed here that of converse accident or of composition? From what I understand, it is the ...
0
votes
1answer
30 views

Non-empty intersection of specific sets

For any set Y (to begin with, it may be countable), given a collection of relations $$R = \{R_y \subseteq \{0,1\}^Y \mid y \in Y\},$$ having the finite intersection property and such that for ...
0
votes
1answer
38 views

What does “resolve away” exactly mean in propositional logic?

I have never had logic classes so I always struggle with the assignments that concern this interesting field. I was reading the slides about resolution theorem proving and there was a step-by-step ...
0
votes
0answers
42 views

Math, logic symbol for “instance of”

I saw a discussion of a possible symbol for "example," but I need "example/instance of." There is of course $a \in S$ which is a is a member of/in S, but is there a specific way of stating $a ...
1
vote
1answer
20 views

Prove $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$

I want to show that: $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$ I started my deduction as follows: $\vdash\forall x(\alpha\to\beta)\to(\forall ...
2
votes
1answer
30 views

Are the following logical statements equal? Solution verification

We were requested to rewrite the following statement: \begin{equation*} ((\phi \rightarrow(\psi \lor \lnot X)) \land (\phi \rightarrow (\psi \land X))) \end{equation*} using $\exists, \land, \lnot $ ...
1
vote
3answers
51 views

How is “p implies q” same as “q unless not p”?

I want to know how is "p implies q" same as "q unless not p"? ie how is "$p\Rightarrow q$" same as "$q$ unless $\neg p$" ?
1
vote
2answers
28 views

Statements for Proof by Contradiction

I was reading the following notes about Proof by Contradiction I understood that (as given above) for showing $P\implies Q$ is true $\equiv (\sim P \vee Q)$ is true $\equiv (P \wedge \sim Q)$ is ...
2
votes
1answer
23 views

Calculating the number of variables and constants in a term

I'm reading Kees Doets's Basic Model Theory and couldn't get around the first exercise, which is rather simple (no doubt my lack of arithmetical skills played a part). Let $t$ be a term and let $n_i$ ...
0
votes
1answer
22 views

Rule T in First-Order Logic

In Enderton's A Mathematical Introduction to Logic (second edition, page 118), we are given the so-called Rule T (Lemma $24C$) : If $\Gamma\vdash\alpha_1,\ldots,\Gamma\vdash\alpha_n$ and ...
2
votes
1answer
36 views

Clarifying some doubts on the definition of “extensional classes”

On page 68 of Jech's "Set Theory" 4th Edition there is the following definition : A class $\mathcal{M}$ is extensional if the relation $\in$ on $\mathcal{M}$ is extensional, i.e., if for any ...
2
votes
1answer
58 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
5
votes
3answers
118 views

Lists of sets as objects of ZF axiomatics

I have a naive question about foundations of mathematics. A common opinion of most mathematicians is that the essential part of mathematics can be reduced to ZF(C) axioms. I do not quite understand ...
6
votes
0answers
38 views

Heyting algebras and infinite distributive law

I want to prove that "a complete lattice satisfies the infinite distributive law $a\wedge(\vee{S})=\vee\{a\wedge s|s\in S\}$ iff it is a Heyting algebra". I proved "if" part but can't "only if" part. ...
2
votes
2answers
29 views

Natural deduction $\{A \vee L, A \leftrightarrow N, L \rightarrow N\} \vdash N$

Natural deduction $\{A \vee L, A \leftrightarrow N, L \rightarrow N\} \vdash N$ my work 1- $A \vee L$ 2- $A \vee$ Elim FROM 1 3- $A \leftrightarrow N$ 4- $A \leftrightarrow$ Elim FROM 3 5- $L ...
-1
votes
3answers
42 views

Prove that the set of sentences $\{A \land (B \lor C), (\lnot C \lor H) \land (H \rightarrow \lnot H), \lnot B\}$ is inconsistent

Prove that the set of sentences $\left\{A \land (B \lor C), (¬C \lor H) \land (H \to \lnot H), \lnot B\right\}$ is inconsistent. I'm confused because it doesn't look like any of the forms I've ...
2
votes
2answers
36 views

A Natural-Deduction proof of $ \{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $.

I would like to prove $\{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $. My work until now is as follows: $$ \begin{array}{l|ll} 1 & \neg N ...
0
votes
1answer
14 views

Entailment Checking Description Logic

I am reading a research paper in Description Logic. Say L be a knowledge base which consists of axioms. Then $C \sqsubseteq D$ is an axiom. Theorem: L $\vDash C \sqsubseteq D $ iff L $\vDash C ...
0
votes
1answer
39 views

Prove that the following argument is valid

I'm asked to show the following arguments are valid: P1) $[E \lor (L \lor M)] \land (E \leftrightarrow F)$ P2) $L \rightarrow D$ P3) $D \rightarrow \neg L$ C) $E \lor M$ Our work (so far): P2) ...
1
vote
1answer
40 views

Natural deduction proof: {A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A

$ 1- {A → B, B → (C \land D), ¬C \vee ¬D} ⊢ ¬A$ Our work (so far): $1- A → B$ $2- B → (C \land D)$ $3- ¬¬A$ $4- A$ $5- B$ (from 1,4) $→E$ $6- B$ $7- C \land D$ (from 2,6) $→E$ This is ...
-2
votes
0answers
24 views

2. {A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A

{A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A {¬N, (¬N → L) & (D ↔ ¬N) } ⊢ (L v A) & D {A v L, A ↔ N, L → N} ⊢ N my try to number 2 is that 1- A → B 2- B → (C & D) 3- ¬¬A 4- A 5- B ...
-2
votes
2answers
34 views

Monadic second order logic (Tree) [on hold]

I'm studying for a final exam by trying to review some problems from around the internet. I just can't seem to nail this one down: I need to express the property of a graph G (given by a binary ...
1
vote
1answer
35 views

{(¬A v ¬B) → C, D & ¬C} ⊢ A

{(¬A v ¬B) → C, D & ¬C} ⊢ A this is my try 1- (¬A v ¬B) 2- A 3- ¬B ( 1,2 vE ) but I'm stuck on the others , please help
3
votes
3answers
91 views

If $A$ and $B$ are sets, then either $A \in B$ or $A\notin B$

Given that $A$ and $B$ are two sets, is the following proposition a tautology: $A\in B \vee A\notin B$. I do not know any set theory beyond the naive one.
-3
votes
2answers
45 views

How many workers each company have? [on hold]

If total there are 90 workers between 2 companies and one company have 16 more workers then the other. How many each company have?
1
vote
1answer
31 views

Reference for a proof of the recursion theorem, for a general case.

Herbert Enderton in his A Mathematical Introduction to Logic 2nd edition, proves a theorem (a "recursion theorem") in section 1.4, p. 39. Using his example, the idea is the following: We have some ...
3
votes
1answer
83 views

If the answer is “no” then “yes” and vice versa type of paradoxes. What are they?

I'm a complete layman, so my technical terms might be misleading. Sorry for the many small questions, it's just that I don't know how to formulate my question right. What is the deal with paradoxes ...
5
votes
3answers
87 views

Complete extensions of a consistent theory

I understand that I need to use compactness but somehow can't finish it. Suppose $L$ is a language and $T$ a consistent $L$-theory with only finitely many logically inequivalent complete extensions. ...
3
votes
1answer
34 views

False $\Sigma_1$-sentences consistent with PA

I'm preparing for an exam and encounter the following exercise in the notes I use. In the next chapter we shall see that there are $\Sigma_1$-sentences which are false in $\mathcal{N}$ but ...
2
votes
4answers
64 views

Why Mendelson axiom schemas are true?

I'm taking course in logic. The book is available here I don't understand why is Mendelson axiom schemas are the way they are. For example implication creation schema $φ ⇒ (ψ ⇒ φ)$ My thoughts ...
4
votes
2answers
77 views

How I can express in a pure symbolic way common reasoning? Examples inside.

I have a broad question here, I know, but I will go define it clearly through examples. I want to know how express reasoning in a pure symbolic way, with no words, this is possible? Example: I was ...
3
votes
2answers
24 views

Test for symmetric property of this ordered pair

Suppose the set $$S={1,2,3}.$$ I must show that the equivalence relation $$R=\{(1,1),(1,3),(2,2),(3,1),(3,3)\}$$ is on the set. The reflexive property states that: $$(a,a) \in R \;\forall a \in ...
8
votes
2answers
105 views

Intuitionistically, are these inequivalent? $P \rightarrow Q,\; \neg Q \rightarrow \neg P,\; P \wedge \neg Q \rightarrow \bot,\; \neg P \vee Q$

Sometimes we get questions like this that essentially ask: Okay, I know there's at least three different ways of proving an implication, namely: direct proof proof by contraposition ...
1
vote
1answer
47 views

Universal languages are primitive recursive.

First of all, this are the definitions I am working with. Definitions: A language $L$ is $universal$ if it is countable, has infinitely many constants, and for each $n$, $1 \leq n$ has infinitely ...
4
votes
3answers
55 views

Logic: Can you drop parentheses in a conjunction?

In propositional logic, $p \land (q \land r) = (p \land q) \land r$ , where $p, q$ and $r$ are propositions. Does this mean $p \land (q \land r) = p \land q \land r$ ? If so, why?
-1
votes
0answers
35 views

Proofs involving 3 quantifiers: A(3,3)=6 cases [closed]

I knows how to prove statement involving 1 or 2 quantifiers. So there are 6 combinations of 3 universal quantifiers ("for all" and "there exist") with an extra implication that makes a quantified ...
2
votes
0answers
30 views

Defined negation in intuitionistic linear logic

Is it possible to define a negation in intuitionistic linear logic, the way one does in intuitionistic logic, i.e. $\neg A \equiv A \multimap \bot$? While I can prove, e.g. the theorem... $$\neg\neg ...