Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

0
votes
1answer
87 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
68 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
160 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
91 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
43 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
43 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
222 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
72 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
221 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
113 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
88 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
88 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
77 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
108 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
122 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
46 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
87 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
313 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
113 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
107 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
120 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
84 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
96 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
51 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
94 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
456 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
184 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
97 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
66 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
178 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
90 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
243 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
6k 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)' + ...
4
votes
5answers
240 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
105 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
159 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 ...
0
votes
2answers
42 views

Simplification of boolean algebra from “not s and p” to “not s”

I am trying to learn more about "Rules of Inference" and their application, but one thing always confuses me, and that is simplification "not s and p" to "not s". I have looked at some examples: ...
0
votes
2answers
107 views

See if “7<4 implies 7 is …” Is the following conclusion valid?

For my homework I need to see if the following conclusion is correct. $$ 7<4 \implies 7\ \text{is not a prime number}\\ \lnot(7<4)\\ -----------------\\ \text{7 is prime number}\\ $$ To tell ...
1
vote
1answer
73 views

Extending a Filter in a Well-Ordered Boolean Algebra to an Ultrafilter WITHOUT the Axiom of Choice

Hypothesis: Let $B$ be a well-ordered boolean algebra and let $F \subseteq B$ be a filter on $B$. Goal: Show that $F$ can be extended to an ultrafilter without the axiom of choice (or any equivalent ...
0
votes
1answer
164 views

Find a L-sentence which is true in a structure $M$ iff the universe $A$ of $M$ consists of exactly two elements

Find a L-sentence which is true in a structure $M$ iff the universe $A$ of $M$ consists of exactly two elements, where the language L consist a unary function $S$ and $2$-ary predicate $<$. This ...
0
votes
1answer
82 views

Rooted Trees & Induction

So I am a little stumbled upon this question: A full binary tree is a rooted tree where each leaf is at the same distance from the root and each internal node has exactly two children. Inductively, a ...
2
votes
1answer
467 views

Question: Prove that a set of connectives is incomplete using structural induction

The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}. Let F be the smallest set such that: 1) Any propositional variable is ...
0
votes
4answers
338 views

What is the answer to this syllogism? Why is option D incorrect?

Q.   a. Some books are not reference books.      b. All books are encyclopedias. A Some reference books are no encyclopedias B No reference books ...
1
vote
5answers
102 views

How to solve this class of problems?

I was presented with the following problem: Ricardo, Rogério and Renato are brothers. One of the is a medic, the other one is a teacher and the other one is a musician. It is known that: ...
2
votes
3answers
81 views

propositional calculus?

I'm very stuck on this question in my High School class. Atomic Sentances: I – I am hungry M – I will eat pie V - I will become lazy. B - I will be happy. Hypothesis: H1 – $I \implies M \land ...
2
votes
2answers
78 views

How to construct a term of a particular type

I am reading the article "Introduction to Type Theory" by Herman Geuvers, the chapter explaining the Fitch style of natural inference. I stuck at the exercise 1.3 (first two are simple): ...
2
votes
1answer
177 views

Is every Boolean algebra a separative partial order?

A partially ordered set $\langle P,\leq\rangle$ is separative iff it satisfies the following condition: \[ \neg x\leq y\Rightarrow\exists z(z\leq x\wedge z\bot y) \] where: \[ x\bot y\iff\neg\exists ...
1
vote
1answer
76 views

Noncontradiction behind the uniqueness proof and proof by mathematical induction

I'm walking through equivalences, as it appears, between $$\exists!x:P(x)\,\,{\overset{\mathrm{?}}{\equiv}}\,\,\exists x:P(x)\wedge(P(x_1)\wedge P(x_2)\rightarrow x_1=x_2),$$ where I am not sure what ...
3
votes
2answers
207 views

Second order logic and quantification over formulas

According to Wikipedia second order logic allows quantification over sets of individuals and thus goes beyond first-order logic, e.g. in expressive power. On the other hand some sort of ...
3
votes
3answers
213 views

Difference between “if $\vdash P$, then $\vdash Q$” and “$\vdash(P\Rightarrow Q)$”?

I have agonized about the difference between If $\vdash P$, then $\vdash Q$, $\vdash(P\Rightarrow Q)$. For example, in the axiom set of predicate logic, there are two similar axioms, called and ...