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
1answer
87 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
41 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
32 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
84 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
19 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
99 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
33 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
40 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
400 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
145 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
63 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
71 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
61 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
27 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
26 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
70 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
54 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
58 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 ...
20
votes
6answers
1k views

Meaning of the word “axiom”

One usually describes an axiom to be a proposition regarded as self-evidently true without proof. Thus, axioms are propositions we assume to be true and we use them in an axiomatic theory as premises ...
0
votes
1answer
20 views

Natural Deduction Proof (c ∧ n) → t, h ∧ ¬s, h ∧ ¬(s ∨ c) → p |− (n ∧ ¬t) → p

I'm trying to do a question from Huth and Ryan's book 'Logic in Computer Science' and I am stuck on the following natural deduction proof: prove by natural deduction that the sequent (c ∧ n) → t, h ∧...
0
votes
1answer
37 views

What are the roots of propositional logic?

You know, I actually started learning about propositional logic by asking the same question, but about maths. However, now am wondering what the roots are of propositional logic, I mean, we don't ...
2
votes
2answers
59 views

Intersection of subgroups is a subgroup: What if collection of subsets is empty?

Theorem: The intersection of any arbitrary collection of subgroups of a group is again a subgroup. http://groupprops.subwiki.org/wiki/Intersection_of_subgroups_is_subgroup I don't understand the ...
0
votes
1answer
21 views

Logic Proof using Inference rules and replacement rules

I am trying to prove the following using the inference and replacement rules in logic: (A . F) ⊃ (C ∨ G), ~ (C ∨ (F . G)), F ≡ ~ (X . Y), ~ (X ∨ ~ W) /∴ ~ (A ∨ X) I have this so far: Work But I do ...
1
vote
1answer
38 views

I'd like some clarification in this theorem proof.

Let $(P,Sc,1)$ a Peano's system, then $P=\{1\}\cup Sc\{P\}$ They use the third Peano's axiom, in which if $A\subseteq P, 1\in A$ and $Sc(a)\subseteq A\Rightarrow A=P$. But their proof says in the ...
1
vote
0answers
22 views

Modal extensions (operators) for monoidal (categorical) logics

There is nice generalization of first order logic to monoidal (categorical) logics http://www.springer.com/us/book/9783642128202 which has recently been applied extensively as replacement for deontic ...
5
votes
3answers
94 views

Are sets just predicates with syntactic sugar?

Do mathematicians agree/accept that "sets are just predicates with syntactic sugar"? If not, then Why not? I mean, I can translate between $ x \in S $ and $ S(x) $. Will that change the correctness ...
1
vote
1answer
74 views

Why do we use both sets and predicates?

For every set S we can define s as $$ \forall x:s(x) \iff x \in S$$, and for every predicate p we can define $$P:=\{x|p(x)\}$$. Operations and their properties correspond, etc. In every theorem or ...
0
votes
0answers
27 views

Proving theorems using the Compactness theorem

We say an infinite set $S$ is closed under $\wedge$ if for all $a,b$ $\in S$ so $a\wedge b \in S$. I need to prove that if S is closed under $\wedge$ and for all $a \in S$ we know is that $a$ is ...
1
vote
0answers
32 views

R $\subseteq \omega$ recursive iff $\exists m \in \omega$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$.

The queston I'm trying to solve is use Kleene's enumeration theorem to show R $\subseteq \omega$ recursive iff $\exists m$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$ for some $m \in \...
1
vote
1answer
38 views

For every $x$ and $y$ there exists $z$ such that $x-y=z$

If I have the statement. For every $x$ and $y$ there exists $z$ such that $x-y=z$ What would the predicate be for that statement? And how would it be written in symbolic notation? I can't seem ...