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)

1
vote
1answer
85 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
547 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
79 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
154 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
93 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
112 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
47 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
611 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
143 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" ...
3
votes
5answers
332 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
189 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
81 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
153 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
236 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
79 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 ...
1
vote
2answers
79 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? ...
0
votes
1answer
47 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$ ...
0
votes
1answer
123 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 ...
0
votes
1answer
73 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
410 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
95 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
150 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
85 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
131 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
76 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
59 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 ...
6
votes
4answers
534 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
57 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
392 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 ...
-1
votes
2answers
34 views

Proportions with Time

Sorry about the title, I'm not exactly sure what to call this type of problem. It takes one man one day to dig a $2\text{ m} \times 2\text{ m} \times 2\text{ m}$ hole. How long does it take $3$ men ...
5
votes
1answer
81 views

Question concerning the proof of the equality of $x\sqrt{y}$ and $y\sqrt{\frac{x^2}{y}}$

I want to prove that $x\sqrt{y}=y\sqrt{\dfrac{x^2}{y}}$; I've proven it to myself via calculator (brute forcing it) when $x,y>0$, and this is my proof: $$\begin{align*} x\sqrt{y} &= ...
1
vote
1answer
131 views

Predicate natural deduction: Prove (∀x R(x,x)) => ∀x∃y R(x,y)

Prove that if the relation R is reflexive, it is also serial: $ \forall x \space R(x,x) \vdash \forall x \exists y \space R(x,y)$ I've tried this so far but can't think of anything further: $1. ...
1
vote
2answers
107 views

For which subsystems T of 2nd order arithmetic is there a model of T + $\neg$Con(T)?

A theory T might have the following property: there is a model of T + $\neg$Con(T) 1st order PA has this property, but full 2nd order PA doesn't. Among subsystems of 2nd order arithmetic, which ones ...
0
votes
0answers
46 views

Is any language a formal language?

Definition of formal language in wikipedia : formal language is a set of strings of symbols that may be constrained by rules that are specific to it. For example, let's take (meaningful) English ...
0
votes
1answer
121 views

What are the rules of inference used for syntactic consequence in Gödel's Completeness Theorem?

I am trying to understand the Completeness Theorem, and I was just looking at its explanation in the answer to this question: What is the difference between Gödel's Completeness and ...
0
votes
2answers
57 views

Inference rule for Non-Empty Domains

I am currently experimenting with logic frameworks. I am basically using something along dependent types as in "Proof-assistants using Dependent Type Systems" by Henk Barendregt and Herman Geuvers. ...
4
votes
2answers
87 views

Is there any unreachable result?

I hope that this question is reasonable and make sense because I am not sure. Every theorem's proof is consisting of finite logical steps. Can a proof of the theorem require infinitely many ...