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
51 views

The generalized Axiom of Dependent Choice (DC) - is this a valid generalization?

After studying the axiom of dependent choice, I tried to think of a possible generalization of the axiom that would work in a similar way on infinite uncountable sets: by replacing the binary relation ...
2
votes
1answer
83 views

What is a Primitive Atomic Formula?

I am reading "Axiomatic Set Theory" by Patrick Suppes and he defines a primitive atomic formula as follows: A primitive atomic is an expression of the form ($v\in w$ ), or of the form ($v=w$) where v ...
2
votes
2answers
56 views

Logical Formulation of the Ending of “Ode on a Grecian Urn” by John Keats [closed]

Thanks very much in advance to anyone who can help me on this problem. Here is the well-known conclusion of "Ode on a Grecian Urn" by John Keats: "Beauty is truth, truth beauty,"—that is all / Ye ...
0
votes
1answer
40 views

(Sphere Lemma) Hanf locality Lemma and locally threshold testability

I am reading the proof of Hanf's Sphere Locality lemma for (finite or infinite structures but with bounded degree), and I'm trying to understand the details of the proof! I'm confused with the ...
1
vote
1answer
47 views

How to **formally** prove that $(\exists!x)(A(x))\iff(\exists x)(A(x)\wedge(\forall y)(A(x)\wedge A(y)\implies x=y)$

$$(\exists!x)(A(x))\iff(\exists x)(A(x)\wedge(\forall y)(A(x)\wedge A(y))\implies x=y)$$ This is extremely intuitive, there is only one $x$ that satisfies the property $A$ if and only if there exists ...
3
votes
1answer
54 views

Proofs as implication and proving implications

I am working through a textbook, on my own, having to do with logic and mathematical proofs, and I have a question about a problem I just completed. Here's the problem: "Suppose $P \to (Q \to ...
2
votes
1answer
52 views

Local isomorphism question in logics

The definition of a local isomorphism between structures: a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ ...
0
votes
1answer
31 views

Is this proof using only modus ponens correct?

The mouse is either quick or slow. If it is quick, it will escape the cat. If it is slow, it will take the cheese. If it takes the cheese, it will not escape the cat. A = “the mouse is slow” B = ...
7
votes
2answers
113 views

First-order definition of nonnegative in integers

Given the structure $(\mathbb Z,+,-,\times,0,1)$, what's the easiest way to write "$x\ge0$" in that structure? I know that this works: $$\exists a\exists b\exists c\exists d,a^2+b^2+c^2+d^2=x$$ ...
1
vote
1answer
28 views

How can the composition inference rule be used to prove the correctness of a program split in two segments?

So the basic setup is you have a program segment S and it is split into two segments S1 and S2. You know for a fact S1 is partially correct with respect to initial assertion p and final assertion q, ...
1
vote
0answers
42 views

Is $\exists x(P(x)\rightarrow\forall y P(y))$ a tautology? [duplicate]

This is from the book by D.J. Velleman-"How to prove it?" Sec 3.5 Excercise 31: Prove $\exists x(P(x)\rightarrow\forall y P(y))$ Suppose the universe of discourse is set of all men. Let statement ...
0
votes
2answers
70 views

Does my insurance company commit Gambler's Fallacy, or do I?

I would not be able to put this into symbols, but I ask here because I think it's the correct place to ask. Would the chance of my parked car getting damaged (bumped or scraped) by other cars parking ...
1
vote
3answers
27 views

Converting a statement

This is from "How to Prove It: A Structured Approach" by Daniel J. Velleman. In the selected exercise the goal was to negate the statement, but I'm more interested in its form. The statement is: ...
0
votes
2answers
85 views

Show that $A \lor B ⊢ B \lor A$

Prove the following derivability claim using only our primitive rules: $A \lor B ⊢ B \lor A$ I know this can be attributed to the commutative property, but I'm not exactly sure how to prove this ...
1
vote
3answers
31 views

Difference between these two logical expression

I am trying to solve the following problem: Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate “x has asked y a question,” where ...
-1
votes
1answer
30 views

Find logical errors in the proof

I'm finding it really hard to find the logical errors in this proof. I'm still new at this and trying to learn it. Claim: for all $n$ is in set $\mathbb{N}$(Natural numbers), if $2n+1$ is a ...
1
vote
1answer
35 views

Express $V(\diamond \alpha)$ set theoretically in terms of $V(\alpha)$

I am reading Modal Logic. While going through the basics of the subject I am having problem in a place. Please help me. Say we are dealing with a frame $(W,R)$ and defined a model $M$ using a ...
0
votes
1answer
53 views

Can Incompleteness be Computable?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
2
votes
1answer
50 views

Integer programming: if a or b then a, b, and c

I'm writing a mixed integer programming (MIP) constraint where my $\color{blue}{\texttt{binary variables}}$ are $a, b,$ and $c$ to meet the following condition: $$ (a \lor b) \to (a \land b \land c)$$ ...
4
votes
1answer
46 views

“There are exactly two values of $x$ for which $P(x)$ is true” formula using logical symbols

Assuming $P(x)$ is true. The statement: "There are exactly two values of $x$ for which $P(x)$ is true" can be rewritten using logical symbols as follows: $$\exists x \exists y[(P(x) \wedge P(y) ...
1
vote
1answer
62 views

Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...
2
votes
3answers
38 views

Correct Form of a Logical Statement

I ran across a problem which has stumped me involving existential quantifiers. Let U, our universe, be the set of all people. Let S(x) be the predicate "x is a student" and I(x) be the predicate "x is ...
8
votes
1answer
134 views

Why Does The Reflection Principle Fail For Infinitely Many Sentences?

I've read the proof that ZF cannot be finitely axiomatized via the reflection principle and the 2nd incompleteness theorem. Since ZF can be countably axiomatized, the finiteness requirement in the ...
1
vote
0answers
33 views

Prove Ordering of Mixed Quantifiers

I'm trying to familiarize myself with some of the formal logic behind mathematical proofs, and I'm having trouble proving some things explicitly even though I have no trouble with them intuitively. ...
-1
votes
2answers
27 views

Proof structure validity: assume (a), (b), show (c). Then Permute.

I am given a collection of sets $\mathcal{E}$ and am trying to prove it is an elementary family. To show $\mathcal{E}$ is an elementary family I must show that it satisfies the following properties: ...
0
votes
1answer
27 views

Properties of transitive modal frames

I am working through Fitting and Mendelsohn's First Order Modal Logic and have come across the following exercise: Prove that a frame $\langle \mathcal{G}, \mathcal{R} \rangle$ is transitive if ...
0
votes
2answers
66 views

Goldbach Conjecture predicate form?

I am learning logic, and when I was taking a quiz one of the multiple choice questions was "Which of the following is an unsolved conjecture?" I picked the following answer because I thought it was ...
3
votes
3answers
75 views

How do set theory, and formal logic fit in together?

Im at that stage in my mathematical understanding where I kinda understand what set theory is and what first order logic is but dont really understand how they fit together to create Mathematics. I ...
5
votes
3answers
1k views

How can the axiom of choice be called “axiom” if it is false in Cohen's model?

From what I know, Cohen constructed a model that satisfies $ ZF\neg C $. But if such a model exists, how can AC be an axiom? Wouldn't it be a contradiction to the existence of the model? Only ...
1
vote
2answers
52 views

Orders with no anti-symmetry requirement?

A ordered/partially ordered set is required to satisfy the $x \leqslant y$ and $y \leqslant x$, $\implies x=y$ (antisymmetry) axiom. Are there any viable theories where this condition is weakened? ...
0
votes
3answers
92 views

Godel's Second Incompleteness and the Assumption of Consistency

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given ...
8
votes
1answer
66 views

Is an infinite system of (linear) equations solvable if all finite subsystems are?

I was wondering about the following. Let $A$ be an abelian group, $a_i$ variables indexed with some arbitrary set $I$ and assume we have an infinite set $E$ of linear equations in finitely many ...
3
votes
0answers
36 views

Model-theoretic characterization of local modal correspondence

I've been reading van Benthem's dissertation (available on ILLC's website) on modal correspondence theory. In Section I.3, he develops a model-theoretic characterization of modal formulas having ...
3
votes
3answers
78 views

Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$

Suppose $\mathcal{F}$ and $\mathcal{G}$ are families of sets. Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$ My attempt: Given $\mathcal{F} ...
2
votes
1answer
77 views

Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
1
vote
1answer
32 views

Is PA+ TM doesnt halts consistent?

Suppose there isnt a proof in PA whether some TM halts or not. Suppose further that TM doesnt halt and PA is consistent. Is PA+TM halts necesserely consistent? Is PA+TM doesnt halt necesserely ...
0
votes
1answer
20 views

choose from implication and logical and in write assertions in first-order logic

I am a student and I get confused in translating some sentence to logic assertion. For example: Joe does not have a lawyer, i.e. is not a customer of any lawyer. The right way to translate is: "For ...
7
votes
1answer
288 views
+400

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existential theory ...
0
votes
3answers
91 views

Please Help me understand this proof

DOUBT What i didnot understand is from where it is written our new goal means there exists a... I didnot understand how there exists word popped up here and why the new givens are written as they ...
2
votes
2answers
62 views

How do I express logical connectives with Nand?

Really struggling to understand how to express all the connectives as Nand. I understand that p ^ q would be the opposite of p nand q, but I get stuck when trying to express p -> q and p v q in ...
1
vote
1answer
52 views

A mistaken proof of consistent choice?

Given a set of sets ${\cal A} = \{S_i\mid i\in {\cal B}\}$ and a binary relation $Con$ on $\bigcup {\cal A}$, a $Con$-choice on $\{S_i\mid {i\in F}\}, F\subseteq {\cal B},$ is a function $\epsilon\in ...
1
vote
1answer
96 views

Prove that “No one likes Reggae music” is the same as “Everyone does not like Reggae music”.

I interpreted this as a case of the extension of De Morgan's Law to quantifiers. https://en.wikipedia.org/wiki/De_Morgan%27s_laws#Extensions I know that similar questions have been asked before about ...
1
vote
1answer
33 views

How to represent the sentence “If everyone votes then the motion passes” with FOL

Should it be ∀x Votes(x) ⟹ Passes(Motion)? Probably not, because if none but 'John' votes, then using extended interpretation, ...
1
vote
1answer
23 views

Prove that if $\forall A \in \mathcal F (B\subseteq A)$ then $B \subseteq \bigcap \mathcal F $

This is Velleman's exercise 3.3.10. Suppose that $\mathcal F$ is a nonempty family of sets, B is a set, and $\forall A \in \mathcal F (B\subseteq A)$. Prove that $B \subseteq \bigcap \mathcal F $. My ...
0
votes
0answers
17 views

Clarification of conditional propositions [duplicate]

I am studying first order logic and we have been introduced to conditional propositions.$(p \Rightarrow q)\;$ The truth table for $p \Rightarrow q$ is this: ...
1
vote
2answers
116 views

Formula that's only satisfiable in infinite structures [closed]

What formula in first order logic can I write that's only satisfiable over infinite structures, over a dictionary without the = sign?
0
votes
3answers
72 views

Please help me understand the proof

Doubt In third line of the proof, why is Q $\rightarrow$ R ? Thanks
2
votes
1answer
75 views

What is the definition of a definable set of statements, and what is a constructive way to think of this regarding Tarski's Undefinability Theorem?

Logic and model theory are not my area so my thinking is probably off, but I am curious about this so please go ahead and set me straight. A definable set is one for which there is a formula that is ...
9
votes
1answer
390 views

Algorithm to answer existential questions - Reduction

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
2
votes
1answer
70 views

Meaning of “such that”

The use of the term "such that" confuses me I've seen this like $A=\{(x,y) :x,y\in\Bbb R\ \text{and } P(x,y) \}$ and $B=\{(x,y)\in \Bbb R^2:P(x,y)\}$ for some predicate $P$. Is there any difference ...