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
0answers
89 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
2
votes
0answers
21 views

Determine if the members of a set can be made to equal a given number

Is there an easy way to determine if some combination of addition, subtraction, multiplication, and division will enable the numbers in a set to equal a given number? For example, if I have the ...
2
votes
1answer
32 views

If $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable?

In propositional logic, if $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable? I proved that at least one of $\Sigma \cup \{ ...
2
votes
3answers
46 views

Logical Equivalence

Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. ...
-2
votes
1answer
36 views

Methods of Proof and Disproof [closed]

If $2b^2 – 3ab + 1$ is even, then $2a-b$ is odd, where $a,b \in \mathbb{Z}$. If $5x-y$ is divisible by $4$ and $2x+3y$ is odd, then $7x + 2y$ is odd, $7x+2 \in \mathbb{Z}$.
0
votes
2answers
35 views

Another basic Logic Question

Translate this statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) ∀x(C(x) → F(x)) The answer given in the book is:"Every ...
0
votes
1answer
55 views

Very Basic Logic Question

Given a set $S=\{-1,0,-5,-4\}$.Then is the following proposition true? $\forall x, (x>0 \implies x^2>0)$.
2
votes
0answers
31 views

On Levy's formal definition of class terms

I've been reading Levy's Basic Set Theory and it has recently been drawn to my attention a certain problem with Levy's definition of formulas and terms in his extended language (section I.4.1) (well, ...
0
votes
1answer
58 views

Using Sequent Calculus to prove $\exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ]$

I need to prove the validity of the following formula using the sequent calculus LK: $$ \exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ] \text{.} $$ I already had a look ...
0
votes
1answer
18 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...
6
votes
1answer
28 views

Proving consistency by constructing models? How and why?

A theory T1 can be shown to be consistent by describing a model for it. But usually the model is also described in words, using terms from some other theory T2. So unless T2 is also consistent this ...
3
votes
1answer
66 views

Are there weak versions of the axiom of choice equivalent to weak versions of Zorn's lemma and similar principles?

I recalled reading about other weaker forms of $AC$, for example countable choice, where we could make choices from a sequence $(S_{k})_{k \in \mathbb{N}}$ of non-empty sets. I also recalled mention ...
0
votes
1answer
52 views

Proving “If $P$ and $Q$ then $R$”.

I want to prove the statement: If $P$ and $Q$ then $R$. I have proved the statement: If $P$ then $R$. I am done. Right? I want to prove the statement: If $P$ or $Q$ then $R$. I have proved the ...
2
votes
2answers
50 views

Predicate logic by resolution

I've been trying to study logic lately, as part of my AI course, and I've been going through some old, simple exam questions from my school. There is one question about resolution in particular that I ...
0
votes
1answer
38 views

When representable functions are recursive

I'm trying to show the following statement: A representable function in a true, effectively axiomatizable theory is recursive. I'm missing one step in my proof: I need to show that the relation: $ ...
0
votes
2answers
32 views

Isomorphism of a theory

So, I'm preparing for an exam and there are various examples regarding isomorphism, what I don't get at all. I don't seem to be able to grasp the idea of isomorphism. Could you explain please how does ...
1
vote
1answer
26 views

Finite extension of decidable theory is decidable

Exactly what it says on the tin. I'm trying to prove that if T2 is a finite extension of decidable theory T1, then T2 is decidable.
0
votes
0answers
23 views

Logic - “Small model property” for a signature with only binary predicates

The Lemma - Small Model Property says that if a monadic formula phi (i.e. over a monadic signature - contains only constants and (monadic) unary predicates) with k unary predicates is satisfiable, ...
3
votes
3answers
44 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
57 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
57 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
40 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
159 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 ...
5
votes
0answers
43 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
22 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
127 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
58 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
61 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
75 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
57 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
51 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
28 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
42 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
50 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
37 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 ...