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
1answer
24 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 ...
2
votes
1answer
36 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
2answers
80 views

What number(s) is unequal to itself [closed]

Is there any number that does not equal itself (satisfies $x-x\neq0$)? I've seen the question ...
4
votes
2answers
68 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 ...
1
vote
2answers
57 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 ...
1
vote
1answer
49 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) ...
0
votes
4answers
48 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) ∨ ¬ ...
-3
votes
0answers
47 views

Help in Verifying a Set Theory Proof [closed]

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) ...
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$ ...
1
vote
1answer
42 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 ...
0
votes
1answer
38 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) ...
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
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 & ...
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 ...
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
63 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 ...
4
votes
1answer
75 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
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 ...
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 ...
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
2answers
26 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 ...
2
votes
1answer
37 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 ...
0
votes
0answers
31 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
23 views

proof verification for natural deduction

Could someone please let me know if I got the following natural deduction correct 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
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 ...
1
vote
0answers
33 views

I'm looking for a good book on FOL and set theory.

I finally decided to really learn some axiomatic set theory, at least the basics. I've studied a bit of FOL, but a review would be nice. In short, I'm looking for a book that focuses on $\sf ZFC$ or ...
0
votes
1answer
25 views

What does it mean for an object to not be following a definition based on some implication

I want to get a deeper understanding of what being an object that doesn't follow a definition means in terms of predicates and logical operators. Suppose the following definition of the closedness ...
0
votes
0answers
30 views

Reasons for using default logic

I can see the obvious reasons for using default logic but I would like to have a full list of the reasons including the not so obvious ones . what is the motivation behind default logic? why can't we ...
3
votes
0answers
42 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 ...
0
votes
1answer
22 views

Generated subframe of a frame

Let's define that $F=(W,R) $ is a Kripke frame where $W=\mathbb{Z}$ and $R=\{(u,v)\mid v=u+1 \}$. Then we can have generated subframe $F_{0}=(W_{0},R_{0})$, where $W_{0}=\mathbb{N}$ and $R_{0}=\{ ...
0
votes
0answers
32 views

Logic and urn with balls of different colors.

I'm sorry if the community to place such a question is chosen incorrectly, but I think math is quite suitable for this case. So there are two reasoning/logic questions. [temporary deleted]
-1
votes
0answers
20 views

natural deduction proof for predicate logic [duplicate]

I have to prove the following logic equivelence ~∀xP(x)->∃x~P(x) I started by assuming ~∀xP(x),but I have no idea how to prove it. maybe you can help me,and explain! Thank you
0
votes
2answers
46 views

Induction on well formed formula

I need to prove in induction that - In a (WFF) well-formed formula between every two atoms there is a connective. Should my base case be about one atom or two ? In my proof(Induction step) should I ...
0
votes
1answer
29 views

True/False question in Propositional logic

I need to Prove of disprove this statement If $S$ $\cup$ $\{a\}\models{b} $ and $ S$ $\cup$ $\{\neg a\}$$\models{b}$ then $S$ $\models b$ Looks to me like a True statement , but found it hard ...
0
votes
2answers
50 views

$P ⇒ (Q ∨ S)$ , how can I prove $Q$?

I'm asking this in the context of a logical programming language similar to Prolog. Say I have the rule $P ⇒ (Q ∨ S)$ . How would I go about proving the truth value of $Q$, assuming I know the ...
1
vote
2answers
37 views

Difference between proving $\forall n(Q(n) \implies P(n))$ and $\forall nQ(n) \implies \forall nP(n)$

From what I can understand an almost identical proof structure is often used in a direct proof. To prove $\forall n(Q(n) \implies P(n))$ the common would be: (1.) Let $n$ be arbitrary. (2.) Assume ...
1
vote
2answers
55 views

Can an open statement be a tautology?

A tautology is a statement which is true by dint only of the logical connectives contained therein. My question is about a statement which contains an unquantified variable. For example: P: ($x$ ...
0
votes
1answer
18 views

Can you use constants from the domain in a First Order Formula? [closed]

Say I have a First Order Signature defined like so: $N = (\{1,2,3\dots\},T)$ Where T is a binary relation symbol. Can I use values from the domain to define functions over this signature? For ...
-3
votes
1answer
97 views

Does Gödel’s theorem affect anything but the arithmetic of the natural numbers? [closed]

Влияют ли теоремы Гёделя на что-нибудь кроме арифметики натуральных чисел? Существуют ли интересные независимые от ZFC утверждения ,которые рождены теоремами Гёделя о неполноте, и которые ...
0
votes
1answer
29 views

Simplify a Boolean Algebra expression with don't cares

In my homework assignment, I'm asked to simplify an expression of Q'RS'T' + Q'R'S'T + RS'T with don't-cares of m3, m12, and m14. I know how I would achieve this result with a K-map, however the ...
0
votes
1answer
24 views

Constructing a computably infinite tree with no computable infinite branches using PA

Define an infinite tree as any set of sequences closed under prefix restriction, i.e. any prefix restriction of a sequence in the set is also in the set, where a prefix restriction is a restritcion of ...
2
votes
1answer
37 views

Are these results generalizable?

It is a well-known fact that Euclidean geometry and the arithmetic of real numbers are both decidable and complete theories. Here are my questions: Do the non-Euclidean geometries share the same ...
0
votes
0answers
40 views

Is PA the most common foundation for arithmetic?

Are Peano Axioms the most common and widely accepted axiomatization of arithmetic, just as ZFC is the most common and widely accepted foundation for all of mathematics?
1
vote
2answers
17 views

Question about the exclusive or operator

Let $R_1$ be the “less than” relation on the set of real numbers and let $R_2$ be the “greater than” relation on the set of real numbers, that is, $R_1 = \{(x, y) | x < y\}$ and $R_2 = \{(x, y) | x ...
0
votes
1answer
11 views

Convert the formula to CNF and DNF

I want to convert this formula: $\neg(\neg(p \implies \neg g) \land (r \iff \neg p))$ My proccess: $\neg(\neg(\neg p \lor \neg g) \land ((r \implies \neg p) \lor (\neg p \implies r)))$ (De ...
1
vote
1answer
23 views

Application of compactness theorem: finite exponent groups

We call $G$ a torsion group if for every $g\in G$ there exists a natural $n>0$ such that $g^n=1$. We say that $G$ has finite exponent if the inverse quantification holds, i.e. there exists a ...
2
votes
2answers
63 views

Prove that: $\vdash \forall x \exists !y(y=x)$

Prove that: $$\vdash \forall x \exists !y(y=x)$$ in first order logic. The first thing to do would be to write this as $$\forall x (\exists y(y=x) \land \forall y\forall z (y=x \land z=x \to y=z))$$ ...