Questions about 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
2answers
261 views

Why artificial intelligence people didn't use propositional logic to represent knowledge? [closed]

Why artificial intelligence people didn't use propositional natural programming language to represent knowledge?and is there's a relation between propositional logic and first order or predicate ...
1
vote
3answers
214 views

Very simple predicate logic deduction question

I am very new to logic and currently taking a course about it but unfortunately it's a weekend now so I can't get the answers I need! Basically I am wondering a very basic thing. I want to prove ...
2
votes
2answers
53 views

Definable orders

Let $(K, <)$ be an order field, can I define the order "<" in $K$ ? I know that $K \models 0<a \;$ if and only if there is $b$ in the real closure of $K$ such that $b*b = a$. Can I ...
0
votes
1answer
83 views

Write down a proof for $\bot\Rightarrow q$ in proposition calculus

I am given the hint in the question that I will need to use the axiom $(((s\Rightarrow \bot)\Rightarrow \bot)\Rightarrow s)$. The axioms I am using are $$(s\Rightarrow (t \Rightarrow s)) ...
0
votes
1answer
71 views

EFA and recursive algorithm

1) Is EFA stronger than recursive algorithm? (This can be in term of proof theoretic ordinal, or whatsoever - to rephrase the question, are all problems that can be solved(and halt) by recursive ...
1
vote
0answers
151 views

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...
1
vote
0answers
82 views

Ultrapowers by extenders of potential premice

I have a problem with an argument in Fine structure and iteration trees by Mitchell and Steel. Let $E$ be a $(\kappa, \lambda)$-extender. Let $\dot E^{\mathcal{M}}$ the a unary predicate with is ...
2
votes
3answers
271 views

Other ways of proving that the set of all countable ordinals is uncountable

I know that the standard way of proving that the set of all countable ordinals is uncountable is by stating that if the set is countable, then it incurs Burali-Forti paradox. Is there other ways of ...
4
votes
1answer
692 views

Necessity and sufficiency

I'm learning to write mathematical proofs. When the statement to be proven is in the form "p if and only if q", the proof is often broken into two parts: necessity and sufficiency. I wonder whether I ...
0
votes
2answers
33 views

A logic statement. “or” in Abstract algebra - groups

Let H be the subset of $M_2(\mathbb{R})$ consisting of all matrices of the form $H^* = \left \{ \begin{pmatrix} a &-b \\ b&a \end{pmatrix} : a,b\in\mathbb{R} , a\neq 0 \; \text{or} ...
0
votes
2answers
636 views

How to convert a formula to CNF?

I am trying to convert the formula: $((p \wedge \neg n) \vee (n \wedge \neg p)) \vee z$. I understand i need to apply the z to each clause, which gives: $((p \wedge \neg n) \vee z) \vee ((n \wedge ...
1
vote
1answer
25 views

Correct logical operators to express “At (1-α)100% confidence then …”

I would like to express the statement: At (1-α)100% confidence, $e \le z_{\frac{α}{2}}\sqrt{\frac{{p̂(1-p̂)}}{n}}$ But I want to express the first part using logical operators. What is the ...
0
votes
0answers
69 views

Prove $p \rightarrow \neg \neg p$ with Hilbert System [duplicate]

Possible Duplicate: Prove that $\beta \rightarrow \neg \neg \beta$ is a theorem using standard axioms 1,2,3 and MP I need to prove $p \rightarrow \neg \neg p$ My question is very similar ...
0
votes
2answers
218 views

is the following a Boolean Algebra?

Boolean Algebra: $$D_{30}=\{n:n\mid30\}= \{1,2,3,5,6,10,15,30\}$$ I don't know how to test that this is a boolean algbra (a BA is a distributive lattice with $T,F$ in which every element has a ...
3
votes
1answer
594 views

$2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S,<)$

This is (a translation of) an excerpt from a model theory textbook that shows that $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S, <)$, where $S$ is the successor function. ...
1
vote
1answer
171 views

Recommendation for a logic book to understand Godel's theorem

I have studied set theory but I couldn't understand even the first line of the Godel's proof. For instance, $\omega^n$ means the set of functions from $\omega$ to $n$ in my set theory, ZFC, but the ...
3
votes
1answer
432 views

De Morgan's Law

Is it correct to say that de Morgan's Law is one of an isomorphism of classical logic? I think it is. (A bit meta, but is this question an appropriate one for this site?)
0
votes
2answers
98 views

xRy if and only if x is a descendant of y, on the set of all humans. Explain the relations

xRy if and only if x is a descendant of y, on the set of all humans. I have the solution to this. I just don't understand how transitivity follows.
1
vote
2answers
219 views

The real numbers and the axiom of foundation

I am having a bit of confusion about the real numbers and ZF set theory (I asked a question about it a few days ago). I am a bit unsure as to why the real numbers can be in any model of ZF as they ...
8
votes
2answers
16k views

How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $? Or is there some ...
2
votes
2answers
109 views

What's the precise meaning of '$\phi$ is essential in hypothesis of theorem'?

Say, " $\psi \Rightarrow \varphi$ " is a theorem and $\psi$ is essential in the hypothesis. I don't understand what's the meaning of essential. Here's what i guess; If $[\psi \Rightarrow \Phi] ...
3
votes
2answers
381 views

Show that not all sets of Natural Numbers are definable

I'm kind of lost on this problem; I think it has something to do with showing that there are uncountably many relations among N(assuming an included set of functions such as successor, addition, and ...
17
votes
1answer
512 views

Is every model of modular arithmetic either even or odd?

Modular Arithmetic (MA) has the same axioms as first order Peano Axioms (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. ...
5
votes
2answers
290 views

Which are “big theorems” of descriptive set theory?

Question: If one were to fully understand 10 theorems in DST, or 15,20,25,30 theorems, which ones would be the most important to understand in order to work towards an understanding of descriptive set ...
0
votes
1answer
379 views

Peano's Postulates Proofs

How can I prove the following two questions: Prove using Peano's Postulates for the Natural Numbers that if a and b are two natural numbers such that a + b = a, then b must be 0? Prove using Peano's ...
2
votes
3answers
250 views

A theory with exactly $n$ countable models, for each $n>1$

For each $n>1$ we shall construct a first-order theory $T_n$ with exactly n countable models. Let $n>1$, consider the language $L_n=\left\{{R,c_1,...,c_n}\right\}$, where $R$ is a binary ...
5
votes
3answers
285 views

From lightface $\Sigma^1_1$ to boldface $\mathbf\Delta^1_1$

Fix some standard Polish space, e.g. Baire's space. It's a simple observation that every $\Delta^1_1$ is also $\mathbf\Delta^1_1$. It is the same observation that $\Sigma^1_1$ becomes ...
0
votes
1answer
191 views

About proving a arguments is valid

I have a question is about proving a argument is valid or not. Again, cannot really understand the solution. The question is like this Determine if the following arguments are valid. ...
9
votes
5answers
1k views

What does it mean for something to be true but not provable in peano arithmetic?

Specifically, the Paris-Harrington theorem. In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?
1
vote
1answer
145 views

Problem with Morley's Theorem

Greets. Morley's theorem states that a theory which is categorical for an uncountable cardinal is categorical in all uncountable cardinals. My problem with the theorem is that I haven't found a ...
3
votes
3answers
1k views

About the notation of “there exist” and “For all”

I have a question like this Let $P(x,y,z)$ denote $xy=z$, $E(x,y)$ denote $x=y$, $G(x,y)$ denote $x>y$. Transcribe the following into logical notation. Assume that the universe of discourse is ...
3
votes
3answers
463 views

Factoring out universal quantifier in combination with an implication

I just began studying maths and so far everything made sense after tinkering around with it a little bit (e.g. $ \lnot(\forall x \in M : A(x)) = \exists x \in M : \lnot A(x) $ thinking "not all math ...
1
vote
0answers
85 views

Generating Input Binary Combination Dynamically

this is probably right forum to post this question I am currently working on a application where there is a requirement to generate binary combination of input signals in a truth table. The signal ...
4
votes
2answers
338 views

For every axiomatic system in first order logic there exists an equivalent independent system

The question is how to prove the assertion in the title. With "axiomatic system" I just mean any (consistent) set of sentences (over any given language). "independent" means that no axiom can be ...
0
votes
1answer
36 views

Proof if $\mathcal{R}$ is an equivalence relation, either $E_a \cap E_b = \varnothing$ or $E_a= E_b$

Proof if $\mathcal{R}$ is an equivalence relation, either $E_a \cap E_b = \varnothing$ or $E_a= E_b$ The proof given looks like: $E_a \cap E_b = \varnothing$ (Premise) $\exists x (x \in (E_a ...
1
vote
2answers
108 views

Determining the equivalence of two statements

I have been given two statements and told that they are equivalent, but I'm having a hard time convincing myself of that. The two statements are: (1) "Every graph G has a minimum colouring in which ...
0
votes
1answer
85 views

Natural order of rational trees?

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the ...
1
vote
0answers
123 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
-1
votes
3answers
308 views

calculus in term of ZFC and set theory [closed]

Calculus as used normally uses infinitesimal quantity and nonstandard (infinitesimal) analysis to define limits, derivatives, integrations and so on. So, is there any attempt to define calculus in ...
1
vote
3answers
318 views

Predicate Logic Statement Validity

I am thinking about whether this is valid or not; ∃x∀y (P(x,y)) ↔ ∀x∃y (P(x,y)) My attempt so far; Let's assume that P(x,y) function represents that x and y are ...
15
votes
11answers
2k views

Logic nonsense/paradox

I'm not sure if this is a paradox or a nonsense or neither of both. Anyway this is the "problem" if we can call it like that: A: B is True B: A is False How can ...
5
votes
1answer
1k views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions…Induction!

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, where, ...
1
vote
2answers
206 views

Prove the $3^n < n!$ for all $n > 6$

I'm trying to use induction to prove this. I'm sure it's a simple proof, but I can't seem to get over the first few steps. Any help? Allow $P(n)=3^n<n!$ Base Case: $P(7) = 3^7<7! ...
2
votes
2answers
479 views

Axiom 3 of Hilbert System

I have seen that Axiom 3 of the Hilbert System is sometimes written as: 1: $( \neg A \rightarrow B) \rightarrow ( ( \neg A \rightarrow \neg B) \rightarrow A)$ and then sometimes it is: 2: $( \neg ...
0
votes
2answers
143 views
0
votes
1answer
74 views

about a solution of a question in symbolic logic

I cannot understand the following solution from my tutorial note. The question is like this: Let $P(x)$ be a predicate with universe of discourse $\{a,b,c\}$. The quantifier $\exists!$ is used to ...
2
votes
1answer
556 views

Showing a formula is a tautology

I'm currently enrolled in a introductory course on logic and until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of ...
1
vote
1answer
134 views

Entry Level Set Theory Proof [duplicate]

Possible Duplicate: Subsets and equality Hello I'm new to set theory and I want to know how I can solve the following question Let $U$ be a universe and $A,B$ and $C$ be subsets of $U$. ...
4
votes
1answer
293 views

Motivation behind Theory of Relations?

I looked through the nice paper by Tarski On the Calculus of Relations. In the beginning he touched a motivation behind Theory of Relations but this part was not clear to me (page 1, very beginning): ...
0
votes
1answer
149 views

A question on intuitionistc propositional logic

Prove that: Two finite rooted frames are isomorphic iff they validate the same formulas. (This is an exercise in the book "Modal Logic" by A.Chagrov and M.Zakharyaschev)