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)

3
votes
3answers
614 views

Book that is more accessible than Shoenfield

My logic course is based on my Computer Science education and on some random Internet pages (mostly Wiki). I want to make my knowledge of logic more coherent and fill in missing gaps. Thus I started ...
1
vote
2answers
97 views

Deriving $\neg R$ from $\{R↔(R∨(P∧¬P)), R↔¬P, ¬P→(P↔(Q→Q)), P→Q\}$

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
1
vote
2answers
113 views

$(A \iff B) \land (C \implies B) \implies (C \implies A)$

Is the above statement true? Just need a quick confirmation. It makes sense that if A and B are equivalent, and that C implies B then you can "swap" A with B.
0
votes
4answers
66 views

Proof: For all real numbers $x$, If $x^2 - 5x + 4 \geq 0$, then either $x ≤ 1$ or $x ≥ 4$.

I need some help in proving the following statement: $x$, If $x^2 - 5x + 4 \geq 0$, then either $x ≤ 1$ or $x ≥ 4$. It would be greatly appreciated if someone could provide me a generic proof! I'm ...
6
votes
1answer
162 views

Question on existential sentences

A sentence is called existential if it is of the form $\exists x_1 \ldots \exists x_n \ \phi(x_1, \ldots, x_n)$, where $\phi$ is quantifier free. We know that (see Chang-Keisler "Model Theory", ...
1
vote
2answers
88 views

Proof: $m,n$ are integers: either $4$ divides $mn$ or else $4$ does not divide $n$. [duplicate]

I'm having some trouble in proving the following statement: If $m$ and $n$ are integers, then either $4$ divides $mn$ or else $4$ does not divide $n$. Any help is greatly appreciated! Cheers!
1
vote
1answer
308 views

Prove that for all integers $x$ and $y$, $x - y$ is odd if and only if $x + y$ is odd.

the homework question I'm having trouble with is this one. Write a detailed structured proof to prove that for all the integers $x$ and $y$, $x - y$ is odd if and only if $x + y$ is odd. I have the ...
1
vote
1answer
42 views

logical statement: proving $\mathrm{len}(\psi)\leq4\cdot\mathrm{lenz}(\psi)+1$

Given a logical statement $\psi$ I want to prove $\mathrm{len}(\psi)\leq4\cdot\mathrm{lenz}(\psi)+1$ with $\mathrm{lenz}:=\textrm{number of all logical connectives}$ and $\mathrm{len:=\textrm{number ...
6
votes
1answer
113 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
5
votes
2answers
104 views

define the reals in a non-archimedean elementary extension of the real field.

Can it be done? We have the real field $(\Bbb R,+,-,\times,0,1,<)$, of course $(0,1,-,<)$ are definable using the rest. We take an elementary non-archimedean extension. Can we define the ...
0
votes
2answers
375 views

There are two integers whose sum and difference are perfect squares

Definition: A positive integer $m$ is said to be a perfect square if there exists an integer $n$ such that $m = n^2$. Write a detailed structured proof to prove that there exist two distinct ...
0
votes
0answers
63 views

Formalization of the Proof of the Theorem of the Bijection of Composition of Two Mappings

I'm trying to formalize in FOL the proof of the stated theorem. Assume two mappings $f$,$g$. With a slight circularity for brevity's sake, let $B(f): \text{"f is a mapping which is bijective whose ...
4
votes
1answer
608 views

Prove: Sum and Difference of two distinct positive integers are both perfect squares.

I'm trying to prove that there exists two distinct positive integers whose sum and difference are both perfect squares. I cannot find any pattern or characteristic between the pairs of numbers that ...
2
votes
1answer
134 views

Whats the difference between axiom and primitive concept?

I've read the definitions, but they are not very clear to me. Looks like both are a premisse so evident to be accepted as true without controversy. But, what about the axioms on the set theory?? ...
0
votes
1answer
81 views

“===” true or false?

I understand or rather, I have heard, that Gödel as part of his incompleteness theorem enumerates all statements. But how do you single out those that can be used in a test of provability. You will ...
1
vote
2answers
62 views

Logical structure of arguments.

So here are the contextual statements: 1) Maya either listens to music or does her homework. If she listens to music she feels happy.If she does her homework she feels unhappy. Therefore she will not ...
0
votes
2answers
156 views

What approach should I take to establish this logical proof?

I need to design a logical math proof: Write a detailed structured proof to prove that if m and n are integers, then either 4 divides mn or else 4 does not divide n. Hint: Think about the form of ...
0
votes
2answers
72 views

Undirected Graph Bipartite

I am unsure how to approach this problem: Prove that an undirected graph is bipartite if and only if there are no edges between nodes at the same level in its BFS tree. (An undirected graph is ...
1
vote
1answer
35 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
1
vote
2answers
42 views

Negating statements / Finding $(A \cap B)',A \oplus B$ if $A=\{x \in\Bbb R \mid -3\le x\le0\}$ and $B=\{x \in \Bbb R\mid -1 < x < 2\}$

I am a bit new on this field and I am trying to solve some questions. I don't really think they are hard but there are some key points that I don't get it or I am stuck. Lets see. 1) Write the ...
6
votes
1answer
212 views

Name of meta-properties

How are properties like "definability" called (in which formulas are involved): A set $X$ is definable when there is a formula $\phi(x)$ such that $X = \lbrace x : \phi(x)\rbrace$. It is not a ...
1
vote
2answers
65 views

Multiple disjunctions with a Tableaux proof system

I am using the Tableaux proof system, and have a question about branching and disjunctions. Normally the example on how to use the Tableaux proof system is to get the formula to CNF, and then start ...
1
vote
3answers
163 views

Correct progression from DNF to CNF?

Trying to figure out how to transform this predicate from disjunctive normal form to conjunctive normal form (repost of an earlier question): $$( P \land Q ) \lor ( R \land S ) \lor ( P \land S )$$ ...
0
votes
3answers
93 views

Proof by cases, inequality

I have the following exercise: For all real numbers $x$, if $x^2 - 5x + 4 \ge 0$, then either $x \leq 1$ or $x \geq 4$. I need you to help me to identify the cases and explain to me how to ...
1
vote
0answers
82 views

Are there impossible boolean constructions?

I was reading about logic and I remember, for example: That with the binary $\mathtt{NAND}$ connector can be used to assemble all the other binary connectors - I already know that there are primitive ...
0
votes
1answer
73 views

Calculate time needed to solve problem

I have this question in an assignment and I was wondering if I could get help verifying whether my approach to this question is correct... The question is as follow: Suppose that an algorithm uses ...
1
vote
2answers
74 views

Can every function which can be described by words, be formulated as well?

Almost one year ago i was amused when i saw this page. It was the generation of the prime numbers using the floor function, mostly. I became more interested about the things we can do with the floor ...
2
votes
2answers
99 views

Is Addition Defined for Nominal Numbers?

A nominal number is a symbol of a number used for naming. Wikipedia defines it as a " a one-to-one and onto function from a set of objects being named to a set of numerals. . . it is a function ...
2
votes
2answers
112 views

$\underset{x}{\bigvee} \mathfrak{P}x \wedge \underset{x}{\bigwedge} \underset{y}{\bigwedge}(\mathfrak{P}x \wedge \mathfrak{P}y\rightarrow x=y)?$

I'm reading Behnke's fundamentals of mathematics, he written that the following proposition: $$\underset{x}{\bigvee} \mathfrak{P}x \wedge \underset{x}{\bigwedge} \underset{y}{\bigwedge}(\mathfrak{P}x ...
3
votes
1answer
45 views

Is this a valid re-write rule?

In my job (SQL developer) I frequently need to change search conditions (WHERE clauses, database constraints) from disjunctive normal form to conjunctive normal form (CNF). I confess I usually resort ...
2
votes
1answer
78 views

Genericity and category

This paper by Ambos-Spies and Mayordomo on the theory of algorithmic randomness introduces the notion of genericity saying that it is based on Baire category while the usual notion of randomness is ...
4
votes
4answers
242 views

Velleman - How to prove it - Do these two statements really mean the same thing?

Hello and thanks in advance for reading! In How to Prove it P29 Velleman writes: " In general, the statement y ∈ { x | P(x)} means the same thing as P(y), ... " In my understanding the first ...
4
votes
1answer
104 views

Infinite set of standard primes as the set of standard prime divisors of a nonstandard number

Suppose $(N, +, \cdot, 0, 1, <, =)$ is a proper elementary substructure of $(N^*, +^*, \cdot^*, 0^*, 1^*, =^*, <^*)$. Show that there exists some (infinite) $b$, where $b ∈ N^*$, such that for ...
2
votes
1answer
94 views

Help needed with first-order logic representation

I'm very new to first-order logic. I've been working on some tasks below, and would appreciate if somone could check if I have understood and solved the questions correctly Task: Assume that $B$, ...
2
votes
1answer
86 views

Find a structure $M$ for a suitable language $L$ such that $M \not\models (\forall x)(\exists(y)[x<y \rightarrow x+1=y]$

This is a part of exercise $4$ page $38$ in A Friendly Introduction to Mathematical Logic by Leary Find a structure $M$ for a suitable language $L$ such that $M \not\models (\forall ...
1
vote
1answer
78 views

Show that $M \models (\exists x) (\alpha) $ if and only if there is an element $a\in A$ such that $M\models \alpha [s[x|a]]$.

Let $M$ be an $L$-structure for some language first order language $L$. Let $(\exists x)(\alpha)$ be an abbreviation for the formula $¬[(\forall x )(¬\alpha)]$. Show that $M \models (\exists x) ...
1
vote
3answers
93 views

Does statement 1 imply statement 2?

1) (For some $t, P(t).) \implies Q$. 2) For all $t, (P(t) \implies Q).$ I think so, and my reasoning is this: for Q to be true, we just need P to be true for some t. Therefore, over the range of ...
2
votes
1answer
44 views

Express lattice axioms using implication and universal quantification

I'd like to ask for some help with homework. My task is to express lattice axioms in signature $(\leq, =, \sup, \inf)$ using only implication and universal quantification. Here are these axioms in ...
2
votes
2answers
87 views

Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
1
vote
1answer
342 views

How to prove these using natural deduction

I'd like to prove the following logical equivalence by using natural deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x)) \implies q.$$ As far as I'm concerned to show that two ...
5
votes
4answers
168 views

Is every theorem of PA true in the standard model of number theory $N$?

My understanding is that every theorem $\phi$ of $PA$ is true in $N$ because $N$ is a model for $PA$, $N\models PA$. By completeness of first order logic, "$PA\vdash\phi$" implies that "if $N\models ...
2
votes
3answers
91 views

Is $(m \Leftrightarrow m) \Leftrightarrow (m \Rightarrow m)$ a tautology, contradiction or contingent?

Is this a Tautology, contradiction or contingent? $(m \Leftrightarrow m) \Leftrightarrow (m \Rightarrow m)$ My answer is that It is a tautology. But what is yours? Can someone please explain with ...
0
votes
1answer
62 views

Does my logic statement make sense?

I'm trying to convert this sentence to logic notation. "there is an integer less than or equal to all other integers greater than 0". "An integer exists that is less than or equal to all other ...
1
vote
2answers
163 views

Predicate Logic - Is my answer correct?

Construct a predicate logic proof equivalent to the following natural language argument. “No athletes are bookworms. Carol is a bookworm. Therefore Carol is not an athlete.” Could someone please help ...
2
votes
1answer
86 views

Propositional Logic - Is my answer correct?

I have a question relating to Propositional Logic. Any help will be greatly appreciated. Without changing the meaning of the following formulæ, which rely on operator precedence to be interpreted ...
4
votes
2answers
201 views

First order theory of abelian groups and first order theory of cyclic groups are coincide?

Let $T$ be a first-order theory of cyclic groups. Even if an abelian group $(G,+)$ satisfy $(G,+)\models T$ there is no reason that $(G,+)$ is a cyclic. (For example, by Löwenheim–Skolem theorem there ...
2
votes
2answers
4k views

Using DeMorgan's Laws to complement a function

Using DeMorgan's Law, write an expression for the complement of $F$ if: $F(x,y,z) = x(y' + z)$. $F=x'+(y'+x)'$ $F(x,y,z) = xy + x'z + yz'$ $F=(xy)'(x'z)'(yz')'$ $F(w,x,y,z) = xyz' (y'z + x)' + ...
3
votes
4answers
176 views

How is $((X\to Y)\to X)\to X$ a tautology?

$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ converted to its disjunctive normal form is $X' + X$. Why/how does this show me why this formula a tautology?
2
votes
2answers
90 views

formula !x using only x and NAND

Hi how would I get formula that is equivalent to NOT X, using only the variable X and the NAND connective? Regards J
1
vote
1answer
132 views

Convert $(X\lor Y)\land(W \lor Z)$ to disjunctive normal form

Using the distributive laws, I need to convert the formula $(X\lor Y )\land (W \lor Z)$ into disjunctive normal form. The answer needs to be equivalent to this formula by means of a truth table. Can ...