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
95 views

proving tautologically equivalent

This semester I take Introduction to logic and sets theory and for logic our reference is A Mathematical Introduction to Logic by H.B.Enderton. I have some problems with this course I mean it is ...
0
votes
3answers
108 views

Predicate Logic, confusion about implication statement.

Let's say the domain of discourse is the set of 10 balls, numbered as such from 1 to 10. Some (more than 1 but NOT all) of those balls are put into a bag, and then some of those in the first bag are ...
0
votes
1answer
1k views

How to show set of connectives is adequate

I am reading over my notes and I can not understand how to show set of connectives are adequate. I understand that in order for a set to be adequate, we must be able to express them in terms of the ...
0
votes
1answer
80 views

logic - how to model or diagram conditional probabilities of multiple related scenarios.

I am interested in modeling questions and specific outcomes so that i can evaluate conditional probabilities and mathematical expectation. I am looking for a way to diagram or otherwise describe the ...
2
votes
1answer
210 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
52 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
137 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
77 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
47 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
264 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
68 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
346 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
47 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
247 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 ...
9
votes
1answer
211 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
313 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
146 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
53 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 ...
6
votes
1answer
362 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
73 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 ...
-1
votes
1answer
51 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
219 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
161 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
93 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
426 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
101 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
114 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
457 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
315 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
425 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
1k 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
60 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
1k 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
127 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
89 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
112 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
458 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
161 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
185 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
44 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
41 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
31 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
283 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
42 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
64 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
91 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
65 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?
-2
votes
1answer
341 views

Determine whether each of the following sets is well ordered? [on hold]

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