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)

1
vote
3answers
184 views

Are truth tables a valid method to prove an iff statement?

I recently had a homework assignment returned to me (for a Differential Geometry course, undergrad level) in which my instructor wrote "You cannot use truth tables to prove an if and only if statement"...
0
votes
2answers
109 views

truth table of equivalence relation

I have found the following problem in a book: Test the validity of the following argument: If 6 is not even, then 5 is not prime But 6 is even Therefore, 5 is prime I have made a truth table by ...
0
votes
1answer
33 views

Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +…+ n(n+1) = n(n+1)(n+2)/3

The problem is :Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +....+ n(n+1) = n(n+1)(n+2)/3 I have established a base case for n=0, 0*1 = 0(0+1)(0+2)/3 = 0 I have also ...
3
votes
2answers
333 views

Proofs for Relational Predicate Logic --Difficult Question!

I have been working on this problem for four and a half hours and I think I have simply missed something. I need the help of my peers here. The rules I am allowed to use are the Basic Inference rules (...
3
votes
0answers
94 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list $c_1,c_2,...
2
votes
4answers
94 views

Hilbert System with propositional logic $p \rightarrow q,\neg q \vdash \neg p$

This is my set of axiom $A \rightarrow (B\rightarrow A)$ $(A\rightarrow(B\rightarrow C))\rightarrow ((A\rightarrow B) \rightarrow (A \rightarrow C))$ $(\neg A \rightarrow B)\rightarrow ((\neg A \...
2
votes
1answer
68 views

$LK-\Phi$ proof of $\exists y Pby$

I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on: Let $\Phi = \{Pafa\}$, where $P$ is a binary predicate symbol and $f$ is a unary function ...
4
votes
4answers
247 views

“Logically equivalent formulae express the same _______.” <- What word do logicians use for the blank?

Meaning denotes the truth conditions of a sentence: what would have to be the case for the interpreted formula to be true. Nevertheless, without an interpretation, two logically equivalent formulae ...
3
votes
4answers
624 views

Conjectures which can't be right or wrong

Recently I was talking with some of my non-mathematician friends. On some very unrelated subject in order to make my point I said: "There are some conjectures in mathematics which are proven to be ...
4
votes
1answer
122 views

In Whitehead and Russell's PM, is there a typo in ✳72.23?

It seems that where $\gamma$ appears at the end of line 1, 4, 5, there should be a $z$ instead, i.e. $✳72.23\hspace{10pt} \vdash : R,S \in 1 \rightarrow Cls .\supset. R‘‘S‘‘\gamma=\hat{x}\{(\exists ...
-1
votes
1answer
69 views

Everyone has brown eyes [duplicate]

I'm going to prove that everyone's eyes are the same color. Ready? If there is only one person, then it's obviously true; this person's eyes are the same color that this person's eyes. Suppose it is ...
5
votes
2answers
132 views

How does undecidability of 'theoremhood' imply that human ingenuity is necessary in mathematics?

In Robert Stoll's "Set Theory and Logic", there is the following passage on effectiveness of theorems (p. 375) : Mathematical logicians have shown that for many interesting axiomatic theories ...
1
vote
1answer
302 views

Is Douglas Hofstadter's version of Godel's proof utter nonsense?

Is Douglas Hofstadter's version of Godel's proof, which he offers in his book Godel, Escher, Bach, utter nonsense? Hofstadter goes to great length to disguise the fact that there are two distinct ...
0
votes
1answer
50 views

Other conditions than necessary and sufficient conditions, $\Rightarrow$, $\Leftrightarrow$?

I know that $$A\Rightarrow B$$ means that $A$ is a necessary condition for $B$ and $B$ is a sufficient condition for $A$. Also, $$A\Leftrightarrow B$$ means that $A$ is necessary and sufficient ...
-1
votes
1answer
32 views

Struggling with proof, by contrapositive?

I am having trouble solving this proof. I tried to do a proof by contrapositive. Q = $(u+z)/(v+w) < z/w$ P = $(u/v < x/y \land x/y < z/w)$ Assuming $\lnot Q$ got me: $u/v \ge z/w$ If ...
1
vote
2answers
146 views

Boolean Expression simplification help

Hi I am new to the board. Taking a computer architecture course and I am having trouble understanding further simplification on a question I got on a previous quiz. When I type in the expression ...
3
votes
2answers
93 views

Commutivity of unique existence quantifiers

Find an expression P(x,y) to disprove the following equivalence, $(\exists!x)(\exists!y)P(x,y)\Leftrightarrow(\exists!y)(\exists!x)P(x,y)$ I could only think of a few statements of $P(x,y)$ that ...
0
votes
2answers
100 views

How to prove that these two second order formulas are equivalent?

Let $F_1 = \exists P\exists Q\exists R \forall x\forall y\forall z (P(x,y) \land Q(y,z) \rightarrow R(x,z))$ and $F_2 =\exists P\exists Q\exists R \forall x\forall y\forall z (Q(x,y) \land P(y,z) \...
4
votes
4answers
140 views

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L.

Find propositional formulas $\phi$ and $\psi$ such that $(\phi \rightarrow (\psi \rightarrow (¬\psi)))$ is a theorem of L. So every axiom is a theorem of L so I thought there would be some way to ...
0
votes
2answers
74 views

Suppose $\phi$ is a formula of L. Give a proof in L of the formula $(\phi \rightarrow \phi)$ explaining each step of the proof.

Suppose $\phi$ is a formula of L. Give a proof in L of the formula $(\phi \rightarrow \phi)$ explaining each step of the proof. I have the axioms (A1) $(\phi \rightarrow ( \psi \rightarrow \phi))$ (...
1
vote
3answers
236 views

ZFC Axioms to be extended?

Sorry if this is going to be a really loaded question. I was told several times that for virtually all theorems/corollaries/propositions of mathematics (except those cases not compatible with ZFC ...
0
votes
2answers
55 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
0
votes
1answer
176 views

Why is $\mathfrak{ N }_S$ not finitely axiomatizable?

Let $\mathfrak{ N }_S = (\mathbb{ N }; 0, S)$. With axioms ($A_S$): 1: $\forall x (Sx \neq 0)$ 2: $\forall x \forall y (Sx = Sy \rightarrow x = y)$ 3: $\forall y (y \neq 0 \rightarrow \exists x (y =...
1
vote
1answer
251 views

Definable subsets of the natural numbers using only the successor function

Consider the first-order language whose only nonlogical symbol is the unary function symbol $S$, and the structure $\mathfrak{N} = ( \mathbb{N} , S )$, where $S$ denotes the successor function. Why ...
1
vote
2answers
97 views

Show that $((\phi → \psi)→((\psi→\chi)→(\phi→\chi)))$ is a Theorem of L.

Show that $((\phi → \psi)→((\psi→\chi)→(\phi→\chi)))$ is a Theorem of L. I a previous part of the Q i am asked to state the deduction theorem so I assume i have to use this and the axioms A1, A2, A3, ...
1
vote
1answer
325 views

Solving a version of the liar paradox

Given two people $Alice ,Bob$ are either lying or telling the truth Now suppose $Alice$ says "At least one of us is lying." We have two cases: $Alice$ is telling the truth $\implies$ $Bob$ is lying....
3
votes
2answers
323 views

Logic and number theory books

I've recently decided to start preparing for uni, so I figured I need to learn logic and some number theory. I picked up Burton's Elementary Number Theory and wasn't quite comfortable with it, seemed ...
4
votes
1answer
72 views

Necessary and sufficient conditions with single “if”

Before starting your undergraduate program, you decide to make sure you choose the exact program that you will need to get your dream job at Black Mesa Research Facilities. You visit them during ...
0
votes
1answer
42 views

Tranlsation of english to nested quantifiers and forming their negations

You are given the following propositional function: B(x,y): Writer x has written a book on subject y. The domain for x is all people in the world, and the domain for y is all subjects in the world. ...
0
votes
4answers
171 views

Island of knights and knaves

This question is about an island of knights and knaves, where knights always speak the truth and knaves always lie. You encounter two people A and B. Determine, if possible, what each of them are if ...
0
votes
1answer
85 views

About the definition of axiomatizable theory and consistency

Definition: If $A$ is a theory and $B \subseteq A$ then $B$ is a set of axioms for $A$ iff 1) B is recursive and 2) $B \models C$ for all $C \in A$. We say $A$ is axiomatizable iff $A$ has a set ...
-1
votes
1answer
57 views

How to mathematically calculate the indistinguisable and distinct of the following permutation problems?

I'm having trouble calculating how many indistinguishable and distinct solutions there are for each problems. I'm pretty confident with some of my solutions, but could anyone show me mathematically ...
0
votes
2answers
87 views

Quantified Logic with miltuple variables

Problem: ∀y¬∃x¬(¬Fxy ∨ Fyx) ⊢ ∀y∀z(Fyz→Fzy) I don't really understand how to deal with multiple variables in instances like this. So far I have: ...
2
votes
1answer
209 views

Provable formulas in everyday Mathematics

Basically all statements ( lemmas, theoremas, corollaries ) in Mathematics can be expressed as a conditional statement in first-order language, or existential statement ( existence proofs ). Here i'...
1
vote
1answer
102 views

Mathematical logic

Given: $[(A \lor B) \land (A \lor C)] \rightarrow [A \lor (B \land C)]$; $\lnot((x_1 < x_2) \rightarrow (x_1 \cdot x_3 > x_2 \cdot x_3))$ $\forall x_2:f_1^2(x_2, x_3) \rightarrow P_1^2(f_1^1(...
0
votes
1answer
85 views

How to prove $\vdash (\forall v_1 \,\exists v_2\, fv_1=v_2)$

f is a one-place function symbol. I just don't know where to start. $\forall v_1 \,\exists v_2\, fv_1=v_2$ might come from $\exists v_2 \,fv_1=v_2$ Then I don't know how to deal with the "exists"
2
votes
2answers
215 views

How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
3
votes
0answers
48 views

Linear regression, reversing it back then.

Need's formatting, editing will take some time.
6
votes
1answer
413 views

How can I prove that there is no set containing itself without using axiom of foundation?

I've already found some similar questions in here (and other sites), but in most of the case, the use of axiom of foundation is required to complete the proof. Is there any way to prove $\not\exists ...
1
vote
0answers
29 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
4
votes
1answer
364 views

3-Coloring a graph using propositional formulas

Hello everyone I am studying for an exam on logic and computability, I am trying to tackle a specific problem so any help would be greatly appreciated: Let $G = (V,E)$ be an undirected graph ...
2
votes
1answer
41 views

building truth-functional connectives

It is known that $NAND$ and $XOR$ are the only one $2$-argument truth-functional connectives that can be used alone to create every $n$-argument truth-functional connective for all positive integer $n$...
1
vote
2answers
58 views

Resolving a contradiction in the proof of expected value of Binomial distribution

I've seen this proof in a text. I have an issue with it and wanted to check its validity. Let $X\sim B(n,p)$, we seek the expectation. We let $q=1-p$ \begin{equation} E(X)=\sum_{j=0}^{n} j {n\choose ...
4
votes
2answers
381 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
2
votes
1answer
662 views

Is saying 'This statement is true' a logically valid statement?

I understand how 'This statement is false' is not logically valid, but what about 'This statement is true'? I've always heard self-referential statements are not logically sound, but I can't really ...
1
vote
1answer
35 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y \...
0
votes
2answers
84 views

Show that $ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $ is, in general, NOT a theorem.

Show that $$ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $$ is, in general, NOT a theorem. My answer: First, I got the abstraction of the formula which is $ p \rightarrow A \lor q$ then ...
1
vote
1answer
111 views

Do all contradictory statements entail something self-referential?

"The house is all blue(B), and the house is all white(W)" Those statements are, ostensibly, not of the form p ⋀ ¬p. However, they do seem to entail p ⋀ ¬p. For example "The house is all blue" entails ...
1
vote
1answer
33 views

Can covering be done on two elements?

The covering rule is: $$B \bullet (B+C) = B$$ and $$B+(B \bullet C)=B$$ So does it follow from this rule that: $$B \bullet A \bullet \bar{C} + B \bullet D \bullet\bar{F} = B \bullet (A\bullet\bar{C}+D\...
2
votes
1answer
1k views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...