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

0
votes
4answers
30 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
13 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, ...
1
vote
1answer
30 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, ...
0
votes
1answer
48 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
1answer
211 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
1answer
41 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 \...
-4
votes
0answers
27 views
4
votes
1answer
93 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)->(...
2
votes
2answers
70 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 ...
2
votes
1answer
49 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? ...
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 ...
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
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\...
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\...
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 ...
2
votes
0answers
61 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, ...
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 ...
2
votes
0answers
19 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, ...
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): $...
1
vote
1answer
40 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
27 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 $$ ...
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 ...
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 ...
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 ...
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
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
78 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
34 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
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
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
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, ...
0
votes
1answer
52 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^\...
2
votes
1answer
66 views

Gödel's theorem vs unprovable mathematical results

As an answer to this question, Peter Smith wrote: Indeed, it is a fairly gross misunderstanding of what Gödel's theorem says to summarize it as asserting that "there exist mathematical results ...
1
vote
1answer
40 views

Contraposition fallacy in raven paradox?

I do not understand how the contraposition "all non-black objects are not ravens" is logically identical to "all ravens are black." I see that IF all ravens are black, THEN all non-black objects are ...
0
votes
2answers
82 views

Bourbaki: Universal Quantification Interpretation

I'm trying to understand Bourbaki's definition of universal quantification. The definition is on Page 36 in Theory of Sets as follows: $(\exists x R) \equiv (\tau_{x} \mid x) R$ $(\forall x R) \...
0
votes
0answers
21 views

Proving Busy Beaver function is not recursive using Rogers's fixed point theorem

I'm trying to prove that $\operatorname{bb}(x)= \max \{U (e, 0) \mid e \leq x \text{ and } (e, 0) \in \operatorname{Dom} (U)\}$ is not recursive. ($U$ is the universal recursive function, i.e. $U$ is ...
0
votes
0answers
13 views

K-colorable map in FOL

The following claim is true in FOL: Let A be a Π1 formula over some alphabet Σ, and let M be a Σ-structure. If N |= A for all finite Σ-substructures N ⊑ M, then M |= A. A map is k-colorable, for a ...
-1
votes
1answer
33 views

Semantics of exclusive or

How do I get a description of $\text {XOR}$ (exclusive or) only using the operators $\wedge$, $\vee$, $\neg$, $\rightarrow$ And is it possible to prove the correctness of such description?
3
votes
1answer
43 views

$\forall x (P(x) \wedge \neg Q(x)) \equiv \forall x P(x) \wedge \neg \exists x Q(x)$

I'm supposed to determine whether or not these equivalences are valid for all predicates P and Q. I've written my assumptions but I've never done anything like this so it almost seems too simple and I ...
0
votes
1answer
27 views

What’s the relation between deontic logic and epistemic logic?

I’m reading about both epistemic logic and deontic logic and I am trying to understand what is the relationship between them. Is epistemic logic considered a type of modal logic?
1
vote
2answers
110 views
+100

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 $...
5
votes
1answer
47 views

$(p \implies q) \wedge (p \implies r) = p \implies (q \wedge r)$ PROOF

$\def\implies{\to}$I am trying to prove the following: $$(p \implies q)\wedge (p\implies r) \equiv (p\implies q \wedge r) $$ I did this, although I am second-guessing because of the parenthesis ...
1
vote
0answers
45 views

First Order Logic Soundness Equivalent in Enderton An Introduction to Mathematical Logic 2001, p134.

Enderton 2001, An Introduction to Mathematical Logic, states on page 134 : Corollary 25E : If $\Gamma$ is satisfiable then $\Gamma$ is consistent and then comments "This corollary is actually ...
1
vote
1answer
75 views

Why is the definition of inductive set well defined?

I've been studying from Enderton's Mathematical Introduction to Logic in which he defines an inductive set as follows: To simplify our discussion, we will consider an initial set $B \subseteq U$ ...
1
vote
0answers
85 views

Why not consider the model of $ZFC_2 + 0-inaccessibility$ as the standard model of ZFC?

Let's take $ZFC_2 + 0$-inaccessibility; That is, ZFC written in full second order logic and add to it absence of existence of any inaccessible set. So this defines a unique model of all hereditarily ...
0
votes
1answer
36 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 ...
0
votes
2answers
45 views

Syntax of one language as the semantics of another language?

Can formal language serve as the semantic model of another language/logic? Grammatical Framework system is example where such direction is taken: abstract grammar can serve as the model of concrete ...
0
votes
1answer
32 views

How can we know whether an arbitrary sentence corresponds to a sentence in the language of arithmetic or not?

From what I came to understand from Godel's work is that a consistent effectively generated theory $T$ can have its consistency statement $Con(T)$ written in the language of $T$ itself! and that this ...