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

17,938 questions
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 ...
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 ...
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 ...
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 ...
54 views

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 ...
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 ...
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, ...
116 views

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 ...
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 ...
29 views

### what is the XOR output of the 16 bit input sequence 0001_1111_1100_1001? [on hold]

what is the XOR output of the 16 bit input sequence 0001_1111_1100_1001 ?
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? ...
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 ...
328 views

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", ...
29 views

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