Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
0answers
21 views

Connection between quantifier rank and Ehrenfeucht-Fraïssé Games

"Two $\tau$-structures $\mathfrak{A}, \mathfrak{B}$ are $m$-equivalent ($\mathfrak{A} \equiv_{m} \mathfrak{B}$) when... $\mathfrak{A} \models \psi$ iff $\mathfrak{B} \models \psi $ for all ...
3
votes
2answers
69 views

Proving $\vdash \exists x (x=c)$ for each term $c$.

I wish to prove that $\vdash \exists x (x=c)$ for each term $c$. It seems quite obvious that this would be the case, for $c$ is such an $x$, but creating a formal proof of this is escaping me. ...
0
votes
0answers
22 views

computational complexity theory(factorial)

I wanted to ask which class does factorial problems belongs to? there is the naive algorithm that solves the factorial factorial(n) = factorial(n-1) * n. but it is exponential in the length of the ...
0
votes
2answers
85 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
1
vote
2answers
46 views

Proving that $\sqrt{pq} \ne (p + q)/2$ implies $p \ne q$ using the contrapositive

Prove by the contrapositive method, that if $p$ and $q$ are positive real numbers with the property that $\sqrt{pq}$ is not equal to $(p+q)/2$, then $p$ is not equal to $q$. The proof is easy enough ...
0
votes
1answer
20 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
-2
votes
2answers
59 views

What's wrong with this induction based proof?

Claim: $\forall x \in \mathbb{R^+} ,$ $ x^n=1 $ $where$ $ n\in \mathbb{N}$ Proof by induction on n: Basis step: $\forall x \in \mathbb{R^+} ,$ $ x^0=1 $ Induction Step: Let this holds for all ...
5
votes
1answer
104 views

How much maths can we do in NF(U)?

I have recently become interested in non-standard set theories, particularly in NF and NFU and have been reading some things here and there. Of course, I don't know much about it and I'm still trying ...
1
vote
3answers
78 views

How and why can a true statement *never* imply something false?

The premise of 'proof by contradiction' is that a true statement can never imply a false statement. In my lectures (intro to logic), this has been brushed aside as 'obvious', but is there a formal ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
2
votes
1answer
117 views

Are there any “obviously” true propositions in number theory?

After all efforts spent on wrong proofs of famous number theory conjectures and theorems like Goldbach's or Fermat's last theorem, could one find some simple statements (might be correct ones) whose ...
2
votes
1answer
28 views

satisfiability in a structure implies satisfiability in a substructure?

My level: I've studied mathematics and now work through Hebert Enderton's book "An introduction to mathematical logic", second edition, in my free time. Relevant pages: 135-142, specifically 140 ...
1
vote
2answers
51 views

Validity in propositional calculus.

I have read some of the answers on similar questions but I can't really get my head around this. So, here are 2 questions I need to answer. Show using a truth table: That the inference ...
1
vote
1answer
30 views

Confusing about logic gates

Says i have this logic : X = (A & B) | ~B Which can be shorten to : X = ~(~A & B) and then : X = A | ~B so : (A & B) | ~B = A | ~B About this one, i can prove ...
-1
votes
1answer
35 views

$L \in RE$ Question in Computation [closed]

Let L be a language. Suppose a TM exists that halts on all words in L. Which of the following statements is true? a) if L is r.e we have such TM. b) if L is r.e and complement of L is r.e then we ...
3
votes
2answers
81 views

What's the difference between a logic, an internal logic (language) of a category, an internal logic of a topos and a type theory?

maybe this question doesn't make sense at all. I don't know exactly the meaning of all these concepts, except the internal language of a topos (and searching on the literature is not helping at all). ...
1
vote
2answers
38 views

Consending logic gates

Given this logic gate : A AND B OR B AND C AND (B OR C) it can be shorten as : B AND (A OR C) How do we do this ? I ...
1
vote
1answer
98 views

Please help with translation of English to first order logic

In a certain work on mereology, Alfred Tarski claims that the third following statement is deducible from the previous two: The sum of a class is defined as follows: $y$ is the sum of a class ...
0
votes
0answers
30 views

Sum of function applied to parts not equal to function of total

The general goal is to determine the effectiveness of the test pill's ability to keep the test subjects from getting sick using the following data. | Test Subjects | Took Test Pill | ...
1
vote
2answers
28 views

Axiomatizability of finite Isomorphic Classes

If $\mathfrak{A}$ is a finite $\tau$-structure and $\tau$ is a finite signature, is the isomorphic class $K_{\mathfrak{A}} = \{\mathfrak{B} \, | \, \mathfrak{A} \cong \mathfrak{B} \}$ ...
2
votes
1answer
58 views

Using logical OR to combine inequalities.

I have a physical system that must satisfy one of two inequalities: $x\leq y$ OR $p\leq q$ But not necessarily both simultaneously. Is there a way to combine this into a single inequality? ...
13
votes
6answers
2k views

Does $2+2$ really equal $4$? [closed]

If you really think about it, is there any proof that does not rely on other facts of addition or multiplication that can solve $2+2$? My question is, is it possible to prove $2+2=4$? If so, an ...
9
votes
2answers
169 views

The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
2
votes
1answer
44 views

Finite sets defined by First Order Logic

Why is a class of, say, finite groups $(G,\circ,e)$ not axiomatizable by FO logic (we use the compactness theorem to prove this statement) but a finite linear order $(A,<)$ on the other hand can be ...
0
votes
0answers
64 views

Relation between existential and universal quantificator in category theory

Let $\mathscr C$ be a cartesian (i.e. with finite limits) category with subobject classifier $\Omega$ and generic subobject $\tau:I\to\Omega$ (here $I$ denote the terminal object). Let $f:X\to Y$ and ...
-2
votes
0answers
92 views

Absoluteness of $\forall x (x=x)$

Is there any kind of (set-theoretic) absoluteness result for the formula $\forall x (x=x)$? And what about for $\exists x (x=x)$? I know $x=x$ is absolute given that it's $\Delta_0$. Also, if I'm ...
6
votes
1answer
168 views

How much mathematics should a student of mathematical logic know?

I would like to know what areas of mathematic are directly related to mathematical logic, besides the usual courses on model theory, proof theory and computability. If you suggest only one book on ...
1
vote
1answer
61 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
2
votes
1answer
112 views

Keisler Order: Saturated Ultrapowers

Keisler's paper "Ultraproducts which are not Saturated" states the following theorem as a corollary to a (much more) generalized theorem. However, I cannot figure out how to prove it for the specific ...
0
votes
1answer
32 views

Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
1
vote
0answers
50 views

Universal and Existential Quantifiers

Are there any examples of a predicate P(x ) of a variable x such that the truth value of P(x) remains invariant under exchange of the Universal Quantifier ∀ and the Existential Quantifier ∃ -thanks
1
vote
2answers
82 views

Names of 3 input logic gates

I've tried to look this up online, I may have used the wrong terminology. This question is about the names of logic gates with three boolean inputs, and one boolean output. This is a truth table for ...
1
vote
2answers
37 views

Proof that there exist no finite axiomatic system with Compactness Theorem

Say we would like to prove that the class of all infinite groups $(G, \circ, e)$ is not finite axiomatizable by making use of the compactness theorem. We normally prove this by contradiction since we ...
1
vote
0answers
58 views

Is “There are no absolute truths” a paradox?

I was wondering if the statement: There are no absolute truths is a paradox or, rather, can be considered at face value. Also, this is just a naive guess, could this statement be ...
1
vote
2answers
112 views

How to prove or disprove $ \forall x \in \mathbb R, \exists y \in \mathbb R $ |x| = xy

I think that the statement is true in general considering +1 or -1 for y. How can I prove it in proper notation. Similarly I need to prove $ \exists y \in \mathbb R, \forall x \in \mathbb R st, x^2 ...
2
votes
1answer
85 views

How to find the truth values of something like this? If 3×5 = 15, then 3+5=10

The question was to find the truth values of if 3×5=15, then 3+5=10? Is the truth table corresponding to p $\implies $q ? Or is it more complicated than that? Do we have to consider something like ...
2
votes
1answer
23 views

Density and Saturated Models.

Consider $(\mathbb{Q}; \leq)$ and let $T$ be the theory of dense linear orderings without endpoints. Let $\mathfrak{A}$ be the $\omega_1$ saturated model of $T$. Note that ...
3
votes
2answers
50 views

Internal Set Theory: $n$ is standard $\implies\;n+1$ is standard

I'm reading a bit about Nelson's version of nonstandard analysis and in the notes it is said that [$n$ is standard]$\implies$[$n+1$ is standard]. Right after that it is mentioned that an inductive ...
1
vote
2answers
119 views

Three-valued logic as foundation

Isn't it more natural to use Three-valued logic(false-true-unknown) as the foundation of mathematics? It is a better model for natural languages. And it also can model sentences like the lair paradox ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
0answers
52 views

I'm looking for a formula to be applied on a game

I've been working on a game and I need to implement a feature, but I still haven't found a good formula for it. The problem is the following: Each team has X points, and all teams are able to ...
1
vote
2answers
29 views

Logic with finite symbols

What obstructions do you run into if you're trying to develop first order logic when you only have finitely many constant, relation, and function symbols? Are there any cases where you actually need ...
0
votes
0answers
17 views

Analogue of Herbrand Disjunction for Negative Side of the Clark Completion?

For Horn clauses there is the following result. If T is a set of Horn clauses and p is a predicate, and if p is an existential consequence of T: ...
0
votes
2answers
37 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
0
votes
1answer
25 views

Computable Function and Predicate Question

I See on Our Lecture note on Theory of Computation Course that: .... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute ...
0
votes
3answers
43 views

Find an equivalent to $(p\lor q) \to (p \lor r)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $(p\lor q) \to (p \lor r)$ Thanks in advance for help.
0
votes
2answers
50 views

How to find the equivalent formulas of $\neg ((p\land q) \to (p \land r))$ [closed]

I have following formula: $\neg ((p\land q) \to (p \land r))$ I need to find equivalent formulas of above expression. Thanks in advance for the help.
2
votes
1answer
36 views

What does this negation on both sides of K mean: A = ¬ K ¬

What does this negation on both sides of K mean: (A = ¬K¬) ? I'm not sure if it's a typo, as there are some errors in this paper (Hong et al.). Hong, Zhi Ling, and Mei Hong Wu. "Constrained ...
5
votes
4answers
296 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
6
votes
1answer
76 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...