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)

23
votes
12answers
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 ...
3
votes
1answer
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
0
votes
2answers
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 ...
1
vote
1answer
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.,...
1
vote
2answers
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 (...
0
votes
1answer
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 ...
2
votes
1answer
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....
4
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
39 views
1
vote
1answer
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 ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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.
6
votes
1answer
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, ...
2
votes
2answers
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-...
3
votes
5answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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. ...
-1
votes
2answers
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 ...
1
vote
3answers
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 ...
1
vote
1answer
81 views

Can linearity be expressed by a modal logic formula?

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 ...
1
vote
0answers
50 views

Would a “Prenex Sum of Products” be canonical?

I know that prenex normal form (PNF) is not canonical, and there is an example in Wikipedia showing two equivalent formulae in PNF that differ in their prefixes, but have equal matrices: $\forall x \...
0
votes
3answers
57 views

Doubt regarding conditional statement in mathematical logic [duplicate]

Conditional statement is represented as $p\to q$. Its truth table is given as: $$ \begin {array}{|c|c|c|} \hline p & q & p\to q\\ \hline T&T&T\\\hline T&F&F\\\hline F&T&...
1
vote
2answers
80 views

When is this open sentence true? $Q(n): n^3 + n - 1 = 0$, where n is the collection of integers

I've asked my instructor but he didn't really help at all, and I can't find anything on the web that can help me since I'm not sure what the terms are. Question: When is this open sentence true? $Q(...
0
votes
1answer
48 views

Proving injection and surjection with functions $F:C^B\to C^A$, $F(f)=f\circ\varphi$, $\varphi: A\to B$

Let $\varphi: A\to B$ and define $F:C^B\to C^A$ such that $F(f)=f\circ\varphi$. Prove the following: if $\varphi$ is surjective then $F$ is injective. if $\varphi$ is injective then $F$ is ...
0
votes
1answer
128 views

Negation of quantifiers

Prove the following statement on negation of quantifiers: Statement: To negate a statement of the form $$ Q_1x_1 Q_2x_2 \ldots Q_nx_n\; P(x_1,x_2,\ldots,x_n), $$ where $Q_i$ is $\forall$ or $\...
0
votes
1answer
59 views

What does the notation ab1, ab2, etc. refer to in predicate logic?

I'm trying to decipher a set of relations from a John McCarthy paper: $$ specializes(c1,c2) \land \neg ab1(p,c1,c2) \land ist(c1,p) \supset ist(c2,p) $$ and $$ specializes(c1,c2) \land \neg ab2(p,...
0
votes
1answer
77 views

Predicates and Quantifiers in discrete math

Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for ...
2
votes
2answers
72 views

Questions which have false conditions

There are many "questions" on the internet like If $$1=5$$ $$2=6$$ $$3=7$$ $$4=8$$ then how many is $5$? With one "logic" answer is $9$ because $n=n+4$, then $5=9$. With other "logic" ...
2
votes
2answers
446 views

How to determine statement truth values without using a truth table?

I'm currently working on some tautology questions as a brush up for a discrete mathematics course and I'm having a bit of trouble remembering tautology. Precisely, how do I prove certain statements ...
5
votes
1answer
102 views

Is there a syntax for type quantification in higher order logic?

I'm trying to understand higher order logic deduction, and I sort of understand how after going to third order logic and higher you have a type explosion; predicates and functions can have a large ...
0
votes
1answer
59 views

Functions and Relations Predicate logic

If we are given a set universal set $U$ and another set $X$, how do we know if the given set $X$ is a relation on $U$ or a function on $U$ ?
4
votes
1answer
155 views

Set theoretic universe in consistency proofs

I am having difficulties understanding the relative consistency proof $Con(ZF)\rightarrow Con(ZFC)$. Most authors seem to assume at the outset the existence of some universe $V$ satisfying $ZF$ and ...
2
votes
2answers
157 views

Negating the definition of a limit point

Below is a definition of a limit point: $E$ is a subset of a metric space $X$. $p \in X$ is a limit point of $E$ exactly when every ball around $p$ has an element $q \in E$ such that $q \neq p$. ...
1
vote
4answers
86 views

What can be said about $P (A \setminus B) \setminus (P (A) \setminus P (B))$?

This is one of the problem I have been solving in Velleman's How to prove book: Suppose A and B are sets. What can you prove about $P (A \setminus B) \setminus (P (A) \setminus P (B))$ ? Now, I ...
1
vote
1answer
133 views

Reference request - Outline of Edward Nelson's Inconsistency Proof

Edward Nelson retracted his inconsistency proof before it was published. Unfortunately, the outline given by Nelson has been removed. Is there a copy of it on the web? I am interested in how the ...
0
votes
0answers
78 views

Are proofs for many-sorted first order logic shorter than single sorted first order logic?

I understand that the expressive power of first order logic with one sort is the same as any many sorted first order logic, and that higher order logic with general semantics is the same as a many ...
2
votes
1answer
60 views

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map.

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map. I'm not even sure where to begin at the moment. I was informed of "induction on the complexity" ...
6
votes
4answers
549 views

Why aren't valid higher order logic sentences recursively enumerable in full semantics?

It's said (proven in some reduction to the Gödel–Rosser theorem?) that second order logic and higher fails to be complete for full semantics; that is there isn't any semi-algorithm for determining if ...
0
votes
1answer
41 views

For an L-structure $M$, and a formula $\phi$, in which of the cases does $M \models \phi(x/2)$?

For a) $\phi(x)$ is $(\forall y(y=1+1 \implies x=y))$ b) $\phi(x)$ is $(\forall x(x=1+1 \implies x=y))$ The answer is supposed to be a) but I don't know why. I guess I don't fully understand the ...
-1
votes
1answer
58 views

The existence of concatenation functions in Godel Numbering?

I know that there are many schema of Gödel Numbering, and each has its own method of Concatenation, n★m. But is there a general proof that shows 'For every Gödel Numbering scheme there exists a ...
11
votes
2answers
411 views

How to prove that Gödel's Incompleteness Theorems apply to ZFC?

Let us denote Robinson Arithmetic as Q and Primitive Recursive Arithmetic as PRA. Let $T$ be a formal theory formulated in the language of arithmetic. According to this page on the Stanford ...