Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logic]

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 following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

1
vote
1answer
22 views

Arithmetical formalization of “F is sound”

In How subtle is Gödel's theorem? More on Roger Penrose, Martin Davis points out the fact that the statement F is sound $\implies$ G(F) is true where F is some recursively axiomizable extension ...
0
votes
5answers
39 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...
0
votes
0answers
5 views

What is the general formal definition of ordinal definable sets?

The following Wikipedia article about OD sets, mentions the informal definition of ordinal definable sets, yet it says that it cannot be captured formally in first order logic. I just want to make ...
2
votes
1answer
38 views

Are the integers definable in $\mathbb{Z}_{(p)}$?

I am familiar with the statement (not the proof) of Robinson's definition of $\mathbb{Z}$ in $\mathbb{Q}$ in the language of rings. I would like to ask the same question for $\mathbb{Z}_{(p)}$ in ...
0
votes
2answers
54 views

How to prove $\vdash p\to\neg\neg p$ in this system?

I was asked to prove $\vdash p\to\neg\neg p$ in this system. Axioms: $(\mathcal A_1)\vdash p\to(q\to p)$ $(\mathcal A_2)\vdash (p\to(q\to r))\to((p\to q)\to (p\to r))$ $(\mathcal A_3)\vdash \...
3
votes
1answer
40 views

Negation Inference with Gentzen Natural Deduction and Sequents?

I'm trying to understand the negation rules of this system. Wiki's page on Sequent Calculus claims that from: ${\displaystyle \lnot p,p,q\vdash r}$ the following is inferred: ${\displaystyle p,q\...
0
votes
1answer
17 views

Usage of adjective and imperative in statement logic

I think I know how to form sentences in statement logic if it's an "if statement" like (A) and (B) below, but how do I express adjective like "not so easy" or imperative like "Choose X or Y", as shown ...
0
votes
1answer
20 views

How resolution methods' rules apply in proofs

I understand that resolution methods are used to prove something by disproving its negation (proof by contradiction), but I don't understand how this idea is implemented in formulas. The following ...
2
votes
1answer
49 views

The technique that uses the Chinese Remainder theorem, to express 1st order arithmetical statements encoding statements about infinite sets of numbers

I know this technique is heavily used in Number Theory, in Combinatorics (e.g. for phrasing Ramsey's theorems in a first order language of arithmetic), and in some related realms. However, ...
2
votes
2answers
116 views

How early do the second-order definable subsets of $\mathbb{N}$ occur in the Constructible Universe?

$ZFC+V=L$ implies that $P(\mathbb{N})$ is a subset of $L_{\omega_1}$. But I’m wondering what layer of the constructible Universe contains a smaller set. My question is, what is the smallest ordinal $...
2
votes
0answers
64 views

Is Isles' theorem 2.6 correct?

In "Regular Ordinals and Normal Forms", Theorem 2.6, David Isles claims that Bachmann proves that the sequence of normal functions generated by a Bachmann collection has property (6). Firstly, ...
0
votes
0answers
20 views

Boolean function: prime implicants - disjunctive minimal form

I applied the Quine-McCluskey method to determine the respective prime implicants for a boolean functions and find a disjunctive minimal form. We have the function \begin{equation*}f(x_1, x_2, x_3, ...
2
votes
2answers
71 views

When are we allowed to use the $\exists$ elimination rule in first-order natural deduction?

I don't really understand when we're allowed to use $\exists$-elimination when making first-order natural deduction proofs. I understand that the criteria are that the variable must be free in the ...
4
votes
1answer
97 views

Why are there several axiom systems for propositional logic?

There is an axiom system that I found in Elliot Mendelson's, "Introduction to Mathematical Logic", p.27, and Theodore Sider's, "Logic for Philosophy", p.59: (A1) P->(Q->P) (A2) (P->(Q->P))->(P->Q)->(...
0
votes
1answer
52 views

About a famous assertion by B. Russell on mathematical truths considered as conditional truths. Is this claim also true of axioms?

In Mysticism and Logic, Russell says that : "Pure mathematics consists entirely of assertions to the effect that, if such and such a proposition is true of anything, then such and such another ...
0
votes
0answers
26 views

What is your opinion on David Ellerman's Partition Logic and his distinction based view of Entropy? [on hold]

I have been skimming through David Ellerman's work on Partition Logic and Information theory. What exactly is the difference between dits and bits in his treatment of information theory? What exactly ...
1
vote
1answer
217 views

“ Logic does not allow you to say this”: is this assertion outdated?

I think one cannot say nowadays without further qualification " geometry does not allow you to say that the sum of a triangle's angles is less than 180 degrees". The sentence concerning the sum of ...
1
vote
4answers
675 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between $0$ and $1$. I want a constraint such that: if $x_2+x_3+x_4>0$ then $...
6
votes
2answers
209 views

Difference between consistency and satisfiability

If a set of formula is consistent, there exist a model in which every formula is true. This is only if the set is satisfiable. But satisfiability is the fact that it can be true so what is the ...
2
votes
1answer
1k views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
2
votes
1answer
50 views

Mekler’s construction!

I was looking at this slides by Artem Chernikov. But I did not understad what Mekler’s construction is exactly. Can one explain the idea of Mekler’s construction (in model theory) in a simple words? ...
10
votes
6answers
2k views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
2
votes
2answers
328 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with $...
2
votes
1answer
32 views

David Marker Model Theory Cor 5.2.10

This Corollary states that a complete theory $T$ in a countable language with infinite models is $\omega$-stable when it is $\lambda$-categorical for some $\lambda\geq\aleph_1$. I am confused why ...
0
votes
1answer
23 views

Questions regarding the proof of quantifier elimination of DLO

So this is the proof in David Marker's Model theory book, Theorem 3.1.3. I am a bit confused over the first line of the proof. It reads : "First suppose $\phi$ is a sentence. If $\mathbb{Q}\models\...
1
vote
1answer
301 views

Use of undecidability

Suppose someone proved that the Goldbach conjecture was undecidable in an axiomatic system that is consistent as far as we know. Then in some sense we know that Goldbach conjecture must be "true", ...
0
votes
2answers
29 views

Set representing The positive integers which are a multiple of 6?

I know this is a very trivial question, but I'm probably missing something So the set is: $\{n\mid n=2m\, \mathrm{for \,some} \,m \in \Bbb N,\mathrm{and}\,n=3k\, \,\mathrm{for \,some}\, k \in \Bbb N\...
1
vote
1answer
43 views

A (First-Order) theory T such that every embedding between T-models is elementary

I was wondering, is there a characterization for such a theory? It seems like a pretty handy property so there must be something. Would really appreciate any insight.
0
votes
1answer
52 views

Developing new theories by transfinitely iterating the Godel sentence construction

In Turing's Ph. D thesis "Systems of Logic Based on Ordinals", he writes of a simple way to use Gödel's incompleteness theorem to devise a transfinite sequence of new theories. The sequence proceeds ...
3
votes
2answers
871 views

Rule of inference and truth table issue

Let P – Light is on Q – The switch is down R – The door is open ...
1
vote
0answers
33 views

Using natural deduction to prove that $\forall x \lnot (P(x) \lor R(x)) \implies \exists x(\lnot P(x) \lor \lnot R(x))$

Not only do I not understand how to do this, but I don't comprehend the solution: Here, supposons means assume, and donc means thus. I'm specifically confused with line 5, for which I don't ...
0
votes
1answer
28 views

Interpretation in Ebbinghaus's Mathematical Logic

In Ebbinghaus, Flum, Thomas' Mathematical Logic, second edition, page 30: For example, if $S = S^{<}_{\text{ar}}$, and the interpretation $\mathfrak{I} = (\mathfrak{A}, \beta)$ is given by $$ ...
2
votes
0answers
21 views

What is a language “expressible” in second/first-order logic?

This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated. Indeed, ...
3
votes
3answers
5k views

How do I express logical connectives with Nand?

Really struggling to understand how to express all the connectives as Nand. I understand that p ^ q would be the opposite of p nand q, but I get stuck when trying to express p -> q and p v q in ...
1
vote
1answer
20 views

How To Analyze Statements of Quantifiers

Having trouble figuring out how to interpret Universal Quantifiers, from my book there's two sets of statements. Assuming x,y and z are real numbers, determine the truth value of each statement (a): $...
0
votes
1answer
79 views

Which properties are false for an empty set? [on hold]

An empty set is closed, open, bounded, convex... All of that is vacuously true. I wonder which properties are false for empty set?
0
votes
1answer
38 views

How to denote that an expression is expressed in a given language

I want to say something like "Given an expression E in language L..." Is there a 'standard' symbol for 'expressed in'? I think that 'Given expression E ∈ L' is not accurate, as a language is not ...
1
vote
1answer
37 views

Function that maps strings from one formal language into string of another formal language?

Is there branch of mathematics and mathematical theories, that considers mappings from strings of one language into strings of another formal language? Example. Let's consider two languages that can ...
2
votes
1answer
32 views

Discrete math: Inverse, converse, contrapositive - simplifying expressions

State the inverse, converse, and contrapositive of the following implication expression as English sentences. Ensure that you list the symbols you will use for each ATOMIC predicate. You must also ...
2
votes
2answers
62 views

Is there a dual to term “vacuously true” for a universal set?

For an empty set, any statement that claims "for all ... is true/false" are considered "vacuously true". So, can we construct a universal set in which any statement that claims "there exists ... is ...
0
votes
3answers
54 views

Does this means that “anything” implies $T$?

I'm reading Yves Nievergelt's Logic, Mathematics and Computer Science. Here: I am very confused about this. I understand the proof, but does that mean that anything implies $T$? Supposing my ...
-3
votes
4answers
80 views

Should math logic reflect “real” logic

In math we use logic. However, it seems mathematicians were free to define some of its rules. Say the OR. It is true, if either of arguments is true - or both. Now we use math to prove some facts ...
1
vote
1answer
35 views

Ways to show two structures are elementary equivalent

Let $\mathcal{L}$ be a finite first-order language. When we say structure we mean $\mathcal{L}$-structure. Question. Can someone lists different ways which we may use to show two given structures ...
1
vote
0answers
11 views

Using Ehrenfeucht-Fraisse games to prove elementary equivalent [duplicate]

The following theorem is Theorem 2.4.6 of Marker’s model theory book. Theorem. Let $\mathscr{L}$ be a finite a finite language without function symbols and let $\mathcal{M}$ and $\mathcal{N}$ be $\...
0
votes
2answers
2k views

Assumptions, Axioms and Premises

The following attempt of mine at defining these terms, reflects my current understanding of them: Assumption: $\quad$ A statement accepted as true without proof being required. ...
0
votes
1answer
24 views

Proof of the Tarski-Vaught test

The Tarski-Vaught test is a way to determine if a substructure is elementary. To my understanding, here is the theorem: Tarski-Vaught Test Let $N$ be a substructure of $M$. Then the following two ...
0
votes
0answers
21 views

Reference for elementary substructures of the standard model of analysis

Is there was any resource discussing or categorizing elementary substructures of the intended model of analysis? Analysis in this context is also known as second-order arithmetic. They will of course ...
0
votes
1answer
53 views

Is Peano's axiom of induction needed to show $n^\prime\ne n^{\prime\prime}$?

This is the statement of Peano's axioms I will assume for this discussion: $1$ is a number. To every number $n$ there corresponds exactly one number $n^\prime.$ $n^\prime=m^\prime\implies n=m.$ $n^\...
0
votes
0answers
33 views

Stuck in this Proof of the Completeness Theorem for Predicate Logic

I'm studying a proof of the completeness theorem for predicate logic shown in this lecture and I'm caught in an obstacle. It proceeds by showing that if a theory is consistent, then it has a model, ...