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)

0
votes
1answer
17 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 ...
4
votes
3answers
199 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 ...
3
votes
1answer
24 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 ...
0
votes
0answers
10 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
38 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)$. ...
0
votes
1answer
22 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
117 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
83 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
11 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 ...
6
votes
1answer
81 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 ...
5
votes
3answers
213 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
49 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
838 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
32 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
66 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
66 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
1answer
42 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
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
56 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
32 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
18 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
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 ...
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
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 ...
1
vote
1answer
69 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
25 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
1answer
28 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, +, ...
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))) ...
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?
3
votes
0answers
23 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
32 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 ...
2
votes
3answers
63 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 ...
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 ...
2
votes
1answer
35 views

I can't identify the quantifier

For a simple question like Let $x, y \in Z$. If $3 | x$ or $3 | y$ then $3 | x y$. Is it alright to assume all $x$ and all $y$ exist in $Z$? I am trying to negate the statement but since it does ...
1
vote
0answers
33 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 ...
1
vote
2answers
21 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.
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?
0
votes
0answers
52 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 ...