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)

2
votes
2answers
52 views

On provability within minimal logic

In its most naive form my question boils down to this: when is a proposition that is provable "by contradiction" also provable "directly"? IOW, is it possible to know, a priori, that a ...
0
votes
1answer
25 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 ...
1
vote
1answer
27 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 $ ...
0
votes
1answer
34 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 ...
1
vote
2answers
121 views

Modal set-theory

In his “The Potential Hierarchy of Sets”, Review of Symbolic Logic 6:2 (2013), 205-28 Øystein Linnebo has proposed a modal set-theory. I was wondering what kind of utility can such a theory have for a ...
1
vote
1answer
369 views

Meanings of the terms “conjunct” and “disjunct” in a logic?

This sentential logic problem is stated as: Suppose that $A \models B$, where $A$ is a conjunction of literals and $B$ is a disjunction of literals. Show that $ \models \neg A$, $ \models B$, or a ...
0
votes
1answer
17 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 ...
0
votes
0answers
36 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 ...
3
votes
4answers
98 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 ...
1
vote
3answers
45 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
25 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
22 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
35 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 ...
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
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 ...
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 ...
6
votes
0answers
35 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
27 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 ...
2
votes
2answers
35 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 ...
-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 ...
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
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
3answers
90 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.
4
votes
1answer
81 views

Models of infinite groups and 'Group-like' objects

Let $G$ be an infinite group, and for simplicity, we will assume that $G$ is also countable. Now, with $G$ in mind, we construct a new language $L_G=\{f_{a_i\_},f_{\_a_i}:a_i\in G\}$ where ...
-2
votes
0answers
23 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
33 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
34 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
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?
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 ...
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 ...
4
votes
0answers
56 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
5
votes
3answers
82 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
2answers
23 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 ...
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 ...
0
votes
2answers
2k views

DNF and CNF logic problem

So i want to find the DNF and CNF of : $ x \oplus y \oplus z $ . I tried by using $ x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y) $ but it got all messy and stuff, I also plotted it in ...
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 ...
8
votes
2answers
685 views

Is there an algorithm that when given a set of axioms, will generate a statement independent of those axioms?

Is there any mechanism or algorithm where one can generate mathematical statements/problems that are undecidable, i.e their proof is independent, from a certain set of axioms?
8
votes
8answers
3k views

If yesterday were tomorrow, then today would be Friday.

(S) If yesterday were tomorrow, then today would be Friday. Question: What day is today? This seems to be an old puzzle, and depending on the interpretations, the answers are Wednesday or ...
8
votes
2answers
101 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
2answers
34 views

logical associative expressiveness with no negation operator

Let's suppose we can only use $\wedge$ and $\vee$ operators (we have no negation operator), and by default we have associativity to the left. Is this subset of logic as expressive as the one with the ...
0
votes
1answer
64 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
1
vote
3answers
59 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
-1
votes
0answers
34 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 ...
10
votes
1answer
206 views

Do second-order categoricity proofs require a background concept of set?

In his article "The Set-Theoretic Multiverse", Joel David Hamkins (as part of his reply to Donald Martin's argument that the set-theoretic universe is unique, found in "Multiple Universes of Sets and ...
1
vote
6answers
124 views

Why is $P \to Q \equiv \neg P \vee Q$?

By truth table, we know that $P \to Q$ is equivalent to $\neg P \vee Q$. But I'm trying to understand why this work? How can connective "or" be implication. I tried some examples but I still can't ...
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
vote
1answer
40 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 ...
2
votes
0answers
46 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 ...
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 ...