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

Filter by
Sorted by
Tagged with
0 votes
0 answers
4 views

Application of the Löwenheim-Skolem Theorem for theories with uncountable signatures?

The Löwenheim-Skolem asserts the following: For a first order (L_(ω,ω)) theory with signature σ, every infinite σ - structure M and every infinite cardinal κ ≥ |σ|there is a σ-structure N such that |...
SJe967's user avatar
  • 13
0 votes
1 answer
9 views

Is this rule correct in sequent calculus?

In Ebbinghaus's book, the following rules occur in sequent calculus: $\dfrac{\Gamma \phi \dfrac{y}{x}}{\Gamma \forall x \phi}$, if y is not free in $\Gamma \forall x \phi$ $\dfrac{\Gamma \phi}{\Gamma \...
William's user avatar
  • 225
0 votes
1 answer
44 views

$\exists x\in A \ (P(x))$ versus $\exists x \ (x\in A \land P(x))$

I have a pretty simple question on mathematical logic. Consider two logical statements $\exists x\in A \ (P(x))$ and $\exists x \ (x\in A \land P(x))$. How are they logically different from each other?...
RFZ's user avatar
  • 16.8k
1 vote
2 answers
28 views

Difference between making assumptions in the premise of inference rule and including them into the context of the conclusion

What are the differences between the rule $$ \frac{\Gamma\vdash a:A\quad \Gamma \vdash b:B}{\Gamma \vdash T(a,b) \text{ type}} \quad (\text{Rule 1}) $$ and the rule $$ \frac{}{\Gamma,a:A,b:B\vdash T(a,...
user837242's user avatar
1 vote
0 answers
65 views

In a finitely presented group, the set of all words which equal 1 in the group is a recursively enumerable set.

I was reading "An introduction to the theory of groups" by Rotman, chapter 12, the word problem. I am stuck in the following theorem, Let $G$ be a finitely presented group with presentation $...
Dwaipayan Sharma's user avatar
0 votes
0 answers
46 views

Set theoretic definition of terms of the untyped lambda calculus

I am trying to translate the following definition (in Agda) of intrinsically scoped terms of the untyped lambda calculus into more mathematical (in particular set theoretical) notation: ...
user11718766's user avatar
0 votes
0 answers
35 views

Mathematical Deduction Theorem Induction proof, case of minimal two-line deductions

The mathematical deduction theorem from mathematical logic appears extensively in the mathematical logic literature (in my experience) and has been extensively discussed in Stack Exchange. One can see ...
grell6954's user avatar
1 vote
1 answer
88 views

Considering $\Gamma \vdash \varphi$, is $\Gamma$ a set or a list?

As far as I know, most of mathematical logic textbooks state the Weakening Lemma: Let $L$ be a first-order language. Then, for any sets $\Gamma_1$ and $\Gamma_2$ of $L$-formulas and any $L$-formula $\...
Kijeong Lim's user avatar
-2 votes
0 answers
47 views

Proof of the principle of induction [duplicate]

I will be referencing the proof I provided here. I don't understand the remark of a person, who states the incorrectness of such proof. From what I could understand, the proof is also valid not ...
Elvis's user avatar
  • 115
0 votes
1 answer
65 views

What is the accurate definition of inference rule?

Take the inference rule "$P\land Q \Rightarrow P$" for example, what is its accurate definition? "For any string $P\land Q$, if P and Q are w.f.f, then we can derive P" "For ...
William's user avatar
  • 225
1 vote
1 answer
52 views

How is the Łoś–Vaught test applied applied in infinitary logics?

I've been researching model theoretic logics and all the related stuff (categoricity, Hanf numbers) lately, and have been confused on how the Łoś–Vaught test applied to infinitary logics. The Łoś–...
SJe967's user avatar
  • 13
0 votes
1 answer
110 views

What is the Domain of Discourse when one isn’t specified?

The null set is a set that contains no elements. I think I can express this statement like this: $\forall x (x \not\in \emptyset)$ Here x could be a number, a word, a function, really anything. What ...
Dr. J's user avatar
  • 51
-1 votes
0 answers
32 views

Why is this sentence of predicate logic false on this model?

The sentence: $\forall x \forall y \forall z ((Rxy \land Rxz) \rightarrow Ryz)$ Model. Domain = 0,1,2. R: <0,1>, <1,2> This sentence is apparently false on that model, but I'm struggling ...
songdivision's user avatar
1 vote
0 answers
44 views

Proof within Łukasiewicz's infinite-valued logic $Ł_{א}$

Using the axiom system for Łukasiewicz's infinite-valued logic $Ł_{א}$, I need to construct a proof of the following: ⊢ (A → B) ∨ (B → A) ⊢ (A → (B → C)) → (B → (A → C)) A → B ⊢ (A ∧ C) → B A → B ⊢ ¬B ...
Amilio's user avatar
  • 11
2 votes
0 answers
46 views

Relating the Semantics of Church's Simple Type Theory to Dependent Type Theory [closed]

I'm looking at the 'standard' semantics of Church's simple type theory/simply typed lambda calculus (see for example section 2 here or pp. 194-196 in the January 2024 version of this), and I'd like to ...
user837242's user avatar
-3 votes
0 answers
32 views

Mathematical logic -informal statement calculus- Adequate sets of connectives [closed]

Prove that {∼,↔} is not an adequate set of connectives. Please help me with this exercise, I cannot prove it.thanks
Alireza Alehoseini's user avatar
-1 votes
1 answer
100 views

De Morgan's Laws Proof for Logic

Hello I am working on the logic proof for De Morgan's Law. I can only work with a very specific set of axioms, rules, and theorems and I need to prove all four implications. I am very lost on where to ...
waffles's user avatar
0 votes
1 answer
74 views

Are "(",")","," indispensable components for terms of first order language?

They are called auxiliary symbols in some books, which seems to say they are not necessary, at least for terms. But without them, how can we determine the categories of symbols in a formula such as: $...
William's user avatar
  • 225
0 votes
0 answers
55 views

Proof that every consistent theory has a maximally consistent extension via the Compactness Theorem

I am trying to prove that it follows from the Compactness Theorem that every consistent first-order theory has a maximally consistent extension (I hope that this will allow me to turn the usual Henkin ...
Jon's user avatar
  • 155
0 votes
0 answers
64 views

On the definition of 'dependent functions' in the set-theoretic semantics of dependent product types

I'm working in a framework (see e.g. this) where a context $\Gamma$ is interpreted as a set $[\![{\Gamma}]\!]$, a type $A$ in context $\Gamma$ is interpreted as a family of $[\![{\Gamma}]\!]$-indexed ...
user837242's user avatar
2 votes
1 answer
46 views

How to show that the application of two elementary embeddings is an elementary embedding?

Let $\mathcal L$ be a language of first-order logic. Given two structures $\mathfrak M$, $\mathfrak N$ for $\mathcal L$ with domains $M$, $N$ respectively, an elementary embedding from $\mathfrak M$ ...
C7X's user avatar
  • 1,207
0 votes
0 answers
106 views

What are advantages of formalizing mathematics in logic (without set theory)? [closed]

Parts of mathematics can be formalized in logic directly (e.g., parts of graph theory can be formalized in monadic second-order logic), or in ZFC set theory, which is a theory in first-order logic. ...
Max Flow's user avatar
  • 248
2 votes
1 answer
71 views

Real degrees after forcing a random real

We know a lot about the properties of the real degrees if we assume the existence of an $L$-generic Cohen real (e.g. see Abraham and Shore Degrees of Constructibility of Cohen Reals). Among other ...
Lorenzo's user avatar
  • 2,601
-1 votes
1 answer
57 views

How to proof P ∨ Q, ¬Q ∨ R entails P ∨ R by Natural deduction [closed]

Could you show me the way by using Natural Deduction?
Gabo meza's user avatar
1 vote
1 answer
82 views

Set-theoretic semantics for sigma types

I'm trying to understand the set-theoretical semantics of sigma types. Suppose $\Gamma\vdash A : \text{type}$, $\Gamma.A\vdash B:\text{type}$, $\Gamma\vdash a:A$, $\Gamma\vdash b:B[1.a]$, $\Gamma\...
user837242's user avatar
0 votes
0 answers
57 views

$\forall x\in\{\} : \exists y\in\mathbb N : x<y$ true or false? [duplicate]

We are simply asked if this statement is true or false. From what I was able to gather this statement is true because an empty set has no values to make a counter argument. Yet I do not fully ...
Wannabree's user avatar
2 votes
1 answer
38 views

Why doesn't order-invariance increase the expressive power of first-order logic over arbitrary structures?

I’m currently working through Leonid Libkin’s Elements of Finite Model Theory in my spare time, and I find myself stuck on the following exercise: Exercise 5.1. Prove that over arbitrary structures, $...
Ibby's user avatar
  • 23
3 votes
0 answers
99 views
+100

Proving a corollary of Trakhtenbrot theorem

In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows: Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
John Davies's user avatar
0 votes
3 answers
94 views

What is the fundamental difference between := and = operators?

I was studying discrete mathematics and I came across the assignment operator ":=" so I made a quick search and found both of these questions: What does := mean? What's the difference among ...
Life Long Learner's user avatar
2 votes
0 answers
87 views

(weak necessity) proof a collection is closed under Modus Ponens from prior assumptions

I am looking for help understanding Exercise 7.3 from A Philosophical Introduction to Higher-order Logics by Bacon. The ultimate goal of the exercise is to prove the right-to-left direction of the ...
C D's user avatar
  • 43
0 votes
0 answers
53 views

Predicate Logic: Prove ¬∃x.p(x), given 1. ∀x.(p(x) ⟹ ¬q(x)) 2. ∃x.p(x) ⟹ ∀x.q(x)

I'm having trouble solving: Prove ¬∃x.p(x), given 1. ∀x.(p(x) ⟹ ¬q(x)) 2. ∃x.p(x) ⟹ ∀x.q(x) I think I need to get $\exists x.p(x) \Rightarrow \neg (\forall x.q(x))$ to then use negation introduction, ...
Johny's user avatar
  • 1
-1 votes
1 answer
80 views

Could propositions that have only universal quantifiers be interpreted as specifying domains of discourse? [closed]

Could propositions that have only universal quantifiers be interpreted as specifying domains of discourse? I ask because of the following: Let $P(x)$ signify at the pub Let $D(x)$ signify is drinking ...
AUTIST INC's user avatar
1 vote
1 answer
52 views

Mapping Reflection Principle

I'm reading this paper written by Moore and he mentions the notion of a continuous $\in-$chain. Can anyone tell me what he means by that? I can't find the definition The link for the original paper ...
Selena's user avatar
  • 71
0 votes
0 answers
78 views

Interpreting statements in a proof which have implications for the non-emptiness of sets (sets, logic, cartesian products) - Tao Analysis I 3.5.6

This question is about deriving requirements for non-emptiness of sets from the algebraic steps in a proof. It is not primarily about the proving the primary objective of the exercise. Why am I asking ...
Penelope's user avatar
  • 3,177
1 vote
3 answers
104 views

Can an axiomatic system be consistent if the system obtained by removing some axioms isn't?

I asked another question before, where I asked if this: $\mathrm{Con}(\mathcal S + \neg\mathrm{Con}(\mathcal S))$ Could be true for some axiomatic system $\mathcal S$. I was told that it's totally ...
Elvis's user avatar
  • 115
1 vote
1 answer
55 views

Can an axiomatic system $\mathcal S$ be consistent with the claim of its own inconsistency?

Considering the statement: $\mathrm{Con}(\mathcal S + \neg\mathrm{Con}(\mathcal S))$ Is it possible for it to be true? Doesn't the negation of the consistency of a part of the axioms by another axiom ...
Elvis's user avatar
  • 115
2 votes
0 answers
45 views

If a $\Pi_1$ sentence is proven undecidable in PA, can I add its negation to the axioms?

I know that a sentence $P$ that is independent from a certain axiomatic system $S$ can be added to the axioms without affecting the consistency of the system, and so can its negation. If $P$ is a $\...
Elvis's user avatar
  • 115
3 votes
0 answers
24 views

Is there a connection between the topology of R/Q+ and the logic fundamental to Smooth Infinitesimal Analysis?

As I read through the discussion related to this question (Visualizing quotient groups: $\mathbb{R/Q}$) posted 11 years ago I am reminded of a line on page 20 in a book by J. L. Bell, A Primer of ...
21stCenturyParadox's user avatar
1 vote
0 answers
50 views

Is it possible to prove the consistency of ZFC using another logical theory? [duplicate]

I understand that it’s not possible to prove the consistency of any mathematical system assuming basic Peano arithmetic with another system that also models Peano arithmetic. But is it possible to ...
Fraser James's user avatar
0 votes
1 answer
95 views

Does an undecidable sentence still have a truth value?

I don't quite understand the concept of undecidability/independence. Okay, a sentence is not provable in a certain axiomatic system, but can it be true nonetheless? Or is it "truth value-less&...
Elvis's user avatar
  • 115
-3 votes
1 answer
102 views

How to write $P\wedge Q\wedge R$ using the word "or"? [closed]

I want to write $P\wedge Q\wedge R$ using the word "or." I can't write something like "we have $P,Q$ or $R$" because the would mean "we have [$P$ and $Q$] or $R$." How ...
Hilbert's user avatar
  • 780
-1 votes
1 answer
47 views

Analysing answers: why the first sentence is true and the second - false? [closed]

∀x∃y R(x,y), ∃x∀y R(x,y) There is an interpretation example, which makes first sentence true and the second false: Domäne: 0, 1 R(x,y): ⟨0, 1⟩, ⟨1, 0⟩ I do not understand why the second sentence is ...
fghjkl4083's user avatar
-1 votes
0 answers
29 views

If the truth of a sentence follows from its undecidability, does that imply that its undecidability is undecidable? [duplicate]

Say Goldbach's conjecture is undecidable. If it was proven undecidable, that would prove (correct me if I'm wrong) that it's true, since if it was false you could give a counterexample, thus proving ...
Elvis's user avatar
  • 115
0 votes
1 answer
104 views

Szekeres proof of set distributive law inadequate?

I'm reading "A Course in Modern Mathematical Physics" by Peter Szekeres. In problem 1.1, he asks the reader to show the distributive law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. The ...
MattHusz's user avatar
  • 173
0 votes
0 answers
31 views

Question about categorical interpretation of formulas in modal logic

Within Kripke semantics of modal logic, modal formulas are interpreted via digraphs. Since digraphs can also be considered categories (either innately or when equipped with a category structure), are ...
m. lekk's user avatar
  • 372
2 votes
0 answers
37 views

Why were Poincare, Kronecker and Brouwer hesitant to accept classical logic in an infinite domain but not a finite one?

I am not very well versed in mathematical logic, but I was reading a post on the subject of classical logic and these names popped up. My guess would be that in theory if we have a finite set of ...
Fraser Pye's user avatar
0 votes
2 answers
64 views

A statement: If $b \gt a \gt 0$ then $b^2 \gt a^2 \gt 0$. What is the contrapositive of this statement?

A statement: If $b \gt a \gt 0$ then $b^2 \gt a^2 \gt 0$. for example If $x \gt 2 \gt 0$ then $x^2 \gt 4 \gt 0 $ which is true for all $x \in \Bbb R$ We all know that If $x^2 \leq 4$ then $-2 \...
Stats Cruncher's user avatar
0 votes
1 answer
24 views

Applying Theorem to verify the logical equivalences, trying to verify if this is correct no answer in the book

Simplify: $(p~\land~(\lnot(\lnot~p \lor q)))~\lor~(p~\land~q)~\equiv~p$ A: $(p~\land~(\lnot(\lnot~p \lor q)))$ B: $(p~\land~q)$ A: $(p~\land~(\lnot(\lnot~p \lor q)))~\equiv~(p~\land~(\lnot\lnot~p \...
Alix Blaine's user avatar
2 votes
3 answers
79 views

Proof of Negation of Implication

I just saw that in the proof of $P\implies Q$, if P is $F$, then the implication is still $T$. This is so because when P is $F$, the implication is not getting disproven. So when we find proof of $P \...
Sahil Gupta's user avatar
1 vote
2 answers
98 views

If L+ is a sublanguage of L, and {A} is a set of axioms and transformation rules used to create S and S+, is every theorem of S+ a theorem of S?

I am not sure whether this holds universally or not. On one hand, since L+ is a sublanguage of L, since the axioms and inference rules are the same for S and S+, it seems like anything derivable in S+ ...
Anon's user avatar
  • 27

1
2 3 4 5
560