Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
2answers
85 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" ...
4
votes
5answers
154 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
46 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
26 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
65 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
93 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 ...
0
votes
3answers
47 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
53 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
47 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
42 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
67 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
32 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
47 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
30 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
0answers
41 views

Would a “prenex Blake normal form” 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
1answer
43 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
69 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" ...
-1
votes
0answers
23 views

Understanding proof about $∀ j ∈ I (A_j ⊆ A _i )$

This is one of the problem which has been solved in Vellmena's How to prove book: Suppose $\{A_i | i \in I \}$ is a family of sets. Prove that if $P (∪_{i \in I} A_ i ) ⊆ ∪ _{i \in I} P (A_i )$, ...
2
votes
2answers
55 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
44 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 ...
-1
votes
1answer
35 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$ ?
0
votes
0answers
35 views

Proof (~p→~q) Equivalent to (q→p) [duplicate]

Anyone can teach me how to proof (~p→~q) equivalent to (q→p) without truth table? Please help
4
votes
2answers
119 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
29 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
64 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
94 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
24 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
49 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 ...
7
votes
4answers
305 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
27 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
35 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 ...
10
votes
2answers
164 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
31 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
71 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
56 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
57 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 ...
-1
votes
0answers
34 views

Are my definitions correct? (Formal language)

I will describe how I understand below. Please tell me where I'm thinking wrong or correct. Symbol is an undefined term just like a set. Symbol can be ragarded as a object we consider. ...
-1
votes
0answers
23 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
87 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
1answer
44 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
77 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 ...
6
votes
2answers
99 views

Defining addition in second order logic

(before saying it's duplicate, read whole question) I was told by someone that we can define addition and multiplication purely in terms of successor function, provided that we work in second order ...
5
votes
4answers
83 views

Writing “$f$ is not a bijection” with quantifiers only

Is it possible to write '$f$ is NOT a bijection' with quantifiers only, and without using "$\neg$"? What is the negation of "$\exists$!"?
-1
votes
1answer
110 views

Can someone explain Godel's Completeness theorem in the simplest terms?

I wrote a blog on logic. http://deepturtel.blogspot.com/2014/12/logic.html I may need to correlate this with Godel's Completeness Theorem. I understand Principia Mathematica (without the formal ...
2
votes
2answers
57 views

DNF Form of XOR Operator with N Arguments

I’m working on this problem: Explain how to express $p$ using the boolean connectives AND, OR, and NOT so that the resulting expression has length polynomial in $n$. $$p(x_1\cdots x_n) = x_1 \oplus ...
1
vote
1answer
63 views

Complicated FOL Formula {∃a,c(a≠c) ∧ ∀a,c[(a≠c)⇒(h(a,c)⟺ ¬h(c,a))] ∧ ∀a,c[h(a,c) ⇒ ∃b(h(a,b)∧h(b,c)∧b≠c)]} ⇒ ¬{∃a∀b[b≠a⇒ h(a,b)]}

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid and if not, then give a model that does not satisfy the ...
2
votes
1answer
55 views

Does order of qualifiers matter in FOL formula?

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid. FYI, $m$ is a binary predicate. $$(\forall x \,\exists ...
1
vote
1answer
44 views

If $\bigcup F = A$ then $A\in F$ then prove that $A$ has exactly one element

This is one question which has been asked in Velleman's How to prove book: Suppose $A$ is a set, and for every family of sets $F$, if $\cup F = A$ then $A ∈ F$. Prove that $A$ has exactly one ...
1
vote
2answers
52 views

If $T \models \phi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \phi$

Use the Compactness Theorem to show: if $T \models \varphi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \varphi$. I don't see how I can use the compactness theorem here. ...
0
votes
0answers
54 views

Well-formed formulas: Difference between $\forall x(x \in A \implies x \in B)$ and $(\forall x \in A) x \in B$? [duplicate]

Let $A$ and $B$ be sets. There seem to be two ways of writing $A \subseteq B$: \begin{equation} \forall x(x \in A \implies x \in B) \end{equation} or \begin{equation} (\forall x \in A) x \in B ...