Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
1answer
22 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
2
votes
1answer
27 views

Question regarding using the natural deduction system

I have the following: Premise: ((V → ¬W) ∧ (X → Y)) Premise: (¬W → Z) Premise: (V ∧ X) |- (Z ∧Y) The part I want to know is how do I go about separating ...
2
votes
1answer
57 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
4
votes
3answers
143 views

A function defined for all inputs?

This might seem like a weird question, but is it actually possible to define a function for all possible inputs? By this, I really mean /all/ possible inputs, including numbers, true and false, sets, ...
2
votes
2answers
60 views

Soft question about logic and Banach-Tarski Paradox

I precise for the possible down voters that I'm not student in maths I'm learning chemistry, and my friend is learning litterature, and we were speaking about BT paradox, my friend discovers this ...
1
vote
0answers
33 views

If $\nvDash\phi$ must it be $\vDash\lnot\phi$? If $\nvDash\phi$ where $\phi$ first order sentence must it be $\vDash\lnot\phi$?

I am stucked at this problem: Determine wether the following sentences are true or false in first order logic: (1) If $\nvDash\phi$ must it be the case that $\vDash\lnot\phi$? (2) If ...
1
vote
3answers
115 views

Definition of the mathematical proof

How do we define a mathematical proof? Is it a series of arguments? Is it a series of conclusions? Is it manipulation of formulas? Is it a mixture of laws of logic and axioms,theorems or ...
2
votes
0answers
69 views

What are the connections between linear algebra and logic?

I was wondering whether someone could tell me what connections there are between linear algebra and first order or second order logic, whether it be the model theoretic or proof theoretic component of ...
9
votes
2answers
145 views

Can $T$, $T+A$, and $T+\neg A$ all have different consistency strengths?

Let $T$ be a consistent theory, and let $A$ be a statement in the same language. Consider the three theories $T$ $T+A$ $T+\neg A$ Is it possible for them to be pairwise distinct in consistency ...
0
votes
1answer
23 views

Proving $S_1 \subseteq S_2$ for transitive closure

This is one of the problem I have been working from Velleman's How to prove book: Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l (a) Let $S_1$ and $S_2$ be the reflexive ...
4
votes
2answers
81 views

Every theory eliminates quantifiers in an appropriate definitional expansion?

I need to prove that every theory eliminates quantifiers in an appropriate definitional expansion. For this, consider: let $T$ be a theory in language $L$. Consider the following expansion of the ...
1
vote
1answer
26 views

If for any $M' \subseteq M$ there is an embedding of $M'$ into a $Mod(T)$, then there is an embedding of $M$ into $Mod(T)$.

I need to prove that, for $M$ a given $L$-structure and $T$ be a theory in the language $L$. Show that if for any finitely generated substructure $M'$ of $M$ there is an embedding of $M'$ into a model ...
2
votes
4answers
95 views

Logical puzzle. 3 Persons, each 2 statements, 1 lie, 1 true

I got a question at university which I cannot solve. We are currently working on RSA encryption and I'm not sure what that has to do with the question. Maybe I miss something. Anyway, here is the ...
0
votes
1answer
76 views

Disjunctive normal form and shannon normal form

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form ...
0
votes
0answers
22 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
1
vote
2answers
59 views

Deduction theorem in modal logic

I am looking for a semantic for deduction theorem in modal logic,I wanna find a semantic way to prove this theorem,but I wasn't successful.tnx for your help
1
vote
1answer
41 views

Given a closed formula $B$ of a first order theory, if it's true in every countable model, is it true in every model?

Given a closed formula $B$ of a first order theory, if it's true in every countable model, is it true in every model? I'm not sure if this is true, but it sounds too powerful.
0
votes
1answer
46 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
2
votes
0answers
37 views

Is there a standard name for using a function application, rather than a variable, as a summation index, as in $\sum_{f(x)}$?

I am trying to find out whether there is a standard notion of generalizing indexing such as $\sum_i$ to function applications as in $\sum_{f(x)}$. Intuitively, the latter means "iterating over all ...
0
votes
1answer
54 views

Complete operator base logic [closed]

Show that $F={0,\to}$ is a complete operator basis by giving equivalent formulas for negation,conjunction and disjunction over F.
0
votes
3answers
42 views

How is this true? Bookworm puzzle

This is from Eugene Northrop's book Riddles in Mathematics. Why is the answer 1 inch. Iit should be three. What logic am I missing here?
7
votes
3answers
69 views

Formal writing in math: equations

What is the formally correct way to solve a bunch of equations in math? Is it \begin{align} 42x = 4324 \\ x = 4324/42 \end{align} or \begin{align} 42x = 4324 \\ \Rightarrow x = 4324/42 \end{align} or ...
2
votes
1answer
33 views

Can the empty theory (in the language of Peano arithmetic) imply anything?

How can a theory, $T$ (a set of sentences in $L_{PA}$) which is empty imply something? Is it stated and assumed trivially that it implies a sentence such as $\phi(x): \forall x : x=x$ is implied by ...
0
votes
1answer
28 views

Eventually constant variable assignments

One proof of the Downward Löwenheim Skolem Theorem is via consideration of elementary substructures. In a discussion of this theorem, Christopher Leary writes the following: "Suppose that $ ...
0
votes
1answer
64 views

Some exercises on Models in First Order Logic [closed]

So these are some practice exercises for a Math Logic exam, I can't get a hold on how to do these. Semantically what does T = Th(N) represent? And how do I go about constructing a model A for T, ...
0
votes
1answer
69 views

Characterisation of a complete first-order theory

Let $T$ be a set of formulas of a first-order language $L$. Show that $T$ is complete if and only if there is no sentence $A$ of $L$ such that both $T \cup \{ A \}$ and $T\cup \{\neg A\}$ are ...
2
votes
1answer
39 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
3
votes
1answer
50 views

What is the set of propositional formulas?

What is the set of propositional formulas? I am not sure if I understand this
1
vote
2answers
35 views

Non isolated types of $\mathcal M$ cannot be isolated in $\mathcal N \succ \mathcal M$?

Suppose $a \in M$ realizes a non-isolated type over $\emptyset$, and let $\mathcal N \succ \mathcal M$, furthermore let $|\mathcal M| = \aleph_o$ while $|\mathcal N| = \aleph_1$. Is it true that the ...
0
votes
0answers
25 views

Elementary substructures and eventually constant variable assignments [duplicate]

One proof of the Downward Löwenheim Skolem Theorem is via consideration of elementary substructures. In a discussion of this theorem, Christopher Leary writes the following: "Suppose that $ ...
2
votes
1answer
40 views

Löwenheim-Skolem in an extension of first order logic

I'm trying to show that the Löwenheim-Skolem Theorem holds in $\mathscr{L}_{Q_{0}}$, which we have defined as an extension of FoL with the following added properties: If $\varphi$ is a formula, then ...
1
vote
1answer
45 views

Propositional logic laws

$$ (P\leftrightarrow Q) = (P\lor Q)\to(P\land Q)$$ How can I prove this equation using propositional logic laws? it would be great if someone can explain this with all steps.
-1
votes
2answers
75 views

What are the prerequisites required if I have to do induction to prove a certain theorem

I have always been fascinated by mathematical induction. The idea of induction is itself such a great analogy. But sometimes induction makes me feel that it is very messy. My professor keeps on saying ...
0
votes
1answer
43 views

Discrete Math Validating Argument Using Deduction Method

I am lost trying prove that the expression below is a valid argument using the deduction method (that is using equivalences and rules of inference in a proof sequence). ...
1
vote
4answers
64 views

Filling in a missing portion of a truth table

I have the following truth table: $$ \boxed{ \begin{array}{c|c|c|c} a & b & c & x \\ \hline F & F & F & F \\ F & F & T & F \\ F & T & F ...
0
votes
0answers
16 views

Is this an instance of the base-rate fallacy?

The following line of probability reasoning is supposedly fallacious, and is an instance of the base-rate fallacy. The argument is that $(1)-(3)$ don't give us enough reason to conclude that $(C)$. ...
0
votes
0answers
15 views

On Consequence Set Of Formulas

I am not sure the exact answer. I want to learn your ideas... Question: Let $\Sigma=\{a_1, a_2, a_3\}$ be independent set of formulas.Then; $Cn(\Sigma) \setminus \bigcup_{i=1}^3 Cn(\{a_i\})=?$ PS: ...
0
votes
1answer
26 views

Unique readability showing an $\mathcal{L}$-formula

Question: Show the string $$\forall v_1\forall v_2(Pv_1\rightarrow Pv_2\rightarrow\equiv fv_1v_2c)$$ is not an $\mathcal{L}$-formula Answer: Assume for contradiction that $\forall v_1\forall ...
2
votes
3answers
49 views

Does $P(A) = 1$ imply that $P(A) = P(A \mid B) = P(A \mid \neg B) = 1$?

Suppose for proposition $A$ we have that $$P(A) = 1$$ Then does it follow that for all $B$ $$P(A) = P(A \mid B) = P(A \mid \neg B) = 1?$$
1
vote
1answer
49 views

Gödel's First Incompleteness Theorem

By Gödel's First Incompleteness Theorem (in Enderton's "A Mathematical Introduction to Logic", p. 236) if A ⊆ Th R and #A is recursive, then Cn A is not a complete theory. Proof: Since A ⊆ Th R, we ...
1
vote
1answer
38 views

Hilbert-calculus, formal proof

I have to give a formal proof in the Hilbert calculus for $(\forall x\,\,\phi)\rightarrow (\forall y\,\, \phi\frac{y}{x})$, if $x$ is free for $y$ in $\phi$ and $y$ is not free in $\phi$. ...
0
votes
0answers
14 views

Logic problems : references

I'm looking for problems from mathematical contests about logic (similar to the problem PMWC Problem T5).
0
votes
3answers
125 views

Which axiom of set theory does this formula represent ? Why? [closed]

Which axiom of set theory does the statement below represent? Why? \begin{align}\exists x\bigg(&\forall y\Big(\neg\exists z\left(z\in y\right)\to y\in x\Big)\\&\land\forall w\Big(w\in ...
0
votes
0answers
19 views

Extending monadic predicate calculus

If we used currying to extend monadic predicate calculus to polyadic predicates, would validity of a formula in this predicate calculus be decidable? Why or why not? EDIT: I am led to believe that ...
1
vote
0answers
56 views

Why does a definition of multiplication in Presburger Arithmetic result in an undecidable theory?

Presburger Arithmetic is a decidable theory but if multiplication is added to it would that theory remain decidable? UPDATE: I began to write out the axioms that would distinguish Presburger ...
4
votes
0answers
44 views

What is a formal definition of 'randomness'?

What is a rigorous mathematical/logical definition of 'randomness'? Under what conditions can we truthfully apply the predicate 'is random'?
1
vote
1answer
13 views

First, second and monadic second order logic

I have some confusion in understanding notions First, second and monadic second order logic. It will be great if some one can explain these concepts with examples (for beginners). Thank you.
1
vote
1answer
20 views

Number of Distinct Axiomatic Systems

This may well be a vaguely formulated question. Please bear with me and help me modify it to make it meaningful and rigorous, or show that it is hopelessly meaningless. I understand an axiomatic ...
0
votes
2answers
27 views

How to work with a premise containing multiple ' if 's?

Premise 1: If $A_1$ if $A_2$ ... if $A_a$, then $C_1$. Premise 2: If $B_1$ if $B_2$ ... if $B_b$, then $C_2$. $\ ----$ Conclusion: Then $C_3$ (whatever this is). Please explain in simple ...
0
votes
0answers
43 views

How does $\;$ 'B unless J' $\;$ mean: $\;$ If J, then not B $\;$?

[Source:] Edit: As a further example of the perils, here's an alternative use for "unless". See how time (as tense) can make a difference: (14) The box is empty unless John filled it. [John ...