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)

0
votes
2answers
54 views

Prove that if $ \Gamma $ is inconsistent, then $\Gamma \vdash \beta $ for every formula $\beta$

Considering that $\Gamma$ is inconsistent if $ \Gamma \vdash ¬(\alpha \rightarrow \alpha) $ for some formula $\alpha$. How to prove that if $ \Gamma $ is inconsistent, then $ \Gamma \vdash \beta $? ...
2
votes
1answer
64 views

Which theorems of classical mathematics cannot be proved without using the law of excluded middle?

The law of excluded middle is a logical principle that says that for any sentence $A$, the sentence $A\lor\,\neg A$ is true. This is a valid law of classical logic, but is rejected by intuitionistic ...
0
votes
1answer
37 views

How to prove equivalence of different definitions for compactness?

My workbook considers three different definitions for compactness in logic. It says that it can be shown that these are equivalent, but what would be a strategy to show this? I'm familiar with showing ...
1
vote
1answer
25 views

negating propositional formula with quantifiers

In order to solve an exercise in computer sciences (proving a language $L$ to not be context-free) I need to negate the Pumping-Lemma. I was provided with the definition in the following form: If $L$ ...
1
vote
0answers
20 views

How to find the best way with the least amount of steps to find the matching hole (2 balls and 100 holes given)? [duplicate]

To extend the heading a little bit further. There are 100 holes ordered from min to max (min-hole with minimal radius, max-hole with maximum radius). There are two balls given which are to be used to ...
2
votes
5answers
70 views

Proof by mathematical induction (conditional statements)

Suppose we need to prove a statement of the form $$\forall n\in\mathbb{N}(P(n)\to Q(n))$$ where $P(n)$ and $Q(n)$ are propositions using mathematical induction. Say for the base case $n=1$ it is true. ...
1
vote
1answer
34 views

I have a question involving logical quantifiers which I have been stuck on for a while. I have trouble understanding the concept.

There is a question that has been bothering me where the concept is confusing to me. Assume B is the set of all boys and G is the set of all girls. L(B,G) represents that B likes G. $$\forall b \in ...
0
votes
1answer
53 views

Proof of a theorem using Hilbert's system

I am trying to prove various theorems considering a Hilbert System. However, i could not find the answer for these three. $\vdash(\alpha \rightarrow \beta) \rightarrow ((¬\alpha\rightarrow\beta)\...
0
votes
2answers
82 views

What is the set of all premises called?

An argument has two parts, the set of all premises, and the conclusion drawn from said premise. Now since there's only 1 conclusion, it would be weird to choose a name for the 'second' part of the ...
1
vote
1answer
118 views

How Do I Prove the 6 Letter Thesis Cδδ0δp?

There exists a 1951 paper by C. A. Meredith which proves a completeness meta-theorem for the "C, 0, δ, p" system which has as it's sole axiom Cδδ0δp under uniform substitution for propositional ...
-2
votes
1answer
24 views

How many k-ary functions are there for n-valued logic? And what are the formal language implications?

I believe the answer is n^n^k for any values n and k, where k=the number of arguments and n=the number of possible values that may be taken on. I just want to verify this, since I haven't been able to ...
0
votes
1answer
39 views

“logical constant” vs “logical variable”

I'm learning introduction to logic on coursera offered by Michael Genesereth with Stanford University, where the the course used the term "logical constant" to denote a proposition sentence. For ...
1
vote
2answers
38 views

precedence problem of multiple implication operators in logics

Should a→b→c be read as (a→b)→c or a→(b→c)? I used a online truth table generator (http://logic.stanford.edu/intrologic/secondary/applications/babbage.html) to test and got a→(b→c) is the ...
0
votes
0answers
22 views

Putting this formula in Prenex Normal Form

Given this well formed first order logic form: $\forall x (\mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \mathcal A_2^2(x,y)) \Rightarrow (\forall x \ \mathcal A_1^2(x,\mathcal f_1^2(y,z)) \lor \forall ...
0
votes
2answers
46 views

Prove in axiomatic system S

The question is to prove this in the axiomatic system S: $$(\forall x)(\forall y)((A_x \rightarrow R_{xy}) \rightarrow \neg A_y) \vdash (\forall x)(R_{xx} \rightarrow \neg A_x) $$ The problem is,...
0
votes
1answer
41 views

Switches, Lights, and Logic!

Venus has switches at the top and bottom of her stairs to control the light for the stairwells. (Why she has lights on the side of her stairs, I don't know...) She notices that when the upstairs ...
0
votes
1answer
35 views

Show for closed terms $t$ and formulas $\phi$. Given a structure $M$: $M\vDash t = \overline{t}\,^M$

Show for closed terms $t$ and formulas $\phi$. Given a structure $M$: $$ \begin{align} M&\vDash t = \overline{t}\,^M\\ M&\vDash \phi(t) \leftrightarrow \phi(\overline{t}\,^M) \end{align} $$ ...
3
votes
2answers
76 views

Prove $(A\rightarrow C)\land(C\rightarrow\neg B) \land B\rightarrow\neg A$ is valid without using truth tables

just finished proving an argument without the use of truth tables and was wondering if my reasoning is sound. The problem given was Prove using a proof sequence that the argument is valid (hint: ...
-1
votes
2answers
49 views

How to prove semantical equivalence?

Prove that: If $ \alpha \equiv \beta $ and $ \beta \equiv \gamma $ then $ \alpha \equiv \gamma $ I know that: $ \alpha \equiv \beta $ if and only if $ \alpha \leftrightarrow \beta $ is a ...
-1
votes
1answer
52 views

Verifying an equivalence using propositional logic theorems

How to verify the following equivalence: $ \alpha_1 \to \alpha_2 \to ... \to \alpha_n \equiv \alpha_1 \land \alpha_2 \land ... \alpha_{n-1} \to \alpha_n $ How should I use the deduction theorem in ...
0
votes
0answers
12 views

Valuation in the proof decidability of normal systems of modal logic

In The logic of provability, by G. Boolos, it is stated in the chapter 5 that if L is a formal system between $GL$, $T$, $B$, $K$, $K4$, $S4$, $S5$; then $L\vdash D$ iff $D$ is valid in all models of ...
1
vote
1answer
52 views

On the truth of $GLS$ and Löb's theorem

Consider the formal system $GLS$, whose axioms are the theorems of $GL$ plus all sentences of the form $\square A\rightarrow A$. A translation maps a sentence of modal logic to a sentence in the ...
1
vote
3answers
55 views

Why does $p$ (is true) strictly agree with $p$ while $p$ (is false) strictly disagrees?

Let's make the truth table: $$\begin{array}{|c|c|c|} \hline p&(p) \text{ is true}&(p) \text{ is false}\\ \hline T&T&F\\ F&F&T\\\hline \end{array}$$ "$p$ is true" strictly ...
0
votes
3answers
93 views

When is a definition via properties considered valid?

How one would define the validity of a definition of an object by its properties? Little background: I'm trying to implement a kind of framework of mathematics in which the user is not restricted to ...
3
votes
2answers
50 views

Can a simple (atomic) proposition be a tautology?

Definition: "A tautology is a propositional formula that is true under any truth assignment to each of the atomic propositions in the domain of propositional function." Let $p$ be a simple (or atomic)...
1
vote
1answer
22 views

$\vDash \phi \Rightarrow\, \vDash \psi$

How can I prove the last part of the following exercise. Show that $R\vDash \phi \Rightarrow R\vDash\psi$ for all structure $R$ implies $\vDash \phi \Rightarrow\, \vDash \psi$, but not vice versa. ...
0
votes
0answers
26 views

Minimalistic Statements

Is "for some(at least 1 tupel) $a,b\in\mathbb{Set}$ $a\circ b=b\circ a$" a statement? And if so, why would only "$a\circ b=b\circ a$" be no statement?
0
votes
0answers
26 views

Categorical semantics for dynamic epistemic logic

Dynamic epistemic logic tries to reason about knowledge that certain actors (people, machines, etc.) have and how it can change in response to outside events. It is usually possible to discuss such a ...
1
vote
1answer
31 views

Logical equivalences of quantifiers

This is an excerpt from the Kenneth Rosen book of Discrete Mathematics. Show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent (where the same domain is used throughout). This ...
0
votes
1answer
31 views

What is objective and observer in logic?

I am a beginner at logic and took a elementary course in it... Could someone help me in the elementary definition of some part of a proposition that build the semantic part of a programming language ...
0
votes
1answer
57 views

Incompressible countable Total-ordering implies well-ordering i

A totally-ordered set (S,<) is incompressible if $(S,<) \cong (T,<)$ and $S \supseteq T$ implies $S = T$. Is it true that if $S$ is incompressible countable and totally-ordered then $S$ is ...
1
vote
0answers
35 views

Applied Rational Choice Theory

I am a programmer researching the application of Rational Choice Theory. I have found many links to the philosophical nature of it. And fewer documents formalizing it's mathematical principles. ( ...
-4
votes
2answers
42 views

Use the laws of logic to simplify the expression [closed]

Use the laws of logic to simplify the expression P∨¬(¬P→Q)
0
votes
1answer
28 views

Invalid Application of Universal Introduction

The following is my attempt to formalize Berkeley's argument that it's not possible for a sensible object to exist without conceiving it. Line $3$ involves a meta-argument which I believe might be ...
0
votes
1answer
41 views

Proving the equivalence between two congruences.

According to this answer (and the modular arithmetic theory), $ax\equiv ay \pmod{n} \iff x\equiv y \pmod{n}$, if $a$ and $n$ are relatively prime. I tried to prove the forward implication but reached ...
3
votes
1answer
61 views

What is the pushout of $\mathbf{1} \longleftarrow \mathbf{2} \longrightarrow \mathbf{1}$?

I wonder what the pushout of the following diagram would be $$\mathbf{1} \stackrel{f}{\longleftarrow} \mathbf{2} \stackrel{g}{\longrightarrow} \mathbf{1}$$(here $\mathbf{1}$ and $\mathbf{2}$ denote ...
0
votes
1answer
28 views

Set of “perfect” Numbers in quantor logic

Write $D=\{6,28\}$ as the set of perfect numbers which are bigger then 2 and smaller then 30. $D=\{x\in\mathbb{N}:(2<x<30)\wedge (d_{1,2,...,i}\in(\{d\in\mathbb{N}:d|x\}\backslash\{x\}):d_1+d_2+...
0
votes
1answer
36 views

$y \in \{x:\varphi(x)\} \longrightarrow \varphi(y)$ not $\longleftrightarrow \varphi(y)$

In "Axiomatic Set Theory" By Patrick Suppes there is a Theorem Schema 47: $y \in \{x:\varphi(x)\} \longrightarrow \varphi(y)$ (available on books.google.com, page 34) Then on page 36 (also avilable ...
0
votes
1answer
83 views

Doing math with nonstandard numbers

Assume we have a computable, nonstandard model of Robinson arithmetic consisting of the set of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their ...
1
vote
0answers
37 views

Set of primetwins below 30

The Subset $C$ of the primes between 1 and 30, which have at least one primetwin (eg. 11,13). Would this be correct? $C=\{x\in \mathbb{N}\backslash\{1\} :(\nexists a\in \mathbb{N}\setminus\{1,x\}(a\...
0
votes
2answers
41 views

Non model-theoretic, constructive proof that it is valid to introduce new unique constants in a first order theory with equality

I'm currently reading through Mendelson's `Introduction to Mathematical Logic', and one of the proofs has left me dissatisfied. In general, I am fine with seeing metamathematical results proven ...
0
votes
2answers
44 views

Are these two sentences logically equivalent?

What i'm essentially asking is if the following statement is true: $ \forall x \exists y (R(x) \lor Q(y)) :\Leftrightarrow \exists y \forall x (R(x) \lor Q(y)) $ where $:\Leftrightarrow $ means ...
3
votes
1answer
34 views

Confusion about there exist and forall

Which of the following is a correct predicate logic statement for "every natural number has [at least] one successor?" \begin{align*} A: \quad & \forall x\exists y\left(\operatorname{succ}(x,y)\...
0
votes
1answer
24 views

Logic determine whether a set is consistent

I got a question regarding defining whether a set of formulas is consistent in predicate logic. For example if we have the following sets: ...
3
votes
0answers
89 views

Definition of “Differentia” in Lewis Carroll's Symbolic Logic?

I am reading chapter $2$, and from what I understand, it seems like the differentia of a class is not well-defined. The book gives some definitions: The class "Things" here refers to the class ...
4
votes
1answer
79 views

Appealing axioms incompatible with large cardinal axioms

I'm interested to know what are some 'appealing' axioms that are inconsistent with ZFC plus some large cardinal axiom. I saw the question On the contradictory nature of large cardinals & choice-...
0
votes
1answer
25 views

A lemma for interpolation for propositional logic

I'm working on an exercise for William Craig's Interpolation Theorem for propositional logic, and I'm having troubles proving the following lemma: Let ϕ and ψ be sentences of propositional logic and ...
4
votes
0answers
53 views

Is there a schsim between classical logic and categorical logic?

I've been trying to learn a little bit more about the foundations of mathematics, and it has strike me that there seems to be two competing points of view about what the foundations should be. While ...
0
votes
0answers
22 views

Street problem validated with SMV. How to model this problem?

I'm new with SMV and I am trying to solve the following problem using SMV. (http://www.kenmcmil.com/smv.html) Problem: Environment: A cross with three times signal (the first for pedestrians, the ...
0
votes
1answer
29 views

Showing validity of a formula in first order logic [duplicate]

So I'm trying to prove the validity of this formula and I am a bit lost, not sure how to start. I know generally speaking a valid formula is one where if all the premises are true, then the conclusion ...