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)

2
votes
2answers
22 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. ...
3
votes
3answers
357 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?
3
votes
1answer
66 views

Why are Duals of Two Equivalent compound propositions Equivalent?

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of ...
0
votes
0answers
15 views

Turing and Post–Turing machine [on hold]

Got an interesting question from my professor of mathematical logic. He asked as to prove this, as he said, "theorem": "For every Turing's machine exists Post–Turing's machine, which creates a ...
0
votes
0answers
15 views

Simple question about binary relation [on hold]

P - binary relation. P $\subseteq$P - binary relation. P $\subseteq$ $R^2$. P = {(x,y)| y = |x|}. 1) Find range of definition. I guess that R 2) Find all possible values. I guess that R+ Prove by ...
1
vote
0answers
20 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
21 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
24 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 ...
0
votes
2answers
41 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 ...
11
votes
4answers
2k views

What is the purpose of free variables in first order logic?

I understand the difference between free and bound variables, but what are free variables actually useful for? Can't you use quantifiers to express everything that you would want to express with both ...
1
vote
0answers
27 views

Extracting a first-order proof from a second-order one

Let $T$ be a first-order theory and $\phi$ be a first-order sentence. Suppose we have a proof $\pi^1$ of $\phi$ from $T$ in some second-order proof system $S^1$. Then by the soundness of $S^1$ and ...
1
vote
1answer
23 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 ...
5
votes
3answers
205 views

Linear Logic, what is it used for?

I read a lot about Linear Logic recently but I failed to find any real use to the logic. I'd like to know how and where Linear Logic could be applied. Something like lambda calculus can be clearly ...
0
votes
1answer
36 views

Translating comparison operators into logic

I have $P: x > 30$; $Q: x < 20$ Write simply as you can: a) $P \land Q$ My answer: $x > 30 \;and \; x < 20$ Which is always false: So if I write: $30 < x < 20$ is it still ...
5
votes
1answer
45 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 ...
1
vote
0answers
20 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 ...
-2
votes
2answers
61 views

How do I prove\disprove the following logical statement?

I saw this statement in one of my logic books and I was curious how to prove or disprove it? Let $S_1$ and $S_2$ be sets of propositions. If $S_1$ is satisfied (all propositions in $S_1$ are true) ...
1
vote
2answers
49 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 ...
1
vote
0answers
54 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: The linked question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since ...
0
votes
3answers
134 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 ...
2
votes
1answer
16 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 ...
2
votes
1answer
37 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
19 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)$ ...
0
votes
1answer
42 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
26 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 ...
4
votes
7answers
126 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 ...
5
votes
3answers
87 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 ...
6
votes
1answer
82 views

Examples of provably${}^n$ unprovable statements

Given any statement $A$ and a classical theory $T$ which we assume is at least as strong as Peano Arithmetic ($\sf PA$), we have that $T\vdash A$ implies $T\vdash T\vdash A$ (that is, if a statement ...
6
votes
3answers
229 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 ...
3
votes
1answer
60 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 ...
32
votes
7answers
2k views

Do the axioms of set theory actually define the notion of a set?

In Henning Makholm's answer to the question, When does the set enter set theory?, he states: In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is ...
2
votes
0answers
65 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
18
votes
5answers
870 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
2answers
34 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 ...
1
vote
2answers
70 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
1answer
89 views

Is ({1, 0}, ⊕, ∨) a field? and Is ({1, 0}, ⊕, ∧) a field?

1 and 0 denote the logical statements True and False. These two questions are for homework so would rather an answer that could help explain it to me then just a straight answer. Thanks to anyone who ...
1
vote
2answers
25 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 ...
2
votes
3answers
405 views

Why does adding a negative number to a positive number reduce the original positive number?

There's a question over on stack overflow about adding negative numbers to a negative number. The question surrounds why 10 - -5 is equal to 5. I'm very happy that the result is 5, but why is it 5 ...
2
votes
2answers
57 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 ...
1
vote
2answers
70 views

Deducing $((\neg a \to \neg b) \to ((\neg a \to b) \to b)))$ from axioms

I have seen many questions here, using a different set of axioms than mine. Here is mine : $$1) (a \to (b \to a))$$ $$2) ((a \to (b \to c)) \to ((a \to b) \to (a \to c)))$$ $$3) ((\neg b \to \neg a) ...
3
votes
3answers
235 views

Why is this contradiction using axiom of constructibility incorrect?

Today I thought of this paradox and I'm trying to find the wrong assumption that causes it. Does anyone know what is wrong in the following argument: let $$A=\{x\in \mathbb{R}|\exists\phi:\forall ...
1
vote
0answers
44 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 ...
0
votes
1answer
34 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 ...
0
votes
1answer
19 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 ...
-1
votes
1answer
128 views

Why are the rules of logic universally applicable? [duplicate]

We can imagine physical constants to be different in a different universe or even not be constant in our own universe. We can imagine and simulate different physical and information-theoretical laws, ...
1
vote
1answer
36 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 ...
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 ...
0
votes
1answer
12 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
35 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
19 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 ...