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
155 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
70 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
211 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
64 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
160 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
81 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
111 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
77 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
230 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
93 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
90 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
327 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
163 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
161 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
85 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
192 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
3k 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
174 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
130 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
95 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
67 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
66 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
68 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
223 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
246 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
98 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
78 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 ...
1
vote
1answer
64 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
90 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
69 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 ...
2
votes
2answers
161 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
175 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 ...
2
votes
3answers
41 views

Negating “If no one is absent, then if the weather permits, we will study outside”

I am a beginner; please help solve this. Write the negation of the statement: "If no one is absent, then if the weather permits, we will study outside."
5
votes
3answers
230 views

Showing that the Class of Cyclic Groups Aren't Axiomatizable

The class of finite cyclic groups are not axiomatizable, for if we supposed they were by some set of sentences $\Sigma$, then there would exist a model for $\Sigma$ of at least order $n$ for all $n ...