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)

3
votes
1answer
57 views

Logic and one interview question, is there any solution?!

I took an interview last day. I remember one question: If we know "mouse is a toy", "toys are funny", "some toys is harmful". Then which of the following propositions not necessarily true? (Some ...
17
votes
3answers
1k views

Why does what I've written fail to define truth?

I stumbled across a set of axioms for first order logic a bit ago. Intrigued, I decided to try to write it all down and organise what I read. After I did that, it seemed to me as though one could ...
0
votes
1answer
36 views

Proving general proposition using HPC

If I have a general Proposition $c$ in HPC + another axiom that $(a \rightarrow b)$. HPC axioms - $$1 .a \rightarrow (b \rightarrow a)$$. $$2. (a \rightarrow (b \rightarrow c))\rightarrow ...
0
votes
2answers
50 views

Well-formed formula, systematically rule out

Does the following formula is or is not a well-formed formula of the language of set theory? $a\in (A\subset B)$ and in either case How to systemtically tackle the above question?
0
votes
1answer
29 views

Translating “some student asked every faculty member a question” into a logical expression.

$ S(x) $ is the predicate "$x$ is a student" $F(x)$ is the predicate "$x$ is a faculty member" $A(x,y)$ is the predicate $x$ asked $y$ a question I need to translate this sentence into logic: Some ...
0
votes
1answer
40 views

Binary resolution: how to prove that it is not complete in FOL

My question is very simple: how can I prove that binary resolution is not complete in First-Order Logic? I have found a first attempt of explaination by means of counterexample in which I have: ...
2
votes
2answers
46 views

How does ~ distribute over parentheses?

In my recent Discrete Math final exam, we had a question where I thought the answer was false but apparently it is true. It is the following: $$((\forall x)P(x)) \rightarrow ((\forall y) Q(y))) ...
1
vote
1answer
23 views

Proof of the negation of an existential Quantifier

This was an exercise in my book and I was wondering if I got it correct. ...
3
votes
1answer
118 views

Is there some kind of deep relationship between substitution and recursion?

Define $\mathbb{N}$ as the initial object in the following category: Objects. Sets $X$ equipped with a function $S : X \rightarrow X$ and an element $0:X$. Morphisms. Functions that preserves ...
0
votes
0answers
28 views

How to Prove? - If the interpretation of theory is consistent, then the interpreted theory is consistent

Let L1 and L2 be finite or recursive languages, and T a theory in the language of L2. A translation of L1 into T is an assignment to each sentence S of L1 into a sentence i(S) of L2 such that: (T0) ...
2
votes
1answer
33 views

Finding Model Containing Commutative Diagram as Elementary Submodels

I'm looking at a justification for why we work inside a big model, but I'm having trouble proving a particular comment. Assume we're working with a complete theory $T$ and we have a commutative ...
5
votes
0answers
59 views

Examples of provably${}^n$ unprovable statements

Given any statement $A$ and a classical theory $T$ which we assume is at least as strong as Peano Arithmetic ($\sf PA$), we have that $T\vdash A$ implies $T\vdash T\vdash A$ (that is, if a statement ...
-3
votes
1answer
15 views

Logical equivalent or not justify the answer with example [closed]

(∀x (p(x) → q(x)) and (∀x p(x) → ∀x q(x)) 2.∃x p(x)∧∃x q(x) and ∃x (p(x)∧q(x)) 3.(∀x (p(x) ↔ q(x)) and (∀x p(x) ↔ ∀x q(x)) are logically equivalent or not justify the answer
3
votes
1answer
106 views

Justification of ZFC without using Con(ZFC)?

I saw this post by Carl Mummert, which describes how one can 'see' the reasonableness of ZFC, via iterating the power-set operation starting from the empty set. However, this iterations proceed in ...
1
vote
2answers
40 views

Modus Ponens: why it should not work

The scenario I'm analyzing is the following: I have the set of clauses $${ ( \neg A \Rightarrow B ),\, ( B \Rightarrow A ),\, ( A \Rightarrow ( C \wedge D ) ) }$$ and I have to prove the ...
0
votes
1answer
35 views

If a theory is 1-consistent then it is consistent

I am attempting to back two claims in this problem: I use $\textbf{Q}$ to denote minimal arithmetic for this post. I use the term 'rudimentary sentence' to denote formulas built using only negation, ...
1
vote
1answer
24 views

Minimal arithmetic proving a statement similar to a Gödel sentence

I will use $\textbf{Q}$ to denote minimal arithmetic for this post. (I suppose Robinson arithmetic would also suffice (?)) Suppose we have $F(x)$ be a formula defining, in $\textbf{Q}$ the primitive ...
0
votes
2answers
32 views

How do I get the goal $(A \land B) \lor (A \land C)$ from the premises $A \land (B \lor C)$? (Using Fitch)

I have $$\begin{array} {r|c:l} 1. & A \land (B \lor C) \\ 2. & A \land B \\ 3. & A & \land \textsf{ Elim } 2 \\ 4. & B ...
1
vote
1answer
51 views

Naive set theory really need axiom of power?

given the axioms of extension, pairing, specification, unions, unordered pair, as stated in naive set theory, this do not ensure the existence for each set of a collection of sets containing among its ...
0
votes
2answers
17 views

About free and bound variables

I am currently learning about first order logic, and as an exercise was asked to provide free and bound variables in the following formula: $$(\exists x P(y,y) \implies \exists y P(y,z))$$ I'm ...
1
vote
1answer
19 views

Is the set of numbers of computable functions f(x) = c recursively enumerable?

Consider the set of numbers of computable functions such that is $f(x)$ defined, $f(x) = c$ for any $x$. Is this set enumerable or co-enumerable? (Or neither). A bit of my thoughts on it. We can take ...
6
votes
1answer
53 views

If finitely many algebraic identities do not imply some identity, is there always a finite counterexample?

This question just popped up while experimenting with Prover9 and Mace4. Say we have a finite signature and some finite set of identities $E_i$ in the sense of universal algebra, like the axioms for ...
0
votes
2answers
16 views

Simplifying propositional logic formulae

Prove $\neg ((P\land Q)\lor \neg (P\land T)\lor (Q\land T)) \equiv P \land \lnot Q \land T$ Using only De Morgans Laws and the Distribution Laws. I managed to get the left hand side to reduce to the ...
0
votes
1answer
37 views

Pigeonhole Principle Painting a Plane

I need help with this question, because I do not understand some points. PidgeonHole Question: Paint every point of the plane with either blue or red color. Show that there are 2 points on the plane ...
2
votes
1answer
100 views

Is it possible that Gödel's completeness theorem could fail constructively?

Gödel's completeness theorem says that for any first order theory $F$, the statements derivable from $F$ are precisely those that hold in all models of $F$. Thus, it is not possible to have a theorem ...
1
vote
4answers
26 views

Help Proving this Propositional logic

Can someone help me with my proof? Let p, q, r and s be propositions. Consider the hypothesis $(p\space\lor\space q \to r)$, $\lnot s$, $r \to s$ and conclude $\lnot p$. My Proof $ r \to s\\ \lnot ...
-1
votes
1answer
10 views

How to use parentheses with one logical conective? [closed]

is (((a and b) and c) and d) equal to a and b and c without parentheses? Why?
2
votes
1answer
38 views

Are there other methods of proof other than contrapositive, induction, contradiction, construction, and counter example?

I have only heard of a few methods of proof, namely, contrapositive, induction, contradiction, construction, and counter example. Are there other types of proofs?
25
votes
9answers
2k views

Is formal truth in mathematical logic a generalization of everyday, intuitive truth?

I'm trying to wrap my head around the relationship between truth in formal logic, as the value a formal expression can take on, as opposed to commonplace notions of truth. Personal background: When I ...
1
vote
2answers
39 views

Logic - What does ∴ mean in a truth table?

I see the symbol used, and I've never seen it logically defined. In words, It's defined as a symbol meaning 'therefore'. Because of a lack of definition, I have no idea why this is false: ...
-1
votes
1answer
40 views

Strong induction postage stamp problem [closed]

Using 5 cent, 11 cent, and 17 cent stamps, what are all possible amounts of postage that can not be formed? Prove your answer. Part of your answer needs to use strong induction.
1
vote
1answer
25 views

Equivalence between Minimality Conidition, Well-Founded Property, Descending-Chain-Condition, and Noertherin Induction

Let $(M, \preceq)$ denote a partially ordered set $M$ along with a partial order $\preceq$ on it. Proof of the equivalence between: A: Descending Chain Condition If ($\mathcal{C}$ is a decresasing ...
1
vote
0answers
38 views

Is this deduction false?

Is this deduction accurate? I have been trying to find out how we can get ~~B by showing contradiction by asssuming A.
2
votes
0answers
29 views

Describe a set with FOL formula

This is a problem from Introduction to Mathematical Logic course A structure $\mathscr{A}$ with domain $\mathbb{N}^k$ is for FOL language $\mathscr{L}$ with $k$ predicate symbols $p_1, \ldots, p_k$ ...
0
votes
0answers
35 views

Rosser Sentences and Theories

Let T be any theory extending Q. Let R be the Rosser sentence of T. Let T0 be T + {R} and T1 be T + {∼ R}. Show that T0 and T1 are both consistent. Show that T0 ∪T1 is inconsistent. Show that for each ...
0
votes
1answer
60 views

Let T be a consistent, axiomatizable theory extending Q.

Question: Let $T$ be a consistent, axiomatizable theory extending $Q$. Let $P+$ be the set of (code numbers for) sentences provable from $T$; let $P−$ be the set of (code numbers for) sentences ...
0
votes
0answers
8 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
1
vote
1answer
23 views

Propositional resolution: the correct way to proceed

I'm trying to solve the following exercise: using resolution, tell whether the following formula can be proven: F = {( L $\wedge$ V) $\rightarrow$ H, L $\rightarrow$ V , L } entails (V $\wedge$ H). ...
1
vote
0answers
60 views

What is the relationship between Realizability and the Curry-Howard isomorphism?

I have recently been studying the Curry-Howard isomorphism/correspondence. My sources have primarly been Sørensen [1] and Girard [2]. Realizability is introduced here in the form of Kleene's ...
0
votes
1answer
22 views

Predicate Logic - Software Testing

This is a section from Logic Coverage in Software Testing, I don't understand how the logic of the image below is resolved. Assuming that the value of b is true, (true <-> b) should resolve to ...
9
votes
1answer
111 views

Independent Transcendental Numbers

I've been thinking about numbers which have not yet been proven nor disproven to be transcendental, such as $e + \pi,\, \pi - e,\, \frac{\pi}{e},\, \gamma,\,\zeta(3),$ etc. Some of these numbers ...
0
votes
0answers
49 views

What questions or areas in the foundations of mathematics remain active research fields?

By foundations of mathematics I am referring to the mathematical, logical, and philosophical foundations of the subject. I'm interested in seeing which of these have active research going on within ...
1
vote
1answer
37 views

how to construct a boolean algebra out of a set of well formed formulas?

Given a set of well formed formulas of a first order language (with equality, constants, variables, non-logical symbols, etc), is it possible to use it as some kind of base to construct a (possible ...
1
vote
1answer
45 views

What is the name of a “basis” in Boolean algebras

So, a basis in linear algebra is the smallest set which generates a particular vector space. (More formally, a subset of the vector space which is linearly independent and spans the vector space) Is ...
0
votes
1answer
42 views

Which rules of inference does Suppes use?

I'm reading Axiomatic Set Theory by Suppes, and I'm having a bit of trouble understanding which rules of inference (logical system) he is using, here's an example (capital letters are used for sets): ...
3
votes
0answers
67 views

Are all statements about math inherently formal? Can one do math without formal logic? [duplicate]

Are all people who do mathematics applying (whether they know it or not) formal logic? Does every statement someone may make about math, at its core, a formal statement in mathematical logic? ...
5
votes
0answers
28 views

Difference between a variable and an indeterminate

What are the differences and common points between a variable and an indeterminate ? Is an indeterminate also a variable ? Thank you EDIT : I am not trying to solve anything in particular, it was ...
0
votes
1answer
26 views

Alternate form of Modus tollens applicable?

The definition states that not(q) p--> q ---------- not(p) Is the following form is also true? ...
3
votes
1answer
57 views

Can multiplication and division be treated as logical operations?

A few of my friends and I were playing around with math (more specifically, why (-1)(-1)=1) and we figured out that multiplication (with regards to signs) was an "nxor" operation (I.E. If we treat "1" ...
0
votes
1answer
33 views

Every function that is representable in Robinson arithmetic, $\mathsf{Q}$, is computable

I am reading through the proof of this theorem, in particular the one presented in the Open Logic project, where it appears as Lemma 20.3 currently. The definitions in this text are as follows: A ...