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)

3
votes
2answers
29 views

prove or disprove logical inference

I need to prove or disprove the logical inference of the formula b from formula a: $$ a = \exists y (\forall x P(x) \implies Q(y)) $$ $$ b = \forall x (P(x) \implies \exists y Q(y)) $$ $$ P(x) \...
0
votes
1answer
23 views

Formula to calculate Price of Service

I would like some help in elaborating a formula for a service I will be providing, to a retailer's clients. In simple terms I would be payed a 5% percentage over the price of the clients purchase, ...
2
votes
1answer
23 views

Confussion about substitution use and free variables requirement for rules of inference in natural deduction

In our course of logic we've been given th following rules of inferences for introducing and eliminating quantifiers: $$ \frac{\Gamma \vdash \phi} {\Gamma \vdash \forall x\phi} \; x\not\in FV(\Gamma) ...
3
votes
1answer
45 views

“One cannot hope to find any further essentially new lattice properties…”

I found the following passages in “A Course in Universal Algebra” by Burris and Sankappanavar. One cannot hope to find any further essentially new lattice properties which hold for the class of ...
1
vote
0answers
20 views

first order logic - help with translation algorithm between dictionaries

given a dictionary $\Sigma = \left \{f(),g(),R(,),c_0,c_1,c_2 \right \}$ and a sentence $\phi$ over $\Sigma$, I need to find an algorithm to translate $\phi$ to $\psi$ over $\Sigma'$ where $\Sigma' =...
0
votes
2answers
28 views

Context-Free Grammars: How to understand substitution rules

I am at a bit of a loss when it comes to understanding how to apply substitution rules for checking if a string is accepted / rejected for a given context-free grammar (CFG). Suppose I have been ...
0
votes
1answer
21 views

Logical Arithmetic: Distribution

Hi I'm reading through "How to Prove it" and I was doing one of the practice problems. The question asks you to simplify as far as possible and they give you the following: $$\neg(\neg p \vee q)\vee (...
2
votes
2answers
79 views

Changing Hilbert-style axioms

Consider the following system for Hilbert-style deduction: Axioms: $A \rightarrow (B \rightarrow A)$ $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ ...
1
vote
2answers
43 views

How to generalize the principle of mathematical induction for proving statements about more than one natural number?

Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this ...
0
votes
3answers
125 views

Would a theory with model $\{\}$ be consistent?

I don't know much about model theory, but it was suggested in another math forum that a theory with model $\{ \}$ would be consistent. Is this correct?
0
votes
1answer
49 views

Formal representtion of cases in mathematics

Trivial part: Solving a quadratic equation $ax^2 + bx + c = 0$, where $a,b,c$ are real numbers, requires to consider two cases: (i) $a=0$ and (ii) $a \neq 0$. In the first case there is only one ...
1
vote
1answer
36 views

NFA to DFA: Removing unnecessary states - What is NEW start state?

I'm trying to understand the transformation scheme from NFA to DFA, and think I have grasped most of it (in terms of method). The original NFA is the following: And the DFA was constructed by: ...
3
votes
1answer
86 views

Classical logic without negation and falsehood

It seems to me that Gerhard Gentzen's sequent calculus could just omit negation and falsehood, and still prove any classical tautology in a suitable form. (One approach might be to translate $\lnot A$ ...
2
votes
1answer
40 views

All translations of classical logic into intuitionistic logic

What are all possible ways of translating classical logic into intuitionistic logic? That is, if $S$ is the collection of sentences of first order logic, what are all the functions $f : S \to S$ such ...
2
votes
2answers
88 views

Overly formal book on mathematical logic.

In the preface to his book on logic Dirk van Dalen talks about the duality between "profane" and "sacred" logic, referring to relaxed logic and extremely formalized logic. He then explains his book ...
2
votes
4answers
72 views

How Do I Figure Out Which Door to Choose From?

A computer game involves a knight on a quest for treasure. At the end of the journey, the knight approaches two doors. The left door has a sign saying "One of these doors leads to a ferocious dragon!"...
0
votes
3answers
30 views

DFA - Union operation: How to?

I'm currently looking at deterministic finite automata, and learning how to combine two DFAs using AND or OR. I think I understand how to construct the INTERSECTION (AND) of two DFAs, but I'm at a ...
0
votes
1answer
37 views

Help about one math problem -Euclid and copies

I' m doing some interesting logical games from time to time, so i've got stuck at some problem, and i am very curious about the solution (i am doing this on some site that edit the solution few days ...
0
votes
1answer
16 views

Can a universal quantifier be applied to statements including equality?

The example I found on this site is as follows (this is specifying that some property holds for exactly two things): ∃x∃y((x≠y∧P(x)∧P(y))∧∀z(P(z)→(z=x∨z=y))) The problem I'm having is that trying to ...
2
votes
1answer
83 views

Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
-1
votes
1answer
41 views

Using the laws of logic (algebraic version) to show the following equivalences [closed]

I have some questions about algebra and discrete, with using law of logic. I am not sure how to prove the equivalences. Can someone please show me how this works and show the equivalence using the ...
1
vote
2answers
57 views

Unsolvability of Quintic + equations from a logical perspective

From what I understand, equations higher than the fourth degree cannot have a general solution. I am curious if there are logical reasons for this. By extending ZFC in some non-trivial way, could we ...
-2
votes
3answers
75 views

Is it true that, if $A\setminus B \subseteq C$, then $A\setminus C \subseteq B$?

Prove or provide counterexample for : If $A\setminus B \subseteq C$ then $A\setminus C \subseteq B$ My approach was, supposed $A\setminus B \subseteq C$, then let $x \in A\setminus B$, since $A\...
0
votes
0answers
18 views

Proving implications by resolution

We have to prove that (using resolution) $$\exists x A(x) \land \forall x\forall y (A(x) \land A(y)) \rightarrow x = y)$$ implies $$\exists x \forall y (x = y \rightarrow A(y))$$ So, we should try ...
0
votes
1answer
25 views

Concerning substitution and existential elimination in classic natural deduction using sequents

I am trying to prove $\exists x(P\lor Q)\vdash \exists x P \lor \exists x Q$, so I have: $$\begin{array}{r l l} (1) ~&~~ \exists x (P \lor Q) ~&~ \mbox{[premise]} \\ (2) ~&~ \quad (P \...
1
vote
1answer
43 views

Second-order logic and Russell's Paradox

I know that in first-order logic the following holds [see e.g. George Tourlakis, Lectures in Logic and Set Theory. Volume 2: Set Theory (2003), page 121] : $\vdash \lnot ∃y \ ∀x \ [A(x,y) \...
0
votes
2answers
23 views

Constructing DFA - Criteria / Multiple solutions

I'm currently studying for my logic exam, and looking into examples on DFA construction. Assume the alphabet is {a, b}, and the language to be constructed is defined as follows: ...
2
votes
2answers
27 views

Logic Puzzle (Valid and Invalid Arguments)

I have been given a logic puzzle and I am having a tough time figuring out how to set it up and solve. Here is the puzzle: a) The Statement "If Dr. Jones did not commit the murder then neither Ms. ...
4
votes
1answer
98 views

Complete calculus of first-order logic working for empty structures too

Usually, in model theory, one presupposes that structures (models) are non-empty. I don't like this (related: What's the deal with empty models in first-order logic?). So let us explicitly permit ...
0
votes
2answers
32 views

How to simplify this logical expression?

Using logical laws, I would like to simplify the following expression: $\neg a \lor \neg b \lor (a \wedge b \wedge \neg c)$ 1) Distribution law: $(\neg a \lor a) \land (\neg a \lor b) \land (\neg ...
1
vote
1answer
65 views

What do propositional function in ZFC mean?

I know that a propositional function is a WFF which can be either true or false depending on the value of at least one variable. The axiom schema of specification (subsets) says that for every ...
1
vote
1answer
39 views

Resolution - what about the same variables in different formulas?

$$\begin{array}{l:l} (1) & \forall x~\exists y~\big(R(x,y) \lor S(x,y)\big) \\(2) & \exists x~\forall y~\big(R(x,y) ~\to~ S(x,y) \land T(x)\big) \\(3) & \forall x~\Big(\exists y~\big(S(...
1
vote
0answers
33 views

Consistency Lemma in Lindenbaum's Theorem

Let $\Lambda$ be a modal logic, we say that a formula $\varphi$ is $\Lambda$-inconsistent if $\vdash_\Lambda (\neg \varphi)$ and is consistent otherwise. Similarly we say that a set of modal formulas $...
3
votes
3answers
395 views

Do Gödel numbers have a practical use?

Is there any example of Gödel numbers being actually used in practice? If so for what purpose?
0
votes
3answers
144 views

How to suppress the words “if” and “then”?

My math teacher keeps making us write mathematical sentences with "regular" words. I always ask her if it is possible to supress them but she always says "no" or she starts laughing. Take for example ...
0
votes
3answers
62 views

Propositional Logic - Can you Derive $C \to A$ from $A$ alone, given the introduction rule?

Apparently, according to the Conditional Introduction rule, this is valid: Prove $C \to A$ Source: http://kpaprzycka.wdfiles.com/local--files/logic/W12R Page 5 So before this, the way I viewed ...
5
votes
1answer
69 views

Intuitionistic logic plus $A → B \lor C \vdash ( A → B ) \lor ( A → C )$

The following is a classically valid deduction for any propositions $A,B,C$. $\def\imp{\rightarrow}$ $A \imp B \lor C \vdash ( A \imp B ) \lor ( A \imp C )$. But I'm quite sure it isn't ...
2
votes
2answers
60 views

Logic - What does a half T mean in logic?

TLDR nevermind I'll include a screenshot; I've looked for the symbol everywhere, it wasn't even found via wikipedia: https://en.wikipedia.org/wiki/List_of_logic_symbols It also wasn't in the list of ...
0
votes
0answers
26 views

Simplifying logical expression using logical laws

I simplified the logical expression: $(z \land w) \lor (\lnot z \land w) \lor (z \land \lnot w)$ using logical laws following these steps: 1) Absorption Law: $(z \land w) \lor (\lnot z \land w)$ ...
2
votes
1answer
23 views

How to express the following statement with Quantifiers and Predicates

Use quantifiers and predicates with more than one variable to express this statement: There is a student in this class who has taken every course offered by one of the departments in this school ...
0
votes
1answer
47 views

How to know the contrapositive of a compound logical expression?

In simple expressions like: $p \implies q $ the contrapositive would be: $\lnot q \implies \lnot p$. But in other cases where the expression gets more complex: ($p \land q) \implies (\lnot q \lor p)$. ...
1
vote
1answer
32 views

Stuck at one step on the proof of distributive law of implication over disjunction

I'm working with classic natural deduction system NK and the elimination rule for disjunction is stated as follows (I apologize, I don't know how to express it in tree-form): $\Gamma \vdash \chi$ is ...
3
votes
1answer
68 views

The Meta-Mathematics of Multiple Forcing

In forcing we have the forcing theorem (also called the truth and definability theorem). It guarantees that forcing works. What are the similar theorems for multiple forcing? To elaborate: Kunen, in ...
0
votes
2answers
36 views

Is my translation of unless into propositional logic correct?

I have the following sentences: I won't go the library unless I need a book p: I will go the library q: I need a book I replaced unless with if not as follows: I won't go the library ...
6
votes
3answers
242 views

How does induction fail in computable nonstandard models?

Tennenbaum's theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus ...
4
votes
7answers
146 views

A logic riddle from “The Lady or the Tiger?” by Raymond Smullyan

Just to clarify, Case 3 and Case 4 must have flawed reasoning in order to reconcile my proof with the author's. I have been having a problem with a particular riddle from Raymond Smullyan and I can't ...
1
vote
2answers
53 views

Is there a name for the logical scenario where A does not necessarily imply B, but B implies A?

A real life example of this is the 'Active' status on Facebook Messenger. (For those interested see this article here, and some Quora answers here for details.) When you are actively using Facebook ...
3
votes
2answers
87 views

Explicit example of countable transitive model of $\sf ZF$

Do we know any explicit example of a countable transitive model for $\sf ZF$ or $\sf ZFC$?
1
vote
2answers
30 views

Can a propositional function have quantifiers?

According to Wikipedia, an open formula is a WFF without quantifiers. I have read that a propositional function is the same as open formula. Are both of these statements correct? Is it true that ...
1
vote
1answer
57 views

Given list of 10 statement , 8th statement is “Exactly 8 statements in list are false” . Then what is complement of 8th statement

I'm confused during solving this question means if 8th statement is false then what the 8th statement became ? does it became 1.Exactly 8 statements in list are true. or 2.This is not the case ...