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
-4 votes
0 answers
13 views

please solve this $F = xyz + xy' + x'y'z' + xyz'$ [closed]

please solve this $F = xyz + xy' + x'y'z' + xyz'$
user avatar
0 votes
1 answer
21 views

Relativization of Pairing

In Chapter 12 of Jech's Set Theory, he proves that ZF is consistent with ZF minus Regularity by showing that if $V=\bigcup_{\alpha\in Ord} V_\alpha$, then in ZF minus Regularity $\sigma^V$ holds for ...
user avatar
0 votes
0 answers
33 views

How objectively do we evaluate likelihood of two very rare events?

I've been pondering the concept of objectiveness to evaluate likelihood and predictability of extremely rare events. I'd like to demonstrate my questions over trivial hypothethical examples below. ...
user avatar
  • 11
0 votes
0 answers
18 views

Choosing interpretation which make the formula true?

There was this quiz question we got in out weekly quiz and I am very lost, I have tried understanding it but I got nowhere: For the following formula $∀x ∃y (P(x,y) ∧ P(y,x)).$ Let us assume to have a ...
user avatar
0 votes
0 answers
12 views

Requirements on a decidability proof for the satisfiability of formulas

In 1928, Skolem gives a decision procedure for first-order formulas of the form $\forall x \exists y_1, …,y_n F$ using his (1922) construction of leveled instances that approximate to the quantified ...
user avatar
  • 491
1 vote
1 answer
61 views

Absolute definition of 'True' and 'False' in Mathematical Logic

I searched for the definition of Truth. According to this Wikipedia: https://en.m.wikipedia.org/wiki/Truth , Truth is the property of being in accord with fact or reality. when I searched for the ...
user avatar
1 vote
0 answers
17 views

Intuitionistic logic, tree-like Kripke model

There is a tree-like Kripke model in which the set of worlds $\mathfrak{W}$ is ordered as a tree: (a) there is a smallest world $W_0$ (b) for any $W_i \ne W_0$ there is a unique preceding world $W_k: ...
user avatar
  • 11
1 vote
0 answers
24 views

How to show that the Alexander Subbase Theorem is ZF-equivalent to the Compactness Theorem for first order logic?

Alexander Subbase Theorem (ASB): Let $X$ be a topological space. $X$ is compact if and only if there is a subbase $\mathcal{B}$ for the topology of $X$ such that every subcollection of $\mathcal{B}$ ...
user avatar
  • 2,982
0 votes
1 answer
36 views

Quantifiers and usage of the infinum

Let $A$ be a set. Define $d(x,A) = \inf \{d(x,a)| a \in A \}$. So for any $a$, $d(x,A)\leq d(x,a)$ and for any other $r \leq d(x,a)$ we have $r \leq d(x,A)$. Now let $x$ and $y$ be two different ...
user avatar
  • 493
-1 votes
0 answers
39 views

Properties of the Zariski topology on $\mathbb{R}$ [closed]

Consider the Zariski topology on $\mathbb{R}:\Omega=\{\emptyset\} \cup \{X \subseteq \mathbb{R}:\mathbb{R}\setminus X \text{ is finite}\}$. I'm trying to understand how does this work. I found this ...
user avatar
  • 7
1 vote
0 answers
30 views

Proving two statements about HA (Heyting Arithmetic) and Friedman’s Translation

I'm studying Intuitionistic Logic from the textbook Constructivism in Mathematics Vol 1 (A.S. Troelstra, D. van Dalen), which is not an easy-to-read book! I find it very difficult to follow the book's ...
user avatar
0 votes
0 answers
35 views

Probabilities and Logical Implications

Let $X$ and $Y$ be two continuous random variables over $\mathbb{R}$. Suppose I knew for certain i.e w.p 1 that $E[X]>E[Y]$ then of course $X\neq_d Y$ (i.e $X$ and $Y$ must not share the same ...
user avatar
-4 votes
0 answers
49 views

Why is this statement in logic a meaningful statement?

In my book, It gave a logic statement as, (3<5)∨(1=0) The Author said this statement is silly but he also said that this statement is mathematically meaningful and also true. I fail to understand ...
user avatar
0 votes
0 answers
48 views

Key Lemma for Elementary Submodels

I'm reading through Jech's Set Theory, in particular chapter 12 on model theory. After defining an elementary submodel, he writes that The key lemma in construction of elementary submodels is this: A ...
user avatar
1 vote
3 answers
73 views

$A$ is consistent iff $\lnot A$ is not provable

I'm currently reading through Jech's Set Theory and in chapter 12, an introduction to Model Theory. In particular, the section on "Relative Consistency" contains the assertion The question ...
user avatar
2 votes
0 answers
87 views

Number of three-tuples such that $c_1a_1 + c_2a_2 + c_3a_3 = n$ and $c_1 \ge c_2 \ge c_3$

I'm trying to figure out how to find the number of three tuples that sum up to $n$ when each element has a weight of $c_i$. In other words, how many combinations are there of $(a_1, a_2, a_3)$ such ...
user avatar
1 vote
2 answers
36 views

Question about demonstration of the type $A\Leftrightarrow B$

I have an important question when it is asked to us to proove affirmation/theorem wich look likes this $A\Leftrightarrow B$ I know that in order to proove $A\Leftrightarrow B$ i must proove first that:...
user avatar
0 votes
1 answer
104 views

References for me to understand current approaches to settle $P$ vs $NP$ [closed]

I am an undergrad student that likes to study approaches to settle $P$ vs $NP$. I know that there is GCT method, and another way is to attack it by logic equivalent. I am a double major student in CS ...
user avatar
0 votes
2 answers
42 views

"Sentences" and "Formulas" in the Stanford Encyclopedia of Philosophy

I have quite a bit of issues with an article about classical logic in the Stanford Encyclopedia of Philosophy (SEP) and I am not sure if it is me or the article: We now introduce a deductive system, ...
user avatar
  • 925
-3 votes
0 answers
31 views

Hi... I just beginning with the study of categories so my question might seem elementary. [closed]

Please in want to know how to show that the functor $\mathcal{P}(\Sigma \times Id) $ weakly preserve pullbacks.
user avatar
  • 1
-1 votes
0 answers
12 views

Subset multiplication - like the subset sum problem.

Question, although its not completely related to math, it is still mathemathics.. Like the original subset problem. does there exist a subset multiplication problem? I tried searching and could not ...
user avatar
0 votes
0 answers
25 views

Is there a Turing degree/number of unknowns combination beyond which Diophantine equations are independent of PA?

Is there a certain limit in terms of Turing degree and # of unknowns beyond which Diophantine equations (for positive integer solutions) are independent of PA? Specifically, is it meaningful to talk ...
user avatar
1 vote
0 answers
53 views

Elementarily equivalent models of arithmetic that are not isomorphic.

The book is Predicate Calculus by Goldrei. Given the hint and other similar exercises, this is the only way I know how to go about this: Take the set $\text{Th}(\mathcal{N}) \cup \{ \textbf{c} \not = \...
user avatar
  • 493
4 votes
2 answers
103 views

Still not getting difference bettwen Implies and Entails and the role of "interpretation"

Background I am trying to understand the answers to the question Implies ($\Rightarrow$) vs. Entails ($\models$) vs. Provable ($\vdash$). In his answer, ryang wrote: material conditional $\left(\to\...
user avatar
  • 925
10 votes
3 answers
223 views

Is there a purely topological proof that a certain topological space derived from logical compactness is compact?

Let $L$ be a first order language, and let $S_{L}=\{\sigma:\sigma\;\mbox{is an $L$-sentence}\}$. Also, by logical compatness I mean the Compactness Theorem of first order logic. Compactness Theorem: ...
user avatar
  • 2,982
-1 votes
1 answer
35 views

In a swimming race, the odds that A will win are $\frac23$ to $3$ and the odds that B will win are $\frac14$. Find the odds that A or B win the race.

Problem : In a swimming race, the odds that A will win are $\frac23$ and the odds that B will win are $\frac14$. Find the odds that A or B win the race. My Approach : I guess we can add up the odds of ...
user avatar
  • 11
0 votes
1 answer
78 views

Is it meaningful to invert large cardinals?

As cardinal numbers involve the notion of ever increasing multitudes of things, is there a mathematically useful concept of ever decreasing multitudes? We already have rationals tending to zero, and ...
user avatar
  • 279
5 votes
2 answers
110 views

Are this two sentences equivalent?

I have a sentence in natural language: "the sum has a neutral element and it is unique", which I have to write in a first order language that has a binary relationship symbol of equality $='$...
user avatar
  • 183
2 votes
2 answers
76 views

What is the purpose of a certain problem?

I am self-learning the material and I have encountered this question in the lecture notes by Stephen G. Simpson that I am reading: Let $L=\{R,\ldots\}$ be a language which includes a binary predicate $...
user avatar
  • 2,982
4 votes
2 answers
84 views

Build a "rich" first-order logic within a given category

I would like to know a mathematical framework with an internal logic where isomorphic objects can be considered equal. For example, consider the rationals $\mathbb{Q}$. With this set we can construct ...
user avatar
  • 679
0 votes
1 answer
61 views

Proof of Łoś-Tarski theorem: explanation of the obtained contradiction

I'm going through the following document about model theory: https://webspace.science.uu.nl/~ooste110/syllabi/modelthmoeder.pdf in which a proof of the Łoś-Tarski preservation theorem is given. I ...
user avatar
  • 83
-2 votes
0 answers
41 views

Can Cantor's diagonal argument be used for an informal proof of the internal inconsistency of formal logic systems?

So I've been thinking about how Cantor's diagonalization argument might be analogous to Tarski's theorem on the undefinability of truth ("Arithmetical truth can't be defined in arithmetic") ...
user avatar
0 votes
1 answer
45 views

How do I translate this pattern of sentence into a quantified statement using logical operators?

How do I translate this pattern of sentence into a quantified statement using logical operators? (It's basically introducing a new symbol, "b" in this case, in a proof.) So a = xb where b ...
user avatar
-2 votes
0 answers
69 views

Is there a counterexample for this statement? [closed]

$(a<b \land \ b<c) \Longleftrightarrow a<c \ (a,b,c \in \mathbb{R}).$ I'm new to the topic, so I don't know much about disproving statements. Any help would be appreciated.
user avatar
  • 87
1 vote
1 answer
29 views

Notation for the set of conjonctions of two adjacent level of the levy hierarchy

Let $\Sigma_n$ and $\Pi_n$ be two levels of the levy hierarchy. We consider the set of formulas $$\Gamma = \left\{ \phi \wedge \psi, \phi \in \Sigma_n, \psi \in \Pi_n \right\}$$ Is there a common name ...
user avatar
  • 173
0 votes
3 answers
66 views

$A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$?

$A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$ ? The logic is Knights always tell the truth and Knaves always lie. What I'm thinking is ...
user avatar
  • 1,340
1 vote
1 answer
68 views

What strategies could be used to prove the validity of this argument in order to not violate restrictions on universal generalization (Hurley)

I'm considering a particular argument while working through Hurley's Concise Introduction: ...
user avatar
  • 11
0 votes
0 answers
48 views

Should the word "or" be exclusive or inclusive when stating a theorem?

Let $X$ and $Y$ be arbitrary sets. Further, let $X'\subset X$ and $Y', Y''\subset Y$, where and $Y'\neq Y''$. I am currently stating (and proving) a theorem of the form \begin{gather} x\in X'\...
user avatar
  • 800
1 vote
0 answers
34 views

Is Kleene's realizability recursive?

Kleene introduced realizability as a practical semantical interpretation of Heyting Arithmetic (see link for definition). The key result he proved is that provability of $\varphi$ in HA implies the ...
user avatar
  • 11
-2 votes
0 answers
12 views

Write the truth value of the following statement below [closed]

Write the truth value of the following statement: If x/y = 0, then y should not be equal to zero If x > y, then x + 3 < y + 3
user avatar
2 votes
1 answer
45 views

Consistent full Horn theories of two structures

Suppose that two structures $A$ and $B$ whose cardinality is greater than 1 (added in a revision) have the same positive primitive theory. Does it follow that the union of the full Horn theory of $A$ ...
user avatar
  • 7,230
-1 votes
0 answers
26 views

How complex can ZFC-decidable sentences be? [closed]

Let's take the set of ZFC-decidable Diophantine equations. What level of complexity can they attain? Are there ZFC-decidable sentences that are impossible (on a practical level, not principle) for ...
user avatar
1 vote
1 answer
65 views

How to prove that $∃x J(x)$ and $J(m)$ are not logically equivalent?

I'm supposed to use counter models to establish that the two sentences $∃x J(x)$ and $J(m)$ are not equivalent. My initial work is this, does it seem right? Domain: Lionel Messi, Cristiano Ronaldo J(...
user avatar
-1 votes
1 answer
36 views

Why for a zeroth-order logic is not possible to have a complete Peano arithmetic with quantifier free arithmetical sentences?

In my previously question I still have some doubts and in particular about this part Peano arithmetic is impossible to rewrite into zero-order logic since Peano arithmetic has functions like the ...
user avatar
  • 127
1 vote
0 answers
55 views

How do formal proofs work and relate to interpretations?

As far as I know statements in formal logic are written in a (formal) alphabet which are just symbols, where the allowed sentences have to follow certain rules. If they do, they are called well formed....
user avatar
1 vote
2 answers
72 views

Implies or iff between two equations that are the same?

Say I have the following equality $$ \ln x = d $$ This means that $x = e^d$. However, I am questioning whether, when writing this equivalence in one go, whether to use $\Rightarrow$(implies) or $\...
user avatar
  • 1,243
0 votes
2 answers
36 views

Using pre-definitions to bind variables without explicitly writing them down

In logic, we can use quantifiers, like $\forall$ or $\exists$, or binders, like $\sum_x, \min_x, \prod_x$, to bind variables. At least the quantifiers seem to also be called constants, while there are ...
user avatar
  • 925
-5 votes
0 answers
56 views

How do I translate the following sentences from English to predicate logic? [closed]

The thief is only liable if they saw him enter the tunnel and found the stolen item in his possession. If witnesses see him enter the tunnel and the stolen object is not found in his possession, then ...
user avatar
0 votes
1 answer
60 views

First Order Logic Question: How to interpret ∀x~∃y when L(x,y) means ___x loves ___y? [closed]

I am given a sentence and my professor wishes for me to convert it to FOL. The problem is that I do not know what the form of this quantifier order would look like. For instance, if L(x,y) means ___x ...
user avatar
3 votes
1 answer
85 views

The empty set in Ackermann set theory

Let $A$ denote Ackermann set theory, as laid out e.g. here. It is a standard result due to Levy and Reinhardt that $A$ and $ZF$ are mutually interpretable in conservative extensions of one-another. ...
user avatar
  • 1,681

1
2 3 4 5
506