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)

-1
votes
0answers
26 views

Inference in First Order Logic Problem

I read one logic note by Michle Sipser from MUT. I get stuck in inference. please help me in step by step inference? By using First order logic and Resolution Rules, and Proof by contradiction from ...
6
votes
3answers
164 views

A question regarding ❋166.44 in Whitehead & Russell's Principia Mathematica

In the first step of Dem, I wonder how $\Sigma ‘\times P^{;}Q$ is transformed into $\Sigma‘ \Sigma^;(P \overset{\downarrow}{.,})\dagger^; Q$. Thanks,
0
votes
2answers
77 views

Blue Eyes: A Logic Puzzle, has a puzzling solution (a.k.a. What does common knowledge have to do with it?)

In Blue eyes: a logic puzzle (specifically, the follow up questions), the most common answer is that it needs to be common knowledge that someone has blue eyes for all the blue-eyed people to leave. ...
0
votes
2answers
43 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
6
votes
0answers
53 views

Does such a first-order theory exist? A question pertaining to transitive models of ZFC.

Assume a proper class of inaccessibles. Does there exist a first-order theory $T$ subject to the following conditions? $T$ admits an infinite model Whenever $M$ is a transitive model of ZFC with $T ...
3
votes
0answers
54 views

Replacing the “if x ≤ y, then x + z ≤ y + z” axiom in Reals.

How can I prove that we cannot (or maybe can) replace preservation of order under addition i.e. "If $x \leq y$, then $x + z \leq y + z$ with "if $0<x$ and $0<y$ , then $0<x+y$" in axioms ...
3
votes
3answers
80 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
1
vote
2answers
129 views

How many undecidable statements are there in ZFC?

There are several statements known to be undecidable in ZFC, with the continuum hypothesis probably being the most "popular" one. Is it known how many undecidable statements are there in ZFC? I.e. ...
2
votes
0answers
30 views

On the back and forth conditions for a set of partial isomorphisms

I've recently begun reading Poizat's A Course in Model Theory and already in the first pages I had some doubts. One odd (not necessarily bad) thing is that he defines notions such as isomorphism only ...
1
vote
1answer
30 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
14
votes
3answers
4k views

Gödel's ontological proof - How does it work?

Gödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. Can someone please explain what those symbols are, and explain the proof? Thanks. Does it prove ...
-1
votes
1answer
37 views

looking at the alphabet ,the letters are numbered 1-26 ,

looking at the alphabet ,the letters are numbered 1-26 , such that 1 =one=15+14+5=34 (O=15, N=14, E =5 ) 2=two=20+23+15=58 (T=20, W=23, 0=15) 3=three =56 4=four=60 ...
1
vote
1answer
75 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 ...
8
votes
0answers
425 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
0
votes
4answers
84 views

deductions in a propositional calculus

Hope you're all doing well. I have a question about deductions in logical systems. Say we have a logic in the language of propositional logic. We can think of this as the set of tautologies of ...
0
votes
1answer
41 views

How to prove validity of following sequent [closed]

How to prove validity of following: Premises: $p\rightarrow q$, $s\rightarrow t$, Conclusion: $(p \lor s) \rightarrow (q\land t)$
0
votes
0answers
61 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 ...
0
votes
2answers
40 views

Concluding Truth Value from Universe of Discourse

I have been working on the following problem from Velleman's How to Prove book: Are these statements true or false? The universe of discourse is the set of ...
3
votes
3answers
420 views

Idiomatic mathematical english statement for ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]

I have been working on problems from Velleman's How to Prove book and hit upon the following problem: Translate the following statements into idiomatic ...
1
vote
2answers
62 views

Exercise about truth functions in J.R.Shoenfield's “mathematical logic”

The first exercise in Joseph R. Shoenfield's "mathematical logic" is: An n-ary truth function $H$ is definable in terms of the truth functions $H_1,\dots,H_k$ if $H$ has a definition ...
0
votes
2answers
341 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
2
votes
0answers
56 views

Manifolds of Non-Standard Dimension

Can there exists (non-trivial) manifolds of non-standard dimensions? Certainly, there do exist manifolds of dimension $n$ for any $n \in \mathbb{N}$ (as well as manifolds of countably many ...
-6
votes
1answer
39 views

Logical argument [on hold]

Let A, B, and C be propositions. Let ∧ denote logical AND, let ∨ denote logical OR, and let ¬ denote logical NOT. Argue that if (𝐴∨𝐵) ∧(¬𝐵∨𝐶) is true, then (𝐴 ∨𝐶) must be true as well.
-2
votes
1answer
71 views

Single best example for mathematical reasoning [on hold]

Please provide the best example to learn/teach mathematical reasoning. It is suggestible that the problem should contain at least 3 mathematical statements (not core mathematical but like Socrates ...
2
votes
2answers
43 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
2
votes
1answer
101 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 ...
5
votes
1answer
99 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 ...
0
votes
1answer
21 views

FO-axiomatizable class?

I came across this question while preparing for my logic exam. Can this class be (finitely) axiomatizable, where the class contains all structures $\mathfrak{A} = (A, <, f)$, and for no $a \in A$ ...
0
votes
2answers
39 views

Questions regarding Universal Quantifiers

The question is to show that: $$\exists x:(P(x) \implies Q(x))\qquad\equiv\qquad\forall x:P(x) \implies \exists x:Q(x)$$ First I use double negation to get to the universal quantifier since it ...
8
votes
1answer
4k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
3
votes
2answers
63 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
20 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 ...
0
votes
2answers
524 views

Duality discrete math problem

This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm The dual of a compound proposition that contains only the logical operators ...
0
votes
0answers
21 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
83 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
45 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 ...
1
vote
2answers
231 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
0
votes
1answer
17 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 ...
1
vote
2answers
27 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
2answers
54 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 ...
-1
votes
1answer
33 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 ...
2
votes
1answer
114 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 ...
1
vote
3answers
72 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
35 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...
3
votes
1answer
55 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). ...
2
votes
1answer
26 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
49 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 ...
4
votes
2answers
89 views

Which natural number predicates can be defined in Robinson arithmetic?

I'm especially wondering about the order relation, subtraction, division and exponentiation here: $x \leq y \quad \Leftrightarrow \quad \exists u\ y=x+u$ $z= x-y \quad \Leftrightarrow \quad ...
2
votes
2answers
60 views

Can Goodstein's theorem be expressed as an axiom or axiom scheme in PA?

A statement like $\mathsf{Con(PA)}$ depends (or at least seems to depend) on a specific Gödel numbering. My question is whether Goodstein's theorem may be expressed directly in the language of ...
1
vote
1answer
29 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 ...