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)

0
votes
2answers
16 views

Seeking help with theorem proof (Propositional Logic)

During the beginning of my Logic class, my professor wrote a theorem on the board as an example, saying that it would be something we could easily prove after a few weeks in the course. I wrote it ...
0
votes
2answers
25 views

Why is the unique readability of wff's important?

I am reading Classical Mathematical Logic by Epstein. The author defines: $L(\neg, \rightarrow, \vee, \wedge, p_0, p_1, ...)$ i. For each $i=0, 1, 2, ..., (p_i)$ is an atomic wff, to which we ...
0
votes
1answer
43 views

How are variables introduced?

In natural deduction as far as I know after an $\exists\text{E}$ the resulting symbol is bound to a subcontext preventing us from a subsequent $\forall \text{I}$, then how, if in any way, one ...
0
votes
1answer
58 views

What does $\exists x:\top$ mean? [on hold]

Does it mean that something exists?
-1
votes
0answers
36 views

Is there a way to simplify the following logic proposition… [on hold]

Is there a way to simplify the following logic proposition? $$(A \implies B) ∧ ( C \implies D)$$ Thanks!
1
vote
3answers
29 views

What are m-placed relation symbols and function symbols?

In This Model Theory book, Weiss refers to "m-placed function symbols" and "m-placed relation symbols". Are these just supposed to be functions of $m$ objects and relations between $m$ objects? I'm ...
0
votes
1answer
48 views

Understanding direct proofs and proofs by cases?

I'm reviewing my book Mathematical Proofs a Transition to Advanced Mathematics and looking to understand things at a deeper level. I will try to explain what I've considered so far in regards to this ...
3
votes
1answer
74 views

Is there a formal way to show that $X \cap Y \subseteq X$.

The question is in the title. It is trivial that $X \cap Y \subseteq X$. Because $X \cap Y$ only contains elements that are both in $X$ and in $Y$. So every element in $X \cap Y$ is also an element of ...
1
vote
1answer
37 views

Two questions about first order theories having only finite models.

Let T be a consistent theory formalized in the first order predicate calculus, all of whose models are finite and have cardinal numbers less than some positive integer n(T). Is T necessarily decidable?...
0
votes
1answer
37 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
21 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
33 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
104 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
75 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
29 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
1answer
27 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
65 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
32 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
61 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
19 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
87 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
98 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
55 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
90 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
24 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
178 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 ...
2
votes
1answer
57 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
92 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
60 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
51 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
65 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
96 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
28 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
67 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
26 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
483 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 [closed]

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
47 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
264 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
74 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
23 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 ...