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)

-1
votes
0answers
5 views

Nicolas Choquet problem of bottles

Nicolas Choquet writed in 1484 the first frensh algebra book . In a problem , he want to devise between 3 persons 21 bottles. 7 of them are full 7 others are half filled 7 others are empty to ...
0
votes
0answers
12 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 ...
3
votes
2answers
59 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
21 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
16 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
59 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*}$$ ...
6
votes
0answers
80 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
58 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
117 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
86 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
33 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
61 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
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
46 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 ...
2
votes
0answers
49 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
50 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
34 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
33 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 ...