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
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 ...
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
72 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 ...
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
24 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
37 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
31 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
155 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
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
29 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
27 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
72 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
61 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
10 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
39 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
72 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
36 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
35 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))) \...
2
votes
1answer
23 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 ...
4
votes
1answer
152 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: This 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 the ...
1
vote
1answer
42 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
105 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
48 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 q)...
1
vote
3answers
115 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
68 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 "...
1
vote
1answer
59 views

Elimination of quantifiers for the theory of equivalence relations with two infinite classes by back-and-forth

As I said in an earlier question, I'm trying to understand how to obtain elimination sets by way of back-and-forth arguments. Since I'm not totally sure I understood how it works, I wanted to check my ...
1
vote
3answers
48 views

logic: order of quantifier with free variables

Take the sentence, "You can't win them all." This could be logically written as "For all people, there exists a thing they cannot win at." $\forall x.\exists y.(\neg win(x,y))$ Now suppose I was ...
0
votes
0answers
29 views

Predicate logic example..

I've got this predicate symbol: $(\forall x R(x,y)) \implies (\forall y Q(x,y))$ $R=\{(x,y) \in Q \times Q \hspace{0,2cm}|\hspace{0,2cm} x<y\}$ $Q=\{(x,y) \in Q \times Q \hspace{0,2cm}|\hspace{0,...
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: $...
0
votes
1answer
35 views

Is the conjunction of all necessary statements sufficient? What about the converse?

A necessary condition for consequent $q$ is a proposition $p$ such that: $$\neg p \implies \neg q$$ let $P:= \{p_i: \neg p_i\implies \neg q\}$ What I want to know is if $$\bigwedge_{p_i\in P} p_i \...
0
votes
1answer
54 views

Gödel number for contradicting modus ponens?

When Gödel numbered statements, for instance modus ponens and connectives got their own numbers, does it matter which number each connective gets as long as they are different? Sometimes I'm not ...