Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
1answer
12 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
0answers
8 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 R(y,z) ...
1
vote
1answer
22 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
0answers
8 views

Suppose $\phi$ is a formula of L. Give a proof in L of the formula $(\phi -> \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))$ ...
0
votes
0answers
39 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 ...
3
votes
1answer
80 views

Theorems that we can prove only by contradiction

While most of the world is fine with proofs performed by contradicting the thesis, direct proofs are sometimes considered more elegant than indirect ones. Those who prefer intuitionism or ...
2
votes
1answer
98 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 ...
0
votes
1answer
70 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 ...
4
votes
0answers
128 views

Puzzle - zero knowledge proof

I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...
2
votes
0answers
57 views
+50

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 ...
4
votes
3answers
298 views

What does this combination of symbols mean? $\exists !$

I just want to know what this combination of symbols means: $\exists !$ I know ∃ means 'there exists', but what does it mean when it is paired with a '!'? I have written down 'there exists unique" ...
0
votes
2answers
26 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
0answers
20 views

Algorithm for determining whether one formula in propositional logic is a substitution of another?

In propositional logic, one formula A is a substitution instance of another formula B just in case A is obtainable from B by a series of uniform substitutions. A uniform substitution is obtained just ...
1
vote
2answers
54 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, ...
-2
votes
1answer
29 views

Show that the set {¬, v} is adequate.

So to show it is an adequate set, I need to be able to show that we can write pvq, p∧q and ¬p in terms of only the connectives {¬,v}. Clearly, ¬p and pvq are already written in terms of connectives ...
1
vote
1answer
85 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 ...
0
votes
1answer
40 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 ...
0
votes
4answers
47 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 ...
2
votes
2answers
70 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 ...
2
votes
5answers
85 views

Question about definition of binary relation

Wikipedia says: Set Theory begins with a fundamental binary relation between and object $o$ and a set $A$. If $o$ is a member of $A$, write $o \in A $. I thought that a binary relation is a ...
1
vote
1answer
24 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
2answers
59 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: ...
45
votes
8answers
5k views

Is it possible that “A counter-example exists but it cannot be found”

Then otherwise the sentence "It is not possible for someone to find a counter-example" would be a proof. I mean, are there some hypotheses that are false but the counter-example is somewhere we ...
0
votes
4answers
40 views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
1
vote
2answers
84 views

Virtues of Presentation of FO Logic in Kleene's Mathematical Logic

I refer to Stephen Cole Kleene, Mathematical Logic (1967 - Dover reprint : 2002). What are the "pedagogical benefits" (if any) of the presentation chosen by Kleene, mixing Natural Deduction and ...
0
votes
1answer
36 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 ...
0
votes
1answer
38 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 ...
3
votes
2answers
73 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 ...
3
votes
1answer
236 views

Working with negation of quantifiers

How would you prove $\exists x\neg P(x)$ given $\neg \forall xP(x)$ using first-order logic?
2
votes
2answers
98 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 ...
2
votes
2answers
78 views

How to write negation of statements?

How to write negation of following statements in words? ...
2
votes
2answers
52 views

Logical implication of the form $P\to P$

Two logical propositions are given. $$P:\ good\ books\ are\ not\ cheap\\ Q:\ cheap\ books\ are\ not\ good$$ Now 3 statements are given: $A:\ P \ implies\ Q\\ B:\ Q\ implies\ P\\ C:\ P\ and\ Q\ are\ ...
3
votes
0answers
30 views

Linear regression, reversing it back then.

This is my first Question. I am performing linear regression upon set of floating point between 0 and 1. there are few hundred points.once the slope and intercept is found for first iteration,the ...
0
votes
1answer
44 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"
3
votes
3answers
51 views

General Strategy for Derivations in Propositional Logic

In Propositional Logic, one is often tasked with showing that some particular formula is a theorem of a given deductive system, i.e. $\emptyset \vdash \psi$. These formulas can look very simple and ...
4
votes
1answer
254 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 ...
0
votes
0answers
18 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 ...
1
vote
1answer
25 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
2
votes
2answers
145 views

Again about McGee objections to modus ponens

I would like to "reopen" the previous post regarding Modus ponens because, frankly speaking, I'm not satisfied with some (most of ?) answers by the mathematicians community. Disclaim: I'm not aiming ...
1
vote
2answers
29 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 ...
34
votes
9answers
4k views

Infinite sets don't exist!?

Has anyone read this article? Set theory This accomplished mathematician gives his opinion on why he doesn't think infinite sets exist, and claims that axioms are nonsense. I don't disagree with his ...
3
votes
2answers
101 views

Show there are a pair of sentences where the first says the second is provable and the second says the first is unprovable

Given $B_1(y)$ and $B_2(y)$ in the language of arithmetic, show there are sentences $G_1$ and $G_2$ such that: $$\vdash_Q G_1 \leftrightarrow B_2(\ulcorner G_2 \urcorner)$$ $$\vdash_Q G_2 ...
2
votes
1answer
23 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 ...
0
votes
3answers
407 views

knight and knave problem

For this question, suppose you are on the island of knights and knaves. Remember that knights always speak truth while knaves always tell a lie. (a) Suppose you come across two of the natives. You ask ...
12
votes
3answers
303 views

Does every complete theory admit quantifier elimination?

Does every complete theory admit quantifier elimination? I know that at least in some simple cases the reverse is true; such as some reducts of number theory.Thanks
2
votes
1answer
44 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
31 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 ...
-2
votes
0answers
46 views

Boole's functions' domain is D = {1, 2, 3, 4}. Find ∃xF(x, 2), when F(x, y) = 1100 1111 0011 0101. [on hold]

The problem is, I actually do not understand this problem very well. When the logical function is given, making truth table is not a problem for me at all. I wonder, if this exercise requires to make ...
0
votes
1answer
42 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 ...
4
votes
1answer
116 views

Basic question about encoding ZFC into PA

1) Are ZFC and PA arithmetic mutually interpretable if we extend PA to PA+A , where A is the set formulas of PA that result from the translation of the axioms of ZFC (or any large cardinal axioms ...