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
1answer
10 views

Venn diagram - How to choose the right conclusion with the given statements?

In the following question, three statements aling with a set of four conclusions are given. Select the correct answer from the options given. Statements ...
0
votes
0answers
10 views

Set Theory Logic Complement

Hi just doing some homework on set theory and I'm unsure of what this answer would be. I just need some reassurance that I have understood it correctly. U = { 1, 2, 3, 4, 5, 6, 7 } A = {2, 5, 6, 7 } ...
-1
votes
2answers
22 views

Pigeonhole Principle - Consecutive Days

If an athlete trains for 20 days in a 31-day month, how can I prove that he/she will need to train on consecutive days at least once using the Pigeonhole Principle?
3
votes
3answers
151 views

How does Russell's paradox relate to the existence ( in fact non-existence) of the set of all sets?

I think I understand the way in which Russell's paradox shows that the following principle is wrong: " for every predicate, there is a set having as elements all the objects that satisfy this ...
0
votes
0answers
23 views

Logic of predicates over predicates?

Is there logic, that allow to form predicates over predicates (or even formulas), I.e. derive is-interesting-statment(is(I, liar)). Of course, the model operators in the modal logic can take ...
1
vote
2answers
25 views

Natural deduction proof: $C, (C \land D)↔F \vdash (D \land E) \to F$

I'm having trouble with proving C, (C Λ D) ↔ F |- (D Λ E) → F If it were $\lor$ instead of $\land$, then I would be able to do it. If I can prove that $(C ...
0
votes
1answer
20 views

Usage of (x, 1) (1) in natural deduction

When neither one of premises and conclusion includes a number like "1", like the following, I could at least proceed to some extent (although I don't know how to connect Q(y) of the first premise and ...
0
votes
2answers
36 views

If the language has only one predicate, can we simplify the quantifiers?

Assume that our language has only one predicate symbol. Then $(\forall x_1 \forall x_2 )(\phi)$ is equivalent to $(\forall x)(\phi')$ where $\phi'$ is a formula obtained by replacing all occurrences ...
0
votes
0answers
24 views

Rewriting statements in full detail with logical operators, but without quantifiers

I've been given the following question: Let P and Q be predicates on the set S, where S has two elements, say S={a, b}. Then the statement $\forall xP(x)$ can also be written in full detail as $P(a) \...
0
votes
1answer
28 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
2answers
56 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 ...
2
votes
1answer
57 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
1answer
31 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
26 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 ...
0
votes
5answers
41 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
23 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
1answer
61 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
66 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 ...
1
vote
1answer
226 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 ...
0
votes
1answer
62 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
30 views
4
votes
1answer
110 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
72 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
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? ...
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
213 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
33 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
24 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
30 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
53 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
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, ...
1
vote
0answers
34 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
22 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
21 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
45 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
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 $$ ...
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
63 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
80 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
55 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
0answers
22 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
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^\...
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
41 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 ...