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

3k views

### Why not both true and false?

Why can't some mathematical statement (or whatever is the correct term) be both true and false? For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive ...
121 views

### Is there any identity which cannot be proved

For example, if we want to prove that $a^2+b^2\ge 2ab$ for all $a,b\in\mathbb{R}$, we will start from something which is true (axiom or something that is already proved). In this case we will use fact ...
370 views

### Elementary embeddings vs isomorphisms

I'm trying to get a better handle on the concepts of literal embeddings, elementary embeddings and isomorphisms, as the show up in logic. This is the problem: It seems to me, (and is, according to my ...
38 views

91 views

### o-minimal structures and definable functions

Consider the following definition of an o-minimal structure: An o-minimal structure $O=\{O_n\}$ is a sequence of Boolean algebras $O_n$ of subsets of $\mathbb{R}$ which satisfies the following axioms:...
166 views

### A ⊆ B ∪ C -> x ∈ B or x ∈ C.

This is one of the problem I have been working from Velleman's How to Prove it book: Theorem: Suppose A, B, and C are sets and A ⊆ B ∪ C. Then either A ⊆ B or ...
84 views

### Proof in sequent calculus without cut

I met an exercise in Gaisi Takeuti, Proof Theory [Exercise 2.7, page 14]. How to construct a cut-free proof of$\ \forall xA(x)\rightarrow B\vdash \exists x(A(x)\rightarrow B)$, where A(a) and B are ...
33 views

### How to prove that predicate is expressible?

I have to prove, that predicate "x is transposition" in $S_5$ group. I can use such symbols, as *, 1, -1, =. However, I don't know any algorithm or way, which can ...
83 views

### Translate sentences in first-order logic

I need to translate the following sentence: "All mothers love their daughters". I thought: $\forall X \forall Y (mother(X) \wedge daughter(Y, X)) \Rightarrow love(X, Y)$ but on my book I found this ...
1k views

### Is this a correct solution to determining which of two people is the liar using one question?

I am a newbie to Stack-Exchange and if there is any problem in my question -- I apologize beforehand . I was working my way through some Propositional Logic Questions in Discrete Maths by Rosen , ...
87 views

### Logic - Prove the following

Here's the Problem: Which one of these is true? A) All of the below B) None of the below C) Some of the above D )None of the above E )None of the above My attempt: Suppose ...
153 views

115 views

### Is there a logic to formalize the concept of “understanding” [closed]

The question may seem little bit weird given that philosophers have been struggling to have a full grasp on the concept of "understanding". But I'm wondering if there are any logics (modal-based or ...
70 views

### All Vatican anarchists are honest and dishonest at the same time if there is no anarchists in Vatican! How to resolve this contradiction? [duplicate]

Lets suppose we want to investigate proposition "All Vatican anarchists are honest". We can transform this proposition into implication "If a citizen of Vatican is an anarchist then he/she is honest". ...
44 views

### when does $a\in\mathbb{R}$ does $\neg(a\leq 15\implies a>1)$ hold? [duplicate]

How can I formally write down for which $a\in\mathbb{R}$ the statement $\neg(a\leq 15\implies a>1)$ holds?
111 views

### Help with proposition whether it's true or false [closed]

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0)$$ And why? I'm confused as to what exactly is being claimed.
58 views

### Simple rewrite of a question to mathematical form

Simple rewrite of a question For all real numbers x with $x^2-3 x+2\leq 0$, $1\leq x\leq 2$ I am trying to put this into a better form, Could someone give me feedback : stands for: "Such that" ...
149 views

### Extended Socratic Syllogisms?

I'm not entirely sure where I might ask this, but there is a logic tag, so I guess this fits the budget. I am taking an introductory course on logic, mainly revolving around Syllogisms, or a logical ...
68 views

### Flattening quantification over relations

I already asked this question in stack overflow here and somebody suggested to post it here. I repeat the question again: I have a Relation f defined as $f: A \to B × C$. I would like to write a ...
69 views

36 views

### Logics for resource control over time

I'm studying proof theory and I've seen that linear logic can be used as a "way" to control resources usage, since by the propositions-as-types it is equivalent to the linear lambda calculus. Is ...
49 views

### Propositional formula, consisting of $p, q, r$ is true iff only one of them is true

I have some difficulties in building a formula $\phi(p, q, r)$, which is true iff only one of the variables is true. I suppose that it's reasonably to start trying, using the truth table, but ...
41 views

### infinite mape is $k-$colourable if and only if each finite subset of the map is $k-$colourable

Prove: An infinite map is $k-$colourable if and only if each finite subset of the map is $k-$colourable . How to use compactness theorem at this problem? And the compactness theorem says that $\sum$...
43 views

96 views

### fake proof of $\forall a. \forall b. a = b \to 1 = 0$

I saw a less formal version of this fake proof that claimed to prove $2=1$ but because it assumed $a=b$ from the start I knew why it was wrong. It does seem however that the proof can be used to prove ...
139 views

### What syntax exists for higher order logic?

I know this is sort of a broad question, but I'm having trouble getting a handle on the syntax for higher order logic, when going from first order logic. Basically I want to be able to do resolution ...
98 views

### Beginning Haskell - cannot understand proof

I've just started reading "Thinking Functionally with Haskell" by Richard Bird In the preface he states : And after stating the proof he also states the proof will be used throughout the book. ...
Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$\exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ \... 2answers 349 views ### Prove ( \lnot C \implies \lnot B) \implies (B \implies C) without the Deduction Theorem The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove (\lnot C\implies\lnot B)\implies(B\implies C) by using the three axioms (A1,A2,A3) without using ... 2answers 69 views ### Proof, is \lnot p \land \lnot q \vdash p \iff q? I have derived the proof to some extent, mentioned below:-$$\begin{array}{rll} 1. &\lnot p \land \lnot q &\text{Premise} \\ 2. &\lnot p &\land\text{elim}...
There are formulas in modal logic which which do not have a first-order frame condition, as stated here (Non-Sahlqvist formulas, Wikipedia). An example is the McKinsey formula for $p$: \Box\,\...