# Tagged Questions

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

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

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 ...
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 ... ...
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 ...
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: ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
84 views

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 ...
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$, ...
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 ...
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}$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
51 views

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,\... 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 ... 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 ... 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 ... 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' ... 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 ... 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 ... 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 "... 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, ... 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_\... 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. 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 ... 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, ... 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? 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 ... 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 ... 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 ... 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 ... 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 \...
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. ...
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 ...