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
1answer
18 views

Equivalence of these propositions

Let $V$ be a $ \Bbb{K}$-vector space. Let $S$ be a subset of $V$, the $S$ is a subspace of $V$ if and only if: 1) $0_V \in S$ 2) $v, u \in S \implies v+u\in S$ 3) $c \in \Bbb{K}, v \in S \implies ...
2
votes
1answer
41 views

Peano and consistency, how to understand it rightly.

I'm struggling with the notion of consistency, and a few cases : I'm writing in the following $Con(T)$ to denote the arithmetic formula which expresses the consistency of $T$, for $T$ a consistent ...
0
votes
2answers
43 views

The problem of Free Variables in natural deduction rules ($\forall$, $\exists$, =).

I am in need of some clarification relating to the rules mentioned. I am doing two different courses on Logic (Philosophy / Computer Science departments) and unforunately they use slightly different ...
1
vote
2answers
61 views

Prove disconnectedness of a graph is not generalized first-order logic definable

I have proved the connectedness of a graph is not generalized first-order logic definable. How about the disconnectedness? Is it also not first-order logic definable? (A property $\Phi$ of ...
2
votes
1answer
52 views

Vaught's two cardinal theorem using Vaught pairs

I've been reading David Marker's Introduction to Model Theory, and found Vaught's two cardinal theorem (4.3.34): if a theory $T$ has a $(\kappa,\lambda)$-model, where $\kappa > \lambda \geq ...
0
votes
1answer
51 views

reduction from 3sat to 3 dimensional matching.

I've been reading about the standard reduction from 3sat to 3DM and my question was regarding the 'clean up gadgets'. So suppose i take an instance of 3-Sat with $n$ variables and $k$ clauses. Once we ...
0
votes
1answer
55 views

Fuzzy logic de morgan

i should show, that de morgan's law is also correct in the fuzzy logic: $\neg(A\vee B)$ could be written as: $1-max(a,b)$ $(\neg A) \land (\neg B)$ as: $min(1-a, 1-b)$ But how could I show, that ...
2
votes
1answer
31 views

Hilbert Calculus, Formal Proof Converse

I'm trying to find a proof of $\exists x\phi\rightarrow\exists y\phi^x_y$ in the Hilbert-calculus while working through a completeness proof for FOL on my own. Can anyone provide a proof of this ...
2
votes
1answer
51 views

“Every set is equinumerous to a well-founded set” - provable in $\sf ZF-Reg$?

What is the relationship of the following to other axioms of $\sf ZFC$? $\sf WB$: Every set $A$ is in bijection with a set well-founded by $\in$. Obviously, $\sf ZF$ implies $\sf WB$ (because ...
2
votes
2answers
61 views

Extended version of the theory of reals and its decidability

It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
2
votes
1answer
41 views

Writing a sentence that is true in one model and false in the other

Let $Σ=(R)$, where $R$ is a binary relation. Write a sentence that is true in $\mathcal M_1$ but false in $\mathcal M_2$: $$\mathcal M_1=(P(N),⊂)$$ $$\mathcal M_2=(N,<)$$ I've been ...
0
votes
4answers
63 views

Have I drawn this Venn diagram correctly?

Does this look correct? http://i.imgur.com/vmlpYD8.png I'm trying to find out whether this syllogism is valid (I'm guessing it's not valid) Many thanks
8
votes
0answers
137 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
69 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
50 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
109 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
71 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 ...