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)

8
votes
0answers
136 views

A consequence of zero sharp (successor cardinals having countable cofinality)

So the existence of $0^\sharp$ in set theory is really the assertion on the existence of indiscernibles for the constructible universe $L$ that also "generate" $L$ (see ...
0
votes
1answer
68 views

Is “smarter than” a transitive relationship?

A logic assignment requires me to create a model in which most X's are smarter than most Y's, but most Y's are such that it is not the case that most X's are smarter than it. It's easy to do this ...
0
votes
1answer
40 views

Interpreting predicate formulas in the structure of arithmetic

Given two formulas a) $(\forall x)(\phi(x)\rightarrow\varphi)\;\;\;\;\;\;$ b)$(\forall x)\phi(x)\rightarrow\varphi\;\;\;\;\;$ Let $\;\mathbb{S}=(\mathbb{N},+,\times,\le,0,S)$ (where $S$ stands for ...
2
votes
1answer
49 views

In which direction is this statement true?

Having a hard time how I would go at this question. $\exists x \in G, P(x) \wedge Q(x) \iff (\exists x \in G, P(x)) \wedge (\exists x \in G, Q(x))$ $\forall x \in D, P(x) \vee Q(x) \iff ...
21
votes
4answers
2k views

How can you show Godel's incompleteness theorem using mathematical symbols?

I want to get this as a tattoo as I love the role maths plays in the universe and the idea that the farthest reaches of what we can ever know, fall short of the limits of what is true, even in ...
0
votes
7answers
108 views

Prove $ \{(p \lor q) \land (p \implies r) \land (q \implies r) \} \implies r$ is a tautology using logical properties

I spent quite a bit of time on this and have little to no ideas on how to proceed. Using the conditional laws and De Morgan's law, I got to $$( \sim p \land \sim q) \lor (p \land \sim r) \lor(q ...
9
votes
2answers
188 views

Why is $\omega$-consistency needed in Gödel's original Incompleteness proof?

I don't see why the original version of Gödel's first incompleteness theorem (before Rosser's improvement, I mean) had to include the assumption of $\omega$-consistency in order to show that $F ...
2
votes
1answer
47 views

Creating a proposition from a truth table using only ~ ⋀ and v

I have to find a simple expression for the third column in the truth table using only the logical connectives I've mention above. There are two questions that are involved here. Problem 1: Truth ...
1
vote
0answers
33 views

Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and ...
1
vote
0answers
44 views

Term models in group theory

Let $S_{Gr}$ be the language of groups, $Z$ an arbitrary set that does not contain elements of $\mathcal A_{S_{Gr}}$ (the corresponding alphabet). For each $z \in Z$ take a new constant symbol $c_z$ ...
0
votes
1answer
29 views

Conjunctive Normal Form to Disjunctive Normal Form

My question is this... Convert: ((A->B)&(~A->C)) into ((A&B)|(~A&C)) using the natural deduction system My working so far is: (A->B) by simplification (~A->C) by commutation and ...
4
votes
2answers
105 views

What is the difference between intuitionistic, classical, modal and linear logic?

I am currently going through Philip Walder's "Proposition as Types" and a passage of the introduction has struck me: Propositions as Types is a notion with breadth. It applies to a range of ...
4
votes
1answer
43 views

Boolean algebras, Stone theorem and being isomorphic to a field of sets

I'm a little bit confused about duality between boolean algebras and topological spaces or sets. I know the following theorem (which is due to Stone, as far as I know): Every boolean algebra $B$ ...
4
votes
1answer
124 views

Why a system becomes incomplete once it's capable of doing arithmetic?

For a Formal axiomatic system to obey Godel's incompleteness theorems, It has to be powerful enough to incorporate Peano Axioms. Why It does not apply to say, Presburger arithmetic or the axioms of ...
0
votes
1answer
69 views

Metrizability, Models, of Non-Standard Reals

according to compactness theorem in logic, there are models for the Reals of all infinite cardinalities, and these are elementary-equivalent to those of the "Standard" Reals ( Reals with ...
1
vote
1answer
21 views

Can you give a simple CDCL example?

I am trying to understand how Conflict-Driven Clause Learning works. After reading through the lecture slides, wikipedia article and some additional slides I found online I realized that I still can't ...
1
vote
1answer
56 views

Difference between $a,b \in S$ and $\forall a,b \in S$

Is there any difference between these two notations, $a,b \in S$ $\forall a,b \in S$ where $S$ is any non-empty set.
1
vote
0answers
21 views

Implication truth table [duplicate]

According to my textbook the implication P --> Q has the following truth table: I don't understand the last two rows. For example in the last row, how can we determine P --> Q if all we know is ...
2
votes
1answer
40 views

How to prove UG is sound?

I want to show that the PL is sound for the set of rules $ S=\{P,T,C,US,UG,E \} $ That is, if $\Gamma \vdash_s \phi$, then $\Gamma \vDash \phi$ And I have already proved it except for UG If $ ...
4
votes
2answers
101 views

The contrapositive

Considering an arbitrary model, is law of the excluded middle the weakest axiom needed to make the contrapositive of a statement logically equivalent to the statement? I've seen and done the first ...
1
vote
2answers
25 views

Can I use De Morgan's law in the third step as shown below to solve this problem?

$(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(\neg p \vee q) \wedge (p \vee q)$ $\equiv \neg(\neg (\neg p \vee q) \vee \neg(p ...
1
vote
1answer
37 views

Intersecting Scopes: Quantifier and Predicate

I came across an expression in predicate logic that made me wonder whether it was actually syntactically valid, and if so, semantically correct. For a sentence like "Every dog chases a cat", there ...
0
votes
1answer
24 views

Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
1
vote
2answers
33 views

Let $P(x)$ be an open sentence. Is "$P(x)$ and not $P(x)$ proposition?

Let P(x) be an open sentence. Is "P(x) and not P(x)" a proposition ? And another question. Is " if n=2, then n is even" a proposition ? P.S. I don't know where link of teaching for writing symbol of ...
5
votes
1answer
111 views

The Hyperreal number system

Currently reading Infinitesimal Calculus by Henle and Kleinberg. In this text, page 25, they note that they define a hyperreal number system, not the hyperreal number system. This is because "there ...
0
votes
1answer
35 views

if skolem($\alpha$) is valid then $\alpha$ is valid

I am trying to prove the following claim: let $sk(\alpha)$ be the sentence received from the skolemization of a given sentence $\alpha$. Prove : $\vDash sk(\alpha) \implies \vDash \alpha$ I tried ...
3
votes
1answer
45 views

Simplifying propositional logic

Hi I asked a question a few hours ago which has been solved but I got stuck on another exercise so I thought I'd reach out for some help. I have the premise: $((A \to B) \land (\lnot A \to C))$ ...
6
votes
0answers
74 views

Elementary submodels in stationary logic.

In the paper "Stationary Logic" by Barwise, Kaufmann and Makkai the authors prove that stationary Logic L(aa) has Löwenheim number $\aleph_1$, i.e. every satisfiable set of sentences has a model of ...
8
votes
6answers
971 views

“All true theorems are logically equivalent”

I've seen the phrase "all true theorems are logically equivalent" thrown around here, when people ask if a theorem X and a theorem Y are logically equivalent. What is meant by this? Are they just ...
1
vote
1answer
64 views

Prove or disprove wether the sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true

I got stuck at this problem for some hours: Determine whether the first-order sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true, where $Q$ is a 2-ary predicate ...
2
votes
2answers
60 views

Help with natural deduction (Propositional logic)

I'm trying to get to $(\neg A \to C)$ from the following formula: $$(A \wedge B) \vee (\neg A \wedge C)$$ I have attempted the following: $$((A \wedge B) \vee \neg A) \wedge ((A \wedge B) \vee C ...
0
votes
3answers
56 views

Verifying logic without drawing truth tables

Want to know is there a way to solve these sort of problems without drawing truth tables? I found that it's kinda time consuming drawing truth table for each question. Help pls. Check the images ...
1
vote
1answer
57 views

Using the notion of provability only, how to show that $\Gamma \nvdash \varphi$?

For a practical example, suppose I want to show that $\{ P\} \nvdash Q$. From completeness, this is trivial: just find a model where $P$ is true and $Q$ false. But suppose I am stubborn and I don't ...
3
votes
2answers
38 views

Rule of inference and truth table issue

Let P – Light is on Q – The switch is down R – The door is open ...
2
votes
2answers
39 views

Prove using Hilbert calculus $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$, formal proof.

Prove: $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$ Using Hilbert Calculus Format of solution: Step (my understanding) Solution: (1) $\forall x(Px\rightarrow x\equiv a)\vdash ...
1
vote
1answer
29 views

Problems with basic proof in modal logic (event based)

I am having trouble deriving the following basic result: $\ast$) For every $\omega \in \Omega, \omega \in P (\omega),$ from the following axioms: A1) $K (\Omega) = \Omega$, A2) $K (A) \cap K (B) ...
1
vote
1answer
38 views

Prove that iff a formula $\phi (v_1, v_2,…v_n)$ is satisfied in the substructure $\mathcal M$, then it is satisfied in structure $\mathcal N$

Assume $\mathcal M \subseteq N$ structures for signature $S$. $\mathcal M$ is a substructure of $\mathcal N$. Let $\phi(v_1, \cdots v_n)$ be a formula without quantifiers. Prove by induction on ...
0
votes
1answer
77 views

Hanf Numbers and Decidability

Currently reading J.L. Bell's Models and Ultraproducts and at the end of Chapter 4 section 4 the authors comment that "In spite of the fact that most languages can easily be shown to possess Hanf ...
2
votes
1answer
76 views

Determine under which conditions the formula $\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow \phi)$ is logically true

I am stucked at this problem for a long time: Determine under which conditions the following first-order formula is logically true $$\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow ...
4
votes
4answers
79 views

If $T$ a consistent set of sentences and $a,b$ sentences such that $T\vdash (a\rightarrow b)$and $T\vdash (\lnot a\rightarrow b)$ Then $T\vdash b$ [closed]

I am stucked at this problem for a long time: Let $T$ be a consistent set of first-order sentences and let $\alpha,\beta$ be sentences. Prove that if $T\vdash( \alpha\rightarrow \beta)$ and ...
2
votes
0answers
31 views

A fundamental question on relation between logic, formal system and mathematics.

I was reading this book titled "Godel - A Life of Logic, by J.L Casti and W.DePauli " In pages 30-32 he mentions how a formal system is developed by using a set of symbols as 'axioms' and a set of ...
3
votes
1answer
51 views

Generalizations of pregeometries

Combinatorial geometries and pregeometries are important in classifying strongly minimal (as well as O-minimal) theories. More formally, a model of a strongly minimal (or an O-minimal) theory with the ...
2
votes
1answer
46 views

Determine whether the given pair of statements are contrary, contradictory, or neither.

Consider the following pair of statements: All multiples of three are odd / Some multiples of three are odd. No triangle has an interior angle sum of zero degrees / Some triangle has an ...
3
votes
3answers
35 views

Proof Using Natural Deduction (including '=' rules)

I have a natural deduction proof that I'm stuck on. Obviously I'm not asking someone to just tell me the answer, but if anyone could help me with the next step/point out any mistakes I've made it ...
0
votes
0answers
56 views

Negating a conditional statement

Statement:If Fido barks, then Fido is a tree. Let p = Fido barks Let q = Fido is a tree. symbolic form $p \to q$ My attempt $p \to q $ is logically equivalent to $\lnot\ p \lor q$ ...
3
votes
1answer
59 views

Show that the set of all points $x \in \mathbb R$ where $f$ is differentiable is definable in $\mathcal M=(\mathbb R; +,-(), \cdot, \lt, 0,1,f)$

For the structure $\mathcal M=(\mathbb R; +,-(), \cdot, \lt, 0,1,f), n_f=1 $ show that the set of all points $x \in \mathbb R$ where $f$ is differentiable is a definable set. My issue here is how to ...
-2
votes
1answer
64 views

What is 0^0 ?? 0, 1 or not defined [duplicate]

What is the value of $0^0$ ?? I have read many discussions regarding it but the result was only confusion. Is it 0, 1 or not defined??
0
votes
1answer
15 views

Placement of quantifiers in a symbolic statement

I have the statement: Let $A_n$ be an indexed set of numbers defined by $A_n = n\mathbb{Z}_{\geq m}$ for $n,m \in \mathbb{Z}$. Consider the claim C: For all $n$, if $x,y$ is in $A_n$, then ...
1
vote
1answer
55 views

Prove by Natural deduction that $\lnot\exists xP(x)\rightarrow\forall x\lnot P(x)$

I got this problem: Prove by Natural deduction in First Order Logic that $\lnot\exists xP(x)\rightarrow\forall x \lnot P(x)$ I tried to prove it using the Contradiction Theorem but I got ...
2
votes
0answers
34 views

Example of language $\mathcal{L}_1$ and set $\Gamma_1$ s.t. $\Gamma_1$ is Henkin but not consistent

Question: Give an example of language $\mathcal{L}_1$ and set $\Gamma_1$ of $\mathcal{L}_1$-formulae such that $\Gamma_1$ is Henkin but not consistent Answer: Let $\mathcal{L}_1$ be arbitrary and ...