Tagged Questions

Questions about logic and 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)

4
votes
1answer
87 views

What is the intuition behind $\Delta_1^0$ sets and $\Delta_1^1$ sets?

In the context of first-order arithmetic, if $\phi$ is a formula with only bounded quantifiers, then if you put existential quantifiers in front it becomes a $\Sigma_1^0$ formula according to the ...
0
votes
1answer
64 views

Prove by Hilbert deduction: ⊢∃x(AvB)→(∃xAv∃xB); ⊢(∃xAv∃xB)→∃x(AvB)

I'd really like your help proving: 1)⊢∃x(AvB)→(∃xAv∃xB) 2)⊢(∃xAv∃xB)→∃x(AvB) Our proof system contains next Hilbert's axioms: 1.A→(B→A) 2.(A→B)→((A→(B→X))→(A→X)) 3.(A&B)→A 4.(A&B)→B ...
0
votes
2answers
181 views

What is the negation of the following statements?

I need some help double checking my work and the teacher likes to obfuscate his answers. I am negating the given statements regardless of whether they are true or false. 1: Given a line and a point ...
2
votes
5answers
695 views

Logic and set theory textbook for high school

Do you have any advice for a textbook or a book for high schools students which completely adresses basics of logic (proposition, implication, and, or, quantifiers) and set theory (intersection, ...
0
votes
1answer
34 views

Discrete math logic problem

Prove or disprove that $\{\mathcal{M},\;\Phi,\;\neg,\;\bigvee,\;\bigwedge,\Rightarrow \}$ can be reduced to $\{\mathcal{M},\;\Phi,\;\nabla\}$, where x$\nabla$y is equivalent to $\neg$(x $\bigvee$ y). ...
0
votes
4answers
48 views

Where is a flaw in these logical implications?

We have a theorem: If $a \le x < a + {\frac yn}$ for $y > 0$ and all natural $n \ge 1$ then $x = a$. Suppose I derive that $a < x$ and $x < a + {\frac yn}$ for all $n \ge 1$. In other ...
2
votes
1answer
45 views

What subsystem of second-order arithmetic can interpret the theory of real closed fields?

Real numbers can be encoded as sets of natural numbers, because they can be encoded as Dedekind cuts or Cauchy sequences of rational numbers, and a rational number can be encoded by a natural number. ...
2
votes
1answer
70 views

Problem about logic

A Mathematics lecturer can’t find a nice exercise for the final exam paper of his course. Then he makes up his mind and gives the following one-line exercise: Write an exercise you think suitable for ...
9
votes
1answer
183 views

What was the planned topic of Gödel's second paper on incompleteness?

Gödel's incompleteness theorems first appeared together in a paper titled (translated to English) "On formally undecidable propositions of Principia Mathematica and related systems I," with the Roman ...
1
vote
3answers
74 views

Prove the following $f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$

There is option to prove the following with truth table? $$f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$$ I would like to get some hints how to do it in formal way(not truth table) thanks!
4
votes
2answers
100 views

Non-upper bounds without excluded middle

Motivated by an earlier question, I'm curious if we can prove the following statement without the law of excluded middle: Let $E$ be a set of real numbers. A number $x$ is said to be an upper ...
2
votes
2answers
54 views

How come that two inductive subsets can be different

In Enderton's "Mathematical Introduction To Logic". Author says that if we have two operations $f(x,y)$ and $g(x)$ and two sets $B$ and $U$ such that $B \subseteq U$. We say that $S \subseteq U$ is ...
1
vote
2answers
64 views

Do “equational theories” include sequents?

In equational logic, which of the following best describes the term "equational theory"? A collection of identities. A collection of quasi-identities, by which I mean sequents of the form ...
1
vote
1answer
55 views

Universal Generalization properties

So I am looking for a proof (it is probably simple) to : $ \vdash (\forall x)A \rightarrow A$ Any help would be appreciate !!
2
votes
0answers
103 views

Isomorphism of finite models

Let $\mathfrak A$ and $\mathfrak B$ are models of finite signature $\sigma$. Prove that $\mathfrak A$ and $\mathfrak B$ are isomorphic, if $\mathfrak A \equiv \mathfrak B$ and $\mathfrak A$ is ...
14
votes
6answers
533 views

When to use the contrapositive to prove a statment

My question tries to address the intuition or situations when using the contrapositive to prove a mathematical statement is an adequate attempt. Whenever we have a mathematical statement of the form ...
3
votes
1answer
118 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
3
votes
1answer
85 views

$\mathrm{Pol}_m(\mathbb{A})$ viewed as a relation pp-definable from $\mathbb{A}$

First let me recall some (abbreviated, and possibly simplified to suit my situation) definitions: Let $A$ be a finite set and $\mathbb{A}$ some set of relations on $A$. Let $m, n$ be positive ...
7
votes
2answers
280 views

Number of Non-isomorphic models of Set Theory

Assume that the meta theory allows for model theoretic techniques and handling infinite sets etc (The meta theory itself is, informally, "strong as ZFC"). Also assume that I'm studying ZFC inside this ...
1
vote
2answers
140 views

A question about tableau method for first-order logic

I have a doubt about tableau method for f-o logic. In Smullyan's book (First-Order Logic, 1968, Dover reprint) the method is defined (pag.53) for formulae but - if I'm not wrong - all examples that ...
4
votes
1answer
125 views

Gödel Incompletness theorem

I am not familiar with model theory. As a matter of fact, I only had my first Logic and Set theory courses last semester. But still, there is a question that bothers me, and It could be nice if ...
0
votes
2answers
40 views

Questions regarding bound variables

$$x\in(\cap F)\cap(\cap G)=[\forall A\in F(x\in A)]\land[\forall A\in G(x\in A)]$$ Since the variable $A$ is bounded by universal quantifier, it is regarded as bounded variable, according to the ...
4
votes
1answer
138 views

How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to ...
4
votes
1answer
105 views

What do identities mean in $\mathrm{Set}^\mathrm{op}$?

Since $\mathrm{Set}$ has finite coproducts, thus we may consider models of equational theories in the opposite category $\mathrm{Set}^\mathrm{op}$. The result is basically that function symbols $f : ...
3
votes
6answers
128 views

Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent

Given there are 2 logical variables $p$, $q$ . Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent without using the truth table. And here is my ...
5
votes
5answers
438 views

Ambiguity in the Natural Numbers

What I am wondering is if mathematicians know whether (assuming consistency) the natural numbers are a definite object, without ambiguity. This seems intuitively obvious, but I don't know if its been ...
0
votes
2answers
71 views

Showthat $\mathrm p \leftrightarrow \mathrm q$ and $(\mathrm p\wedge \mathrm q) \vee (\neg \mathrm p \wedge \neg \mathrm q)$ are logically equivalent

Given there are 3 logical variables p, q . Show that $(\mathrm p \wedge \mathrm q) \vee (\neg\mathrm p \wedge \neg\mathrm q)$ and $\mathrm p \leftrightarrow \mathrm q$ are logically equivalent without ...
1
vote
1answer
42 views

Does definable imply recursively enumerable? [duplicate]

Is there any subset of the natural numbers that is definable but not recursively enumerable?
2
votes
1answer
71 views

The Consistency of Arithmetic

I believe that within ZFC (or maybe even a weaker subset of ZFC) there is a proof of $\mathbb{N}=(\omega,+,.,<,0,1)\models{PA}$. What would be a standard reference for this?
0
votes
1answer
42 views

Implications using inequality signs <= and <

Suppose we have a theorem that says: If $A \le X \le B$ and $A$, $B$ both have property $p$ then $X$ has property $p$. I'm working on some problem and I derive that $A < X < B$ and $A$, $B$ ...
3
votes
3answers
208 views

Paradoxes in Logic

What is it that makes something a paradox? It seems to me that paradoxes are just, in many cases, misunderstandings about the properties some object can have and so misunderstandings about ...
0
votes
0answers
98 views

Why is the implication $P \Rightarrow Q$ false if and only if $P$ is true and $Q$ is false? [duplicate]

Why is the implication $P \Rightarrow Q$ false if and only if $P$ is true and $Q$ is false ? Is this because if $P$ implies $Q$, where $P$ is true and $Q$ is false, then $Q$ is also true by ...
2
votes
2answers
93 views

Double negation distributes over conjunction

In Exercise I.1.11.(ii) of Johnstone's Stone Spaces, it is claimed that in any Heyting algebra, $$\lnot\lnot (a \land b) = \lnot\lnot a \land \lnot\lnot b.$$ It is easy to see one direction: Since ...
2
votes
1answer
59 views

Algebraic signatures as quivers; is there somewhere I can learn more about these definitions?

In my opinion, a cool definition of "algebraic signature" is as follows: An algebraic signature on the sort symbols $\mathcal{X} = \{X_0,...,X_{n-1}\}$ is precisely a quiver whose underlying set ...
0
votes
2answers
589 views

DNF and CNF logic problem

So i want to find the DNF and CNF of : $ x \oplus y \oplus z $ . I tried by using $ x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y) $ but it got all messy and stuff, I also plotted it in ...
0
votes
2answers
63 views

How do I show that these are the same logical statement?

I know that if I wanna show that the following statement are the same, I may use some rules in Logic: $$P\Longrightarrow Q,\quad [P \text{ and } (\sim Q)]\Longrightarrow [R\text{ and }\sim R]$$ Is ...
0
votes
1answer
97 views

Logic boolean algebra problem

so I have to prove that these equations : are equivalent?
2
votes
0answers
48 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
7
votes
1answer
194 views

What is the dual of implication?

You may divide Intuitionistic Propositional Logic into the negative and positive fragments. The negative fragment includes truth, conjunction, and implication while the positive fragment includes ...
0
votes
1answer
109 views

Proof by contradiction: May I assume $P$ (true) in $\neg Q \land P \Rightarrow P \land \neg P$ to prove $Q$ by contradiction

Suppose I wish to do a proof by contradiction the statement $Q$. In proving $Q$ may I assume $\neg Q \land P$ (where $P$ is a statement known to be true) and show the implication $\neg Q \land P ...
1
vote
1answer
41 views

Other than $\models$, is there standardized notation for semantic consequence?

It is common practice to use $\models$ both for the satisfaction relation between models and sentences, and for the corresponding semantic consequence relation. Question. Suppose I don't want to use ...
3
votes
2answers
74 views

Formalising Definite Description (Russell)

So, we've been doing a lot of formalising of definite descriptions according to Russell, where we take the Definite Description as a predicate rather than designator. So, I've formalised sentences ...
0
votes
1answer
88 views

Karnaugh map minimum sum of products

I'm trying to give the minimum sum of products using Karnaugh Map of this expression: ...
1
vote
1answer
130 views

∀x ∀y Q(x; y) What is the meaning

What is the meaning of ∀x ∀y Q(x; y)? Does this mean that: For all values of X every value of Y will satisfy Q(x;y)? so if Q(x;y) = x + y = x * 2 in this case ∀x ∀y Q(x; y) would be false? ...
2
votes
0answers
50 views

Help understanding Smullyan’s semantics definition for First-Order Logic

Ref.to Raymond Smullyan, First-Order Logic (1968 – Dover reprint). Some background : [pag.44] - individual variables (to be used bound) and individual parameters (to be used free) [pag.47] - ...
2
votes
1answer
79 views

Are my answers for these propositional calculus questions right?

Formalize the following English sentences as propositional logic formulas: $i)\quad$ "When the front and back doors are closed then the light is off." $ii)\quad$ "Either the lift doors are open or ...
3
votes
1answer
67 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
3
votes
2answers
117 views

Formal definition of effective proof

I am someone who likes precise definitions for mathematical terminology. So, is there some text where there is a precise definition of an effective proof? The notion is vague to me.
0
votes
1answer
44 views

Using existential quantifiers to turn equalities into inequalities

I have a formula of the form $f(x)^2 = 0$, where $x \in \mathbb{R}^n$ and $f$ is a Diophantine polynomial. I am wondering if there is a general way to produce a formula of the form $\exists y \in ...
7
votes
3answers
243 views

Why is zero important?

I am not sure whether this question is more appropriate here or in theoretical computer science. I leave it to the wisdom of moderators. On the computer science site I came across the following ...