# Tagged Questions

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 ...

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 ...
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\}$$ ...
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 ...
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 ...
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?
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. ...
94 views

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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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
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.
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 ...
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 ...
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.
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?
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 ...
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 ...