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)

5
votes
3answers
67 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 ...
2
votes
7answers
91 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
1answer
34 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
2answers
46 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
22 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
0answers
41 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 ...
18
votes
5answers
804 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
16 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
26 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 ...
1
vote
2answers
52 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
10 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
16 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 ...
3
votes
1answer
44 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 ...
0
votes
1answer
57 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
23 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
31 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
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 ...
0
votes
0answers
15 views

about finding the diagonals of the rhombus given the angle

suppose,only the angle of a rhombus is given then how can I find the length of the diagonals?(without measuring the side) Is there any equation where the angle is related to the diagonal only?
2
votes
0answers
22 views

Proving Logical equivalence [5-26]

I have to prove a problem statement with logical equivalences but I seem to keep getting stuck. Here is the problem: $$ [(q \to p) \land \lnot p] \to (p \land q) \equiv p \lor q $$ Here is the work I ...
0
votes
1answer
31 views

True in one infinite model implies true in all other infinite models?

Suppose we have some sentence in first order logic with equality, NOT using any non-logical symbols (functions, predicates and constants). If this sentence is true in some infinite model, is it then ...
1
vote
1answer
15 views

Proving Logic statement

So I have an statement that I need to prove using Logical Equivalences: $$(p\land q) \lor [p \land (\lnot( \lnot p \lor q)) ] \equiv p $$ I made it through some steps but I can't seem to make it to ...
1
vote
1answer
27 views

Completeness theorem for second-order logic in the language $\{\}$

It is well-known that the completeness theorem fails for second-order logic. In particular, there is no calculus $C$ that proves exactly those second-order sentences $\phi$ in the language $\{0, s, +, ...
1
vote
1answer
46 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
0answers
31 views

Natural Deduction Proof $\neg(P \to Q) \vdash Q \to P$

I am trying to answer Question 3(e) in Exercise 1.2 of Huth and Ryan's Logic in Computer Science book for revision and I am stuck on it. The question asks you to prove the validity of the following ...
1
vote
0answers
28 views

Prove/Disprove: a clause $\exists xA$ is true in structure $M$ iff there is a term without FV such that $A\{\frac{t}{x}\}$ is true in $M$

Prove/Disprove: Let $M$ such that for every $a\in D$ (the domain) there's a term $t$ such that $t\mapsto a$,in $M$. Claim: a clause $\exists xA$ is true in $M$ iff there is a term without free ...
1
vote
0answers
16 views

Logic - logical connective for (~ABC) + (A~BC) + (AB~C)?

Is there a logical connective that says 'True, if and only if 1 proposition is true'. Or perhaps even better, is there one that describes 'True, if and only if n propositions is true'? Where n is an ...
0
votes
1answer
18 views

What effect does a negation have on a proposition in a bracket.

Say for example ¬ (p ∧ ¬q}, what does the negation outside the bracket do to the proposition inside the bracket?
1
vote
2answers
20 views

Commas in propositional logic

I want to know what effect a comma has on a propositional statement. For example: $\{\neg p, p \vee q \} \vDash q$ Does this bit $\{\neg p, p \vee q \}$ mean just $q$? Thanks.
2
votes
3answers
62 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
0
votes
0answers
49 views

Is there any linear algebra textbook presented using logical symbols?

I'm currently going through a book called Linear Algebra Done Right by Axler, and to be honest, his book seems to be very loose with what things he defines. For instance , the symbol 0 could be mean a ...
0
votes
1answer
9 views

How to eliminate bi conditionals?

p <--> q can be written as (p → q) ∧ (q → p) (~p V q) Λ (~q V p) After this I am confused. If I distribute Λ over V, I get (~p V q Λ ~q) V (~p V q Λ p) which becomes (~p V q Λ ~q ) V (~p V q ...
0
votes
2answers
35 views

Simple Proof Question on Fundamentals (if x implies y, and y implies z, how does x imply z?)

So as the title says, the question I am attempting to wrap by head around is "x implies y, y implies z, then x implies z". It seemed almost like a joke, I thought the answer was right in the question. ...
1
vote
2answers
68 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) ...
0
votes
0answers
17 views

Show that the propositions $\alpha$ and $(Z\rightarrow\alpha) \wedge Z$ are equally satisfiable

I already found that $\alpha \not\equiv (Z\rightarrow \alpha) \wedge Z$ but now I was ask to see if those propositions are equally satisfiable but I don't know how. Hope someone can help me. Thank ...
0
votes
0answers
34 views

What effect do brackets have around propositional statements?

I want to know the effects of bracket around propositional statements. For example is number 1 and number two the same? 1) ¬(p∧q) 2) ¬p∧¬q Thanks
0
votes
1answer
18 views

Prove that if $S$ is closed under $\wedge$ and every $\alpha \in S$ is satisfied then $S$ satisfied

Let the infinite set $S$ be closed under $\wedge$ (for every $\alpha,\beta\in S$ exists $\alpha\wedge\beta\in S$ ). Prove that if $S$ is closed under $\wedge$ and every $\alpha \in S$ is satisfied ...
2
votes
2answers
30 views

Propositional calculus axiom the other way around

I have the following axioms of propositional calculus (as well as modus ponens and the deduction theorem if needed): $$(a \to (b \to a)) \tag1$$ $$ (((a \to (b \to c)) \to ((a \to b) \to (a \to c))) ...
-1
votes
0answers
32 views

how to prove this in logic

i am actually trying to solve this problem but cant even start it never did the logic before just trying first time. anyone could help me to understand? Specify the following statements in predicate ...
0
votes
0answers
32 views

Proving in predicate logic

So I am prepairing to take a math course in the summer, and I noticed that the first thing in the course is predicate logic, so I started doing some exercies on it. My knowledge so far is very simple, ...
2
votes
1answer
18 views

Problem understandig lambda-calculus incompatible problem.

Let $K \equiv \lambda xy.x$ and $S \equiv \lambda xyz.xz(yz)$. Show that S and K are incompatible. The solution goes like: Let $S=K$ and $I \equiv \lambda x.x$, we have to show that all terms are ...
1
vote
0answers
42 views

When does the dual of $s =s$? [duplicate]

When does $s^*=s$? $s^*$ represents the dual of $s$, where $s$ is a compound proposition involving only $T, F, \wedge, \vee, \neg $, and $s^*$ is obtained by interchanging $T$ for $F$, $F$ for $T$, ...
7
votes
0answers
89 views

5x5 Bingo Puzzle [Logical thinking problem]

5 people participate in a custom game. They are given blank cards, in which they have to fill numbers from 1-25 in a 5x5 table. The host of the game, then calls out random numbers (between 1-25, ...
1
vote
1answer
37 views

Tarski's schema T

On Wikipedia, Tarski schema T says: A sentence of the form "A and B" is true if and only if A is true and B is true A sentence of the form "A or B" is true if and only if A is true or B is true A ...
0
votes
2answers
92 views

Need help in assignment task in logic proof field!

We are currently struggling with this task in an exercise session. The problem is that none of us are that much familiar with proofing and this seems quite difficult. The task it self says: A list ...
0
votes
2answers
43 views

Prove $[(P \lor A) \land ( \neg P \lor B)]\rightarrow (A \lor B)$

I want to prove that $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$, using distributions or reductions (even though I am aware that simpler proofs exist). The issue is that I keep ...
0
votes
3answers
21 views

Help with logical equivalences and proving tautology

I've been wracking my brain trying to figure this out, but I don't know what to do after a certain point. I'm trying to prove whether or not this is a tautology: $$ [(p\wedge r)\wedge (p\rightarrow ...
-4
votes
0answers
17 views

prove the proposition using formal logic [on hold]

prove using formal logic $\forall x ( \neg P(x) \lor Q(x)) \vdash \forall x ( \neg H(x) \lor Q(x)) \lor \exists x ( H(x)\wedge \neg P(x))$
1
vote
3answers
106 views

How do I prove something without premises in a Fitch system?

If asked “Prove in Fitch: From no premises, derive $A \lor (A \to B)$. Without using Taut Con?" These are the are the Fitch rules, and this is what I have so far. Should I aim to use V Elim to ...
2
votes
1answer
61 views

Generators of the Lindenbaum-Tarski algebra

I am a bit confused about the role of propositional variables in the construction of the free Lindenbaum-Tarski algebra. In the entry "Lindenbaum-Tarski algebra" on Wikipedia, in the section ...