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)

3
votes
3answers
45 views

Is $\Diamond (p \rightarrow q) \rightarrow (\Diamond p \rightarrow \Diamond q)$ valid in K?

The modal logic K is the weakest normal modal system, comprised by classic logic augmented by (K), the necessity distribution axiom schema: $$\Box (\alpha \rightarrow \beta) \rightarrow (\Box \alpha ...
39
votes
9answers
3k views

Does mathematics become circular at the bottom? What is at the bottom of mathematics? [duplicate]

I am trying to understand what mathematics is really built up of. I thought mathematical logic was the foundation of everything. But from reading a book in mathematical logic, they use ...
2
votes
2answers
58 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
3
votes
1answer
58 views

Are all models of Peano arithmetic elementary equivalent?

By Löwenheim-Skolem we know there are models of (first order) PA that are not isomorphic to the standard model, but are elementary equivalent to it, i.e. they satisfy the same set of first-order ...
1
vote
2answers
27 views

Axiom of separation for $n$ tuples or $n$ place predicates

The axiom of separation seems to only work when you are using an arity 1 type predicate, how then can we form relations? I know the power axiom allows for you to work with a set of subsets and in turn ...
2
votes
2answers
41 views

Need help with checking whether a predicate logic formula is a tautology.

I have an example like this, and I don't know how to solve it (check if is tautology): $\left(\exists_{x} \forall_{y}: q(x,y) \Rightarrow \forall_{y} \exists_{x}:q(x,y)\right)$ So the question is how ...
5
votes
1answer
160 views

Since arithmetic has a model (thus it is consistent) why care if consistency can't be proved?

Since arithmetic has a model, the numbers as we know them, it is consistent. Why do we care if consistency can't be proved within arithmetic? Do I miss something, ie in what we can consider a model?
-1
votes
0answers
19 views

Wolfram with predicates any posibility?

Hi everyone i need some help. I would like to check on wolfram is it tautology something but when type in it (that the simplest example:)) : $ForAll[x, p(x)~~or ~~q(x)]$ i'm getting error. Is there ...
1
vote
1answer
49 views

Introduction to Symbolic Logic: 'Understanding Symbolic Logic, 2nd Edition,' by Virginia Klenk, Page 294

I read this passage in my textbook: ...if there is a counterexample in a domain with $m$ individuals, then there is also a counterexample in all larger domains. It follows by contraposition (and ...
6
votes
0answers
48 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
0
votes
2answers
23 views

How do you find the minterm list of a boolean expression containing XOR?

Let's say I have a boolean expression, such as F1 = x'y' ⊕ z . How do I go about finding the minterm list for that expression? The method I've tried is to take each term, such as x'y' and z, ...
5
votes
2answers
128 views

A Knight and Knave Problem

There are $69$ people in a room, of which $42$ are truth-tellers (they always tell the truth) and the rest are liars (they can lie or tell the truth). You are allowed to ask any person $A$ whether ...
3
votes
0answers
76 views

How can temporal and epistemic logic be combined?

Recently I read all kinds of work from logic scientist in which epistemic logic was the main topic. Where epistmic change refers to change in knowledge of some agent in a multi-agent system (in a ...
2
votes
1answer
59 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
1
vote
1answer
15 views

Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...
2
votes
2answers
62 views

Logic vs. type system

What's the difference between logic (in a narrow sense, i.e. a logical system such as ZOL, FOL, etc.) and type system? I will sketch my understanding of this -- please correct if I err. Under ...
0
votes
1answer
35 views

Proof that given an empty vocabulary, P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not definable.

Hi there i would like to prove this: Given an empty vocabulary L ( by empty I mean L = $\emptyset$), the property P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not ...
-3
votes
4answers
77 views

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$ [closed]

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$. I need to prove it by using equivalent sentences.
2
votes
1answer
26 views

Modal Logic: ◊-Distribution

It's a theorem of K that $\diamond$ distributes to disjuncts and vice versa: $$\diamond(p \lor q) ≡ \diamond p \lor \diamond q$$ Does it distribute to negated disjuncts? Is the following a licit ...
0
votes
1answer
76 views

What is the arithmetic flaw/contradiction in The Paradox of the Knower?

I have linked and quoted from an article below, he states that there is some elementary contradiction based upon simple logic/arithmetic; I am failing to see the contradiction. Where/what is the ...
2
votes
1answer
50 views

If a theory over a vocabulary $L$ has a model with countable domain, then it has a model with uncountable domain

For a homework I have been ask to prove that if a theory $\Sigma$ over a vocabulary $L$ has a model with countable domain, then $\Sigma$ has a model with uncountable domain. I have no idea how to ...
4
votes
2answers
191 views

Gödels incompleteness vs incompleteness

This has been nagging me, and might be an unfit question, but still: I've been taught that completeness of a theory $T$ means that for any sentence $\varphi$ in the language of the theory, we have ...
5
votes
0answers
60 views

What are some arguments/counterarguments for Zeilberger's “proof certificates”?

Here is the quote I wish to ask about: "I speculate that similar developments will occur elsewhere in mathematics, and will 'trivialize' large parts of mathematics, by reducing mathematical ...
1
vote
1answer
53 views

Proof that an property is definable if and only if its axiomatiazable and its complement its axiomatizable

For a homework of first-order logic I need to prove that a property, lets call it P, is definable if and only if P is axiomatizable and the complement of P is axiomatizable. I have no idea of how to ...
2
votes
1answer
29 views

Semi decision procedures for Peano arithmetic?

Is there an efficient semi-decision procedure (i.e. an algorithm that sometimes works and sometimes not) for -at least- elementary problems in peano arithmetic? I am not talking about weak fragments ...
0
votes
0answers
107 views

What to teach in Set Theory & Logic Course. [migrated]

I will be teaching a third-year introductory course on Set Theory and Logic soon and was hoping to get advice from this community. I would rate my students' proof abilities as weak and was hoping to ...
1
vote
1answer
34 views

Logic normals forms, wolfram, problem.

This is formula which I must write as CNF, DNF and Negation of formula as CNF and DNF: $$(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow \neg r) \rightarrow (p \rightarrow \neg q))$$ ...
1
vote
3answers
43 views

When I can reverse the logical operators?

I heard say that is logically equivalent to say it: $$\neg (p \vee q) = p \land q$$ So every time you have a negation operator in front can make a "distributive" altering the operator from within? ...
0
votes
1answer
27 views

Logical implications in classic logic

I have the following problem: If Joseph is playing piano or Joaquim is playing guitar, then John is not sleeping. I perfectly understood the situation but didn't understand the second row of ...
1
vote
1answer
51 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...
1
vote
0answers
26 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
2
votes
2answers
40 views

Difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$

Existential quantifier confusion: what is the difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$? What are the differences between those two ...
2
votes
1answer
49 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
1
vote
1answer
59 views

Python Integer Game

Jacob and Vicky play the fun game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Jacob always starts with p = 1, does his multiplication, then Vicky multiplies the number, ...
4
votes
3answers
49 views

Can I simplify: $(¬P ∧ Q) ∨ (P ∧ ¬Q)$?

I got stuck on this development: $$\begin{align} (¬P ∧ Q) ∨ (P ∧ ¬Q) & \iff ((¬P ∧ Q) ∨ P) ∧ ((¬P ∧ Q) ∨ ¬Q) \tag{1} \\ &\iff (P ∨ Q) ∧ (¬P ∨ ¬Q) \tag{2} \\ \end{align}$$ Can't this ...
5
votes
1answer
68 views

Does a proof by contrapostion guarantee an alternative direct proof?

If $ P \Rightarrow Q$ is true and can be proved by "directly proving" its contrapositive $ \lnot Q \Rightarrow \lnot P $, does the former, necessarily, also have an alternative direct proof? ...
0
votes
1answer
39 views

Unclear why (first order) satisfiability undecidable and not semi-decidable.

Hoping this will just be a terminology question, otherwise I have a bigger problem of harboring a misunderstanding re: decidability. We know that (first order) satisfiability (for the general case of ...
0
votes
0answers
32 views

What are non-monotonous computable convergent sequences of rationals with non-computable rate of convergence?

A computable convergent sequence of rationals can have a non-computable rate of convergence. By a rate of convergence of a sequence $(q_k)_k$, I mean a function $f : \omega \rightarrow \omega$ such ...
1
vote
0answers
35 views

What is the connection between game theory and (modal) logic?

I'm interested in dynamic epistemic logic lately (reasoning about information and change in multi-agent systems). I also like game theory. I'm looking for some good resources about the connection ...
0
votes
1answer
63 views

Mistake in http://plato.stanford.edu/entries/type-theory/#2

There seems to be mistake in http://plato.stanford.edu/entries/type-theory/#2: First-order logic considers only types of the form $i,…,i → i$ (type of function symbols), and $i,…,i → o$ ...
-1
votes
0answers
19 views

given a language L proof via direct reduction ATM < L.

Regarding my previous question: Direct Reduction, Turing machine and a DFA here agaian: > L ={ < M , D >| M is s TM and D is a DFA so that L(M) = L(D)} ...
1
vote
1answer
43 views

Prove that the class of non-standard models of arithmetics is not axiomatizable

Given the language of arithmetics $L=\{0, 1, +, \cdot\}$ one should prove that the class of all non-standard models is not axiomatizable. So basically we have (for $M$ - standard model of ...
0
votes
0answers
30 views

Direct Reduction, Turing machine and a DFA

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
1
vote
2answers
100 views

How to prove that $1=2$ from $0<0$

Maybe a simple question, but I heard that an inconsistent theory can imply everything. For example: How to prove that $1=2$ from $0<0$.
0
votes
0answers
18 views

Direct Reduction, Turing machine and a DFA [duplicate]

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
1
vote
0answers
18 views

Prove that class of models isomorphic to some infinite model $M$ is not countably axiomatizable

In a related question the author posted similar problem for finite models, and stated that in case of an infinite model the class of models isomorphic to the given one is not with FO-axiomatizable, ...
1
vote
1answer
23 views

Can I use logical equivalence instead of biconditional in proofs?

My textbook defines the symbol <=> to mean equivalent to, has the same solutions as or if and only if. It defines the symbols => and <= to mean implies or leads to. The textbook does not use the ...
1
vote
2answers
59 views

Strange logic question, truth of predictions

1: Half of my predictions come true; 2: I predict A; 3: I predict B. Now, suppose A come true, so that the prediction 2 is true; and B come false. So, half of my predictions came true and 1 is also ...
2
votes
1answer
33 views

First Order Theories

Are there first order theories where every sentence or its negation is a theorem of the theory? I know there are many examples of theories without this property, such as fields and statements such as ...
0
votes
1answer
54 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...