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 ...

learn more… | top users | synonyms (1)

1
vote
0answers
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?
-2
votes
1answer
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) ... ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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)...
0
votes
0answers
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 ...
1
vote
3answers
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 ...
-2
votes
1answer
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.
0
votes
1answer
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: ...
-3
votes
0answers
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 ...
0
votes
2answers
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....
0
votes
1answer
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$ ...
1
vote
3answers
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 ...
1
vote
1answer
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$ ...
2
votes
2answers
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 ...
0
votes
2answers
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 ...
10
votes
4answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
3
votes
4answers
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. ...
3
votes
3answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
-2
votes
1answer
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$?
2
votes
3answers
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 ...
5
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
6
votes
2answers
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.....
2
votes
1answer
45 views

First Order Logic Double Implication [on hold]

I have a Logic Assignment of First Order Logic that I have to prove an initial claim, but one of the equations is kind of confusing for me because it has double implication and quantifiers. $$\...
2
votes
2answers
45 views

Axiomatizing stacks and queues using first-order logic

In the textbook I'm using to prepare the logic exam says that first order logic may be used to implement axiomatize data structures. There is an example of that: "Stack": uses a language that ...
2
votes
1answer
54 views

Show that there's no such algorithm

Show that there's no such algorithm, $A$ which gets a sentence, $\varphi$ (a formula without free-variables) and returns $\varphi'$ such that: $\varphi$ is satisfiable iff $\varphi'$ is valid (meaning,...
6
votes
1answer
200 views

Russell's paradox from Cantor's

I learnt how Russell's paradox can be derived from Cantor's theorem here, but also from S C Kleene's Introduction to Metamathematics, page 38. In his book, Kleene says that if $M$ is set of all ...
4
votes
2answers
262 views

Definition of truth in first-order logic

Let $L$ be a first order language. Let $P$ be a predicate symbol from $L$, and $c$ a constant. Given an interpretation $I$ of $L$, a definition states The formula $P(c)$ is true in $I$ iff $c\in ...
1
vote
1answer
73 views

is there still interest in finitary/syntactic mathematical logic?

A lot of textbooks on mathematical logic now rely on set-theoretic tools (models and topology). do people still care about developing mathematical logic from finitary methods? is there still ...
0
votes
1answer
22 views

Show that an axiom in Hilbert Calculus is valid

Consider the axiom in Hilbert Calculus: $$(\forall x(A\to B))\to (A\to\forall x B)$$ Where $x$ is not free in $A$ I want to show that for evry structure $M$ and for every interpertation $\rho$, the ...
1
vote
1answer
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 ...
1
vote
1answer
56 views

Can multiple Boolean variables and equations be converted to a single integer variable and multiple modulo equations?

e.g. let $x,y,z \in \mathbb{B}$ (Boolean) and $w \in \mathbb{Z}$ (integers) and $p,q,r \in \mathbb{P}$ (primes) For $x$ let $(0,1)$ be represented by integers $(\overline{a},a)$ mod p For $y$ let $...
4
votes
3answers
129 views

How is a set subset of its power set?

This question is from S C Kleene's Introduction to Metamathematics, page 38: If we prescribe as admissible elements of sets (a) $\varnothing$ and (b) arbitrary sets whose members are admissible ...
0
votes
2answers
24 views

Is the 1-consistency of $PA$ necessary to prove that $\diamond^{m} \top\implies \diamond^{n} \top$ is false if $m<n$?

In The logic of provability, by G. Boolos, there is a remark in chapter 7 saying that $\diamond^{m} \top\implies \diamond^{n} \top$ is false if $m<n$ (unless $PA$ is 1-inconsistent). Now, it seems ...
0
votes
1answer
34 views

Express that a set is finite using symbols

Two related questions: What's the most elegant way to express that the set $S$ is finite using logical symbols? Obviously this will depend to some extent on what you allow yourself to quantify, so ...
8
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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....
3
votes
2answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
50 views

How to rewrite all the boolean operations using if-then-else operator?

Cited by Conditional Term Rewriting Systems: 1st International Workshop Orsay, France, July 8-10, 1987, p. 105 Additional Boolean operations are not needed, because all the usual Boolean ...
-5
votes
1answer
36 views

Gödel numbering for sequences Using the Chinese remainder theorem [closed]

I looked into some youtube videos and got a simple idea about Gödel numbering and Chinese remainder theorem separately.... But can't see how to use them as one. Wikipedia giving a way or may be its an ...