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

Proving a formula is valid

Let a formula $A$, and a term $t$ such that $x\in FV(t)$. Show that $\varphi = A\{t/x\}\to \exists x (x=t\to A)$ is valid. So let's assume by contradiction that the formula isn't valid. Therefore ...
1
vote
1answer
38 views

Formalizing a self referential sentence

In The logic of provability, by G. Boolos, we are asked to ponder about this statement: If this statement is consistent, then you will have an exam tomorrow, but you cannot deduce from this ...
-2
votes
1answer
51 views

Are the conditionals equivalent: $p → q ≡ q → p$?

I know that a conditional is if $p$ then $q$, but is that equivalent to saying if $q$ then $p$? Is $p → q$ saying the same as $q → p$?
2
votes
3answers
65 views

Negating the statement $\exists x \in \Bbb R$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$

There exists a real number $x$ so that $x$ is not an integer, $x > 2016$, and $\lfloor x^2 \rfloor = \lfloor x \rfloor^2$. I would like clarification on how to negate this. My idea of negation is ...
5
votes
2answers
98 views

Meta proof-searching

Suppose you have a particular theory (ex: $ZFC$) in which you want to prove a statement $\phi$. One can attempt to find a proof of $\phi$ that can be verified, but another tactic can be to find a ...
1
vote
1answer
28 views

Monadic signature with constant

Consider a signature $\Sigma = \{ P^1, R^1, c\}$. Where $P^1, R^1$ are unary predicates, and $c$ is a constant. Let A be a formula in FOL over $\Sigma$. Prove/Disprove: If A is satisfiable ...
0
votes
2answers
68 views

How could we formalize the introduction of new notation?

What I am thinking about is how in a textbook/proof/theorem/discussion/definition one states that from now on a new notation will be used in the appropriate scope. Example: Let $V^*$ denote the ...
1
vote
1answer
28 views

Sequents: if-introduction and discharging assumptions

I am reading through "Mathematical Logic by Ian Chiswell & Wilfred Hodges"(amazon, and publisher) for context I am reading through this for self-study, so I don't have the normal support of a ...
6
votes
2answers
485 views

What is the correct definition of a group?

What is the correct definition of a group? More precisely the predicate "being a group"? According to Wikipedia A group is a set, G, together with an operation • (called the group law of G) that.....
2
votes
1answer
45 views

First Order Logic Double Implication [closed]

I have a Logic Assignment of First Order Logic that I have to prove an initial claim, but one of the equations is kind of confusing for me because it has double implication and quantifiers. $$\...
2
votes
2answers
48 views

Axiomatizing stacks and queues using first-order logic

In the textbook I'm using to prepare the logic exam says that first order logic may be used to implement axiomatize data structures. There is an example of that: "Stack": uses a language that ...
2
votes
1answer
54 views

Show that there's no such algorithm

Show that there's no such algorithm, $A$ which gets a sentence, $\varphi$ (a formula without free-variables) and returns $\varphi'$ such that: $\varphi$ is satisfiable iff $\varphi'$ is valid (meaning,...
6
votes
1answer
200 views

Russell's paradox from Cantor's

I learnt how Russell's paradox can be derived from Cantor's theorem here, but also from S C Kleene's Introduction to Metamathematics, page 38. In his book, Kleene says that if $M$ is set of all ...
4
votes
2answers
265 views

Definition of truth in first-order logic

Let $L$ be a first order language. Let $P$ be a predicate symbol from $L$, and $c$ a constant. Given an interpretation $I$ of $L$, a definition states The formula $P(c)$ is true in $I$ iff $c\in ...
1
vote
1answer
74 views

is there still interest in finitary/syntactic mathematical logic?

A lot of textbooks on mathematical logic now rely on set-theoretic tools (models and topology). do people still care about developing mathematical logic from finitary methods? is there still ...
0
votes
1answer
23 views

Show that an axiom in Hilbert Calculus is valid

Consider the axiom in Hilbert Calculus: $$(\forall x(A\to B))\to (A\to\forall x B)$$ Where $x$ is not free in $A$ I want to show that for evry structure $M$ and for every interpertation $\rho$, the ...
1
vote
1answer
20 views

Algorithms for type checking, typability and inhabitation problems?

Studying typed lambda calculus, I was asked the following questions: (1) Given a lambda term $M$ and a type $\sigma$, does one have $\vdash M : \sigma$? That is, is $M$ of type $\sigma$? (type ...
1
vote
1answer
58 views

Can multiple Boolean variables and equations be converted to a single integer variable and multiple modulo equations?

e.g. let $x,y,z \in \mathbb{B}$ (Boolean) and $w \in \mathbb{Z}$ (integers) and $p,q,r \in \mathbb{P}$ (primes) For $x$ let $(0,1)$ be represented by integers $(\overline{a},a)$ mod p For $y$ let $...
4
votes
3answers
129 views

How is a set subset of its power set?

This question is from S C Kleene's Introduction to Metamathematics, page 38: If we prescribe as admissible elements of sets (a) $\varnothing$ and (b) arbitrary sets whose members are admissible ...
0
votes
2answers
24 views

Is the 1-consistency of $PA$ necessary to prove that $\diamond^{m} \top\implies \diamond^{n} \top$ is false if $m<n$?

In The logic of provability, by G. Boolos, there is a remark in chapter 7 saying that $\diamond^{m} \top\implies \diamond^{n} \top$ is false if $m<n$ (unless $PA$ is 1-inconsistent). Now, it seems ...
0
votes
1answer
34 views

Express that a set is finite using symbols

Two related questions: What's the most elegant way to express that the set $S$ is finite using logical symbols? Obviously this will depend to some extent on what you allow yourself to quantify, so ...
8
votes
1answer
65 views

How math help reduce terms and conditions of someone's dying wish?

Good morning everyone... This is my very first question here, so I apologise in advance for any wrongdoing which I possibly make unintentionally. So here is a little background story. I'm working at a ...
0
votes
2answers
28 views

Relating taking the power set to logical operations

I'm an undergraduate math major reviewing "Mathematical Proofs, A Transition to Advanced Mathematics" and specifically the first two chapters on sets and logic. I'm trying to find ways to write set ...
1
vote
1answer
59 views

If P then not Q and if not P then Q. What is the relationship called?

Is there a name of this relationship? P => Q and ~P => ~Q seems to be called equivalence. But could not find a name for P => ~Q and ~P => Q by cursory googling and browsing related Wikipedia articles....
3
votes
2answers
31 views

Quantification = statement about an open sentence?

The book I'm reading is talking about quantification being a method to convert open sentences into statements. From what I can see this method boils down to making a statement about the solution set ...
2
votes
0answers
109 views

Russell's paradox in the language of modern mathematics

In the Wikipedia article about Russell's paradox the authors present the naive set theory as a first order theory (as far as I understand), but without references. Can anybody share some references ...
1
vote
1answer
51 views

How to rewrite all the boolean operations using if-then-else operator?

Cited by Conditional Term Rewriting Systems: 1st International Workshop Orsay, France, July 8-10, 1987, p. 105 Additional Boolean operations are not needed, because all the usual Boolean ...
-5
votes
1answer
36 views

Gödel numbering for sequences Using the Chinese remainder theorem [closed]

I looked into some youtube videos and got a simple idea about Gödel numbering and Chinese remainder theorem separately.... But can't see how to use them as one. Wikipedia giving a way or may be its an ...
0
votes
1answer
26 views

First Order Logic problem using instant axiom

I was trying the following exercise of identity of VanDalen's Predicate Logic. It is as follows. $$\vDash \phi(t) \leftrightarrow \forall x(x=t \rightarrow \phi(x)), \ \ \ x \not \in FV(t)$$ It ...
0
votes
4answers
75 views

Proving $(H \implies H) \implies G \quad \therefore \quad G$ using natural deduction [closed]

I'm stuck on this extra credit logic problem for my course... Prove $$(H \implies H) \implies G \quad \therefore \quad G$$ using methods of natural deduction. Any help would be ...
2
votes
1answer
33 views

Defining functions in second-order arithmetic

In ZF, a function is a special kind of set, namely a set of ordered pairs where no two pairs have the same first component but different second components. How are functions defined in SOA? Are ...
3
votes
2answers
83 views

What is the exact role of logic in the foundations of mathematics?

At high school and in the beginning of my university studies, I used to believe the following "equation": Foundations of mathematics = Logic + Set Theory Of course, this "equation" does not hold ...
5
votes
4answers
348 views

Negation of definition of continuity

This should be a very easy question but it might just be that I'm confusing myself. So we have the definition of a function $f$ on $S$ being continuous at $x_0$: For any $\epsilon$>0, there exists ...
0
votes
0answers
50 views

How can I prove the following theorem: [duplicate]

Let $\Sigma$ and $\Sigma'$ be satisfiable sets of formulae such that $\Sigma\cup\Sigma'$ is not satisfiable, then there exists a formula $\Phi$ such that $\Sigma\models\Phi$ and $\Sigma'\models\lnot\...
0
votes
0answers
32 views

Importance of Th() into Reiter extension

i'm studying the Reiter extension but i don't understand the importance of Th() into it's definition: So given a default theory: $ \Delta = (W,D) $ The Reiter extension 'E' is defined basically by: ...
1
vote
1answer
37 views

Can every decision algorithm be expressed as a first order predicate?

Suppose we have a decision algorithm over, let's say, the set of natural numbers. Can this algorithm always be expressed as a first order predicate A(x) over the natural numbers, using only the ...
0
votes
3answers
40 views

What is the Post-fix and Prefix form of this two infix expression, See the details please?

There is two infix expression i mentioned below. Now i want to justify whether my answer is correct or not. So please tell me the correct post-fix and prefix form of this two infix expression. AB+(...
1
vote
1answer
21 views

translating algorithm to preserve validity?

Let two languages $\Sigma_1 = \{R^2, P^1, =^2\}$ and $\Sigma_2 = \{c, f^1, =^2\}$. Prove or disprove: There's an algorithm (procedure that halts) which gets as an input a formula $A$ above $\Sigma_2$ ...
0
votes
1answer
26 views

formula for defining terms in a finite set

Suppose there's a finite set, $S$ of terms in $\mathbb{R}$ which have the property $P(x)$. Suppose we know how to define the maximum value of the set by the relation, $max(x)$. We also have the ...
4
votes
5answers
391 views

Negation of the definition of limit

A sequence $(x_n) $ of real numbers converges to a real number $ x $ if For all $\epsilon> 0 $ there exists a natural number $ n_0 $ such that for all $ n \ge n _0 $, $|x_n - x| < \epsilon $. ...
5
votes
1answer
119 views

Relation between open sentences and sets (conceptual question)

Hi I'm a college student getting into the more proof oriented side of math. I was reviewing Mathematical Proofs, A Transition to Advanced Mathematics 2nd edition and after thinking about chapters 1 ...
6
votes
0answers
79 views

Is there a finite list of identites in the language of $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm})$ that generates all the others?

Let $\Phi$ denote the set of all identities satisfied by $(\mathbb{N},0,1,+,\times,\mathrm{gcd},\mathrm{lcm}).$ Question. Is $\Phi$ finitely axiomatizable? If so, I'd like to see a list of ...
0
votes
0answers
110 views

Writing a set of first order clauses to define a predicate

I need some help on where to begin with the following question: We say that a list (term) represents the natural number $k$ in binary if it consists of constants 0 and 1 and the digits of the ...
0
votes
1answer
38 views

Model for first order formula

I need to find a model for the following formula: $$(\forall x \forall y \forall z.R(x,y) \wedge R(y,z) \Rightarrow R(x,z)) \wedge (\forall x\forall y.\neg R(x,y) \Leftrightarrow R(y,x))$$ So I ...
0
votes
1answer
34 views

Prove/ Disprove a logical claim

Prove/ Disprove: $\Gamma \vDash_v A$ iff $\Gamma \cup \{\lnot A\}$ isn't valid for every structure. Clarifications: $$\Gamma \vDash_v A: \forall M (\forall \rho. [|\Gamma|]^M_\rho = t) \to (\forall ...
0
votes
1answer
32 views

Proof Sequences using inference

$(p \land (p \implies q) \land (q \implies r)) \implies r$ It is written slightly different in the text book, but this should be the equivalent form. The book is a bit unclear but I think the author ...
0
votes
1answer
57 views

(How) can one proposition be logically contradictory?

On this page in the book Probability Theory: the Logic of Science written by E. T. Jaynes, the author says that: If A implies B then a false proposition implies all propositions, and if we tried ...
1
vote
2answers
119 views

How can logic talk about itself? [closed]

How can there exist theorems like Goedel's Completeness theorem or Incompleteness theorem? They all make some statements about logical theories, but don't we need a certain logical scheme first to be ...
0
votes
0answers
40 views

Why does every closed normal default theory have an extension?

according to Reiter every closed normal default theory has an extension. but lets say W={} and D = {BIRD(x):FLY(x)/FLY(x)}. this default theory is closed, normal and yet doesn't have an extension. ...
0
votes
1answer
52 views

is the product of totally ordered sets is total order [closed]

I was working in products of structures and I am trying to find a counterexample to the following: "the product of totally ordered sets is a totally ordered set." Unfortunately I could not find one. ...