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).
26,500
questions
0
votes
0
answers
21
views
Why are there 5 propositional connectives in propositional calculus?
I don't understand why there are 5 propositional connectives (conjuction, disjunction, implication, negation and equivalence) that are regularly given a priori in propositional calculus?
If the goal ...
5
votes
0
answers
47
views
When should one use transfinite induction?
I've come across it multiple times now in proof theory papers that authors use (sometimes quite elaborate) inductions in order to prove easy results. The most striking example is the following, where ...
- 650
4
votes
0
answers
91
views
Gödel on the “True Reason” for Incompleteness
In footnote 48a of his famous paper on incompleteness, Gödel writes:
[T]he true reason for the incompleteness inherent in all formal systems of mathematics is that the formation of ever higher types ...
- 141
3
votes
1
answer
57
views
Intuitionistic Logic vs Constant Domains
Quantified modal logic is a controversial field, specifically since it forces one to consider what is meant by “world” in Kripke Semantics. For example, the formula $\Box \forall x \varphi \implies \...
- 467
-1
votes
0
answers
31
views
Determining a statement's truth value from given definitions [closed]
Let the predicates $P(x)$ and $Q(x)$ be defined on set $\{a, b, c\}$ as
\begin{array}{|c|c|c|c|}
\hline
x& a & b & c \\ \hline
P(x) & 1& 1&0\\ \hline
\end{array}
\begin{array}{|...
- 1
-3
votes
0
answers
22
views
use the law of logic to show that ~(p->~q) ^(r->q)^q is equivalent to p^q [closed]
Use the law of logic to show that ~(p->~q)^(r->q)^q is equivalent to p ^ q. Explain each step fully
- 1
0
votes
0
answers
47
views
Ambiguity about principle of excluded middle
According to the principle of excluded middle, every statement is either true or false.
It might sound a little ridiculous, but consider the following statement:
Mountains believe in God.
Believing ...
- 144
1
vote
0
answers
26
views
How to proof that Classic (Propositional) Logic and Priest's (Propositional) Logic of Paradox have the same logical truths?
As far as I understand it, in Priest's "Logic of paradox" there is a proof to the effect that $\phi$ is classically valid IFF $\phi$ is valid in the Logic of Paradox (LP), that is: $\vDash_C ...
- 111
0
votes
0
answers
36
views
How to understand Godel's Theorems [duplicate]
Can someone with close to zero knowledge of higher mathematics understand Godel's Theorems or does he first have to learn some mathematics? If the answer to the first part of the question above is yes,...
1
vote
0
answers
35
views
Software Recommendation for Theorem Suggestions
So I am not sure if this software already exists or perhaps this is something that humanity has to embark on to finally have as a product. A bit about myself, I am student training in a sub-area of ...
- 75
0
votes
1
answer
24
views
Ockhamist temporal language - confusion on definitions
What does $T,t',b \models\phi$ mean? Is it the same as $T,t' \models \phi$ after you have fixed the branch $b$ and $t'$ such that $t' \in b.$ If so wouldn't "for all branches $b'$ through $t$: $T,...
- 186
1
vote
0
answers
77
views
$ \exists \alpha>0 \quad \forall s>0 \quad \exists x>1 \quad\left|\int_1^x \frac{f(t)}{(t-1)^\alpha} d t\right|<s$ and its negation
Suppose $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function. Write down the negation and decide whether the statement or its negation is true and then prove it.
$$
\exists \alpha>0 \...
- 11
0
votes
1
answer
29
views
Priorean temporal language - Show that U (the until operator) is not definable
The definitions i am working with are:
U is the until operator:
To show U is not definable i'm trying to come up with two bisimilar models that disagree over some formula involving U.
The textbook ...
- 186
2
votes
0
answers
37
views
What does it mean that we need $𝜖_0$ induction to prove PA consistency?
I have started to learn about Peano Arithmetic, and also about ordinals.
In particular, I have seen that the Goodstein theorem is an example of a statement that can be expressed in PA but that ...
- 389
1
vote
0
answers
23
views
Two definitions of $\limsup$ on sequences of sets and underlying logic systems
Let $X$ be a set, $(E_n)$ be a sequence of subsets of $X$. As I know, the definition of $\limsup_n E_n$ is the subset of $X$ consists of $x \in X$ such that $x \in E_n$ for infinitely many $n$. Also, ...
- 148
2
votes
0
answers
63
views
Is there a sheaf model where the Weak Markov's principle fails?
We define a real number $x$ to be pseudopositive if $\forall y \in \mathbb{R}$ we have $ \neg \neg (x > y) \vee \neg \neg (y > 0) $.
The Weak Markov's Principle (WMP) is the axiom that every ...
- 577
-1
votes
0
answers
33
views
How to find latitude and longitude values of point on surface of earth knowing the latitude and longitude values of a point nearby
Assume that there are two points $x_1$ and $x_2$ on the surface of the earth. Assume that we know the distance between both points, and we know the geo-coordinates (longitude and latitude) of $x_1$. ...
2
votes
0
answers
57
views
Can Gödel's theorem be proved within PA?
Gödel proves his theorem informally by using natural languages. However, is there a way to carry out his proof in PA itself? (so that maybe PA could prove that itself could not prove its own ...
- 21
2
votes
1
answer
158
views
Beginner logic question on the continuum hypothesis
I am very new to logic and don't know very much about it.
One thing that I know is that there are models of ZFC in which no cardinal lies strictly between $|\mathbb{Z}|$ and $|\mathbb{R}|$. There are ...
- 5,337
0
votes
1
answer
94
views
Statement is true but contrapositive is false?
It seems that the contrapositive of a true statement is true. Consider the following:
$A,B,C,K\in \mathbb{N}$
$\exists A,B,C: A^K+B^K=C^K→K≤2$
Take the contrapositive: $$K>2→∀A,B,C:A^K+B^K<C^K∨...
0
votes
1
answer
92
views
"No integers $x$ and $y$ exist for $28x+7y=8$"
What is the logical structure of this statement?
No integers $x$ and $y$ exist for $28x+7y=8.$
I'm not sure, but I think the answer is
$$¬∃x\;∃y\;(x ∈ \mathbb Z ∧ y ∈ \mathbb Z ∧ 28x + 7y = 8).$$
- 11
0
votes
1
answer
42
views
Gödel's second incompleteness theorem and Consistency.
According to Gödel's second incompleteness theorem, no consistent axiomatic system which includes Peano arithmetic can prove its own consistency. As I understand it, this result contributed to spark a ...
- 1,261
0
votes
1
answer
39
views
Every subset of $\Bbb N$ is defineable in the language of monoids
Let $\mathcal L=\{\cdot,e\}$ be the language of monoids so that $\cdot$ represents an operation which is closed and associative, and $e$ represents an identity. Consider the structure of natural ...
- 4,959
-4
votes
0
answers
27
views
For any sets 𝐴,𝐵,𝐶 within a universal 𝑈 set, prove that 𝐴∪𝐵⊆𝐶 iff (𝐴∪𝐶)∩(𝐵∪𝐶)=𝑈? [closed]
Need help with this one, not sure how to prove this. For logic class, and need a proof using set rules.
- 37
1
vote
0
answers
31
views
Names for two different kinds of first-order graph properties
Let's define a simple graph as a model of $\{ \forall x (\lnot xRx), \forall x y (xRy \to yRx) \}$.
Consider the property of a graph $G$ being bipartite.
This property can be encoded with a first-...
- 9,228
1
vote
2
answers
100
views
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ [closed]
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$
Confused on how to do this, any help would be great.
Correction: Accidentally ...
- 37
0
votes
1
answer
76
views
What is the reason for different typographical symbols for logical operators?
I thought that ∧ is a standard symbol for logical conjunction used in textbooks. I understand that many typographically restricted environments, e.g. programming ...
- 171
1
vote
1
answer
61
views
Is there a G4ip equivalent for first-order logic?
G4ip is a sequent calculus for propositional logic (by Dyckhoff) that is contraction-free, thus (if I understand correctly) greatly simplifying the writing of automated theorem provers by avoiding ...
- 13
-5
votes
0
answers
36
views
Liars, Truth-Tellers, and Alternators [closed]
In an isolated village, there are three tribes: the Liars, the Truth-Tellers, and the Alternators. The Liars always lie, the Truth-Tellers always tell the truth, and the Alternators alternate between ...
- 445
0
votes
1
answer
55
views
Alternative proofs that connectedness is not a first-order property of simple graphs
Are there proofs that connectedness is not a first-order property of simple graphs besides the two proofs (or perhaps one proof) shown below?
For motivation, I'm interested in techniques for showing ...
- 9,228
-3
votes
0
answers
32
views
Prove: (((A ↔ B) → C) → (¬(A ∧ B) ∨ C))
How does one prove (((A ↔ B) → C) → (¬(A ∧ B) ∨ C)) is a tautology in TFL? I have been struggling with this natural deduction problem for weeks. Any help is appreciated.
-3
votes
0
answers
75
views
Math logic for applying different lightness weights on colors
I have "colorA" with lightness $= 0.69$ (range is $0-1$). I want to decrease its lightness to $= 0.32$? Thats a $0.37$ decrease.
However I also have "colorB" with lightness $= 0....
- 49
1
vote
1
answer
58
views
The concepts of P, NP and NP_complete problems for the dummies
While there are already lot of questions on this topics here on Mathematics (1,2, 3) and several (too many perhaps) Wikipedia pages on the subject (a, b, c), they all involve concepts that I am not ...
- 239
0
votes
1
answer
58
views
Policy fallacy in a youtube video
The picture of a YouTube video below suggests that out of policy A, B, or C in a 3-voter system, policy A would win. The voters ranked policies by how much they favorite them. However, if we rank ...
0
votes
1
answer
44
views
Forcing $\pi_1(\tilde f(a))=f(a)$ for an object of a sigma type
Suppose I have an object $f$ of type $\Pi x:A.B(x)$, and consider a new type $\Pi (x:A).\Sigma (t:B(x)).C(t)$. If $\tilde f$ is an object of the second type and $a:A$, then $\pi_1(\tilde f (a)):B(x)$, ...
- 177
1
vote
1
answer
32
views
Logical implication in existence of partial derivatives with non differentiable function
I ask for some help in unknotting this chain of reasonings, in particular in spotting logical errors due to wrong implications and possible mathematical misbeliefs about this problem.
Theorem: If $f(x,...
- 2,059
0
votes
0
answers
47
views
Is Perturbation Theory a mathematical consistent theory? [closed]
My bet is that it's not consistent mathematically in the sense of logical consistency.
But I cannot pinpoint any mathematical contradiction in it.
Maybe because it's an area in applied maths then it's ...
- 4,057
0
votes
0
answers
44
views
Proof in Natural Deduction, Sequent Calculus or Hilbert System
Is there any smart way to check if certain statements are not provable in any of these proof systems?
Like for example the following task:
Prove or disprove the following statements:
$\vDash \exists ...
- 69
0
votes
2
answers
64
views
Adding $\tfrac{}{\Gamma \varphi}$ (for a fixed non-correct $\Gamma \varphi$) to the rules of the sequent calculus, can one now derive every sequent?
One knows that the sequent calculus over the set of sequents $\Gamma \varphi$ is correct and complete, meaning that the derivable sequents are precisely the correct ones.
However, adding just one ...
- 33
0
votes
0
answers
36
views
Set of consequences of $\Gamma$.
Let $\text{Con}(\Gamma):=\{\varphi:\Gamma\vdash\varphi\}$. Prove that $\text{Con}(\text{Con}(\Gamma))=\text{Con}(\Gamma)$.
I think I have the first inclusion. Let $\varphi\in\text{Con}(\text{Con}(\...
- 449
0
votes
1
answer
73
views
Question on finite structures
I need to find a sentence such that it is valid for all finite structures but false in some infite structure. I've couldn't find any sentence that includes only "=" to be true in finite ...
- 83
-2
votes
0
answers
71
views
Where should models come from? [duplicate]
I am studying logic and trying to understand the meaning of model theory (I have read this and the Wikipedia page on Model theory).
My understanding if that a theory is concerned with:
a language, in ...
- 389
2
votes
1
answer
53
views
Cardinals In Boolean-valued models
I had two questions on Cardinals in Boolean-valued models.
First question: What is the difference between $\hat{\aleph_{\alpha}}$ and $\aleph_{\hat{\alpha}}$ ? (If I understand correctly, the first ...
- 523
-2
votes
0
answers
35
views
Elementary Function Arithmetic functions construction [closed]
Elementary Function Arithmetic: https://en.wikipedia.org/wiki/Elementary_function_arithmetic
It seems that most of the finite functions can be constructed from basic elementary functions. But I don't ...
- 37
2
votes
1
answer
183
views
Having hard times to understand the double negation translation implications. Is constructive logic at least as strong as classical, after all?
I do understand that constructive logic forbids the "lemma of excluded middle" for various reasons (let's not discuss these now).
I do understand that lots & lots of classical theorems ...
- 1,426
0
votes
1
answer
51
views
How to prove: if $P_1 \Rightarrow (P_2 \Rightarrow P_3)$ then $P_1 \land P_2 \Rightarrow P_3$ [closed]
Let $P_1, P_2, P_3$ be predicates. I believe if $P_1 \Rightarrow (P_2 \Rightarrow P_3)$ then $P_1 \land P_2 \Rightarrow P_3$. But how can I justify this?
More specifically, on what mathematical basis, ...
- 319
0
votes
0
answers
32
views
Is there a general form of a logical formula with N variables?
Let N = 2. Then there are 16 possible non-equivalent N variable logical formulas, listed below.
False,
A ∧ B,
¬(A → B),
A,
¬(B → A),
B,
A ⊕ B,
A v B,
¬(A v B),
¬(A ⊕ B),
¬B,
B → A,
¬A,
A → B,
¬(A ∧ B),...
- 65
3
votes
1
answer
34
views
If you have a tableau proof for $\Box A$, show that there is also a tableau proof for A.
If you have a tableau proof for $\Box A$, Show that there is also a tableau proof for A.
Here is my attempt but I'm not sure if it's correct:
If we have a tableau proof for $\Box A$, it means that all ...
- 41
1
vote
1
answer
29
views
Tableau Calculus for Reflexive Frames
How would you create a tableau calculus for modal logics that have reflexive frames? What rules would need to be added to the existing system K?
My attempt is to refer to the axiom scheme for ...
- 53
2
votes
1
answer
58
views
Definition of first order logic and property.
$\newcommand{L}{\mathcal{L}} \newcommand{A}{\mathcal{A}} \newcommand{Trm}{\operatorname{Trm}} \newcommand{Frm}{\operatorname{Frm}}$
I am reading the first order logic (FOL) section in the Open Logic ...
- 91