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

5k views

### Is there a law that you can add or multiply to both sides of an equation?

It seems that given a statement a = b, that a + c = b + c is assumed also to be true. Why isn't this an axiom of arithmetic, like the commutative law or associative law? Or is it a consequence of ...
66 views

### More than one quantifiers for one variable: $\forall x\exists x P(x)$

I couldn't find any definiton about this: $\forall x\exists x P(x)$ Is here the for all or the there exists stronger? Cheers
109 views

### What to use for r in proof by contradiction?

This is a problem from Discrete Mathematics and its applications To this proof, I am trying to use proof by contradiction. Here is how the book described the process of proof by contradiction. I ...
48 views

### Models of H and GL

I've been reading The Logic of Provability by George Boolos, and something he said stumped me for a bit. Let us use H (for Henkin) to refer to the system that results when (YS) is added to K, i.e.,...
50 views

### Truth Table Logic XOR

I'm not sure if my solution is correct. Would be very happy if you can check and say what I did wrong. a) Is to make A xor B with only conjunction, disjunction and negation. b) Is to check if A xor (...
58 views

### Next step to take in direct proof?

This is a problem from Discrete Mathematics and its Applications. I understand the basic ideas of the direct proof. Basically a proof is a conclusion from a series of steps to establish the truth of ...
54 views

### Next step to take in direct proof or a workaround around current dilemma?

This is a problem from Discrete Math and Its Applications I used a direct proof to do this proof. I understand the process/idea behind the direct proof, mainly (from https://courses.cs.washington....
111 views

### Order type of real analytic monotonic functions ordered by eventual domination

Let $\mathcal F$ be the set of all functions $\mathbb R^+\to\mathbb R$ that are: real analytic on $\mathbb R^+$, monotonic on $\mathbb R^+$, and having derivatives of any order that are also ...
87 views

### Trouble Reading “On Formally Undecidable Propositions”

I've been working my way through Godel's original paper of the incompleteness theorem in my spare time, and I'm stuck with something stupidly simple. I'm looking at the list of 45 definitions of ...
39 views

...
71 views

### What does if-then has to do with not being true?

I'm reading Chihara's: Constructibility and Mathematical Existence. It says: An even more radical view rejects the assumption that mathematics is true—at least in the straightforward way that ...
564 views

### Need help understanding discrete mathematics logic

I am having a heck of a time understanding Discrete Mathematics. I have tried this myself and put my answer below. If anyone could help me if my answer is incorrect could you please explain to me what ...
87 views

### Ultraproduct of a metric space

I am currently trying to understand "Curvature bounded below: a definition a la Berg--Nikolaev" by Nina Lebedeva and Anton Petrunin. They start with a complete, intrinsic metric and space $X$ and say ...
167 views

### Are the following logically equivalent? $\;p \rightarrow (q \rightarrow r) \text{ and }\ (p \rightarrow q) \rightarrow r$

Determine whether the following pair of statements are logically equivalent or not... $$p \rightarrow (q \rightarrow r) \;\;\text{ and }\;\; (p \rightarrow q) \rightarrow r$$ I am new to logic ...
97 views

### Lindenbaum's Lemma

I am working on the proof of the Lindenbaum's lemma and there are some passages which are not very clear for me. Here is the statement: Let $\mathbb{L}$ a countable signature, $T$ a consistent set of ...
120 views

### How to express exact quantifier in this situation?

This is a problem from Discrete Mathematics and its Applications My question is on 10g. Here is my work so far. My logic behind this is to first iterate over all peoples in the world, for each ...
48 views

### Would including the outside quantifier make more sense/be logically correct?

This is a question from Discrete Mathematics and Its Applications. My focus/question is 1b. What I got was for this question was (English translation) There is a student in your class who has sent ...
50 views

### Is my inference based on previous assumptions correct?

This is to check my work on a problem from Discrete Math and Its Applications. Here is the problem. My question is on part d. I would say that c does not follow from a and b because it is true that ...
58 views

### How can I prove this relation between the elementary set theory and the elementary logic?

If you need to prove an equality like $A\Delta B=(B\setminus C)\cup[C\cap (B\Delta A)]$ we can first prove $p\underline{\lor} q\Longleftrightarrow (q\land\overline{r})\lor(q\underline{\lor}p)$ (with a ...
42 views

### Why is the Reflexive Property just about one number equal to the same one?

Why do $10=10$ and $c=c$ belong in the Reflexive Property group? I understand they're the same and equal but why? Why does this happen? Also $5+4=5+4$. Just let me know.
637 views

### Structural Induction vs Normal (Mathematical) Induction

In computer science and semantics I have come across structural induction many times. In that context, it is often presented as something different from but similar to mathematical induction, ...
149 views

### Proof of $\exists x(P(x) \Rightarrow \forall y P(y))$

Exercise 31 of chapter 3.5 in How To Prove It by Velleman is proving this statement: $\exists x(P(x) \Rightarrow \forall y P(y))$. (Note: The proof shouldn't be formal, but in the "usual" theorem-...
341 views

### Does taking courses in mathematics give any help for mathematical logic?

I'm undergraduate student of philosophy department and I think I'll major in mathematical logic. For studying mathematical logic, I thought studying math lectures would give help to logic. So I ...
207 views

### How to identify rules of inference that establishes validity?

I've been trying to determine an explanation for the falsity of a logical statement for some time now and I've had no luck in figuring out exactly how to go about it. The two part question goes as ...
86 views

### How to explain why a particular logical statement is false?

I've been trying to determine an explanation for the falsity of a logical statement for some time now and I've had no luck in figuring out exactly how to go about it. The statement in question goes as ...
87 views

### what does “a wff f(x, y)” mean exactly? (context: transfinite recursion)

I'm currently working through Herbert B. Enderton's book "Elements of set theory". I have a question concerning notation in logic, of which I know the basics but in which I'm not that firmly grounded. ...
154 views

### Definition of Bound/Free Variables

You may have already seen that: $$\int_0^1 x \, dx = \int_0^1 y \, dy$$ But the formal reason why this is done is because $x$ is a bound variable correct? QUESTION: We are allowed to change ...
253 views

### Designing a circuit to verify operation of an OR gate.

Consider the following image: I need to design a circuit that verifies the logical operation of the OR gate. In the above image, the LED will be on (f = 1) if the or gate is working properly. I can ...
Can I write a modal logic formula that describes linearity? by linearity I mean the following properties: reflexive transitive $\forall{x,y} \;\; (xRy \lor yRx)$ I'm thinking on it for over a day ...