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)

2
votes
1answer
278 views

This sentence is false

"This sentence is false". Is this sentence true or false? My attempt: If this sentence were true, then what it says would be the truth , it implies that it is false which is a contradiction. if ...
1
vote
2answers
65 views

Properties of the deductive closure

Let $\Phi_0$ be the set of $\cal L$-sentences. For $\Gamma\subseteq\Phi_0$, the deductive closure of $\Gamma$ is given by $$\mathsf{Cn}(\Gamma)=\left\{\phi\in\Phi_0\mid\Gamma\vdash\phi\right\}$$ ...
1
vote
1answer
68 views

Every positive formula is satisifiable

We say that a propositional logical formula is positive if it does not include the negation connective ¬ anywhere in it (but it may still use ∧, ∨, ↔, →, and propositions). Show that all ...
2
votes
1answer
78 views

Did I analyze the logical form of a statement well?

Analyze the logical forms of the following statements. You may use the symbols ∈, !∈, =, !=, ∧, ∨, →, ↔, ∀, and ∃ in your answers, but not ⊆, ⊆, P , ∩, ∪, \, {, }, or ¬. (Thus, you must write ...
2
votes
1answer
103 views

Intuitionistic Logic: introduction and elimination rules for the universal and existential quantifiers

Are the natural deduction introduction and elimination rules for the universal and existential quantifiers in Intuitionistic Logic the same as those for Classical Logic?
1
vote
2answers
63 views

Truth values for 2 implications and whether or not they imply each other

Let A, B, C, and D be arbitrary statements. Consider the following implications: $\text{If $A$ and $B$, then $C$ or $D$}$ $\text{If $A$, then $D$}$ Question: Suppose that (1) is true. ...
3
votes
1answer
94 views

Models of the successor function

I would like to ask a few questions about models of the succesor function (s(x)=x+1), intact that is a bit vague, consider $T_{S}$ to be the set of axioms given by; S1: $\forall xy[s(x)=s(y) ...
3
votes
2answers
170 views

Is there a more useful formulation of the frame condition for the McKinsey axiom?

I am looking for a Kripke frame condition corresponding to the McKinsey axiom M: $\Box\Diamond p \rightarrow \Diamond\Box p$. I read somewhere the following condition: "For every partitioning of the ...
3
votes
4answers
404 views

logic puzzle (truth-tellers / liars)

I am trying to solve this puzzle. It is supposed to be solvable. There are 3 people A,B,C. One of them is always lying, one of them is always telling the truth and one of them is always answering ...
1
vote
2answers
50 views

Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
1
vote
1answer
88 views

Mathematical Logic descending chains

I'm working on a mathematical logic question. Suppose $<$ belongs to $S$ and $\Phi \subseteq L_{0}^{S}$. Assume that for any $m \in \mathbb{N}$ there is a model $\mathfrak{A}$ of $\Phi$ such ...
5
votes
0answers
118 views

Mathematical Thinking - How does it work? [closed]

Not only am I hoping you can answer my question, but perhaps refine my question itself. Unfortunately it is something I do not know how to ask, but I will give it my best attempt. Either I ask it, or ...
0
votes
0answers
41 views

Church’s Thesis with regard to R-decidability and R-enumerability.

Church’s Thesis with regard to R-decidability and R-enumerability: If some set is enumerable/decidable, then there exists a program, i.e., a register machine, with respect to which the set is ...
2
votes
1answer
121 views

A problem in the first-order predicate calculus.

So the teacher decided to make our life harder by giving us an extra-credit problem: Use the language of the first-order predicate calculus to express that in a group $ S $ of elements with a ...
1
vote
1answer
107 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
1
vote
0answers
58 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
1
vote
1answer
51 views

Translate proposition into formal language

Knowing that predicate $P(x)$ means '$x$ is a prime number' and $a/b$ denotes '$a$ is a divisor of $b$' express the following using logical operators, quantifiers, etc: 'number $z$ is a divisor of the ...
2
votes
2answers
82 views

Logical Implication Question

$A: \text{Humans are at most 12 feet tall}$ $B: \text{Humans are at most 9 feet tall}$ Neither implies the other. A contradicts B and B contradicts A. Am I correct?
3
votes
2answers
60 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
6
votes
1answer
76 views

Distance between theorems

In automated proving one can define the best proof of a theorem as the one which minimizes the length of the proof. Given a set of known statements one could define the difficulty of a theorem as the ...
1
vote
1answer
87 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
27
votes
5answers
1k views

Are there any nontrivial examples of contradictions arising in non-foundational or applied math due to naive set theory?

I understand that naive set theory, whose axioms are extensionality and unrestricted comprehension, is inconsistent, due to paradoxes like Russell, Curry, Cantor, and Burali-Forti. But these all ...
0
votes
1answer
25 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
2
votes
1answer
44 views

Question regarding using the natural deduction system

I have the following: Premise: ((V → ¬W) ∧ (X → Y)) Premise: (¬W → Z) Premise: (V ∧ X) |- (Z ∧Y) The part I want to know is how do I go about separating ...
2
votes
1answer
82 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
4
votes
3answers
190 views

A function defined for all inputs?

This might seem like a weird question, but is it actually possible to define a function for all possible inputs? By this, I really mean /all/ possible inputs, including numbers, true and false, sets, ...
2
votes
2answers
111 views

Soft question about logic and Banach-Tarski Paradox

I precise for the possible down voters that I'm not student in maths I'm learning chemistry, and my friend is learning litterature, and we were speaking about BT paradox, my friend discovers this ...
0
votes
0answers
50 views

If $\nvDash\phi$ must it be $\vDash\lnot\phi$? If $\nvDash\phi$ where $\phi$ first order sentence must it be $\vDash\lnot\phi$?

I got stuck at this problem: Determine whether the following sentences are true or false in first order logic: (1) If $\nvDash\phi$ must it be the case that $\vDash\lnot\phi$? (2) If ...
1
vote
3answers
326 views

Definition of the mathematical proof

How do we define a mathematical proof? Is it a series of arguments? Is it a series of conclusions? Is it manipulation of formulas? Is it a mixture of laws of logic and axioms,theorems or ...
2
votes
0answers
91 views

What are the connections between linear algebra and logic?

I was wondering whether someone could tell me what connections there are between linear algebra and first order or second order logic, whether it be the model theoretic or proof theoretic component of ...
9
votes
2answers
164 views

Can $T$, $T+A$, and $T+\neg A$ all have different consistency strengths?

Let $T$ be a consistent theory, and let $A$ be a statement in the same language. Consider the three theories $T$ $T+A$ $T+\neg A$ Is it possible for them to be pairwise distinct in consistency ...
0
votes
1answer
31 views

Proving $S_1 \subseteq S_2$ for transitive closure

This is one of the problem I have been working from Velleman's How to prove book: Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l (a) Let $S_1$ and $S_2$ be the reflexive ...
4
votes
2answers
102 views

Every theory eliminates quantifiers in an appropriate definitional expansion?

I need to prove that every theory eliminates quantifiers in an appropriate definitional expansion. For this, consider: let $T$ be a theory in language $L$. Consider the following expansion of the ...
2
votes
1answer
33 views

If for any $M' \subseteq M$ there is an embedding of $M'$ into a $Mod(T)$, then there is an embedding of $M$ into $Mod(T)$.

I need to prove that, for $M$ a given $L$-structure and $T$ be a theory in the language $L$. Show that if for any finitely generated substructure $M'$ of $M$ there is an embedding of $M'$ into a model ...
2
votes
4answers
308 views

Logical puzzle. 3 Persons, each 2 statements, 1 lie, 1 true

I got a question at university which I cannot solve. We are currently working on RSA encryption and I'm not sure what that has to do with the question. Maybe I miss something. Anyway, here is the ...
0
votes
1answer
138 views

Disjunctive normal form and shannon normal form

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form ...
0
votes
0answers
25 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
1
vote
2answers
121 views

Deduction theorem in modal logic

I am looking for a semantic for deduction theorem in modal logic,I wanna find a semantic way to prove this theorem,but I wasn't successful.tnx for your help
1
vote
1answer
49 views

Given a closed formula $B$ of a first order theory, if it's true in every countable model, is it true in every model?

Given a closed formula $B$ of a first order theory, if it's true in every countable model, is it true in every model? I'm not sure if this is true, but it sounds too powerful.
0
votes
1answer
62 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
2
votes
0answers
45 views

Is there a standard name for using a function application, rather than a variable, as a summation index, as in $\sum_{f(x)}$?

I am trying to find out whether there is a standard notion of generalizing indexing such as $\sum_i$ to function applications as in $\sum_{f(x)}$. Intuitively, the latter means "iterating over all ...
-1
votes
1answer
75 views

Complete operator base logic [closed]

Show that $F={0,\to}$ is a complete operator basis by giving equivalent formulas for negation,conjunction and disjunction over F.
0
votes
3answers
120 views

How is this true? Bookworm puzzle

This is from Eugene Northrop's book Riddles in Mathematics. Why is the answer 1 inch. Iit should be three. What logic am I missing here?
7
votes
3answers
127 views

Formal writing in math: equations

What is the formally correct way to solve a bunch of equations in math? Is it \begin{align} 42x = 4324 \\ x = 4324/42 \end{align} or \begin{align} 42x = 4324 \\ \Rightarrow x = 4324/42 \end{align} or ...
2
votes
1answer
44 views

Can the empty theory (in the language of Peano arithmetic) imply anything?

How can a theory, $T$ (a set of sentences in $L_{PA}$) which is empty imply something? Is it stated and assumed trivially that it implies a sentence such as $\phi(x): \forall x : x=x$ is implied by ...
0
votes
1answer
39 views

Eventually constant variable assignments

One proof of the Downward Löwenheim Skolem Theorem is via consideration of elementary substructures. In a discussion of this theorem, Christopher Leary writes the following: "Suppose that $ ...
0
votes
1answer
77 views

Characterisation of a complete first-order theory

Let $T$ be a set of formulas of a first-order language $L$. Show that $T$ is complete if and only if there is no sentence $A$ of $L$ such that both $T \cup \{ A \}$ and $T\cup \{\neg A\}$ are ...
2
votes
1answer
58 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
3
votes
1answer
60 views

What is the set of propositional formulas?

What is the set of propositional formulas? I am not sure if I understand this
1
vote
2answers
45 views

Non isolated types of $\mathcal M$ cannot be isolated in $\mathcal N \succ \mathcal M$?

Suppose $a \in M$ realizes a non-isolated type over $\emptyset$, and let $\mathcal N \succ \mathcal M$, furthermore let $|\mathcal M| = \aleph_o$ while $|\mathcal N| = \aleph_1$. Is it true that the ...