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
1answer
35 views

Rationalization of an integer set

Let $X \subseteq \mathbb{N}^2$ be the set $\{(x,y) \, : \, y \text{ is the greatest power of 2 dividing } x\}$. I'm wondering how the set gets when multipled by the non negative rationals, i.e. what ...
7
votes
3answers
217 views

Does the category framework permit new logics?

It appears to me that a topos permits a broader concept of subsets than the yes/no decission of a characteristic function in a set theory setting. Probably because the subobject classifier doesn't ...
3
votes
1answer
52 views

In predicate logic, are these four expression equivalances?

(1) $\forall x P(x) \wedge \forall x Q(x)$ (2) $\forall x (P(x) \wedge Q(x)) $ (3) $\forall y (\forall x P(x) \wedge Q(y))$ (4) $ \forall y \forall x(P(x)\wedge Q(y))$ I'm sure that (1) and (2) ...
0
votes
1answer
221 views

Constructing a formal proof of certain logical arguments

Given the following arguments: $ \tag A (R \to \neg S) \land (T \to \neg U)$ $ \tag B (V\to \neg W) \land (X \to \neg Y)$ $ \tag C (T \to W) \land (U \to S)$ $ \tag D V \lor R $ $$ ...
0
votes
1answer
109 views

Difference between if-then and iff in predicate logic

Let C(x,y) be student x is in class y. Where the domain for x is all the students in my school and domain of y is the set of all classes in my school. Given ∃x,y ∀z((x≠y)∧(C(x,z)↔C(y,z))) , the ...
1
vote
1answer
54 views

functional completeness of $\{\not\to$, ¬}

Hello I need to proove that $\{\not\to$, ¬} is functional complete concerning {not, or, and}. The definition: x $\not\to$ y : x and not y. My attempt is to show that {not, or, and} can be also ...
2
votes
2answers
500 views

Functional completeness of $\{\text{or},\text{ xor}, \text{ xnor}\}$

I need to prove the functional completeness of $\{\text{or},\text{ xor},\text{ xnor}\}$ with the help of $\{\text{not},\text{ or},\text{ and}\}$ (which have been already proven to be functional ...
2
votes
3answers
93 views

Provability becoming decidable in a larger system?

Let $T$ be an effectively axiomatizable system that we believe to be consistent, and expressive enough so that Godel’s theorem applies to it. Then we have that the provability statements related to ...
2
votes
3answers
723 views

Symbolic Notation for Least Common Multiple

I am trying to write a proof for the least common multiple lcm(x, y), where lcm(x,y), x, and y are of course integers. What are the properties of lcm(x,y) written symbolically in mathematical logic ...
3
votes
2answers
341 views

“Are there finitely or infinitely many Fermat primes?”: decidable?

Has anyone ever proven that there exists a proof or disproof that there are finitely many Fermat primes. I know that it's an unsolved problem whether there are finitely or infinitely many Fermat ...
1
vote
2answers
378 views

Mathematical Logic and venn diagrams

Okay so I'm pretty confused about how to sketch a venn diagram for this operator: ifte(a,b,c) (or this can be written a?b:c) given a, b, c truth table and a?b:c $$\begin{array}{c|c|c||c} a & b ...
9
votes
1answer
616 views

Show that binary < “less than” relation is not definable on set of Natural Numbers with successor function

After reading about the question, I've come to believe that it would suffice to exhibit and automorphism of that is not order preserving. However, I'm unsure of how to construct such an automorphism, ...
5
votes
7answers
296 views

How can I Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology?

Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology Laws of logic I tried prove it by using truth table but it didn't produce a tautology. This is my work so far: $$ [(p \to \neg ...
1
vote
2answers
270 views

predicates & quantifiers

How to express these in terms of predicates & quantifiers : Some properties are tautologies The negation of a contradiction is a tautology The dis junction of two contingencies can be a ...
0
votes
2answers
106 views

Logical quantifiers help please

Let $T(x; y)$ denote the phrase "$x$ likes cuisine $y$", where the domain of $x$ is the set of students and the domain of $y$ consists of all cuisines. Express each English sentence below in terms of ...
1
vote
1answer
264 views

Natural deduction predicate logic

I'm trying to solve this simple natural deduction problem: {∀x(p(x) → q(a)), ∀y¬q(y)} |-nd ¬p(a) I started out by stating the premisses and the assumption, which is p(a). I used p(a) in the first ...
1
vote
2answers
544 views

Boolean Simplification: (A+C)(!A+B)(B+C) = BC

How might I solve this? I can't find any problem similar to this, and I always end up with the wrong terms. If (AB) = 0 and (A+B) = 1, prove that (A+C)(!A+B)(B+C) = BC
0
votes
1answer
106 views

Resolution in Logic

I'm taking a basic intro to logic course in Computer Science, and there's a topic that's baffling me. The instructor seems to be of not much help, and the study group I'm in doesn't seem to fully ...
0
votes
1answer
96 views

How is The strengthened finite Ramsey theorem known to be true for natural numbers?

http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem states that independence of "The strengthened finite Ramsey theorem" from PA is proved by implying consistency of PA. But how do we know ...
3
votes
1answer
75 views

matches between first and second order logic

What is common matches between first order logic and the second order logic? in other word what in first order logic is in second order logic?
0
votes
2answers
208 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
197 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
49 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
79 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
70 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
136 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
76 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 ...
0
votes
2answers
177 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
419 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
374 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
66 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
177 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
474 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
155 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
407 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
88 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
200 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
9k 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
107 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
334 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 ...
15
votes
0answers
418 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)$. ...
4
votes
2answers
259 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
338 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
211 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 ...
6
votes
3answers
248 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
138 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
128 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 ...