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)

35
votes
11answers
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 ...
4
votes
1answer
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 ...
1
vote
3answers
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 ...
0
votes
1answer
38 views

Which of the following conditions must necessarily be true?

Suppose that $\{A, B\}$ is a set of mutually exhaustive conditions, and that $\{C, D\}$ is another set of mutually exhaustive conditions. If the following implications are true: $$A \Longrightarrow ...
9
votes
1answer
221 views

Examples of Forcing in Model Theory

My question is exactly my title: What are some examples of (set theoretic) forcing in model theory? I have been studying (combinatorial) set theory and model theory (independently of one another) for ...
19
votes
3answers
1k views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
5
votes
1answer
63 views

Rewriting $X\leftrightarrow Y$ using only $\neg$ and $\lor$

Note: The book I'm using doesn't have any solutions/answers so I will be posting some of the questions I'm unsure about in the hope that someone will check it for me. Question: Re-write $X\...
2
votes
1answer
57 views

Statement calculus

Turn the statement 'either $X$ or $Y$' into an iterated composition. I'm not sure if my answer is correct, can someone please check for me? : $$\text{either }X\text{ or }Y \equiv (X\vee Y)\wedge (X\...
1
vote
1answer
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:...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 , ...
4
votes
2answers
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 ...
1
vote
1answer
153 views

2 Questions regarding Relative Consistency Proofs

First Question: Let IC be the statement "There is an inaccessible cardinal." I have read that one cannot prove (in ZFC) the relative consistency of ZFC + IC w.r.t. ZFC. i.e. $ Con(ZFC) \rightarrow (...
3
votes
2answers
205 views

Establishing the validity of an argument.

I've been trying to determine the validity of a particular argument for some time now and I've had no luck in figuring it out. The argument in question goes as follows: \begin{align} & p \wedge q \...
4
votes
2answers
61 views

Proving or disproving $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$

Prove/disprove: $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$ I know the LHS isn't like in the definition of ordered sets so it's probably false but I can't find any numbers as counter example, nor ...
1
vote
2answers
60 views

proof for propositional logic

I am unable to prove the following proposition logic. $(p \lor \neg r) \land (r \lor \neg p) \leftrightarrow (p \leftrightarrow q) \land (q \leftrightarrow r)$ My solution is given in the image. ...
1
vote
1answer
129 views

Existence of nonstandard elementary extensions of $PA$?

My question follows from the 1958 result of MacDowell–Specker (located originally in Modelle der Arithmetik, J. Symbolic Logic Volume 38, Issue 4 (1973), 651-652) of the proof of the following theorem:...
1
vote
2answers
41 views

Can we ignore predicates in a statement if they aren't used?

Prove/disprove: $$\forall a>0:a\in\mathbb R: \exists N\in\mathbb R:\forall x\in \mathbb R:\exists z\in\mathbb R:\forall n\in \mathbb N:|n-99|<N\Rightarrow n>10 \vee \frac {n^2} 4 \le 25$$ ...
3
votes
0answers
90 views

Is this a valid proof for $1+1=2$? [duplicate]

I am extremely new to proofs, and quite bad at them. In studying and practicing the different types of proofs, I developed this very rough proof that $1+1=2$, one of the simplest mathematical truths I ...
1
vote
2answers
148 views

Clarification regarding Drinker's paradox [duplicate]

This is the informal proof of Drinker's paradox The proof begins by recognising it is true that either everyone in the pub is drinking (in this particular round of drinks), or at least one ...
2
votes
2answers
109 views

Infinite sets having no RE subsets

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated. Proof: ...
2
votes
1answer
71 views

How to simplify Boolean expression: $(C'B')+(CB)$

I'm very weak in math and logic, and currently tried doing K-map, and got this as result: $$(C'B')+(CB)$$ My question is, can this be further simplified? I tried it myself, but I got $0$ (False). $...
4
votes
0answers
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 ...
2
votes
2answers
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". ...
1
vote
2answers
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?
1
vote
4answers
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.
0
votes
2answers
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" ...
1
vote
3answers
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 ...
2
votes
1answer
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 ...
-1
votes
2answers
69 views

Proof of a Proposition in Logic

Is it possible to prove the proposition if $P \land Q \Rightarrow R$ then $P \land R \Rightarrow \lnot Q $ or in other words ($P \land Q \Rightarrow R) \Rightarrow (P \land R \Rightarrow \lnot Q ...
2
votes
1answer
64 views

Consistency vs Inconsistency in a set of sentences: which is more common

I'm curious whether there is any research in the "probability" that a set of sentences in a first-order logic is consistent. Obviously, there are an infinite number of inconsistent sets and an ...
0
votes
1answer
88 views

Is this an upper bound or lower bound?

I came across a probability distribution function in my work, it is however difficult to find in closed form, therefore I am looking to either upper bound or lower bound it. Assuming $a,b,T$ are non-...
3
votes
1answer
65 views

Proving $P$ by proving $\neg Q$ and knowing $P\lor Q$

This may sound silly. I used to remember studying this in physics class and I thought of asking it in physics.stackexchange and then later I decided to ask it here itself. Let's say, under some ...
2
votes
1answer
67 views

Extension of theory

There are two languages $L_1=\{+\}$ with equation, where nonlogical symbol is binary function. There are formulas: $$φ≡∃n∀x(n+x=x)∧∃n∀x(x+n=x)$$ $$ψ≡∃n∀x(n+x=x∧x+n=x)$$ There are theories $T_1={φ}$, $...
3
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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$...
3
votes
1answer
43 views

$A\cong B$ then $Th(A)=Th(B)$

question: $A\cong B$ then $Th(A)=Th(B)$ answer: $\phi \in Th(A)$ then $A\vDash \phi$ and $A\cong B$ so we have $B\vDash \phi$ then $\phi \in Th(B)$ and $Th(A)\subseteq Th(B)$ and we could prove $...
1
vote
1answer
119 views

is this formula provable in predicate logic? ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1))

"Can you prove ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1)) in predicate logic? explain." I'm saying no, but I'm not sure why. Is it because it's not a tautology? and how would Godel's ...
1
vote
1answer
76 views

Where does this definition for the free variables of a formula come from?

I am doing some reading about this and I have come across the definition of a free variable. The free variables of a formula, $F V (\varphi)$, are defined by induction on the structure of $\varphi$: $...
-2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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. ...
3
votes
1answer
58 views

Existence of two unrelated pairs in a constrained relation

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 \\ \...
1
vote
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 ...
3
votes
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}...
3
votes
1answer
98 views

What does not having a first-order frame imply for models?

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