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

25,269 questions
Filter by
Sorted by
Tagged with
13 views

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

please solve this $F = xyz + xy' + x'y'z' + xyz'$
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 ...
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. ...
• 11
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 ...
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 ...
• 491
1 vote
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 ...
1 vote
17 views

• 493
103 views

• 2,982
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 ...
• 679
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 ...
• 83
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") ...
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 ...
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.
• 87
1 vote
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 ...
• 173
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 ...
• 1,340
1 vote
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: ...
• 11
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'\...
• 800
1 vote
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 ...
• 11
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
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$ ...
• 7,230
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 ...
1 vote
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(...
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 ...
• 127
1 vote
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....
• 195
1 vote