Tagged Questions

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

23 views

Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
14 views

Chain of implications shows equivalence of several conditions

In mathematical articles, theorems frequently have the following form: The following (conditions) are equivalent: (first condition) (second condition) (third condition) ... ...
26 views

Difference between set theory proof and logic proof of complete induction

Set theory proof: Let $\mathbf{A}$ be the set such that $\{0,1,2,...,n\} \subset \mathbf{A} \implies n+1 \in \mathbf{A}$. Our goal is to show that $\mathbf{A} = \mathbb{N}$. To do this, we construct ...
84 views

What are “words”?

Related but not duplicate. I am reading Classical Mathematical Logic by Richard L. Epstein, page $3$: B. Types When we reason together, we assume that words will continue to be used in the ...
56 views

Does anyone know a no-nonsense intro to “logic for mathematics” that I can give to a Year 11 student?

I'm looking for material on propositional and first-order logic to give to a Year 11 student that explains how they're used "in practice." For example, I want to be able to write the null-factor law ...
22 views

Limits to the principle of explosion

In propositional logic, the principle of explosion can be proven in the following way. $\phi \wedge \neg\phi$ (hypothesis) $\phi$ (simplification, 1) $\phi \vee \psi$ (disjunction introduction, 2)...
13 views

model definitions for tautology, contradiction, and connectives quantify too much, no?

Occasionally I come across a definition based on what will happen in all models, for example, that a contradiction is a statement that is false in all models, that a tautology is a statement that is ...
59 views

Is there a 'definition' of truth based on sets of true statements?

been thinking a fair bit about how to think about truth recently. I at one point came up with a deficient theory of truth based on provability, and was directed to Tarski's semantic theory of truth ...
29 views

How to translate this statement to First Order Logic?

“Thus there exists a pet in this house being a cat or a dog” I am unsure of how this statements should be translated.
56 views

Olympiad Books for Primary Students

I am a teacher of gifted program in primary school and currently I am developing Olympiad Curriculum (topic-wise) for my students. I have those topics that could need some help in terms of questions: ...
18 views

Math logic which contains sum

I want say the following sentence in math logic but I don't know how to address the sum in the logic. The sentence is: Correlation(x->y) equals to (For all C as clusters, for all exists members in C ...
84 views

Is there an error in this textbook about Peano Arithmetic?

I encountered this doubt in an online intro-logic open course offered by Stanford Uni. Under the section 9.4 of this textbook here: http://logic.stanford.edu/intrologic/secondary/notes/chapter_09....
33 views

Can someone explain to me this logic sentence using entailment?

Can someone please explain me what does it exactly mean? $KB \wedge B^- \not\models\square$ I understand the entailment symbol in this example here : $T \models A$ is if there's no model of $FS$ ...
87 views

When is the Law of the Excluded Middle Valid/Not Valid?

Sometimes, you can use the Law of the Excluded Middle (LEM) to validly prove things by contradiction (e.g. irrationality of sqrt(2)). However, at other times, you can not, for example when you have ...
53 views

Resolution Algorithms and one Example Problems?

We have a problem in one Resolution question. There is $5$ clauses, and want to prove the $6$th clause is true. which of the following clause is need more than one times to prove $6$th clause? $t$ ...
87 views

A 3-valued mathematical logic?

Classical propositional logic is consistent and in conformity with human language. A formal statement is true or not true and it is possible to develope rules with which it is possible decide which ...
23 views

Chartrand Mathematical Proofs 3e Exercise 5.45

I am self-studying this book, and I'm not sure if there is a typo in this question, or there is a gap in my understanding. The question is: Let $R(x)$ be an open sentence over a domain S. Suppose ...
170 views

How do we know logic works? [duplicate]

Every time I read about a theory in mathematics, it usually starts with axiomatizing the most fundamental concepts that are going to be treated. Recently, I have started finding this troubling. In ...
55 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
31 views

uppersemilattice end extensions

I'm trying to modify an argument in Jockush and Slaman's paper On the $\Sigma_2$ theory of the upper semilattice of the Turing degrees. One of the major hurdles is that I don't actually see why a ...
87 views

Why does “if and only if” mean the exact same thing as “precisely when”?

The proposition "A precisely when B" states that A has the same truth value as B. The proposition "A if and only if B" states that A is true if B is true and that A is true only if B is true. ...
59 views

Prove that $(p \to q) \to (\neg q \to \neg p)$ is a tautology using the law of logical equivalence

I'm new to discrete maths and I have been trying to solve this: Decide whether $$(p \to q) \to (\neg q \to \neg p)$$ is a tautology or not by using the law of logical equivalence I have ...
35 views

Proving a formula is valid

Let a formula $A$, and a term $t$ such that $x\in FV(t)$. Show that $\varphi = A\{t/x\}\to \exists x (x=t\to A)$ is valid. So let's assume by contradiction that the formula isn't valid. Therefore ...
38 views

Formalizing a self referential sentence

In The logic of provability, by G. Boolos, we are asked to ponder about this statement: If this statement is consistent, then you will have an exam tomorrow, but you cannot deduce from this ...
49 views

Are the conditionals equivalent: $p → q ≡ q → p$?

I know that a conditional is if $p$ then $q$, but is that equivalent to saying if $q$ then $p$? Is $p → q$ saying the same as $q → p$?
64 views

Negating the statement $\exists x \in \Bbb R$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$

There exists a real number $x$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$. I would like clarification on how to negate this. My idea of negation is ...
94 views

Meta proof-searching

Suppose you have a particular theory (ex: $ZFC$) in which you want to prove a statement $\phi$. One can attempt to find a proof of $\phi$ that can be verified, but another tactic can be to find a ...
27 views

Monadic signature with constant

Consider a signature $\Sigma = \{ P^1, R^1, c\}$. Where $P^1, R^1$ are unary predicates, and $c$ is a constant. Let A be a formula in FOL over $\Sigma$. Prove/Disprove: If A is satisfiable ...
63 views

How could we formalize the introduction of new notation?

What I am thinking about is how in a textbook/proof/theorem/discussion/definition one states that from now on a new notation will be used in the appropriate scope. Example: Let $V^*$ denote the ...
23 views

Sequents: if-introduction and discharging assumptions

I am reading through "Mathematical Logic by Ian Chiswell & Wilfred Hodges"(amazon, and publisher) for context I am reading through this for self-study, so I don't have the normal support of a ...
479 views

What is the correct definition of a group?

What is the correct definition of a group? More precisely the predicate "being a group"? According to Wikipedia A group is a set, G, together with an operation • (called the group law of G) that.....
45 views

20 views

Algorithms for type checking, typability and inhabitation problems?

Studying typed lambda calculus, I was asked the following questions: (1) Given a lambda term $M$ and a type $\sigma$, does one have $\vdash M : \sigma$? That is, is $M$ of type $\sigma$? (type ...
56 views

64 views

How math help reduce terms and conditions of someone's dying wish?

Good morning everyone... This is my very first question here, so I apologise in advance for any wrongdoing which I possibly make unintentionally. So here is a little background story. I'm working at a ...
27 views

Relating taking the power set to logical operations

I'm an undergraduate math major reviewing "Mathematical Proofs, A Transition to Advanced Mathematics" and specifically the first two chapters on sets and logic. I'm trying to find ways to write set ...
58 views

If P then not Q and if not P then Q. What is the relationship called?

Is there a name of this relationship? P => Q and ~P => ~Q seems to be called equivalence. But could not find a name for P => ~Q and ~P => Q by cursory googling and browsing related Wikipedia articles....
31 views

Quantification = statement about an open sentence?

The book I'm reading is talking about quantification being a method to convert open sentences into statements. From what I can see this method boils down to making a statement about the solution set ...
106 views

Russell's paradox in the language of modern mathematics

In the Wikipedia article about Russell's paradox the authors present the naive set theory as a first order theory (as far as I understand), but without references. Can anybody share some references ...