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

learn more… | top users | synonyms (1)

0
votes
2answers
32 views

How do you prove this logical equivalence?

$\\ (\exists! x:P(x)) \leftrightarrow ((\forall x:P(x) \rightarrow Q(x))\leftrightarrow(\exists x:P(x) \land Q(x)))$ If there's only one $x$ for which $P(x)$, then saying "all $x$ for which $P(x)$, ...
1
vote
0answers
34 views

Hilbert style proof for $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) \right) $

How can I proof that the following formula is a tautology by using Hilbert calculus? $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) ...
1
vote
2answers
55 views

Is $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ a tautology?

Is this proposition a tautology? $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with ...
0
votes
0answers
14 views

$\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?

Let P be some statement. Is my negation correct? $\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?
2
votes
1answer
33 views

Show that for propositional logic $\vdash_i \neg \varphi \Leftrightarrow \vdash_c \neg \varphi$.

As the title says, where $\vdash_i$ is derivations in Intuitionistic logic and $\vdash_c$ is derivations in Classical logic. I am allowed to use a corollary that states that $\vdash_i \varphi ...
0
votes
1answer
16 views

Proof for association law?

I am new in logic and I getting a little bit confused with maths. Can I do something like this following the Associative Law? $$(p ∨ ¬r) ∨ (r ∨ ¬p) ≡ (p ∨ ¬p) ∨ (r ∨ ¬r)$$ Thank you in advance for ...
0
votes
1answer
33 views

Using a truth table to prove or disprove $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ and $¬(P\wedge (Q\vee R))=¬P\vee (¬Q\vee ¬R)$

This question was taken from the MIT OCW Math for Computer Science course. Use a truth table to prove or disprove the following statements: a) $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ b) ...
1
vote
0answers
18 views

How to define the functions and relations for a logical model?

In model theory one has to define functions and relations on a set for the function and relation symbols of the logical theory. My questions are: What kind of operations are allowed to define ...
0
votes
2answers
19 views

help on simplifying boolean algebra

I need t show the the terms on the left simplify to the ones on the right $$(X+Y).(X'+Z)= X.Z+X'.Y$$ My attempt: I went with $$XX'+XZ+YX'+YZ= 0 +XZ+YX'+YZ$$ But I'm stumped beyond ...
0
votes
1answer
15 views

Hilbert style proof of double negation introduction and reductio ab adsurdum

I'm trying to prove: $\phi\to\neg\neg\phi$ $(\neg\phi\to\neg\psi)\to((\neg\phi\to\psi)\to\phi)$ Using these axioms with modus ponens and the deduction theorem: A1: $\phi\to(\psi\to\phi)$ A2: ...
0
votes
1answer
17 views

Number of steps

In a shopping complex Sunita walks down an escalator moving down from the first to ground floor in 30 sec taking 6 steps for every 5 sec. On reaching the ground floor she realizes she has to go back ...
0
votes
0answers
42 views

Stronger Konig's Lemma

Assume T is "the" infinite binary tree: the one generated by branching, starting at the root, indexed by $\left\{0,1\right\}$. Konig's Lemma (binary case) states that: "There is an infinite (and ...
0
votes
0answers
27 views

Is there any way to retain Russell's original proof of induction in Appendix B of PM 1925?

Recently I was reading this question again and the following question occurred to me, Can there be some new interpretation of the system of PM $1925$ so that Russell's proof of $^\ast89.16$ is not ...
-1
votes
0answers
29 views

If P = NP, mental effort of mathematician completely replaced by machines (apart from postulating axioms). (Godel) Why not? [on hold]

Reference link from a book called The Nature of Computation. What restricts an machine (that can learn everything but doesn't know everything) from asking questions ?
0
votes
1answer
33 views

Is T an infinity spectrum whenever T is a spectrum?

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
0
votes
2answers
34 views

Not very sure about this contraposition…open and closed sets

I have this lemma that states, Let $X$ be a topological space and $A \subseteq X$. Then, $A$ is open in $X$ if and only if $\forall x \in A$, there is a neighborhood of $x$ that is contained in ...
1
vote
1answer
39 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
3
votes
1answer
30 views

Prove that in every WFF, there is a logical connective between every two atoms.

First, I have defined a well-formed formula as such: 1) Each atom is a WFF. 2) If φ is a WFF, so is ¬φ 3) If φ and ψ are WFFs, if ∗ is a binary connected (i.e., ∨,∧,→), then (φ∗ψ) is a WFF. What ...
0
votes
1answer
23 views

List of primes and compactness

I'm working on the following problem: Let $p_0,p_1,...$ be a list of the prime numbers in increasing order. Show that for any set $X\subseteq\mathbb{N}$, there is a model of Th($\mathbb{N})$ which ...
0
votes
1answer
60 views

What kind of proof is this?

Let's say that we want to prove that object A is blue. Is the following reasoning true? First assume that $A$ is indeed blue. Then, use other axioms to show that depending on a control parameter ...
0
votes
2answers
77 views

What number(s) is unequal to itself [on hold]

Is there any number that does not equal itself (satisfies $x-x\neq0$)? I've seen the question ...
4
votes
2answers
64 views

Trouble with “only if”

This is from pg. 45 of Discrete Mathematics with Applications by Epp: I'm having trouble understanding the last sentence. If we say that $p$ is John breaking the world's record and $q$ is John ...
3
votes
1answer
59 views

A question about Goodstein's theorem

It is known that if Peano's Arithmetic (PA)-which is a first order theory-is consistent, then Goodstein's theorem is an example of a sentence of PA that can be neither proved nor disproved in PA. Is ...
3
votes
0answers
36 views

How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
1
vote
2answers
104 views

Do 'nice' first order logics have universal models?

A first-order logic is interpreted in a model where sentences of the logic can be said to be true or false. There may be more than one model, and we can identify morphisms between models. Do we have ...
0
votes
4answers
47 views

Negation with De Morgan’s law

I'm having a hard time getting my head around transformation proofs. There is one particular example demonstration in the material I'm studying which I can't make sense of From this ¬ (¬ (¬ p) ∨ ¬ ...
0
votes
1answer
25 views

Logic Integer Proof with Common Divisors

Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ ...
-3
votes
0answers
45 views

Help in Verifying a Set Theory Proof [on hold]

let X and Y be algebras of subsets of disjoing sets M and N, respectively. prove that $ X∪Y= \{{A∪B:A∈X, B∈Y}]$ is an algebra of subsets of the set $M∪N$ 1) $(M∪N)∈(X∪Y) $ $∵M∈X, N∈Y$ 2) ...
1
vote
1answer
38 views

What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
6
votes
2answers
432 views

Two definitions of strong homomorphism

We say that $f: A \to B$ is a homomorphism iff it preserves the operations and relations of the structure: $f(o^A(\bar{a})) = o^B(f(\bar{a}))$ where $a ∈ A^{ar(o)}$, $o$ any function symbol from the ...
2
votes
1answer
53 views

why can't this proof of Löwenheim-Skolem Theorem be shorter?

An algebraic introduction to mathematical logic page 46 has the following: the proof continues on, but it seems to me we can stop here. Every consistent theory has a model, and we've just proven ...
0
votes
1answer
60 views

Are these statements “truly” equal?

Consider a set $A$, elements $x,y$ in $A$ and the following propositions: \begin{equation} \exists x\in A\ |\quad x=x \end{equation} \begin{equation} \forall x\in A:\quad x=x \end{equation} ...
0
votes
2answers
113 views

The Adjunction $\_\times A\dashv (\_ )^A$ for Preorders: The Deduction Theorem.

The following is from Turi's Category Theory Lecture Notes. Definition 11.11 Let $A$ be an object of a category $\mathbb{C}$ with binary products. The right adjoint of $\_\times ...
1
vote
1answer
92 views

Why a formula must be closed in order to prove decidability?

Based on this from https://www.encyclopediaofmath.org/index.php/Decidable_formula A decidable formula is a formula A of a given formal system that is either provable in this system (that is, is a ...
1
vote
1answer
96 views

What are non-categorical theories about?

With theories that are categorical, it seems like you could say that the theory is about collections of objects (numbers, points, etc.) with a certain structure (the structure the standard models ...
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
1
vote
0answers
31 views

What is the root of first class object in programming languages?

What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and ...
0
votes
0answers
62 views

Profane Model Theory, sacred Proof Theory

Dirck van Dalen starts the Preface to his Logic and Structure with the following words: "Logic appears in a ‘sacred’ and in a ‘profane’ form; the sacred form is dominant in proof theory, the ...
3
votes
1answer
57 views

Well-ordering of sets of cardinal numbers

Proposition For every cardinal number $m$ there is a definite next larger cardinal number. This proposition is proved on page 136 of "Proofs from the Book" using the fact that any set of ordinal ...
0
votes
0answers
22 views

representing a periodic circular shift for a vector formally

I'm writing an algorithm in which the operation of circular shift to a given vector $x=[1 \ 0 \ 0\ ... 0]$ is needed on periodic basis i.e. every $\Delta t$ a circular shift will occur. How this ...
0
votes
2answers
25 views

Prove/disprove a propositional statement

I have a homework question that I've been struggling with. I need to prove or disprove that: $(p ∧ (q ∨ r)) \to (r ∨ (q ∨ p)) = p ∨ q$ I've already constructed the first step of the proof which is ...
0
votes
2answers
37 views

This logic problem seems to be missing info?

This is a sample question for an employment related test I have to take: Assume the first two statements are true: Tom greeted Beth. Beth greeted Dawn. Tom did not greet Dawn. If statement 3 is ...
1
vote
2answers
26 views

Definition of an ideal in a L-language

Let $\mathcal{L}_\text{ring}=\{0,1,+, \cdot, I\}$ where $0,1$ are constants, $+, \cdot$ are binary function symbols and $I$ is an unary relation symbol. Give $\mathcal{L}$-formulas which ...
0
votes
0answers
30 views

Find a $\mathcal{L}$-formula to fullfill a condition

Let $\mathcal{L} = \{f,g\}$ where $f$ is binary and $g$ unary. Consider the $\mathcal{L}$-structure $\mathfrak{M}$ with underlying set $\mathbb{R}$ and $f^{\mathfrak{M}}$ is the default ...
2
votes
1answer
36 views

how to give a truth value for the following formula

I am trying give a structure that makes that makes the formula T and a structure that makes the formula F for the following formula ...
1
vote
1answer
22 views

proof verification for truth table

Hi I wanted to know if I got this question correct. Below is the question and the truth table. I said that they were not equivalent as columns 4 and 5 are different. ...
0
votes
0answers
30 views

Is this unifiable? SDLNF Derivation of the Generic Goal.

I found a problem which is a definite program problem and ask to obtain all SDLNF derivations of the generic goal. $Product(x,y) ← Quantity(x),Rate(y)$ $Rate(x) ← Sub(x)$ $Quantity(a)$ ...
0
votes
1answer
22 views

proof verification for natural deduction

Could someone please let me know if I got the following natural deduction correct for the following formula ...
0
votes
1answer
20 views

Can I interchange variables and terms in these expressions? Find Most General Unifier

I just found a question asking to find the most general unifier for, ${P(x,g(y,z),y),P(g(h(a,u),y),x,h(a,b))}$ Where $x$ , $y$ , $z$ And $u$ Are variables and $a$ and $b$ are constants. As far as ...
0
votes
1answer
38 views

How should one without any university mathematics background study mathematical logic?

How should someone who hasn't studied any math at a university level start studying mathematical logic? (There are already questions like this but they mostly focus on book recommendation for people ...