Questions tagged [logic]
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 following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).
27,996
questions
0
votes
1
answer
70
views
How do I approach finding a simplified function of an 8 variable boolean function given a truth table
I need two (8 variable) boolean function that gives
$$
F_1(A,B,C,D,W,X,Y,Z) =1 \iff ABCD≥WXYZ,\\
F_2(A,B,C,D,W,X,Y,Z) =1 \iff ABCD≤WXYZ,
$$
I cant imagine using K-maps but I think that I can use the ...
- 1,358
1
vote
1
answer
77
views
Is there a paper that formalizes questions from a mathematical perspective?
Is there a paper or text that formalizes what a question is, from a mathematical perspective? I am sure there has been some work on this topic. I would be very interested in work on the logic of ...
- 20.7k
3
votes
0
answers
87
views
Is "$Y=3$" common knowledge among the boy, the robot and the girl? How to apply the common knowledge formalism to this use case?
I am trying to understand the formalism of common knowledge. The sense behind the concept is already well explained here, however I struggle with linking the formalism to a practical use case.
When ...
- 1,594
-1
votes
2
answers
87
views
What is the definition of a statement implying or being equivalent to another statement given a background theory?
I understand what it means for a statement $P$ to imply, or be equivalent to, another statement $Q$. However, in mathematics, two statements are often not equivalent to each other by themselves, but ...
- 20.7k
0
votes
2
answers
185
views
Prove or disprove: if Γ ⊢ α and Γ ⊆ ∆ then ∆ ⊢ α
I am trying to solve this question but I am doubting about the answer. Namely:
Γ ⊢ α means that there is a derivation with conclusion α and with all hypothesis in Γ. Since Γ ⊆ ∆, we can use the same ...
- 67
0
votes
0
answers
118
views
Graph theory proposition proof using induction
Let $G=(V,E)$ be a graph with $v:=|V|, e:=|E|.$ Then a result in graph theory says that if $G$ is connected, then $v-1 \leq e$. The proof I know uses induction over $v$. I wondered, however, why this ...
- 597
0
votes
1
answer
64
views
How $b>a \lor a \leq 0 \implies \max(b,0)-\max(\min(a,b),0) \geq 0$?
Disclaimer: I'm not a mathematician. I'm a developer (with physics degree).
I'm programming tax form and stumbled on following (simplified) definition of one of the fields, lets name it P:
$$a = \dots$...
- 155
2
votes
2
answers
245
views
What is the formal definition of an equation?
I asked recently what a differential equation is, formally. However, I now realize that I should have asked a more basic question first. My question is, what is the formal, rigorous definition of an ...
- 20.7k
0
votes
1
answer
93
views
Modelling a problem in Graph Theory language
I am trying to model the following problem that I found in the AI field in graph theory language, but I have limited experience in graphs.
We consider a network of devices. If two devices are close ...
- 317
0
votes
1
answer
117
views
Gödel's Incompleteness Theorem - question
Could someone correct me on the below logic.
If a statement cannot be proved then I cannot find a contradiction to said statement. If I cannot find a contradiction to said statement then that ...
- 55
1
vote
0
answers
98
views
Intuition behind Solovay's proof of arithmetical completeness theorem
Solovay's Arithmetical Completeness theorem states that if $A$ is sentence of modal logic, then if every realization $A^*$ of $A$ is proved by $\mathsf{PA}$, then $\mathsf{GL}\vdash A$.
The way this ...
- 101
2
votes
1
answer
133
views
Fitch proof: Given $p(a), ∀x.(p(x)⇒p(f(x)))$, and $∀x.(p(f(f(x)))⇒p(g(x)))$, prove $∀x.p(x)$
I know how prove: Given $p(a), ∀x.(p(x)⇒p(f(x)))$, and $∀x.(p(f(x))⇒p(g(x)))$, prove $∀x.p(x)$
But I have no idea how I can prove: Given $p(a), ∀x.(p(x)⇒p(f(x)))$, and $∀x.(p(f(f(x)))⇒p(g(x)))$, prove ...
2
votes
3
answers
271
views
Disproving the statement $\alpha\rightarrow\beta\models\forall x.\alpha\rightarrow\forall x.\beta$
Prove or refute: $\alpha\rightarrow\beta\models\forall x.\alpha\rightarrow\forall x.\beta$
I believe that this statement is incorrect and want to provide a refutation for it. I know I should show that ...
- 29
4
votes
1
answer
277
views
If on a piece of paper you can draw a collection of points that satisfies the vertical line test, then there is a function that contains these points
I recently posed the following question in a comment section:
If I draw a curve on a piece of paper that passes the vertical line test and exhibits some particular property (e.g. 'Always greater than ...
- 4,984
-1
votes
1
answer
68
views
Forming simple epistemic logic formula from a given sentence
Sentence: I don't know if I know whether Lionel Messi is the GOAT.
$a$: I/Myself
$φ$: Lionel Messi is the GOAT
Attempt 1: $\,\lnot K_{a}\,(K_{a}φ \, \lor K_{a}\lnotφ)$
Attempt 2: $\,\lnot K_{a} \,\to ...
- 11
1
vote
2
answers
403
views
how can prove $n^n$ is primitive recursive
I try to prove $n^n$ is primitive recursive,first i try to releationate this proof with the proof of $x^y$, but in this case is different, because the base is not the same.
So my attempt was to see ...
- 39
1
vote
1
answer
83
views
Help in proving ∀x(¬A(x) → B(d)) ⊢ ∀xA(x) ∨ B(d) without using Disjunctive syllogism in the proof
Stuck on a problem of ∀x(¬A(x) → B(d)) ⊢ ∀xA(x) ∨ B(d), however the system I am using does not allow me to use DS in the proof. Here is another method I tried, but it says that it's wrong on the last ...
- 11
4
votes
0
answers
102
views
Recent literature on the gaps of reals on L or other inner models?
(I also asked this in MathOverflow)
I'm doing my Bachelor's Thesis on Gödel's constructible universe L.
I'm interested in the gaps without new reals (sets of natural numbers) in the hierarchy, as ...
- 159
0
votes
1
answer
105
views
How do I prove Separation Schema within ZFC?
I am assuming consistency of ZFC throughout this post. Here are what I believe is correct, but please correct me if I am wrong:
Every formal proof within ZFC uses finite fragment of ZFC.
Separation ...
- 772
1
vote
2
answers
170
views
proof of diamond lemma
I am trying to prove the diamond lemma: Suppose we have two elementary cancellations of a word
$w$
then there exists some $w'$ such that there are (possibly trivial) cancellations
The diamond lemma,
...
- 39
1
vote
0
answers
102
views
Should you avoid using the same variable name after existential elimination?
Existential Elimination (also called Existential Instantiation) says:
$$ \exists x[P(x)] \vdash P(c) \text{ For some c} $$
I was wondering whether it's bad form to use the same variable $x$ to ...
- 903
0
votes
1
answer
68
views
How do you derive (~P -> Q) from P v Q as the premise using Fitch?
I've been scratching my head about this for a while. I understand that the definition of an implication would make it ~~P v Q which is P v Q, but I can't figure out how to do it using the Fitch method....
0
votes
2
answers
122
views
Apply Resolution rule in this formula
Consider the following formula that i want check the whether it's satisfiable or not
$$\phi\equiv(u_1\vee v_3)\wedge(\neg u_1\vee \neg v_3)\wedge(u_2\vee v_4)\wedge(\neg u_2\vee\neg v_4)$$$$\wedge(u_2\...
- 21
2
votes
0
answers
189
views
How does one begin to build mathematical logic?
I'm reading a book on mathematical logic by Ebbinghaus, Flum and Thomas. It turns out that set theory is used to build formal languages. I mean, one begins with the definition of an alphabet, which is ...
- 649
0
votes
0
answers
67
views
Formulate a Graph with Predicate Logic
Let $L = \{R\}$ be a predicate language, with the $R$ being the relation that $2$ non-equal vertices are connected. I would like to formulate the following statements, with $v,u$ being vertices in $G$....
- 301
1
vote
2
answers
103
views
Relationship between independence and consistency: Why does Con$(\mathsf{ZFC})\implies\text{Con}(\mathsf{ZFC+\phi})$ imply $\phi$ can't be disproved
Forgive me, because I'm sure this question has been asked before because of how central it is to set theory/logic, but I cannot find it on stackexchange. If someone finds that this is a duplicate, ...
- 2,142
0
votes
3
answers
268
views
What is the truth value if any for $f(x)=y$ when $x$ is outside of the domain of $f$?
What is the truth value if any for $f(x)=y$ when $x$ is outside of the domain of $f$? Could it be false or undefined?
- 14.5k
1
vote
1
answer
168
views
Is the implies arrow logically equivalent to OR?
RESOLVED: I fundamentally just didn't understand implication. Thank you to everyone who helped!
I was going off of my linguistic understanding of "implies", which isn't the same. For example,...
- 13
0
votes
0
answers
57
views
Simplifying the boolean expression $Y = (A\cdot B \cdot C \cdot \overline{F})+(A\cdot B \cdot C \cdot E) + (A \cdot F) $
for the past hours, I have been simplifying a huge boolean expression. There is only one short piece missing, which, for the love of god, I can not manage to simplify.
The term is:
$$
Y = (A\cdot B \...
- 101
1
vote
1
answer
130
views
Which logical rules are used in combining universal quantifiers with same conditional
If I have
$$ \forall x: (x < 5) \rightarrow (f(x)<g(x)), $$
$$ \forall x: (x < 5) \rightarrow (g(x)<h(x)) $$
I'm allowed to combine the implication into:
$$ \forall x: (x < 5) \...
- 903
1
vote
3
answers
104
views
Which rule of logic is used on $\delta$ in this proof of the squeeze theorem
In the Squeeze Theorem delta epsilon proof, we get to a step where
$$
\begin{align*}
& \text{Let } \delta = \min(\delta_1,\delta_2,\delta_3). \\
& \text{Then by }(1), (3),\text{ and }(2) \\
\...
- 903
-2
votes
1
answer
44
views
$\forall x\in A(\in\mathcal P(E)),\,P(x)\Leftrightarrow\forall x\in E,\,(x\in A)\wedge P(x)$? [closed]
The question is in the title.
When I am working in $\mathcal P(E)$, do statements like $\forall x\in A,\,P(x)$ translate to $\forall x\in E,\,(x\in A)\wedge P(x)$ or to $\forall x\in E,\,(x\in A)\...
- 23
1
vote
2
answers
388
views
Why is the Absorption Law considered a Rule of Inference instead of Replacement?
The Absorption Law:
$$ P \rightarrow Q \vdash P \rightarrow (P \land Q)$$
However as wiki (which says it's a Rule of Inference) notes, this can be stated bidirectionally:
$$ P \rightarrow Q \...
- 903
3
votes
1
answer
112
views
ultrafilters as linear orders
In Henson's Model Theory lecture notes I found an exercise quite early on (1.30, p. 12) that prove too difficult for me. It goes like this:
Let $L$ be the first order language whose only nonlogical ...
- 107
1
vote
0
answers
44
views
Which logics cannot be "approximated" with real-valued semantics when the connectives are restricted to be continuous?
Which logics lack a real-valued semantics when the connectives are restricted to be continuous?
For the purposes of this question, I will assume that classical logic has the signature $\{\lnot, \to\}$ ...
- 11.7k
0
votes
1
answer
76
views
Can the distributive law be proven using only ∧-elimination/introduction and ∨-elimination/introduction?
I have been trying to figure out a logic problem for days now; I think I've made it so that my brain can only see one thing and can't look at it a different way. Basically, I need to prove the ...
- 507
1
vote
2
answers
212
views
Is there a difference between using two vs one universal quantifier for two variables?
Is $\forall x \forall y$ equivalent to $\forall (x, y)$?
For example, here is the statement of a Symmetric Relation in both ways:
$\forall x \forall y[xRy \rightarrow yRx]$
$\forall (x,y)[xRy \...
- 903
4
votes
1
answer
188
views
Diophantine vs. existential definability
We consider the language $\{+,\cdot,0,1\}$ of rings.
I want to understand how terminology is used in the work by J. Koenigsmann, Defining $\mathbb Z$ in $\mathbb Q$, Annals of Mathematics 183 (2016), ...
- 1,756
42
votes
6
answers
5k
views
In what sense does a number "exist" if it is proven to be uncomputable?
Uncomputable functions: Intro
The last month I have been going down the rabbit hole of googology (mathematical study of large numbers) in my free time. I am still trying to wrap my head around the ...
- 2,520
0
votes
0
answers
108
views
Help proving: $∀x_1∀x_2∀x_3(x_1<x_2<x_3→f(x_1)<f(x_2)<f(x_3))$ implies $∀x∀x′(x<x′→f(x)<f(x′))$ on the $\mathbb N$
Suppose I know the following:
$\forall x_1 \forall x_2 \forall x_3 \Big(x_1 \lt x_2 \lt x_3 \rightarrow f(x_1) \lt f(x_2) \lt f(x_3) \Big) \quad (\dagger_1)$
Could someone please explain, step by ...
- 4,984
-1
votes
1
answer
84
views
How to prove $(p \to (p \lor q)) \equiv\operatorname{True}$ [closed]
I know how to prove the expression $(p \to (p \lor q))$ being a tautology using truth table. I would also like to know how to prove it using algebraic methods.
Thanks in advance.
- 1
15
votes
1
answer
202
views
Are the algebraic real numbers an automatic structure?
In the 1950's, Julius Büchi showed that $(\mathbb{N},S,+,0)$ is not merely a decidable structure as Presburger had shown, but an automatic structure, i.e. there is an encoding of the natural numbers (...
- 10.2k
0
votes
1
answer
88
views
Representing first order sentences as conceptual graphs
Here are three first order axioms that represents a part of a mereology theory.
Reflexivity $\forall x : part(x,x)$
Antisymmetry $\forall x \forall y : ((part(x,y) \land part(y,x)) \implies (x = y))$
...
- 521
1
vote
2
answers
129
views
Proof of $x=y \rightarrow [P(x) \rightarrow P(y)]$
I'm having a hard time with the proof $x=y \rightarrow [P(x) \rightarrow P(y)]$. I know that the generic steps are: (1) Given $x=y$. (2) Assume $P(x)$. (3) Since $x=y$ and $P(x)$, then, $P(y)$. ...
- 621
1
vote
0
answers
84
views
Natural Deduction and Sequent Calculus
Are there any good natural deduction and sequent calculus solvers online for both predicate and propositional logic? Or perhaps forums that specialise in these proof systems?
3
votes
3
answers
88
views
Compact cardinal cannot be successor?
This is a follow-up question to $\kappa$ is compact $\implies$ $\kappa$ is regular. The definition I'm using for "compact" is the same as there.
I am trying to show if $\kappa$ is compact, ...
- 1,827
3
votes
1
answer
78
views
Is there notation for undecidability?
Assume that it is undecidable whether P=NP. Is there notation for this statement?
I have come across "¬□¬(P=NP)", which supposedly means that it is not provable, but it's clunky and not ...
- 299
0
votes
0
answers
65
views
Definition of semantic consequence relation for substructural logics
How does one define the semantic consequence relation for substructural logics? What options are available.
First a word on notation. Let $\mathbb{N}$ be the integers greater than or equal to zero. ...
- 11.7k
11
votes
0
answers
341
views
Can every functional equation be solved or proved unsolvable?
Recently, I have read articles about how some identities whose "solution" either cannot be determined within $\mathsf{ZFC}$ or other axiomatic systems or the solvability is closely related ...
- 8,347
3
votes
2
answers
369
views
Can a predicate be a contradiction?
In the university course I'm taking, a predicate is defined as a mathematical statement whose truth value depends on the variables involved in the statement. This definition makes me wonder whether a ...
- 83