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

learn more… | top users | synonyms (1)

2
votes
1answer
84 views

How to extract the sets “produced” by a axiomatic set theory, into some newly introduced collection?

Say I know well how to reason in a set theory, which for the sake of this question I'll call $\bf{ST}$, say one of those, it can by $\bf ZFC$. It's principally written down via first order logic and ...
0
votes
1answer
40 views

Limit of decreasing sequence of closed (under logical consequence) theories.

Let $T_1 \supsetneq T_2 \supsetneq T_3 \supsetneq \ldots$ be a strictly decreasing sequence of closed (under logical consequence) theories, where closed means that for any statement $\phi:T_i\vdash \...
-1
votes
2answers
107 views
5
votes
2answers
225 views

Interaction of completeness and second incompleteness theorems

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M \...
3
votes
0answers
154 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
13
votes
5answers
4k views

What precisely is a vacuous truth?

Is there a proper and precise definition that goes something like this? Definition. A statement $S$ is a vacuous truth if ... ...
4
votes
1answer
251 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
0
votes
1answer
32 views

proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
0
votes
1answer
40 views

Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I ...
1
vote
1answer
64 views

$\Sigma \ \vdash A \lor B \ \ $

I'm stuck with the following question: prove or disprove the following: if $\Sigma \ \vdash A \lor B \ \ $ then $\ \ \Sigma \ \vdash A \ \ $ or $\ \ \Sigma \ \vdash B $ Thanks....
1
vote
1answer
117 views

Predicate Calculus English Translation

I'm having difficulty translating the following English sentences into predicate logic. Any help would be greatly appreciated. $B:\qquad$_ is a book $A:\qquad$_ is an author $H:\qquad$_ is a ...
1
vote
1answer
81 views

Truth value of conclusion

Here I are premises followed by a conclusion. I want to confirm if my understanding about conclusion being false is right or not. In the book it was mentioned that their conclusion is false. My ...
2
votes
1answer
94 views

Predicate logic proof

Prove the following formula. $$ \vdash (\exists x)(A \land B) \lor (\exists x)(A \land C) \equiv (\exists x)(A \land (B \lor C))$$ The question is number 10 in chapter 6 in "Mathematical Logic" by ...
2
votes
1answer
31 views

For $\mathbb{X}$ with order relation and field structure extended from $\mathbb{R}$, if it includes real line, then is it real line?

For a set $\mathbb{X}$ given order relation and field structure extended from those of $\mathbb{R}$, if $\mathbb{X} \supseteq \mathbb{R}$ then $\mathbb{X} = \mathbb{R}$ ? This question is derived ...
3
votes
5answers
337 views

Can mathematics be traced back to a fundamental system of truths?

I'm not sure exactly how to state this question, or even if it belongs here. Still, I hope you will consider it, as I find it very interesting: Most of the results I've seen in mathematics come from ...
2
votes
1answer
45 views

Equivalent formula in countable structures

Question, if two sentences A & B, are such that for all countable structures M: M⊨A iff M⊨B, and A & B be thus logically eguivalent. But how?! I understand that I have to use Löwenheim-...
0
votes
1answer
84 views

The definition of interpretation in a Kripke model collides with my intuition of what it should do

In Lindröm and Segerberg (2007) exposition of a Kripke model, with frame $F= \langle W,D,R,E,w_0\rangle$, they define an interpretation $I$ as a family of functions $I_w$, where $w$ ranges over $...
2
votes
1answer
72 views

Are all theorems of minimal arithmetic theorems of a given theory?

I am working on some metamathematics revision and the following question came up. Let the theory $R_0$ be axiomatized by the following axiom schemata which hold for all $n,m \in \mathbb{N}$: $\...
1
vote
4answers
5k views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
3
votes
1answer
67 views

Intuitionistic logic and explicit existence proofs

I have read that to intuitionistically prove a statement of the form $\exists x.\varphi,$ we have to actually describe such an $x$ as an explicit expression (with free variables from $\varphi$, ...
1
vote
1answer
125 views

First Order Logic “More Than One”?

I'm trying to figure out how to express "More than one" in first order logic. What I have so far is: $$\exists S_1 \exists S_2 IsGreen(S_1) \wedge IsGreen(S_2)$$ But that definitely doesn't sound ...
2
votes
1answer
54 views

Logic verification: $x^3$ is irrational, then $x$ is also irrational

Prove, by contraposition, if $x^3$ is irrational, then $x$ is also irrational. Just a verification do I need to show that given $x$ is rational $x^3$ is also rational? Suppose $x \in \mathbb{Q}$ ...
3
votes
1answer
146 views

Theorems that we can prove only by contradiction

While most of the world is fine with proofs performed by contradicting the thesis, direct proofs are sometimes considered more elegant than indirect ones. Those who prefer intuitionism or ...
1
vote
1answer
46 views

Question about the total probability law

Why does $A= (A \cup B) +(A\cup C)$ and not $(A \cap B)+(A \cap C)$? Wouldn't you have to take the intersection to have elements of just $A$ instead of having the elements that $A$ overlaps with? Why ...
3
votes
2answers
88 views

Epistemic logic: in which worlds are the formulas true?

I have a question regarding the following: I don't get both answers. I thought that question 1 was true in w2, w3, w4. But the answer does not show have w3. Why is that? Because the symbol says ...
2
votes
1answer
34 views

How to quantify a specify amount in logic

I'm looking for a way to specify the number of times an event happens in a Discourse Representation Structure, basically using first order predicate logic. I have the existential and universal ...
2
votes
2answers
603 views

How to explain the power of PA to non-logicians

I plan to give a talk to a group of math PhD students (with no exposure to mathematical logic. I should also mention that I'm certainly no logician, myself) about the incompleteness theorems. I plan ...
1
vote
5answers
74 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
0answers
68 views

What do we call functions that are definable by expressions?

Let $X$ denote a model of an algebraic theory $T$. What do we call the functions $f : X^n \rightarrow X$ that are definable by some expression in the language of $T$? e.g. If $S_3$ is the symmetric ...
2
votes
2answers
51 views

What does rule schematic mean?

While I'm studying the mathematical logic, the book says "Each rule of such a calculus either says that certain strings belong to $Z$, or else permits the passage from certain strings $\zeta_1,\cdots,\...
0
votes
0answers
110 views

The unique model of cardinal $\kappa$ of a $\kappa$-categorical countable theory is saturated.

Let $T$ be a $\kappa$-categorical ($\kappa \geq \aleph_1$) first-order theory in a countable language $\mathcal L$. I try to prove that its unique (up to isomorphism) model of cardinal $\kappa$ is ...
0
votes
1answer
188 views

Do syllogisms apply to probabilistic statements?

I came across a statement that triggered my logic 101 alarm on another SE site, regarding risk factors for an illness. The statement was similar to this (modified): Favoring green jelly-beans is ...
1
vote
1answer
266 views

What is the definition of “Winning Strategy” in an Ehrenfeucht-Fraïssé game?

I've read many descriptions and applications of a Winning Strategy, as much as many for a Strategy tout court, but when a formal, algebraic definition is called upon, I've found close to no input. I ...
2
votes
1answer
259 views

Some burning questions on First-order logic from an amateur

I'm currently taking an introductory course in Mathematical logic(prerequisites is only advanced calculus) and my lecture notes are based on Enderton's book 'Mathematical Introduction to Logic' ...
1
vote
1answer
115 views

How to prove if two propositions are always true

Let P1 and P2 denote the following propositions: P1="CS is difficult or not many students like CS". P2="If math is easy, then CS is not difficult". Suppose that both P1 and P2 are true, determine if ...
1
vote
1answer
51 views

big o statement prove or disprove (impossible)

This question is harder than it looks folks for all a in the reals and for all b in the reals, [(a <= b) => (n^a is O(n^b))] n^a is O(n^b) if n^a <= cn^b for some n>= n, (n less than or equal ...
1
vote
1answer
151 views

Prove formula in Predicate Logic

Prove the following $$ \vdash A \land (\exists x) (B \rightarrow C) \equiv (\exists x)(B \rightarrow (A \land C)) $$ as long as $ x$ not free in $A$. This is question number 9 chapter 6 in "...
0
votes
1answer
184 views

rewriting quantifiers using propostional expressions

Let the domain of the propositional function P(x) be D={a,b,c}. Express the following quantified statements without using quantifiers but as logical expressions of P(a), P(b) and P(c) using AND, OR, ...
0
votes
1answer
67 views

Clarification about the definition of term algebras

The following definition has been given in this article. A term algebra is an algebra $ \langle \mathcal{S}, \mathcal{G} \rangle $ where every time that $g_\alpha, g_\beta \in \mathcal{G}$ and $$ g_\...
2
votes
3answers
68 views

Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.
3
votes
3answers
99 views

#23 on GRE 8767

I am unsure how I would do the work for this question: $S(n)$ is a statement about positive integers $n$ such that whenever $S(k)$ is true, $S(k+1)$ must also be true. Furthermore, there exists some ...
3
votes
1answer
271 views

What is the converse of the triangle inequality?

It's usual when presenting a theorem to also present its converse. Surprisingly, I've never seen the triangle inequality's converse stated. Triangle inequality: If the sides of a triangle are a, b, ...
0
votes
1answer
35 views

Can all cardinal numbers be represented by an ordinal numbers, assuming choice?

Can all cardinal numbers be represented by ordinal numbers, assuming AC? (ZF+AC) If or if not, what would be the proof?
4
votes
0answers
129 views

Logic in closed symmetric monoidal categories; reference request.

Suppose we want an algebraic theory $T$ to be interpretable in any closed symmetric monoidal category $\mathbf{C}.$ I am thinking in particular of the case where $\mathbf{C}$ is the category of models ...
0
votes
1answer
58 views

Propositional Logic Proof [closed]

how to prove this statement using propositional logic. The idea is in my head but i just can't seem to figure it out. Here is the statement : (A->B)^(B->(C->D))^(A->(B->C))->(A->D) This is what i've ...
0
votes
1answer
348 views

What is the use of Tarski-Vaught test?

As title says, what is the use of Tarski-Vaught test? I do understand that it is necessary and sufficient criteria for $N$ to be an elementary substructure of $M$, but beside that I don't see how this ...
1
vote
2answers
69 views

What exactly is $L$-terms in model theory?

I got confused after seeing the inductive definition of $L$-terms in model theory. So I do get that there are variables and constants, and when function $f$ is applied to the term, the resulting thing ...
2
votes
1answer
126 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k \...
0
votes
2answers
98 views

How many Scythians were there?

I was doing a maths test yesterday and the last question on the exam was as follows: $2500$ years ago, a Scythian king called Ariantas ordered every one of his subjects to bring him an arrow head. ...
2
votes
5answers
280 views

Question about definition of binary relation

Wikipedia says: Set Theory begins with a fundamental binary relation between and object $o$ and a set $A$. If $o$ is a member of $A$, write $o \in A $. I thought that a binary relation is a ...