Questions about 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)

2
votes
1answer
134 views

How do I use rules of inferences to imply a conclusion from 4 premises?

I am a little confused on how to use 4 premises to prove a conclusion. Can you please tell me if my logic is sound for the following proof: ...
0
votes
2answers
47 views

Inference Proof with Quantifiers

I am trying to figure out this implication proof. Can any of you guys tell me how to prove this? Prove ∀x((¬P(x) ∧ Q(x)) → R(x)) Implies ∀x(¬R(x) → P(x))
1
vote
1answer
119 views

Why is the Ehrenfeucht theory complete?

I am looking at the theory T of Dense linear orders without endpoints, extended with the set $\{c_i<c_j|i\in\omega\}$ and am asked to prove that this theory is complete. I know that it has three ...
0
votes
1answer
73 views

Boolean Queries in First Order Logic

I understand first order logic and how its constructed but I have some trouble understanding how the following statement and its FO query are formed. This is from a book. ...
1
vote
1answer
40 views

Split long relation over two line using boolean operator

Normally, when you have a long equation, you can split it on two lines. Suppose that $a$ and $b$ are very long expression. Then, for example: $$ x = a - b$$ can be rewritten as $$ x = a + $$ ...
12
votes
2answers
243 views

Founding Arithmetic on geometry

In the past I found some fleeting references that some (Frege in his later years being one of them) tried to found arithmetic not on set-theory and logic but on geometry and logic. Unfortunedly Frege ...
1
vote
1answer
65 views

How to prove $G$ is Eulerian

We know that a Eulerian graph has vertices all are even. But how can we prove the sufficiency of it i.e. if a connected graph $G$ has vertices all are even, then how can we prove the graph $G$ is ...
-1
votes
2answers
175 views

Formalizing sentences in predicate logic

I would like to formalize "The lecturer is happy, if all his students love logic" using Lecturer as a constant; $H(X) = X$ is happy; $S(X) = X$ is a student; $L(X) = X$ loves logic; $T(X,Y) = X$ ...
0
votes
2answers
44 views

What is a Boolean Function?

Please explain to me what a Boolean function is, and how do I make an expression. If the statement states that $f=$"she is out of work" and $s=$"she is spending more", how can I write symbolically ...
3
votes
2answers
220 views

Again about McGee objections to modus ponens

I would like to "reopen" the previous post regarding Modus ponens because, frankly speaking, I'm not satisfied with some (most of ?) answers by the mathematicians community. Disclaim: I'm not aiming ...
8
votes
1answer
170 views

Proof-theoretic characterization of the primitive recursive functions?

The total recursive functions are exactly those number-theoretic functions that can be represented by a $\Sigma_1$ formula of first-order arithmetic. Is there a similar characterization of the ...
0
votes
2answers
177 views

Deduction theorem explanation

Can someone please explain Deduction theorem in Logic. I am using the textbook "Mathematical Logic" for Tourlakis. I can't understand it at all.
1
vote
2answers
100 views

Meaning of variables and applications in lambda calculus

The wikipedia definition of lambda terms is: The following three rules give an inductive definition that can be applied to build all syntactically valid lambda terms: a variable, $x$, is ...
2
votes
1answer
51 views

Are there ordinals other than the set of natural numbers which satisfy this property?

Let $\alpha$ be an ordinal. We say that $\alpha$ is good iff for every $\beta\in \alpha$, there exists $\gamma\in \alpha$ such that $|\scr{P}(\beta)|\leq |\gamma|$. Question: Is the set of natural ...
4
votes
1answer
224 views

Why is better to work with first-order Peano's axioms than with second-order Peano's axioms?

In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the second-order version the operations: addition, multiplication and exponentiation ...
0
votes
1answer
71 views

Metaproving Question.

Prove that $ \vdash ((A \rightarrow B) \rightarrow A) \rightarrow A $ I want to make sure my answer is right as the textbook has no solutions. I am using Equational Proof. The textbook is ...
0
votes
1answer
48 views

In each case, write down a sentence of $L_i$ which is true in $A_i$ but not in $B_i$ . Explain your answers briefly.

$L_1$ has a single binary relation symbol $R$ . The domain of $A_1$ is $\mathbb N$ and $R(x_1, x_2)$ is interpreted as $x_1 \le x_2$. The domain of $B_1$ is $\mathbb Z$ and $R(x_1,x_2)$ is interpreted ...
1
vote
2answers
158 views

The connective ! has truth table… Show that the connective is not adequate.

$$\begin{array}{cc|c} P & Q & P!Q \\ \hline T & T & F \\ T & F & T \\ F & T & F \\ F & F & F \end{array}$$ I think this should be proved using induction but I ...
2
votes
1answer
135 views

Why is better to work with first-order logic than with second-order logic? [duplicate]

Why is better to work with first-order logic than with second-order logic? In the case of Peano's axioms the second-order version is categorical, but the first-order is not. Besides, with the ...
0
votes
2answers
76 views

Tautological implication question.

I had this question in the homework and i don't get why the answer is right. $B, A \rightarrow B \vDash_{TAUT} A\ $ is not valid. If there exists a state $v$ such that $v(A) = f$ and $v(B) = t$ then ...
5
votes
3answers
375 views

Derive by modus ponens $[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$

How could I derive by modus ponens the formula $$[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$$ from, and just from, the following axiom schemata? $(A\lor ...
3
votes
1answer
89 views

Reflection schema for PA

I have some questions concerning reflection principle and Peano arithmetic: 1) PA + reflection for $\Pi_{1}$ sentences is equivalent to PA + CON(PA), I saw the proof but I dont quite get why $\bot$ ...
0
votes
3answers
100 views

Rewrite expressions

I have to prove that $$q\lor(¬q\land(p\lor q))$$ is equal to just $q$. This is normally done with logical equivalences, but I can't solve this one. Can somebody please help? ...
1
vote
2answers
280 views

Simple predicate logic question, formalizing sentences

"The lecturer is happy, if he has no students." $\forall l \not \exists s, H(l)$ How can we say "he has no students?" "The lecturer has some students who love logic." Would this be expressed as ...
0
votes
3answers
149 views

Give the truth table of a single binary connective which is adequate.

This might be a silly question, but I am confused. I know there is a theorem saying the only single binary connectives which are adequate are NOR or NAND, so I could use either of them. And then the ...
1
vote
2answers
264 views

Sigma hierarchy of logical formulae

In some papers on mathematical logic I've found references to hierarchy like $\Sigma_1^0$-sentence and so on. What does it mean? What is $\Sigma_n^m$, what is $n$ and $m$ here?
0
votes
3answers
642 views

Show that every formula of Propositional Logic has the same number of left and right parentheses

Show that every formula of Propositional Logic has the same number of left parentheses as it has of right parentheses. I have the answer, but I have failed to understand it.
1
vote
1answer
58 views

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

How do I prove that the function symbol $\circ$ is not a term by induction in the calculus? I've tried to prove it by the definition of term in first-order language. From the definition of term in ...
1
vote
3answers
541 views

Is -1 less than 0.1?

In a High School Maths Test, I presumed that since -1 has as much mathematical mass as a whole unit [-1 x -1 = 1, 1 x 1 = 1] and 0.1 represents one tenth of a unit, that -1 is greater than 0.1 -1 is ...
-1
votes
3answers
121 views

logical negation of a statement: any mammal that has long ears has at least [closed]

Write the negation of the following statement: Any mammal that has long ears has at least one of its predators with yellow eyes having all of its cubs that cannot fly. Write it in the logical ...
1
vote
3answers
77 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
92 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
1
vote
1answer
325 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
1
vote
1answer
139 views

First-Order Languages and Circular Reasoning

I'm reading a book on Mathematical Logic (on my own) and from the beginning there are terms such as "functions" and "relations", but the only definitions of these words that I know are in terms of ...
4
votes
4answers
164 views

When do free variables occur? Why allow them? What is the intuition behind them?

In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound. Why would one write such a formula? Why are free variables allowed? What is the intuition for allowing free variables?
0
votes
1answer
42 views

Two questions about the lattice derived from 0th-order formulas

It's not clear to me if the definitions I've been given are common. Therefore I will give a brief overview of the constructions I'll need to talk about the objects I want to. Prerequisite: Given ...
0
votes
1answer
40 views

Logical form of this statement?

In logical form, how would you express : Take any two fractions, add them together, and the result will be an integer
0
votes
1answer
27 views

How to describe a set of coordinates of variable length?

I need to describe a set of coordinates with up to 8 dimensions. A problem is asking me to describe an event from a experiment involving sampling. The catch is that the experiment doesn't end until a ...
1
vote
0answers
212 views

Substitute Proof by Contradiction/Negation with Direct Proof or Proof by Contrapositive

When do proof by contradiction, or by negation, or direct proof, or proof by contrapositive all work equally well? When can any one be chosen as the proof form? I'm interested in a pragmatic answer ...
0
votes
1answer
38 views

How to express in Propositional Logic

If A(S;C) is the propositional function (predicate) and student S who takes course C receives an A grade and the domain is a set of student belonging to university x. How to express "There are ...
2
votes
3answers
36 views

Put $(a \leftrightarrow b) \wedge c$ in DNF

$$(a \leftrightarrow b) \wedge c$$ I'm having problems with this. If I do: $$(a \rightarrow b) \wedge (b \rightarrow a) \wedge c$$ then $$(\neg a \vee b) \wedge (\neg b \vee a) \wedge c$$ But now I'm ...
1
vote
3answers
57 views

Question about the FT, FF cases in the conditional:

The conditional operator, $\phi \implies \psi$, is True for the values $TT, FT, FF$ and false for $TF$. I can easily understand why it's true for $TT$ and false for $TF$, but why is it for $FT$ and ...
2
votes
2answers
90 views

A quick question about a logical negation

I just want to make sure I'm negating the following logical statement correctly (for a contradiction proof): For every set $A$, there exists a well ordered set $V$ such that there exists no ...
0
votes
3answers
61 views

For $x+y+z=0$, if $x$ and $y$ are divisible by some integer $k$, then so is $z$.

If k|x and k|y and x+y+z = 0, then k|z. Here, "k|x" means that $k$ is a divisor of $x$ and $x,y,z,k \in \mathbb{Z}$ What strategy would you employ to prove this?
0
votes
1answer
174 views

Determine whether each of the following sets is well ordered?

A set is well ordered if every nonempty subset of this set has a least element. Determine whether each of the following sets is well ordered. a) the set of integers b) the set of integers greater ...
0
votes
1answer
92 views

Complexity of Recursively Inseparable Sets

I am interested in examples of recursively inseparable sets. A standard example is the set of positive integers encoding a Turing machine that halts in an odd number of steps on blank input versus ...
1
vote
3answers
318 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: For any relations $R,S$ and $T$ of $\mathcal{T}$, the relations ...
0
votes
1answer
95 views

find integral values k such that sum of expression is minimized

Given n values $X_1 , X_2 , ...., X_n$ , where $X_i$ can be positive or negative. The absolute values of $X_i$ will be less than $100000$ , also $n<=100000$ . What should be the possible value(s) ...
2
votes
1answer
154 views

A Question Regarding Forcing in Gödel's Constructible Universe in Infinitary Logics

In his answer to the MathOverflow question Gödel's Constructible Universe in Infinitary Logics, Prof. Hamkins gives a very interesting answer and proof to user46667's second question: (2) What is ...
1
vote
1answer
79 views

Constructive proof for: P => ((P => Q) => Q)

I'm trying to find a constructive proof for the proposition: P => ((P => Q) => Q) given P and Q to nullary proposition symbols but I can't find a proof without using the excluded middle rule. Anyone ...