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
vote
0answers
24 views

What is the probability that 5 randomly chosen cards in a deck add up to 40 or greater than 40?

I have made a probability game, where you have to pull out any 5 cards without looking (from a deck of 52 cards), and if all five cards add up to 40 or more, they player pulling the 5 cards from the ...
0
votes
0answers
18 views

Vacuously true? Prove or disprove that for every theory $T$, if $T$ is not satisfiable then for every $\phi$, $T \vdash \phi$

Vacuously true? Prove or disprove that for every theory $T$, if $T$ is not satisfiable then for every $\phi$, $T \vdash \phi$. If $T$ is not satisfiable, then there is no structure $\mathcal M$ so ...
0
votes
1answer
12 views

Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$.

Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$. This seems quite right, but I don't know how to prove it. So lets start with ...
0
votes
1answer
19 views

Can a sum of a nonprincipal ultrafilter and a principal ultrafilter be equal to the nonprincipal ultrafilter?

If $ \mathcal U$ is a nonprincipal ultrafilter and $\mathcal V$ is a principal ultrafilter, can $ \mathcal U \oplus \mathcal V$ be equal to $\mathcal U$ ?
-1
votes
1answer
12 views

FOL formula and check valididty of this?

I think the following is logically valid, but my TA says it's not logically valid. $ \forall x (A(x) \to B(x)) \to ( \exists x A(x) \vee \exists x B(x)) $ Who Can Clarify me about this Formula ?
-1
votes
0answers
28 views

R.E set and Recursive Set, A Confusing Axioms !?!?

I want to check true or false of the following two axioms. who can help me or add some hint: I) $ A=\{x \mid \Phi_x\text{ is not one-to-one function} \}$ is an r.e set. II) if $A$ is an r.e ...
2
votes
1answer
23 views

Functional completeness for a ternary operator

If I define a ternary logical connective $\clubsuit(a,b,c)$ by the following truth table: \begin{array}{ccc|c}a&b&c&\clubsuit(a,b,c)\\\hline ...
2
votes
1answer
24 views

Models of Linear Logic

I am looking for an introduction to the model theory of Linear Logic. Can you recommend any clear introductions? I am particularly interested in those models that regard coherence spaces.
0
votes
1answer
17 views

Give an L-formula ϕ4(x) that defines the interval [1,√2) ⊂ R in M.

Let L = {+, · P} where + and · are binary function symbols and P is a unary predicate symbol, and let M be an L-structure where its domain |M| is the set R of real numbers, + and · are the usual ...
-3
votes
0answers
63 views

logic. Decide whether the following sequent is valid. [on hold]

Decide whether the following sequent is valid. Justify any claims. You may freely quote results from the Propositional Calculus. ((∃x) G(x)) ⇒ ((∃y) H(y)) ⊢ (∃x)(G(x) ⇒ H(x))
0
votes
2answers
21 views

Give an L-formula ϕ(x, y) that defines the less-than relation < over R in M.?

Let L = {+, ·, P} where + and · are binary function symbols and P is a unary predicate symbol, and let M be an L-structure where its domain |M| is the set R of real numbers, + and · are the usual ...
1
vote
2answers
45 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) ...
1
vote
0answers
24 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
21 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
37 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 ...
1
vote
2answers
31 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
38 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 ...
2
votes
1answer
56 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
67 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
31 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
21 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
73 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
109 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
77 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
50 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
31 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
43 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
22 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 ...
3
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
119 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
40 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. ...
1
vote
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
43 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) [closed]

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
36 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? [closed]

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 ...