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
2answers
43 views

How is the set of all even numbers definable (from $\omega$)?

This Set Theory textbook (page 89) defines definable sets as follows: Definition 6.8. Given a set $a$ and a formula $\Phi$ we define the formula $\Phi^a$ to be the formula derived from $\Phi$ by ...
1
vote
0answers
16 views

Semantic restrictions for $\forall$-introduction and $\exists$-elimination

I don't understand how the semantic restrictions for $\forall-$introduction and $\exists-$elimination work. These are $\dfrac{\Gamma \vdash \phi}{\Gamma\vdash \forall x\phi}, (x\notin FV(\Gamma))\quad$...
3
votes
1answer
52 views

About Jean-Yves Girard

I am student and I'm studying linear logic. I saw a quote in a book: "I'm not a linear logician" - Jean-Yves Girard. Tokyo, April 1996. I searched on google but I did not find the context of why he ...
0
votes
1answer
45 views

understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
0
votes
0answers
14 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
1
vote
0answers
8 views

Proving logic equivalences

How to prove elementary rules like $\phi\land\phi\iff\phi$ or $\phi\land\psi\iff\psi\land\phi$ without using truth tables? I want to show it using the rules for the connectives, for example the rules ...
2
votes
4answers
56 views

How do you prove that $p → q$ is equivalent to $p \lor q ↔ q$?

I gotta draw $p \lor q ↔ q$ from $p → q$, logically. not by a truth table. While it seems obvious, I cannot find a formal proof. This is how far I came up to: $\quad p \lor q$ $\equiv (p \land T) \...
0
votes
0answers
40 views

What is the best book on mathematical logic

What is the best book on mathematical logic, the most complete, the most formal, and the most up to date? PS: price doesn't matter.
1
vote
0answers
26 views

Prove universal gate math

I tried to deal with this question: $$F(a,b,c,d) = (a'+b'+c')\oplus bcd$$ While I asked to prove that F with the constant '$0$' is universal gate. I know that to prove that some function is ...
1
vote
2answers
47 views

Basic: Sequent definition, and-introduction, and iff

I am reading through "Mathematical Logic by Ian Chiswell & Wilfred Hodges"(amazon, and publisher) So far have it has covered $\land$-Introduction and $\land$-Elimination Sadly this text only has ...
1
vote
3answers
64 views

How to simplify using algebra laws

Simplify the following by using algebra laws. (i) X’.Y’ + X.Y.Z. + X’.Y + X.Y My attempt: X’.Y’ + Y(X.Y.Z + X'Y + X.Y) X’.Y’ + (X.Z + X' + X) X’(X’.Y’ + X') + X.Z + X Y’ + X' + X.Z + X Y’ + X' +...
0
votes
1answer
28 views

Predicate Logic - Archimedes' Library

Problem: Our class takes a field-trip to Archimedes’ Library. Before entering the library, your tour guide makes you notice the sign on the main doors which reads: “Observe the Rule of Archimedes’ ...
0
votes
1answer
14 views

How can I translate this sentence into predicates and quantifiers?

sentence : Every cube is larger than something else. My Working: P(x) = x is larger than something else ∀xP(x) But the answer is something completely different. ∀x (A(x) → B(x)) : the answer ...
1
vote
1answer
23 views

Not getting how to prove reverse hypothesis.

This is a theorem from Dummit & Foote text- Let $G$ be a group acting on the non-empty set $A$.The relation on $A$ defined by $a \sim b$ iff $a=g.b$ for some $g \in G$ is an ...
5
votes
1answer
50 views

Proof of $(\neg A \supset A) \supset A$

As a (total) beginner in logic, I read this introduction : http://www.loria.fr/~roegel/cours/logique-pdf.pdf (in french). They give an exercise I couldn't achieve. Could someone help me (give an ...
0
votes
0answers
14 views

Number of Minimally Functionally Complete (adequate) ternary Operators Sets and what they are

Is there a simpler way than through trial and error to determine the number of Minimally Functionally Complete Operator Sets (MFCOS) (or adequate operator sets) for a given arity and what those ...
2
votes
1answer
50 views

A Puzzle on Infinity: How to guess the color of hats? [duplicate]

Infinitely many (i.e. $\omega$ - many) people each have either a white hat or black hat on their heads. Each person can see everyone's hats except their own. Each person simultaneously announces a ...
1
vote
1answer
35 views

Is this non-constant function periodic for every definable number?

Given the set $\mathbb{D}$ which contains all definable real numbers. The definition must not be infinite long. E.g. it contains $12$, $-3$, $\frac{1}{12}$, $\sqrt{2}$, $\pi^2$, $i+e$, Chaitin's ...
1
vote
1answer
74 views

Contradiction in Davis–Putnam–Logemann–Loveland (DPLL) Method?!

As we see on page $10,11$ and $12$ on Google Books we know about Unit Clause (UC) and Pure Literal (PL) in DPLL Algorithms. in the following example if assign value $0$ to variables is prior to ...
1
vote
3answers
71 views

What does “consistency” mean if formal systems are inherently meaningless?

In the book Gödel's Proof by Ernest Nagel and James R. Newman, the authors insist that formal systems are to be considered as meaningless mechanical systems, which yield theorems by merely applying ...
2
votes
0answers
24 views

Software for solving first-order logic

Is there any class of software that can help me with the following problem in first order logic: given $\phi$ a formula with a "hole" in it (a subformula which is undetermined) and a particular set of ...
0
votes
2answers
430 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
8
votes
2answers
495 views

Was Smullyan really wrong?

EDIT: the OP has since edited the question fixing all the issues mentioned here. Yay! There was a question asked on Puzzling recently, titled ...
1
vote
1answer
52 views

How should I interpret this exercise from Chiswell & Hodges Mathematical Logic?

Exercise 5.4.7 on page 127 of Chiswell and Hodges "Mathematical Logic" is: Let $\sigma$ be a signature, $r$ a term of qf LR($\sigma$), $y$ a variable and $\phi$ a formula of qf LR($\sigma$). Let $...
0
votes
0answers
13 views

Showing a function, defined by bounded maximization of a parameter where another function is zero, is primitive recursive [on hold]

Let $g:\mathbb N^2 \to \mathbb N$ be a primitive recursive function and define $f: \mathbb N \to \mathbb N$ by $f(n)$ = largest $m$ such that $m \leq n$ and $g(n,m) = 0$. If there is no such $m$, set $...
0
votes
3answers
48 views

vacuous truth -> empty set is both included and not included in every set?

I understand the concept of vacuous truth and its use in showing that the empty set is a subset of every set. Based on my understanding of vacuous truth (for example https://en.wikipedia.org/wiki/...
0
votes
0answers
19 views

Henkin theory follow complete

Assume that Γ is a a Henkin theory. For any two constants c,d, either $\Gamma \vdash c=d$ or $\Gamma \vdash c \neq d$. There are two constants a,b such that $\Gamma \vdash a\neq b$.Show that Γ is a ...
1
vote
1answer
48 views

Formulating a problem in terms of set theory

Here is one problem I was trying to solve just by trial-and-error method. However, I was thinking about how to write the clear solution using set theory. Problem: A notebook contains exactly $100$...
1
vote
3answers
121 views

$1+1=2$…but Why? [duplicate]

A study that was carried on recently showed that even babies at the age of few months know that $1+1=2$. My question is : is this a fact that can be proved, or is it a just a postulate as those in ...
0
votes
0answers
58 views

How mathematics would be different if the first derivations, conjectures and theorems would be others? [on hold]

I've realised that mathematics is nothing else that an implication of some assumptions (plus the assumptions themselves, of course). We have axioms and we derive new "things", new rules, ideas, ...
1
vote
2answers
348 views

Prove $( \lnot C \implies \lnot B) \implies (B \implies C)$ without the Deduction Theorem

The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using ...
0
votes
1answer
30 views

can you help me to transform ∀x FO logical formula to it equivalent ¬∃ formula?

i have this formula ∀x ∀y (A(x,y) V A(y,x) → B(x,c1) ∧ B(y,c2) ∧ c1≠c2) to the equivalent formula that start by ¬∃x ¬∃ y ? you will find the question here ...
7
votes
2answers
161 views

Gödel's ontological proof and “modal collapses”

Recent findings on Gödel's ontological argument allowed to ultimately establish a couple of things: Gödel's original axiomata are inconsistent Scott's variation instead is consistent Scott's axioms ...
2
votes
1answer
42 views

An infinite set of axioms in ZF? What does that mean?

Before write this question, I lookeded around enough in this forum for a possible answer and although there are many similar questions, I couldn't find one answer which understand or satisfies me. I ...
-2
votes
1answer
28 views

Answer key to Peter Smith, “An Introduction to Formal Logic”, exercise 13.C.11

If A, B are tautologically inconsistent, then so are $\neg A$ and $\neg B$ This statement is from question C11 at http://www.logicmatters.net/resources/pdfs/answers/Exercises13.pdf, which the answer ...
0
votes
1answer
25 views

True or falsehood of open formula under a fixed interpretation

Given the open formula: $\alpha =(\exists{{x}_{2}})({P}^{1}({x}_{1},{x}_{2}))$ And consider the interpretation $I$ where the domain is the natural numbers, and ${P}^{1}$ means equality. Is $\alpha$ ...
1
vote
1answer
30 views

Reasoning informally about $\{x \in B \mid x \notin C\} \in \mathscr P(A)$

Attempting to apply more flexible, informal reasoning to predicate logic as demonstrated helpfully to me by another user in answer to my last question. $\{x \in B \mid x \notin C\} \in \mathscr P(A)$ ...
3
votes
2answers
23 views

Rewriting $\mathscr P(\bigcup_{i \in I} A_i)\not\subset\bigcup_{i \in I} \mathscr P(A_i)$ in more fundamental terms.

Working through Velleman's "How to Prove It" and currently having a bit of difficulty with a problem where I'm asked to rewrite this: $$\mathscr P\left(\bigcup_{i\in I} A_i\right)\not\subset\bigcup_{...
0
votes
1answer
38 views

Why is $p{\implies}q$ defined to have a truth value if $p$ is false? [duplicate]

At first it would seem that if $p{\implies}q$ means "$p$ implies $q$", then if $p$ is false then the entire statement doesn't make sense. It looks like if we have no way of knowing whether $p$ implies ...
3
votes
5answers
84 views

expanding requirements for equivalent conditions

We have all seen statements about equivalent conditions, such as If any one of the following three conditions hold, then all three conditions hold. Are there any examples of three conditions which ...
0
votes
0answers
12 views

Unary relation in a logical sentence

I'd appreciate help with this sentence: Let there be a language L and a structure M, and I need to prove the following sentence is logically false: $$\varphi :\exists xR(x)\rightarrow \forall yR(y)$$ ...
2
votes
0answers
30 views

Show that the law of the excluded middle does not hold in a BCCC

I want to show that the law of the excluded middle do not hold in a bicartesian closed category (BCCC), interpreted as follows: In general, there need not be a morphism $1 \to A + 0^A$ for $A \in \...
1
vote
1answer
46 views

What are the different ways to get a first-order formula that express the statement“$P$ is the $n$-th prime”

I know that such a $2$-predicate formula exists since Enderton's have already constructed such a formula in his text on mathematical logic but it was not easy to remember so I wonder if there is other ...
1
vote
2answers
164 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
0
votes
2answers
47 views

Natural Deducion: assumptions can be used more than once?

Im trying to prove: $ \forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x)) \vdash \forall{x} \sim P(x,x)$ What i have: $\forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x))\;$ Premise $ \forall{y}...
2
votes
1answer
4k views

Boolean Logic Converting DNF to CNF

I'm confused on how to convert DNF to CNF. On the answer sheet my teacher gave me, she just convert it right away with no explanation. So my teacher convert $F: (A \wedge \neg B) \vee (B \wedge D)$ ...
0
votes
1answer
26 views

Using separators as functional symbols in first order logic

Suppose we have the following definition of a term: A $term$ is: $x$, where "$x$" is a variable $c$, where "$c$" is a constant symbol $f(\tau_1,...,\tau_n)$, where "$f$" is a ...
1
vote
2answers
29 views

Predicate logic: $(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi))$

Given $L$ language and $\varphi$ and $\psi$ are formulas. Needs to show that is happening in general: $$(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi)...