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)

3
votes
1answer
89 views

Modular Inverses Discrete Math

I have to find the modular inverse of a sequence of numbers. When I do the inverse of $5\pmod {37}$, I get $-7$. $$37 = 7(5)+2$$ $$5 = 2(2)+1\text{, then}$$ $$2 = 1(37)-7(5).$$ so the inverse is ...
6
votes
1answer
570 views

Krivine Machine

Can someone please point out online resources to learn about Krivine Machine? My professor briefly touched it while teaching a course in Computer logic. google did not turn up much except some papers ...
2
votes
2answers
2k views

meaning of 'Hypothesis' in simple terms?

could anyone please clarify me the meaning of the term 'hypothesis'? with relation to terms 'reasoning' and 'assumption' ? Many thanks
1
vote
3answers
979 views

Is the associative property of XOR provable or axiomatic?

I have been trying to prove (for my own entertainment) that XOR is associative. However, having reduced $(p \oplus q ) \oplus r = p \oplus (q \oplus r)$ to canonical form, so that the only logical ...
3
votes
5answers
861 views

Common sense in mathematics

Are there any claims and counterclaims to mathematics being in some certain cases a result of common sense thinking? Or can some mathematical results be figured out using just pure common sense i.e. ...
6
votes
6answers
2k views

How to interpret material conditional and explain it to freshmen?

After studying mathematics for some time, I am still confused. The material conditional “$\rightarrow$” is a logical connective in classical logic. In mathematical texts one often encounters the ...
2
votes
1answer
88 views

A Simpler Characterization of Inductive Definitions?

While reading appendix A of John Harrison's "Handbook of Practical Logic and Automated Reasoning" a somewhat advanced theorem is appealed to as a prerequisite for characterizing when an inductive ...
0
votes
2answers
86 views

$\leq$ operation and logical error

We define $x \leq y$ operation as '$x<y \ \ or \ \ x=y$'. But this is false when both $x<y$ and $x=y$ as both can not be true at the same time. But I read text books that use this expression in ...
1
vote
1answer
569 views

Simple Question on Contrapositive Proof

If I want to prove something along the lines of: If there exists a j which satisfies the conditions: 1)... 2)... 3)... then Something awesome happens. I proved the forward direction of this (its an ...
1
vote
1answer
59 views

Propositional calculus. If there is a deduction of $t$ from $S\cup\{s\}$ in $n$ lines,

... then there is a deduction of $(s\Rightarrow t)$ in at most $3n+2$ lines. So I think this should be done by induction. The cases with $t$ being an axiom or a member of $S$ or $t=s$ can be proved ...
1
vote
3answers
167 views

Simple predicate calculus

All I want to do is write the following things into notation. My trouble is in inserting the correct order and understand where to use the same variables. The predicates are Students, Answers, and ...
1
vote
1answer
444 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
3
votes
1answer
117 views

An infinite cardinal agrees with all its well-orders on sets of full size.

Suppose $\kappa$ is an infinite von Neumann cardinal (well ordered by $\in$), and take ${<}$ a well-order on $\kappa$. Does there necessarily exists a subset $X\subset\kappa$ of full size (in ...
3
votes
3answers
237 views

Ways Of Ordering A Set

Perhaps this is a strange question. But it made me think and I have no idea how to answer it. Or if it actually makes sense. I've come across "Well-Ordered Sets" a few times now, and it's well known ...
3
votes
5answers
1k views

Tautology, Contradiction, or a satisfiable equation? Confusion about implication.

I'm having some trouble with a homework question. I have the following $ P \rightarrow \neg P$ This looks like a contradiction to me. This should never be true! Yet, if I transform it using $p ...
1
vote
1answer
178 views

Property of finite structure inexpressibiliy in first-order logic

I want two show that a certain property $u$ of some finite structure is not definable in first-order logic. Is the following reasoning correct? Let $\mathcal{S}$ denote a finite structure. Further, ...
1
vote
1answer
169 views

Finding a resolvent for clauses

I have the following question and am not sure how to do it. Find the resolvent for the two clauses: $P \vee \neg Q \vee R$ $P \vee \neg R \vee S$
2
votes
1answer
562 views

Representing a logic puzzle with mathematical symbols

Consider the following logic puzzle, which is one of many created by Lewis Carroll, the author of Alice in Wonderland. ...
1
vote
3answers
222 views

What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one. Background: (from ...
3
votes
1answer
125 views

Existence of elementary substructures of a uncountable structure over a countable language

Let $\kappa$ be an regular uncountable cardinal carrying a $\tau$-structure for some countable language $\tau$. What can be said regarding the existence of ordinals $\alpha <\kappa$ carrying ...
8
votes
1answer
7k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
1
vote
1answer
524 views

Boolean Algebra Distributive Laws

Given that $x\cdot(y+z)=(x\cdot y)+(x\cdot z)$ and $x+(y\cdot z)=(x+y)\cdot (x+z)$, what is the name for the opposite of those rules? Say I'm trying to prove the opposite, and I need to simplify from ...
16
votes
6answers
2k views

Does Gödel's Incompleteness Theorem really say anything about the limitations of theoretical physics?

Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, ...
1
vote
2answers
229 views

How come proof by tautology is not acceptable?

If we show that a claim is equivalent to a tautology (which is stronger than showing the claim implies a tautology), how come that isn't a valid method of proof?
3
votes
5answers
3k views

How can I get the negation of $\exists!$ (unique existential quantification)? [duplicate]

How can I get the negation of $\exists!$ (unique existential quantification)? if it's $\forall$, So if I wanna re-negate the last one, I'll get $\exists$ but it's not the same as what we started with! ...
1
vote
2answers
300 views

Is double quantifying a variable possible in predicate logic?

I read it as "Everyone is either a student or has read every book". But what's the use of the existential y outside the bracket? ...
3
votes
2answers
131 views

What is the correct propositional translation of this statement?

The question says, Translate the following sentence into the logical notation of propositional functions and quantifiers. H(x): x is a horse G(x): x is gentle. T(x): x has been ...
1
vote
1answer
77 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n? This is a follow up from a previous question: Given a φ independent of PA which is true ...
0
votes
2answers
281 views

What is a “first order signature”?

So I was just given the definition of a signature: A signature is a pair $\Sigma = (\Omega, \Pi)$ where $\Omega$ is a set of operation symbols $\omega$, each equipped with an arity ...
3
votes
2answers
144 views

write as quantifiers of mathematical logic: The barbers shave all those who do not shave themselves

The barbers shave all those who do not shave themselves. Therefore, the barber shaves himself. I need to write this in terms of quantifiers of mathematical logic. (b,Sxy) "So far i have done: ...
1
vote
2answers
198 views

are ternary relationships associative?

I read that all binary relations are associative. i.e (p.q).r = p.(q.r). However, I was curious that does this hold if p,q, and r are ternary relationships. I tried ...
1
vote
3answers
615 views

How to prove two propositions equivalent?

I was given the question: Determine if $\exists x (P(x) \implies Q(x))$ and $\exists xP(x) \implies \exists x Q(x)$ are equivalent, i.e., always have the same truth value. If they are not ...
5
votes
2answers
2k views

What's the difference between a negation and a contrapositive?

What's the difference between a negation and a contrapositive? I keep mixing them up, but it seems that a contrapositive is a negation where the terms' order is changed and where there is an imply ...
7
votes
3answers
3k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
9
votes
1answer
212 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
2
votes
3answers
113 views

What proof strategy can we use to prove this?

$$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$$ I tried to do a proof by case, but it doesn't work because of the quantifiers. So I was wondering what ...
11
votes
4answers
978 views

The Maths necessary to understand Logic, Model theory and Set theory to a very high level

I am studying Philosophy but most of my interests have to do with the philosophy of Maths and Logic. I would like to be able to have a very high level of competence in the topics mentioned in the ...
5
votes
1answer
475 views

Logic and geometry

By delving into topos theory and sheaves one will eventually discover a "deep connection" between logic and geometry, two fields, which are superficially rather unrelated. But what if I have not the ...
0
votes
2answers
129 views

Is this a valid proof of this predicate statement?

$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$ If the LHS is true, then Q(x) must be true for all values of x. Since Q(x) is true for any value, then Q(y) ...
3
votes
3answers
219 views

Are these two predicate statements equivalent or not?

$\exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y)$ I was told they were not, but I don't see how it can be true.
2
votes
1answer
45 views

Predicates variable order in P(x,y)

Is the predicate P with two variables, x and y, x smaller than y , the same thing as the predicate P with two variable , y and x, does it stays x smaller than y or does y becomes smaller than x ? ...
3
votes
4answers
104 views

Prove that if $5$ divides $a^2$, then $5$ divides $a$

Ok so my teacher said we can use this sentence: If $a$ is not a multiple of $5$, then $a^2$ is not a multiple of $5$ neither. to prove this sentence: If $a^2$ is a multiple of $5$, then $a$ itself is ...
3
votes
2answers
185 views

mathematical logic: a step is not clear

I'm reading the Shoenfield's book Mathematical Logic. On page 53 it states: Let r be the special constant for $\exists x.\neg$A. Then $\exists x. \neg A \implies \neg A_x[\boldsymbol{r}]$ ...
1
vote
2answers
252 views

Mathematical Logic.

I am seeking advice or an answer to the following question that is bugging me: How long a list of non-equivalent pure monadic schemata containing only the predicate letters “F” and “G” is there? I ...
0
votes
1answer
272 views

Questions regarding set theory notation

I’ve got some questions regarding set theory. I am struggling to find the right notation in order to express a number of conditions. I have a set named A that ...
2
votes
1answer
2k views

How to prove the distributive property without using truth tables?

I did it with using truth tables but I am inquisitive about how to proof the distributive property without using truth tables (i.e using the other rules of replacement or inference). $$ (P \land (Q ...
2
votes
2answers
86 views

Definability in FO($\mathbb{Q}, +, \leq$)

Is the set $\left\{(x, y) \in \mathbb{Q}_{>0}^2 \, : \, \frac{x}{y} \in 2\mathbb{N} - 1\right\}$ definable in FO($\mathbb{Q}, +, \leq$).
0
votes
1answer
35 views

Rationalization of an integer set

Let $X \subseteq \mathbb{N}^2$ be the set $\{(x,y) \, : \, y \text{ is the greatest power of 2 dividing } x\}$. I'm wondering how the set gets when multipled by the non negative rationals, i.e. what ...
8
votes
3answers
233 views

Does the category framework permit new logics?

It appears to me that a topos permits a broader concept of subsets than the yes/no decission of a characteristic function in a set theory setting. Probably because the subobject classifier doesn't ...
3
votes
1answer
57 views

In predicate logic, are these four expression equivalances?

(1) $\forall x P(x) \wedge \forall x Q(x)$ (2) $\forall x (P(x) \wedge Q(x)) $ (3) $\forall y (\forall x P(x) \wedge Q(y))$ (4) $ \forall y \forall x(P(x)\wedge Q(y))$ I'm sure that (1) and (2) ...