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
0answers
14 views

Are the following logical statements equal? Solution verification

We were requested to rewrite the following statement: $((\phi \rightarrow(\psi \lor \lnot X)) \land (\phi \rightarrow (\psi \land X))) $ Using $\exists, \land, \lnot $ only. My result: ...
1
vote
3answers
39 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$" ?
0
votes
2answers
23 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
21 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
21 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
31 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
55 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 ...
3
votes
3answers
79 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 ...
4
votes
0answers
32 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
23 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
41 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
33 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
22 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
32 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
33 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
89 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
82 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
78 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
31 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
60 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
76 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
22 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
96 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
34 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
34 views

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

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 ...
2
votes
0answers
45 views

Supplementing FOL with the Härtig quantifier

"The Härtig quantifier captures a certain fairly large fragment of second-order logic and contributes to understanding higher-order logic." (p. 1154 ...
0
votes
0answers
30 views

Finding the compliment of a logical expression in respect to another logical expression.

What I would like to do is to find the logical compliment of one expression in respect to another logical expression. If possible, I would like to know if there has been work in this area - I haven't ...
0
votes
1answer
49 views

show that a horn sentence is preserved under a direct product.

show that a horn sentence is preserved under a direct product. If $\varphi$ is a horn sentence and $\mathfrak{A}_i, i \in \text{I}$ is a model for $\varphi$ namely $\mathfrak{A}_i \vDash \varphi$ ...
1
vote
0answers
33 views

show that the theory of fields cannot be axiomatized by horn sentences

show that the theory of fields cannot be axiomatized by horn sentences im not sure how to show it, nearly everything is quantified so easily no free variables, maybe something to do with $\neg0 ...
0
votes
0answers
32 views

Term structure corresponding to a formula in first-order logic

Consider $S= \{ <, s \}$, where $s$ is a function symbol, and the axioms: $\Phi_1 : \forall x \forall y (x < y \vee y < x), \\ \Phi_2 : \forall x \forall y \forall z (( x < y \wedge y ...
1
vote
1answer
48 views

How does PA prove all $\Delta_0$-formulas which are true in the standard model?

Let $\varphi(x_1,\dots,x_n)$ be a $\Delta_0$-formula, i.e. a formula in which every quantifier is bounded. I want to prove that $$ \text{PA}\vdash\varphi(\overline{n_1},\dots,\overline{n_k}) \iff ...
1
vote
1answer
46 views

Indiscernibles and colorations.

Let $L$ be a language, and $(X,\leq)$ be a total order contained in an $L$-structure $\frak{A}$. Now if we denote by $[X]^n$ the set of $n$-sized sequences in $X$ and consider a set $\Gamma$ of ...
2
votes
1answer
102 views

Logic and Metamath book recommendation

Recently, I got interested in Mathematical Logic and now I am looking for good introductory books on Mathematical Logic for beginners. In fact, I plan to read some good books on Metamathematics also. ...
2
votes
0answers
42 views

Hilbert's reduction of second order logic to first order logic

I have read on the internet a theorem of Hilbert that says that we can reduce every second order theory to a first order theory. So there exists only one logic: first order logic. I cannot find it ...
2
votes
2answers
32 views

clarification of a logic proof

I am a bit confused on what this question is asking me to prove: Prove $$ \exists z\forall x\in\mathbb{R}^{+}[\exists y(y - x = y/x)\leftrightarrow x \neq z] $$ Am I asked to prove that there ...
5
votes
6answers
94 views

How to explain that $A \implies B$ is true when $A$ is false [duplicate]

I'm teaching my little sister propositional logic per her request. I was trying to explain to her why $A \implies B$ holds whenever $A$ is false, and I didn't succeed with that. I referred her to ...
1
vote
1answer
33 views

Proving Identities Involving Symmetric Differences (How to Prove It, Velleman)

I tried searching for this (easy) question (both on here and on google in general), so if it's already been asked I apologize. My question concerns #13a in section 1.4, Operations on Sets in ...
0
votes
0answers
32 views

Proof by Resolution and Skolemization

I have this question where i have to prove the conclusion using the given premises : ...
0
votes
1answer
33 views

Logic : How to determine whether these propositions are contradictory ?

http://postimg.org/image/iips2lwdj/ The question asks to draw a truth table with the values of three propositions (linked), and following this, to "Show that the three propositions are ...
1
vote
1answer
52 views

Expressing conditional statements using quantifiers and predicates in Predicate Logic: how to recognize the hypothesis and conclusion in statement

I was solving questions of Discrete Mathematics and Its Applications By Kenneth H. Rosen Chapter 1 The foundations: Logic and Proofs , when i got stuck at this problem; two similar problems are ...
2
votes
3answers
215 views

Truth values in formal systems

Given any sentence $A$ of ZFC (or any other formal system, really), we have exactly four possibilities: $A$ is true and not false $A$ is false and not true $A$ is true and false at the same ...
1
vote
1answer
39 views

Transitive Closure and First Order Logic

Why is it not possible to represent transitive closure in First Order Logic? I am learning about translating from Description logic to FOL. In description logic, it is possible to have transitive ...
2
votes
1answer
38 views

How to use logical conjunction properly

On this website in equation (20) they use $$ d \, S = a \, d \, u \land d \, v $$ I have learned that $\land$ is the truth-functional operator of logical conjunction and that such logical operators ...