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
8 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 ...
3
votes
0answers
23 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. ...
0
votes
2answers
19 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
28 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
32 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
35 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) ...
0
votes
1answer
29 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 ...
1
vote
1answer
30 views

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

1- {A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A Our work (so far): 1- A → B 2- B → (C & D) 3- ¬¬A 4- A 5- B (from 1,4) →E 6- B 7- C & D (from 2,6) →E This is where I've been for the past 6 ...
2
votes
3answers
79 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
20 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
29 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 ...
0
votes
1answer
29 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?
2
votes
1answer
30 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
1answer
76 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
55 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
74 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
21 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 ...
3
votes
2answers
73 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
58 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 ...
7
votes
2answers
91 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
33 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 ...
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
54 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
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 ...
2
votes
0answers
43 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 ...
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 ...
2
votes
2answers
342 views

Four men seated in a boat puzzle

I am looking for an elegant way to solve this rather simple logic puzzle using mathematical logic (statements, conjunctions, disjunctions, implications, tautologies, predicate logic and so on). I am ...
26
votes
6answers
1k views

Are there any nontrivial examples of contradictions arising in non-foundational or applied math due to naive set theory?

I understand that naive set theory, whose axioms are extensionality and unrestricted comprehension, is inconsistent, due to paradoxes like Russell, Curry, Cantor, and Burali-Forti. But these all ...
0
votes
1answer
48 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
30 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
44 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. ...
3
votes
1answer
502 views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...
1
vote
1answer
47 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 ...
6
votes
1answer
296 views

Difference between elementary submodel and elementary substructure

This is a really "elementary" question, forgive the pun. What is the difference between an elementary submodel and an elementary substructure (in first-order Logic)? Sincere thanks for help.
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 ...
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 ...
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 ...
4
votes
4answers
85 views

Why is the numbering of computable functions significant?

My course is about computability theory, and I'm having troubles with one of the main concepts. This might be a really newb question, but I've been struggling with understanding it's significance (and ...