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

Predicate Logic Proof Question

I am struggling really hard with proofs I cannot seem to understand them at all no matter how hard i try. I'm thinking of getting a tutor because questions like this I just give up and fail on. Any ...
2
votes
4answers
94 views

How to prove $C$ from $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$?

How does one prove $C$ from the premises: $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$ ? I've tried to prove $C$ by contradiction, using a sub-proof which presumes $\neg ...
0
votes
0answers
13 views

Discrete math - logic [duplicate]

Can somebody please help me. How do I paraphrase this statement so that it doesn't have a negation anymore at all?
1
vote
2answers
352 views

Confused about how to use semantic tableau to answer questions of satisfiability

I'm taking a course in Mathematical Logic right now and we have to use semantic tableau to find out if a formula is satisfiable (some interpretations give a value of T). My question is: Given these ...
2
votes
1answer
78 views

A knights and knave problem involving a native with a speech disorder

On an island, every native is either a knight, who always tells the truth, or a knave, who always lies. You meet 4 natives, A, B, C, and D. This is what they say: A: "C is a knight iff D is a ...
0
votes
4answers
54 views

Logic - paraphrase propositions with negations to no negations

How do I paraphrase a proposition with a negation to not have a negation? I am thinking about this proposition
2
votes
1answer
68 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
2
votes
2answers
74 views

How is the implication introduction used here?

I don't understand how the implication intruductions, the ones marked with the subscript $2 $ and $3 $ are used here. As I unerstand it, the implication introduction is used when we have a derivation ...
0
votes
3answers
52 views

Simplifying a logical compound statement

I need to simplify $(p \vee r) \wedge (\neg p \vee \neg r)$ (if possible and using the laws of logic) I tried to substitue $s: (\neg p \vee r)$ but that made it even worse. Can anyone suggest an ...
0
votes
1answer
78 views

Applying De Morgan's Law

I'm working on my assignment for Discrete Math and I'm not fully understanding how to do this question for it so I was wondering if anyone here could help show me how to do it properly; Use De ...
2
votes
2answers
81 views

How would I go from DNF to a simplified formula with less symbols?

Here's a DNF: $$(\neg A_1 \land \neg A_2 \land \neg A_3 ) \lor (A_1 \land \neg A_2 \land \neg A_3 ) \lor (\neg A_1 \land \neg A_2 \land A_3 ) \lor (\neg A_1 \land A_2 \land \neg A_3 )$$ And the ...
3
votes
0answers
91 views

Prove that $\Pi_{i \in I} \mathbf{A}_i \cong \Pi_{j \in J} (\Pi_{i \in I_j} \mathbf{A}_i)$ where $\{I_j \ | \ j \in J\}$ is a partition of I.

My problem is following: prove that $\Pi_{i \in I} \mathbf{A}_i \cong \Pi_{j \in J} (\Pi_{i \in I_j} \mathbf{A}_i)$, where $\langle \mathbf{A}_i \ | \ i \in I \rangle$ is an indexed set of similar ...
0
votes
2answers
88 views

How can i solve this logical problem?

This problem involves two people. Person A and person B. They can either always tell the truth, or always lie. When asked, person A replies that: "At least one of us is a liar". Does person A ...
0
votes
1answer
37 views

searching a number in 2D matrix

I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link ...
1
vote
1answer
75 views

Showing associativity holds over n elements

Say we have a set $X$, with an associative binary operator $*$. How can we show that for any string $x_1 x_2 \ldots x_n$, when we insert brackets or the operation $*$, we will always get the same ...
2
votes
1answer
37 views

Formal proof structure for $\forall n \in \mathbb{N}, P(n) \rightarrow \forall n \in \mathbb{N}, Q(n)$

I'm used to proving universal quantification claims (i.e. $\forall n \in \mathbb{N}, [P(n) \rightarrow Q(n)]$) by: Assuming an arbitrary number in the naturals, assuming the antecdent $P(n)$, doing ...
1
vote
1answer
69 views

$\neg P \lor P $ is always true.

$\neg P \lor P $. Why this statements is always true even if $P$ is undecidable statements . I can't understand it for $P$ undecidable in the other case I do ! help please ?
0
votes
1answer
31 views

how do i write a truth table for ∀n ∈ N, P (n) → P (n + 1).?

So i'm supposed to find a predicate such that: ∀n ∈ N, P (n) → P (n + 1) is true and write the truth table for it. So I chose the predicate: "11^n - 6 is divisible by 5 for every positive integer n". ...
1
vote
1answer
56 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
0
votes
1answer
96 views

How to write “Every positive real number has a unique positive real square root” in predicate logic

How to write the following in predicate logic? Every positive real number has a unique positive real square root
0
votes
1answer
97 views

How to write “The equation $ x^{2} + 2x + 1 = 0 $ has no solutions over the natural numbers” in predicate logic

How do we write the following in predicate logic? The equation $ x^{2} + 2x + 1 = 0 $ has no solutions over the natural numbers.
2
votes
3answers
55 views

Why does adding material implication as an axiom to propositional calculus make every formula provable?

I've made it to section 12 in Kleene's Mathematical Logic, which is about completeness. Surprisingly, I was able to understand how every valid formula is provable. However, one of the exercises he ...
0
votes
1answer
33 views

Defining predicates that are true in $\mathbb{N}$

I am a student taking an introduction to the theory of computation course. We have been introduced the simple induction. I was wondering is it possible to define a predicate that is either true or ...
1
vote
1answer
67 views

Structural induction on a set of binary trees

Here is a recursive definition for some set $T$ of non-empty binary trees. A single node is in $T$ If $t_1$ and $t_2$ are in $T$, then the bigger tree with root $r$ connected to the roots ...
0
votes
1answer
25 views

First order logic formula for complete graph with no self loops

I wanted to translate a party scenario where everyone shakes hands with everyone else into a first order logic statement. Since no one can shake hands with themselves, there can be no self loops. I ...
2
votes
1answer
31 views

Laws of equivalence

Need to proof using laws $$\lnot(p \land \lnot q) \lor q \equiv \lnot p \lor q$$ $\lnot(p \land \lnot q) \lor q$ $\equiv (\lnot p \lor \lnot(\lnot q)) \lor q\quad$ First De Morgan's law ...
0
votes
1answer
29 views

Does this three value logic have a name?

If I have three values and these truth tables: Or: $$\begin{array}{c|c|c|} & A & \text{true} & \text{false} \\ \hline A & A & A & A \\ \hline \text{true} & A & ...
1
vote
1answer
39 views

Give a natural deduction proof of $\varphi\vdash\top$, there $\varphi$ is any formula

As the title, the question is Give a natural deduction proof of $\varphi\vdash\top$, there $\varphi$ is any formula Could I do this proof by derive $\varphi \rightarrow \top$ with $ ...
0
votes
1answer
93 views

Negate these statements and then reexpress the results as equivalent positive statements

$$\forall a\in A,\exists b\in B:a\in C\iff b\in C.$$ $$\forall y>0,\exists x:y=ax^2+bx+c.$$ I can't get passed the first step on how to negate these statements.
0
votes
4answers
235 views

Show that if n is an integer and 3n+ 2 is even, then n is even using contradiction

Show that if $n$ is an integer and $3n+ 2$ is even, then $n$ is even, using a proof by contradiction. That's the question. So since we're using contradiction, I need to show that N is odd and prove ...
2
votes
2answers
63 views

Is it acceptable in formal logic to achieve proof by contradiction by obtaining the negation of the assumption made?

I am (re-)working through the Gensler logic book to refresh my command of formal logic. For the most part, he is using proof by contradiction to achieve results. I noticed that the proofs I am writing ...
1
vote
1answer
82 views

Natural deduction proof - I don't' understand the question

I am supposed to give a natural deduction proof of $$(P_1∨P_2), \neg P_1 ⊢ P_2$$ My assumption is $(P_1∨P_2)$ and I am going to derive $P_2$ from $\neg P_1$ or I am wrong? EDIT: Or I am going to ...
1
vote
1answer
124 views

How to prove that $P \rightarrow Q$ is equivalent with $\neg P \lor Q $?

In my book about Logic, which is called 'Language, Proof and Logic', by the way, there is explained that the conditional $ P \rightarrow Q $ is equivalent with $\neg P \lor Q$. There is another ...
1
vote
2answers
28 views

Logic question is it true

Exercise: $$\begin{align} (\forall x>2) &~:~ |x|<3 \tag{P1}\\ (\forall x\in\mathbb{R})(\exists\varepsilon > 0) &~:~-\varepsilon <x<\varepsilon \tag{P2}\\ (\forall ...
0
votes
0answers
33 views

proove logical consequence - my solution

I wounder if I have done right. You can find the question at Question 1b I know that $(1)$ $P_1∧(P_2∨P_3)$ ≈ $(P_1∧P_2)∨(P_1∧P_3)$ which means that these two formulas have the same thruth value in ...
0
votes
1answer
26 views

PA can define 6's multiplier?

Let set A be : {6, 36, 216, 1296 .....} i.e. A={ $6^k$} where $k \in \mathbb{n} $ In the Model PA, can PA define set A? I know PA can define set { $2^k$} and set { $3^k$}. However what about { ...
1
vote
3answers
105 views

Proof by contrapositive: $x^3 + 1$ is even if and only if $x$ is uneven

$x^3 + 1$ with $x \in \mathbb{Z}$ is even iff $x$ is uneven. I want to prove this using a proof by contrapositive, so this is my work: Assume that $x$ is even, so $x = 2k$ with $k \in ...
1
vote
0answers
113 views

Types realized in ultrapowers consisting of definable functions

Let $\mathcal{M}$ be a nonstandard model of arithmetic and let $M$ be its universe. Let $U$ be a nonprincipal ultrafilter over $M$ and let $\mathcal{N}$ be the ultrapower $\mathcal{M}^M / U$. Let $F$ ...
0
votes
0answers
28 views

Expanding a logical expression

I need help understanding the following notation. I tried to expand it and that's where I realized I didn't quite get it. How do you expand the following: $${\underset{i=1}{\stackrel{3}{\bigwedge}}} ...
2
votes
1answer
141 views

Building math theory on absurd axioms - reducing math to logic

I know similar questions have been asked and i know my terminology might be wrong but I am trying to come to an answer to whether math can be derived from logic. Wikipedia defines logic as use and ...
1
vote
1answer
25 views

Give the following expression in the form of a formula:

Does anybody know how to give the following expression in the form of a formula? Let $P$ be the set of all people, and let $K$ and $M$ be binary predicates on $P$ with the following ...
0
votes
2answers
58 views

Prove by Simple Induction that $12^n − 1$ is divisible by $11$ for each $n \in \mathbb N.$

Since $12^n-1$ is divisible by $11$ for small $n$ cases i.e. $(1,2,3,\ldots$, etc), I want to prove that $12^{n+1} -1$ is also divisible by $11$. what I wrote down: ...
3
votes
2answers
87 views

First order formula defining a predicate which asserts that a set is finite.

Is it possible to define a predicate in the first order language of set theory such that $F(x)$ is true iff $x$ is a finite set? I understand that FOL cannot assert that the domain of discourse is ...
1
vote
1answer
66 views

Propositional language has an independent set of axioms

Let $\mathcal{L}_0$ be the language consisting of all propositional symbols $A_n$, along with all formulas formed by using $\neg$ and $\to$. In other words, it is the smallest set $L$ such that $A_n ...
0
votes
4answers
42 views

propositional logic, does An have to be a numerical expression/equation?

So if the $propositional$ $symbols$ are $A_{n}$ for all $n$ in the natural numbers, does that mean that our statements are not in terms of sentences with true/false values (which can be represented by ...
2
votes
2answers
160 views

Is constructive proof of non-existence possible

Constructive proof construct(indicates) object that satisfies given predicate. Question is whether one can give constructive proof of non-existence of an object with given property e.g. that every ...
2
votes
3answers
139 views

propositional language. don't understand the definition?

I'm taking a mathematical logic class, and I don't understand this definition of the $propositional$ $language$, as given by my book: "The propositional language $\mathscr{L}_0$ is the smallest set ...
-1
votes
1answer
41 views

Valid inference or not?

(For some reason I can't write at the bottom). (1) For all real numbers $x$, either $p(x)$ or $q(x)$. (2) $a$ is a real number. (3) [Not sure I understand. Some help would be appreciated.] $$ ...
1
vote
2answers
160 views

What does completeness mean in propositional logic?

During one of the lectures in logic, My prof proved completeness and soundness of Hilbert system of axioms or simple axiom system as in ...
0
votes
0answers
89 views

Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...