Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

2
votes
0answers
23 views

How to deduce $\square p\to p$ from other modal axioms?

I'm trying to deduce the T axiom $\square p\to p$ from the B,D,5 (and also K) axioms. B: $q\to\square\diamond q$ D: $\square q\to\diamond q$ 5: $\diamond q\to \square \diamond q$ I tried to assume ...
0
votes
1answer
17 views

How to name a large number of variables in predicate logic?

What is the most common way of naming a large number of variables in predicate logic? I run out of variables pretty easy in long predicate logic sentences. The simple fact of using a lot of letters ...
0
votes
0answers
37 views

When a particle cannot move according to following rules, it is located at point $(r, r)$. What is $r$?

For any $a$ and $b$, we will define a "move that adds $(a, b)$" as a move from any point $(c, d)$ to the point $(c+a, d+b)$. A particle moves according to the following rules. If a move added $(p, ...
0
votes
1answer
21 views

Consistency of a sentence in $S5$

True or false: if a modal sentence $\phi$ is consistent in K, then it is consistent in S5. This is equivalent to the contrapositive: if $\phi$ is not consistent in S5, then it's not consistent in K. ...
2
votes
2answers
33 views

A type of algae grows continuously such that its population doubles after 3 days. What's the population after 10 days?

A type of algae grows continuously so that its population doubles in 3 days. Given a beginning population of 100 algae cells per milliliter of water, to the nearest whole number, how many algae ...
1
vote
1answer
35 views

Help with Hilbert Calculus

Can u help show that this is a theorem? $ (∀x_1 (∃x_2 (p(x_1, x_2) ⇒ (∀x_2 p(x_1, x_2)))));$ I was trying to use the deduction theorem but i hit a wall. Can u help me out using derivatives and ...
0
votes
0answers
24 views

$\phi$ satisfiable implies $\square \phi$ satisfiable?

Below $\phi$ stands for a modal sentence. The question is to decide whether it is true that 1) if $\phi$ is satisfiable, then $\square \phi$ and $\diamond \phi$ are satisfiable, and 2) if $\phi$ is ...
6
votes
4answers
423 views

Why is a symmetric relation defined: $\forall x\forall y( xRy\implies yRx)$ and not $\forall x\forall y (xRy\iff yRx)$?

Why is a symmetric relation defined by $\forall{x}\forall{y}(xRy \implies yRx)$ and not $\forall{x}\forall{y}(xRy \iff yRx)$? (I have only found a couple of sources that defines it with a ...
2
votes
1answer
23 views

Is the distinction between language and metalanguage strictly parallel the distinction between logic and metalogic?

The distinction language/metalanguage is often used to explain the difference between logic and metalogic. My question is to know whether this explanation is sufficient. More precisely: : is it true ...
1
vote
2answers
35 views

Categorical proof in natural deduction

I'm reading Fitch's book on Symbolical Logic and I don't understand how to prove, with natural deduction, that the following is a theorem without using any hypothesis. This is what is to be proven (...
0
votes
0answers
29 views

Formalization of a Predicate in Intro to Metamathematics, Kleene (Gödel Numbering)

In Introduction to Metamathematics $\S$51, Kleene defines fourteen predicates for a generalized arithmetic with each of $$\supset\,\,\&\,\,\vee\,\,\neg\,\,\forall\,\,\exists\,\,=\,\,+\,\,\cdot\,\,'...
3
votes
2answers
23 views

Natural deduction of (p->(p->q))->q on the hypothesis that p

I am struggling with natural deduction. I am doing the exercises in Fitch's book and now I am supposed to give an intelim proof of the theorem above (an intelim proof is one that uses only ...
0
votes
2answers
38 views

Can a element of a set be also a subset? (Set theory in predicate caculus)

I'm not even sure if this is the question I have to make... I'm trying to formalize (using first-order predicate calculus) a list of rules in a grammar of certain natural language. The first one is ...
0
votes
2answers
29 views

Give a categorical proof of p -> [q -> q]

I am doing Fitch's Exercises of Symbolic Logic, Chapter 1. This is the first exercise. We have so far axioms such as the distributivity axiom, the axiom of conditioned repetition, the transitivity of ...
0
votes
0answers
17 views

Is there an ordering of logical systems defined by reductions?

I am aware of the lambda cube which gives an ordering to several variants of the lambda calculus. My intuition says that this ordering should have the following property: For logics $A,B\in\lambda\...
1
vote
1answer
66 views

Is the 'copy' of the naturals in ZF a unique way to represent the second-order arithmetic in first-order logic?

The following line of thought came into me while studying introductory logic and set theory. I feel like there is an error in it somewhere, but I can't point it. It might even be correct. We have the ...
1
vote
1answer
27 views

Shelah notation

Does someone know what is $K^{\frak s}$ here at the bottom of 2nd page? It is quite frequent in the text but I cannot locate the definition.
1
vote
0answers
20 views

Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
2
votes
2answers
45 views

Measurable Cardinals are Mahlo Cardinals

I am new to set theory and have been working through the proof that every measurable cardinal is Mahlo on page 135 of Jech's text. With the help of Asaf's comments (Measurable $\rightarrow$ Mahlo), I ...
-3
votes
1answer
32 views

Help with the proof of Theorem 1 (Chapter 2) of Suppes' “Axiomatic Set Theory” [on hold]

See the proof of Theorem 1 : $x \notin 0$ page 21 and page 22. Anybody can help me with the first step of the proof. I don't understand why the author uses in this step "x belongs to empty set"...
0
votes
2answers
31 views

Syllogism question using set theory notation

i'm stuck on a question where I have to explain the set theory notation of the syllogism below; boats are vessles $(A ⊆ B)$ boats operate in water $(A ∈ C)$ or $(A ⊆ C)$ Some vessles operate in ...
1
vote
2answers
60 views

Model Theoretical Interpretation of the Incompleteness of Number Theory

This question was sparked by this Numberphile video: https://www.youtube.com/watch?v=O4ndIDcDSGc. Near the end, (12:05), he speaks about the Riemann Hypothesis. He describes that if Riemann is shown ...
0
votes
0answers
9 views

Soundness of Propositional Logics through Morphisms

I'm trying to prove that propositional logic is sound and complete, using the notion of morphism between consequence systems, i.e., pairs $\langle C,\vdash\rangle$ where C is a signature and $\vdash:\...
2
votes
3answers
103 views

Are there cases in mathematics in which it is important to distinguish material implication ( '-->') and logical implication (' ==>')?

My question is : Can any one exhibit a mathematical formula in which a conditional has to be STRICTLY understood as a MATERIAL one, so that the formula would become false if the material conditional ...
7
votes
3answers
88 views

Connection between logic and set theory?

I just noticed there is a similarity between logic operations on propositions and the operations of set theory. It seems: $$\begin{array}{llll} \textrm{disjunction} & (-)\vee (-)& \textrm{...
1
vote
1answer
80 views

Why do mathematicians generally write definitions in “declarative” rather than “imperative style?

In programming, we can make the distinction between declarative / functional and procedural / imperative programming. The distinction is not exact, but nevertheless meaningful. One major difference ...
0
votes
0answers
34 views

How to do induction on formulas with many valued logic?

I have to do a proof that involves induction on formulas with many valued logic (specifically k3). Basically, a formula $A$ is true if $V(A) = 1$, $A$ is false is $V(A) = 0$ and $A$ is indeterminate ...
2
votes
0answers
71 views

Can P vs NP be written as a statement in set theory?

For the problem of $P\neq NP$ it would be useful to have a precise mathematical statement of the question in some logic like set theory or some generalisation of it. And then we could ask given the ...
2
votes
2answers
43 views

What value of $n$ will make a triangle contain 560 lattice points?

I recently met a rather hard problem: A lattice point is a ordered pair where both $x$ and $y$ of $(x, y)$ are both integers. A triangle is forms by of the lattice points $(1, 1)$, $(9, 1)$, and $...
-3
votes
1answer
113 views

Is the following expression unsatisfiable because it is self-contradictory? [on hold]

Expressing Truth directly within a formal system with no need for model theory https://philpapers.org/archive/OLCETD.pdf --- This paper is prerequisite to the following: I am approaching these ...
1
vote
1answer
46 views

Are proofs by “maximality” equivalent to proofs by induction?

I apologize for the lack of proper terminology; I have zero experience in this field. What I mean by "proof by maximality": One way to show that a set $A$ has a certain property $p$ is to assume ...
1
vote
1answer
13 views

Show by Resolution that a set of clauses is unsatisfiable

Im trying to show by resolution that the following set of clauses is unsatisfiable: $\{ p(x,f(y)) \lor p(c,z), ¬p(y,f(f(y))) \lor ¬p(c,x) \}$. Now, I know that to show the unsatisfiability I need ...
0
votes
0answers
41 views

classical logic - rules for quantifiers

I have these formulas of CL: (a) ∀xP(x,x) (b) ∀x∀y∀z(P(x,y)∧P(y,z) → P(x,z)) (c) ∀x∀y(P(x,y) → ¬P(y,x) and I have been trying to prove weather (a),(b) ⊨ (c). First I would use ∀l and then my ...
15
votes
0answers
107 views

Does every effectively axiomatizable first-order theory have a finitely axiomatizable conservative extension?

There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ set theory is a conservative extension of $\sf ZFC$ ...
2
votes
0answers
25 views

Is every degree above ${\bf 0''}$ PA over something close to itself?

The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not ...
0
votes
0answers
26 views

Puzzle game list problem

I'm working on a puzzle game with pygame and I'm stuck on what seems to be a math problem within my game, and I have no idea what it actually is. So I managed to copy a list of sprites that have ...
0
votes
0answers
18 views

Could anyone help me with Boole's Expansion Theorem?

I have searched online, and none of the websites I've looked at help me understand the theorem or the proof.
1
vote
0answers
57 views

About a topological proof of the compactness theorem

I'm trying to prove compactness theorem following this paper https://www.staff.science.uu.nl/~ooste110/syllabi/eric-poizat.pdf. Let $\mathcal{T}$ be the set of all complete theories over a fixed ...
-1
votes
0answers
43 views

Show that there is a formula $F$ such that both $\Gamma \vdash_N F$ and $\Gamma\vdash_N \neg F$. [on hold]

Use the system $N$. Let $\Gamma=\{\neg(B\Rightarrow\neg A), A\Rightarrow \neg B\}$. Show that there is a formula $F$ such that both $\Gamma \vdash_N F$ and $\Gamma\vdash_N \neg F$. Show ...
4
votes
1answer
121 views

An example of incompleteness?

Is it fair to suggest that the fact a base's symbol which would exist in a higher base but is never truly reflected in the base itself is an example(see below) of incompleteness along the ideas of the ...
0
votes
0answers
40 views

Is this Modal (bisimulation) contraction correct?

Bellow I define model M=(W,R,V) and Model K=(W',R',V'). Is model K the model contraction (bisimulation contraction) of M? Model M: $W = {a, b, c}$, and $R = {(a, b), (a, c), (b, c), (c, a), (c, b)}$, ...
2
votes
1answer
70 views

What does this notation mean? $\Phi(x) \downarrow, \Phi(x) \uparrow$

I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am ...
9
votes
3answers
3k views

Why doesn't Gödel's incompleteness theorem apply to false statements?

I've read and heard in lectures that A way to prove that the Riemann hypothesis is true is to show that its negation is not provable. The argument (informally) usually goes like If a ...
0
votes
1answer
35 views

$\kappa\cdot\sum_{i\in I}\lambda_i=_c\sum_{i\in I} \kappa\cdot \lambda_i$

Moschovakis Exercise x4.20 Prove that for all indexed families of cardinals, $$\kappa\cdot\sum_{i\in I}\lambda_i=_c\sum_{i\in I} \kappa\cdot \lambda_i$$ We have $$\kappa\cdot\sum_{i\in I}\lambda_i=...
0
votes
1answer
31 views

$\prod_{i\in A} B=(A\to B)$

Moschovakis Exercise x4.3: Prove that for sets $A,B$, $$\prod_{i\in A} B=(A\to B)$$ where $(A\to B)$ is the set of functions $A\to B$. The product is defined for an indexed family of sets: An ...
1
vote
0answers
28 views

$\lambda\le_c\mu\implies \kappa^\lambda\le_c\kappa^\mu$

Moschovakis, (part of) Exercise x4.16: Prove that for all cardinal numbers $\kappa,\lambda,\mu$ $$\lambda\le_c\mu\implies \kappa^\lambda\le_c\kappa^\mu$$ provided $\kappa\ne 0$. $\le_c$ means "...
2
votes
2answers
55 views

Modus Ponens - Implication vs Disjunction

The Modus Ponens inference rule is generally expressed as: $$ \begin{array}{rl} & P\rightarrow Q \\ & P \\ \hline \therefore & Q\end{array} $$ Is the below rule ...
1
vote
1answer
35 views

Is similar triangles have equal areas a proposition?

Suppose it is a proposition. So we have The conversion proposition is if two triangles have equal areas, then there are similar. The inversion proposition is that if two triangles are not similar, ...
0
votes
0answers
21 views

Unique homomorphic extension, Free generation : Natural Numbers Vs Integers

Unique homomorphic extension says that for a freely generated set $X_+$(say generated from set $X$ and set of functions $F$ ), given a map $h: X \rightarrow B$ (where B is a set with a set of ...
-2
votes
0answers
17 views

epistemic logic [on hold]

Addition Closure (AC). Necessarily, if $S$ knows $p$ and competently deduces ($p4 or 4q$) from $p$, thereby coming to believe ($p$ or $q$), while retaining knowledge of $p$ throughout, then $S$ knows (...