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)

9
votes
2answers
340 views

The “it's not possible” statement in math and the Axiom of Choice

This question actually consists 3 related pieces of text, which I've gathered under this title about which I would like your opinion (they rather contain the implicit question "is this the right way ...
5
votes
1answer
182 views

First order logic - how to prove a specific part of the completeness theorem?

I am working with the proof system for FOL described in Chang and Keisler. It contains the following axiom schemes: $\alpha \to (\beta \to \alpha)$ ...
1
vote
1answer
174 views

Translating statements into Predicate Logic

I am facing problem in translating these statements to logic statements. Some horses are gentle only if they have been well trained. Some horses are gentle if they have been well trained. I am not ...
5
votes
3answers
205 views

Confusion of the decidability of $(N,s)$

In some context the PA has only the successor operator $'s'$, but in logic we always refer the structure of PA is $(\mathbb{N},0,1,s,+,\times)$. I believed the theory of the two sturctures are ...
2
votes
1answer
73 views

What does it mean $Φ^M = Φ$, if $Φ$ is a primitive formula?

$Φ$ is a primitive formula in the language of set theory, while $Φ^M$ is the relativisation of $Φ$ to the class $M$. I can't understand why $Φ^M = Φ$. Let $Φ$ be $0 \in x$, it seems to me, ...
8
votes
3answers
80 views

$(\Bbb R \to \Bbb R : x\mapsto x^2)\equiv(\Bbb R \to \Bbb{R}_{\geq 0} : x \mapsto x^2) \not\equiv (\Bbb C \to \Bbb C:x\mapsto x^2)$

Consider the following functions: $f:\Bbb R \to \Bbb R : x\mapsto x^2$ $g:\Bbb R \to \Bbb{R}_{\geq 0} : x \mapsto x^2$ $h:\Bbb C \to \Bbb C:x\mapsto x^2$ I'm quite sure that $h$ is not equal to $f$ ...
2
votes
5answers
142 views

Value of $(a=1) \wedge (b=1) \wedge (c=2)$ given $a=1$, $b=2$ and $c=2$

How would I solve the following question. Assume $a=1$, $b=2$ and $c=2$ what is the value of the following Boolean expression $(a=1)$ AND $(b=1)$ AND $(c=2)$ I am kind of confused because I know ...
2
votes
5answers
182 views

Prove $(P\to Q) \lor (Q\to P)$

Prove that $(P\to Q) \lor (Q\to P)$ In natural language, it reads as: if $P$ then $Q$, or if $Q$ then $P$
12
votes
8answers
10k views

How do I prove that a function is well defined?

How do you in general prove that a function is well-defined? $$f:X\to Y:x\mapsto f(x)$$ I learned that I need to prove that every point has exactly one image. Does that mean that I need to prove the ...
1
vote
1answer
42 views

Universal quantification via lambda binding?

I remember once saw somewhere that a universally quantified formula can be written using $\lambda$. But I cannot recall very clearly. I have an vague impression that is is something of the form: ...
0
votes
1answer
21 views

“linear order” in descriptive complexity description of class P

In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. So, what does "linear order" mean here?
0
votes
1answer
55 views

$\mid$ in simply typed lambda calculus

$e = x \mid \lambda x\!:\!\tau.e \mid e \, e \mid c$ So, what is $\mid$ in this example of simply typed lambda calculus? The syntax of the simply typed lambda calculus is essentially that ...
8
votes
5answers
1k views

How is exponentiation defined in Peano arithmetic?

How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define. Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using ...
1
vote
1answer
101 views

Applying substitutions in lambda calculus

For computing $2+3$, the lambda calculus goes the following: $(\lambda sz.s(sz))(\lambda wyx.y(wyx))(\lambda uv.u(u(uv)))$ I am having a hard time substituing and reaching the final form of $(\lambda ...
1
vote
2answers
140 views

Writing Fermat's last theorem in arithmetic hierarchy

Somehow connected with How natural numbers can be defined using primitive recursive $\Sigma_0^0$: OK, so here's how Fermat's last theorem is formulated: $$\forall x,y,z,n>2 \quad (x^n+y^n + z^n ...
1
vote
1answer
121 views

How natural numbers can be defined using primitive recursive $\Sigma_0^0$

$$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$ I do get how some set of natural numbers (or numbers) can be defined with $\Sigma_1^0$ ...
5
votes
2answers
80 views

What should I call a sentence which must (not) be true, but the provability is still unknown?

For example, let $\phi$ be a sentence in $ZF$ and $ZFC\vdash \neg\phi$. Then, $\phi$ must not be provable in $ZF$, but we still don't know whether $ZF\vdash \neg\phi$. What should i call this sentence ...
4
votes
1answer
89 views

Why is computable function in $\Delta_{1}^0$?

I am not sure why computable functions are in $\Delta_{1}^0$. Can anyone explain this?
2
votes
2answers
317 views

Proof of Lowenheim-Skolem theorem

For each first-order $\sigma \,$-formula $\varphi(y,x_{1}, \ldots, x_{n}) \,,$ the axiom of choice implies the existence of a function $f_{\varphi}: M^n\to M$ such that, for all $a_{1}, \ldots, ...
0
votes
1answer
76 views

what is the difference between formula and the abbrevation of a formula?

there is a problem which is asking me to determine whether a string is a formula or an abbrevation of a formula but i don't know the diffrence of formula and the abbrevation of a formula i know ...
2
votes
2answers
487 views

what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$?

what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$ ? can you give me the definition supported with some simple examples ? i read the definition in ...
1
vote
1answer
169 views

Formula of hierarchies - arithmetic hierarchy and analytical hierarchy

I am recently learning on these topics, and to help understand these things, it would be helpful if some examples of formula of various arithmetic hierarchies and analytical hierarchies are provided. ...
5
votes
2answers
251 views

What are the rules for the use of dots rather than parentheses in logical formulae?

What are the rules of omission of parentheses of formulas in mathematical logic ? in my text , first order logic mathematical logic by angelo margaris ed 1990 dover , the paretheses is omitted for ...
2
votes
2answers
94 views

$V_k$ transitive model of ZFC when $k$ is inaccessible?

Is $V_k$ transitive model of ZFC when $k$ is inaccessible? I know that $V_k$ is a model of ZFC, but not sure if it's transitive one. If it is, why is it?
0
votes
1answer
130 views

Proving the statement using Resolution?

I'm trying to solve this problem for my logical programming class: Every child loves Santa. Everyone who loves Santa loves any reindeer. Rudolph is a reindeer, and Rudolph has a red nose. ...
3
votes
2answers
98 views

Show that there is a false statement of the form:

Show that there is a false statement of the form: $$\big(\exists xG(x)\land\exists xH(x)\big)\to\exists x\big(G(x)\land H(x)\big)$$ my question is , is the $ x $ in $H(x) $ must be the same $x$ ...
0
votes
1answer
98 views

$\infty$ as inaccessible cardinal and relation of inaccessible cardinal to second-order ZFC

(1) It is provable in ZF that ∞ satisfies a somewhat weaker reflection property, where the substructure (Vα, ∈, U ∩ Vα) is only required to be 'elementary' with respect ...
3
votes
3answers
2k views

How does “If $P$ then $Q$” have the same meaning as “$Q$ only if $P$ ”?

Every lecture that I watched on mathematical logic and my textbook say that $P \Rightarrow Q$ has the same meaning as $\text{"If $P$ then $Q$"}$ which has the same meaning as $\text{$Q$ only if ...
2
votes
1answer
260 views

How is second-order ZFC defined?

I know the first-order version of ZFC, but not second-order ZFC. Can anyone explain how axioms (and other things) of second-order ZFC differ from the first-order version?
0
votes
1answer
36 views

What are objects in the substructure referring to?

Firstly, a cardinal κ is inaccessible if and only if κ has the following reflection property: for all subsets U ⊂ Vκ, there exists α < κ such that ...
1
vote
2answers
101 views

The computability of Kleene's $T$-predicate

Why is Kleene's T-predicate computable? how to argue this using turing computability? would that be useful or writing it as some function
0
votes
1answer
52 views

How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
2
votes
1answer
124 views

$V_k$ being a model of ZFC whenever $k$ is strongly inaccessible

ZFC implies that the $V_k$ is a model of ZFC whenever $k$ is strongly inaccessible.. So if $k$ is weakly inaccessible, it can't be a model of ZFC? Why is it like this? And ZF implies that ...
2
votes
0answers
307 views

Three-god logic problem [closed]

Three gods A, B , and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random ...
0
votes
1answer
57 views

Is this thing K-finite?

This is related to this question: Freyd's Geometric Finiteness : An Example Computation I've essentially reduced the problem to the following question: Equip $\mathbb{N}$ with the discrete ...
0
votes
3answers
383 views

Simplifying Boolean Algebra

I am trying to prove that BC + !A!B + !A!C = ABC +!A I have attempted using De Morgan laws, and substituting X for !A!B and ...
2
votes
2answers
151 views

Are non-standard models always not well-founded?

Are non-standard models of ZF set theory by definition always not well-founded? And it seems it is, because it must be. But then, Wikipedia says that when there is a set that is a standard model of ...
0
votes
1answer
101 views

why is first-order logic strongest?

I get how first-order logic has Lowenheim-Skolem, compactness theorem, but I am not sure why this leads to first-order logic being strongest. All Lowenheim-Skolem seems to say is that for first-order ...
3
votes
1answer
81 views

application of Lowenheim-Skolem theorem

So if minimal model of ZF exists, it is said that it is countable set by Lowenheim-Skolem. So, is Lowenheim-Skolem saying that for any countable theory with existence of infinite model there exists ...
4
votes
1answer
163 views

What exactly is Levy hierarchy?

Wikipedia lacks information on Levy hierarchy, so what exactly is Levy hierarchy? This will tell me what $\Delta_0$ means in KP set theory.
3
votes
2answers
235 views

A possible vacuous logical implication in Topology

While reading "Introduction to Topology and Modern Analysis" by G.F Simmons, in the chapter on Topological Spaces, I came across the following statement that seemed unusual. I feel it may be a vacuous ...
9
votes
1answer
179 views

Difference between a Lemma and a Theorem [duplicate]

What essentially is the difference between a lemma and a theorem in mathematics? More specifically, suppose you come across a general result while solving a mathematical problem, what are the ...
0
votes
4answers
203 views

Mathematical Logic: Inconsistent models

I would like to find out if there are any examples of an inconsistent model in first order logic. I understand that to be an inconsistent model, a formula is consistent in that model and the negation ...
-5
votes
1answer
232 views

Boolean Algebra (Help Needed)

How would I draw the gate-level logic circuit of the following Boolean expression? $$ (((A \land B \lor C) \lor D \land E \land F) \lor G \land (H \lor I \land J)). $$ Then how would I implement this ...
9
votes
1answer
213 views

$\mathcal U$ Grothendieck universe. Is $\mathcal{P(U)}$ a model for NBG?

Suppose we are in ZFC, let $\mathcal U$ be an uncountable Grothendieck universe and consider the set of its parts $\mathcal{P(U)}$. (I will index axioms as $(\mathcal U.n)$) Note that if $x \in ...
2
votes
2answers
119 views

What percentage of formulas is unprovable in a given axiomatic system?

I am trying to use language I am not familiar with, so bear with me. If I make no sense, I try to be clearer. Assume we are given a formal language. Assume $S$ is the set of every well-formed formula ...
2
votes
5answers
116 views

Can any mathematical relation be called an 'operator'?

Mathematics authors agree that $+,-,/,\times$ are basic operators. There are also logical operators like $\text{or, and, xor}$ and the unary negation operator $\neg$. Where there seems to be a ...
0
votes
2answers
91 views

Conjunctive normal form of logical expression

I tried to convert this to a CNF-expression but failed. What did I do wrong? Or are there simply missing steps? $$ F' = (( A \lor \lnot B) \land C) \to ( \lnot A \land C) $$ Removed Implication $$ ...
3
votes
1answer
204 views

System with infinite number of axioms

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
4
votes
1answer
94 views

$\Sigma^0_n$ complete sets

Does anyone know of a way of showing that a $\Sigma^0_n$-complete set is not $\Pi^0_n$ without having to appeal to $\Sigma^0_n$-universal sets? For instance a more direct diagonalization argument ...