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)

0
votes
0answers
43 views

The lexicographic order [duplicate]

If it is given ordinals $\alpha$ and $\beta$, the lexicographic order on $\alpha \times \beta$,$\leq_{lex}$ is given by: $(\gamma_0,\delta_0)<_lex(\gamma_1,\delta_1)$ if and only if either ...
1
vote
2answers
22 views

A free variable $x$ in $\exists x x<(y\cdot y) \wedge\forall y \neg x\doteq (y+y)$

Is $x$ a free variable in $\exists x x<(y\cdot y) \wedge\forall y \neg x\doteq (y+y)$? I'm asking because you can read $\exists x x<(y\cdot y) \wedge\forall y \neg x\doteq (y+y)$ as: ...
6
votes
1answer
178 views

Problem 24 from Chapter 1 of Kunen's Set Theory: An Introduction to Independence Proofs

Just want to make sure I'm tracking Kunen here, and hopefully the proof I have is correct. Comments / Suggestions welcome. Thanks! Problem 24. Let T be any consistent set of axioms extending ZF. ...
2
votes
2answers
105 views

$\mathsf{ZF}$ is not finitely axiomatizable

As we know a first order theory $T$ is finitely axiomatizable if there is a finite set $F\subseteq T$ of axioms such that $F\vdash \sigma$ for every $\sigma \in T$. How we can prove if $\mathsf{ZF}$ ...
0
votes
0answers
33 views

Representing a relation in True Arithmetic

How to write a formula $A(x, y)$ which represents the relation $(y=f(x))$ in True Arithmetic? The formula for $A(x, y)$ can use a formula $B(c, d, i, y)$ that represents the graph of Godel $β$ ...
1
vote
0answers
18 views

Treating a complex argument as a system of linear equations

I've been experimenting with putting logical arguments into matrices by considering it a system of equations and converting the arguments into boolean algebra notation. For example letting ...
0
votes
0answers
55 views

Brute-force searches for counterexamples

Gödel's completeness theorem says that for every statement in first-order predicate caluculus with equality, there is either a proof that it holds in all structures, or a counterexample --- a ...
3
votes
2answers
59 views

How to interpret $\exists x (\forall x \Phi (x))$?

It's clear to me what the interpretation is when we have something like: $$\exists x (\forall y \Phi(x, y))$$ or even how to interpret the formula when x or y are not variables in the expression ...
1
vote
1answer
37 views

A question to the proof of a lemma in Enderton's Mathematical Introduction to logic

I'm referring to the proof to Lemma $25\text{B} \ $,pg$\ 133$ of Enderton's Mathematical Introduction to Logic($2^\text{nd}$ edition): $\overline s(u^{x}_{t})=\overline {s(x|\overline s(t))}(u).$ The ...
1
vote
1answer
41 views

Expressing “Highest” in First Order Logic

I'm writing a First Order Logic sentence to express a "Highest" function. (ie. highest temperatures in a city) I'm thinking along the lines of something like this: HighestTemp returns T1 s.t. ...
2
votes
1answer
43 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
1
vote
1answer
50 views

Show that every existential sentence is preserved upwards

A sentence is existential if it is of the form $\exists x_1 ... \exists x_nR$ and $R$ has no further quantifiers. A sentence is preserved upwards if and only if whenever it is true in an ...
0
votes
0answers
26 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
0
votes
6answers
131 views

Logic - Is $A \rightarrow ( B \rightarrow C) $ equivalent to $A \rightarrow C$?

I know that $A \rightarrow B$ and $B \rightarrow C$ resolves to $A \rightarrow C$ but does $A \rightarrow (B \rightarrow C)$ also resolve to $A \rightarrow C$?
0
votes
2answers
414 views

How to Convert this to CNF and DNF

I am having serious problems whenever I try to convert a formula to CNF/DNF. My main problem is that I do not know how to simplify the formula in the end, so even though I apply the rules in a correct ...
4
votes
2answers
51 views

Peculiar examples to the Stone Representation Theorem

The Stone Representation theorem states that every Boolean algebra is isomorphic to a field of sets. That is, a Boolean algebra whose elements are sets, and sums, products, negation are union, ...
2
votes
1answer
189 views

Origin of the Notion of a Well-Formed Formula

When was the idea of a well-formed formula first stated or can get inferred as such under another name?
-1
votes
2answers
65 views
4
votes
2answers
164 views

Interaction of completeness and second incompleteness theorems

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M ...
0
votes
1answer
18 views

What is the CNF for At Most One?

Learning CNF for the very first time and am confused by the notation. From "A New SAT Encoding of the At-Most-One Constraint" page 6 ...
0
votes
1answer
34 views

Boolean Function question [duplicate]

I need to know how I can prove this question. Prove that not every boolean function is equal to a boolean function constructed by only using And ($\wedge$) and Or ($\vee$)
4
votes
3answers
148 views

What precisely is a vacuous truth?

Is there a proper and precise definition that goes something like this? Definition. A statement $S$ is a vacuous truth if ... ...
0
votes
1answer
23 views

Limit of decreasing sequence of closed (under logical consequence) theories.

Let $T_1 \supsetneq T_2 \supsetneq T_3 \supsetneq \ldots$ be a strictly decreasing sequence of closed (under logical consequence) theories, where closed means that for any statement $\phi:T_i\vdash ...
4
votes
1answer
120 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
2
votes
0answers
56 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
1answer
12 views

first-order predicate calculus logic

Selling a book changes who owns it but not who wrote it How do I represent the above statement in the form of first-order predicate calculus? Does my attempt below makes any sense? Selling(x) ...
0
votes
3answers
72 views

What is a formal definition of “predicate logic”?

I'm currently trying to get clear about some terms that are often used in computer science (I'm a computer science student), but were never formally introduced. Especially, I would like to know what a ...
0
votes
1answer
65 views

Predicate Calculus English Translation

I'm having difficulty translating the following English sentences into predicate logic. Any help would be greatly appreciated. $B:\qquad$_ is a book $A:\qquad$_ is an author $H:\qquad$_ is a ...
0
votes
1answer
25 views

proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
2
votes
1answer
60 views

Predicate logic proof

Prove the following formula. $$ \vdash (\exists x)(A \land B) \lor (\exists x)(A \land C) \equiv (\exists x)(A \land (B \lor C))$$ The question is number 10 in chapter 6 in "Mathematical Logic" by ...
0
votes
1answer
50 views

$\Sigma \ \vdash A \lor B \ \ $

I'm stuck with the following question: prove or disprove the following: if $\Sigma \ \vdash A \lor B \ \ $ then $\ \ \Sigma \ \vdash A \ \ $ or $\ \ \Sigma \ \vdash B $ ...
3
votes
5answers
293 views

Can mathematics be traced back to a fundamental system of truths?

I'm not sure exactly how to state this question, or even if it belongs here. Still, I hope you will consider it, as I find it very interesting: Most of the results I've seen in mathematics come from ...
3
votes
3answers
258 views

Interpretation of a formula and truth

I just started self-studying Mathematical Logic by Ebbinghaus. I already knew something about formal languages, but nothing about model theory. There is something I don't understand: Exercise 3.3, ...
0
votes
0answers
16 views

Structural induction question?

The question is: Give recursive definition of a set "S" of all binary strings starting with a 1. Do the three steps: base, recursion, and restriction So far, I have: base: empty string recursion: ...
0
votes
3answers
33 views

Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the ...
1
vote
2answers
322 views

prove $(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$ in Hilbert System

I'm looking for a way to prove : $$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$$ From the axioms : A1) $(A) \rightarrow ( B \rightarrow A )$ A2) $(A \rightarrow ( B \rightarrow C ...
0
votes
1answer
50 views

Truth value of conclusion

Here I are premises followed by a conclusion. I want to confirm if my understanding about conclusion being false is right or not. In the book it was mentioned that their conclusion is false. My ...
1
vote
2answers
195 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
0
votes
1answer
55 views

The definition of interpretation in a Kripke model collides with my intuition of what it should do

In Lindröm and Segerberg (2007) exposition of a Kripke model, with frame $F= \langle W,D,R,E,w_0\rangle$, they define an interpretation $I$ as a family of functions $I_w$, where $w$ ranges over ...
2
votes
1answer
27 views

For $\mathbb{X}$ with order relation and field structure extended from $\mathbb{R}$, if it includes real line, then is it real line?

For a set $\mathbb{X}$ given order relation and field structure extended from those of $\mathbb{R}$, if $\mathbb{X} \supseteq \mathbb{R}$ then $\mathbb{X} = \mathbb{R}$ ? This question is derived ...
2
votes
1answer
24 views

Equivalent formula in countable structures

Question, if two sentences A & B, are such that for all countable structures M: M⊨A iff M⊨B, and A & B be thus logically eguivalent. But how?! I understand that I have to use ...
2
votes
1answer
31 views

Are all theorems of minimal arithmetic theorems of a given theory?

I am working on some metamathematics revision and the following question came up. Let the theory $R_0$ be axiomatized by the following axiom schemata which hold for all $n,m \in \mathbb{N}$: ...
1
vote
1answer
53 views

First Order Logic “More Than One”?

I'm trying to figure out how to express "More than one" in first order logic. What I have so far is: $$\exists S_1 \exists S_2 IsGreen(S_1) \wedge IsGreen(S_2)$$ But that definitely doesn't sound ...
2
votes
1answer
35 views

Intuitionistic logic and explicit existence proofs

I have read that to intuitionistically prove a statement of the form $\exists x.\varphi,$ we have to actually describe such an $x$ as an explicit expression (with free variables from $\varphi$, ...
2
votes
1answer
47 views

Logic verification: $x^3$ is irrational, then $x$ is also irrational

Prove, by contraposition, if $x^3$ is irrational, then $x$ is also irrational. Just a verification do I need to show that given $x$ is rational $x^3$ is also rational? Suppose $x \in \mathbb{Q}$ ...
5
votes
1answer
398 views

A logic that can distinguish between two structures

it's known that there are non-isomorphic structures that satisfy the same first-order sentences. Likewise it's known (by cardinality arguments) that there are non-isomorphic structures that satisfy ...
9
votes
3answers
611 views

How do I prove $x \vee \neg x$ in Hilbert system?

How to prove $x \vee \neg x$ using the following axioms? $A \rightarrow (B \rightarrow A)$ $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ ...
2
votes
1answer
96 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
3
votes
2answers
39 views

Epistemic logic: in which worlds are the formulas true?

I have a question regarding the following: I don't get both answers. I thought that question 1 was true in w2, w3, w4. But the answer does not show have w3. Why is that? Because the symbol says ...
1
vote
1answer
32 views

Question about the total probability law

Why does $A= (A \cup B) +(A\cup C)$ and not $(A \cap B)+(A \cap C)$? Wouldn't you have to take the intersection to have elements of just $A$ instead of having the elements that $A$ overlaps with? ...