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)

1
vote
1answer
75 views

The Uniqueness of the Join

This question deals with the same topic as can be found here; Uniqueness of meets and joins in posets. However, I would like to show the result - that the join of two given elements is unique - using ...
1
vote
2answers
547 views

Propositional Logic: Models/Counter-Models

I conducted an extensive search on Google, Math.StackE and ProofWiki before posting. Given the following task: (Given a single specification) Use truth tables to check if the specification is ...
4
votes
2answers
288 views

Natural deduction: $(\neg q \to\neg p)\vdash(p\to q)$ without Modus Tollens

Can anyone help me to obtain this result in natural deduction, without using modus tollens: $$(\neg q \to \neg p) \vdash ( p \to q)$$
0
votes
1answer
69 views

2 Sat proof with conjectures

I am trying to convert the following conjectures to implications to then draw the implication graph. The conjectures are: ...
2
votes
1answer
220 views

True and provably true sentences in a model. Are they the same thing?

In logic, it is said that each sentence in a (consistent) theory is either true or false in a given model. Checking the truth of a sentence in a finite model amounts essentially to finite enumeration ...
1
vote
3answers
214 views

Discrete structures Logic exercise

I am a beginner please help solve this What is the contrapositive of the statement: "If you understand the material, you will pass this test."
4
votes
2answers
212 views

Axiomatising Wellorder

It may be of use to recall what a strict total order is; namely a binary relation satisfying irreflexivity, transitivity and totality, as formalised below: $$\forall x(\neg P_{1}(x,x))$$ $$\forall x ...
3
votes
0answers
168 views

Defining “structured sets”

In his Notes on Set Theory (p. 44) Moschovakis defines: A structured set is a pair $U = (A,S)$ where $A$ is a set, the space of $U$, and $S$ is an arbitrary object, the frame of $U$. But even ...
0
votes
1answer
63 views

A set of formulas that classifies two-element structures

Give a set of formulas $\Gamma$ such that for any structure $\mathcal{A}=\langle A;-;-\rangle$ it holds that $\mathcal{A} \models \Gamma$ if $A$ has exactly two elements.
1
vote
2answers
149 views

Interested in a “more fundamental” proof for basic properties of the logical connectives

Starting with the classical propositional logic, is there a rather canonical way to prove that $$p\wedge q=q\wedge p$$ for the commutativity of the conjunction and analogously for the other properties ...
0
votes
1answer
177 views

Length of a formula in propositional logic

I've seen the following problem on a past exam question: Show that the length of a formula in $\mathscr{L}$ is equal to $4m+n+1$, where $m$ is the number of binary connectives and $n$ is the number ...
0
votes
2answers
571 views

$(p\lor \lnot q) \land (q \lor ¬r) \land (r \lor ¬p)$ is true $\iff$ $(p, q, r$ all have the same truth-values$)$

Explain why $(p\lor \lnot q) \land (q \lor ¬r) \land (r \lor ¬p)$ is True when p,q,and r have the same truth value and it is false otherwise. (Without using a truth table ) Please help me solve this ...
6
votes
3answers
127 views

Understanding properties and criticisms of a (specific) sequent calculus

In Ebbinghaus et al., Mathematical Logic, a sequent calculus with the following rules is used: (Ant) $\begin{array}{ll} \Gamma & \varphi \\ \hline \Gamma' & \varphi\end{array}$, if ...
1
vote
2answers
255 views

Proving ${\sim}(p \mathbin\& q)$ implies ${\sim p}\mid{\sim q}$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~(p & q), that ~p | ~q . Any ideas on how I should proceed; I have no idea...?
0
votes
1answer
56 views

Is this symbolic expresson correct?

Hello. I'd like to check my answer for 1. (g) $\forall$ x $\in$ A, P(x), $\forall$ y $\in$ A, C(y) $\wedge$ F(y), $\forall$ z $\in$A, C(z), T(x, y) $\implies$ T(x, z) Is this correct? Thank you
9
votes
3answers
289 views

Logically speaking, why can variables be substituted?

Suppose that $$a^2+a+1=b$$ Suppose also that $a=5/4$. What makes it valid to substitute $5/4$ into the first equation? Is it because equality is transitive?
0
votes
1answer
176 views

How would the venn diagram for this logical expression look like?

Given the expression: (p $\implies$ q) $\wedge$ (q $\implies$ r) I got rid of the implication to get: (¬p $\vee$ q) $\wedge$ (¬q $\vee$ r) I first drew 2 venn diagrams, the left hand side of the ...
6
votes
1answer
298 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...
1
vote
1answer
51 views

discrete mathematics relations question 2

I am a little confused by this relation R3 is a subset of Z×Z defined by (x,y) in the set R3 if and only if x>2y is it reflexive? Symmetric? antisymmetric? or transitive? i say its NOT reflexive ...
3
votes
1answer
184 views

Proof with quantifiers

$(\forall x)(\exists y)(x+y=0)$ $x$ and $y$ are real numbers The statement reads: for all $x$ there exists some $y$ such that $x+y=0$ is true. My proof is: take $y=-x$ Is this valid? I'm just ...
1
vote
1answer
162 views

Discrete mathematics Relations Question

if r2 is in the set of N*N ( natural numbers) with (X,y) in the subset of r2, if and only if x+y=0 is it reflexive? is it symmetric? is it anti symmetric? is it Transitive? i said it is reflective ...
4
votes
2answers
95 views

Crowding the boundary of non-constructivity without crossing it?

Can any sense be made out of my vague feeling that some proofs in Ramsey theory are as close as you can get to non-constructive proofs without crossing the line? Is there any way to make this ...
1
vote
1answer
81 views

Inference rules for equality

Suppose we need to prove a formula Q of the form x=y -> P(x,y). Obviously, the formula Q follows from the formula P(x,x). That is, there is an inference rule of the form: from P(x,x) infer x=y ...
0
votes
1answer
38 views

Is this negation correct for this statement?

¬(for all n in N, there exists m in N, g(m,n)) equivalent to: there exists n in N, for all m in N, ¬g(m,n) Is that correct? Thanks!
1
vote
0answers
78 views

Is this an 'only if' sentence, or a 'if' sentence?

The sentence is: Bertha eats only regularly if Anna does. The only abbreviations are: A: Anna eats regularly B: Bertha eats regularly Is this an 'only if' sentence or a 'if, then' sentence. Is it ...
1
vote
2answers
2k views

Duality discrete math problem

This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm The dual of a compound proposition that contains only the logical operators ...
1
vote
0answers
63 views

Fragments of first-order logic and the functions that preserve them - reference request.

Is there a good resource for learning about different fragments of first-order logic? At this point, I'm mainly just interested in the basic facts, nothing too deep, but preferably presented in a ...
2
votes
0answers
61 views

Countable Ultrahomogeneous Structures

I've been learning about countable ultrahomogeneous structures, where ultrahomogeneous means every isomorphism of finitely generated substructures extends to an automorphism of the whole structure. ...
0
votes
1answer
50 views

Question regarding wffs sets, and satisfiability.

Let A and B be satisfiable (in the way the term is used in mathematical logic, with wffs, etc.). How do I show that the union and intersection of A and B are both also satisfiable? I'm slightly ...
2
votes
1answer
133 views

a consistent model of $\mathbb{N}$ that isn't?

(This question arose from a homework question which asked me to prove that (1st order) induction is independent from the other (1st order) Peano axioms) Let $\mathcal{L}$ be the language of Peano ...
1
vote
1answer
251 views

Injectivity and Imdepotency implies Surjectivity

This question stem from Natural Deduction (FeedBack). The reason why I think it is justifiable to open this up as a separate question is that I am now considering other measures to show it, possibly ...
1
vote
1answer
353 views

Boolean formula over 64 Boolean variables X

This question comes from this homework assignment from ECS20 at UC Davis. Chess is played on an 8 x 8 board. A knight placed on one square can move to any unoccupied square that is at a distance ...
0
votes
2answers
86 views

Why is my logical notation wrong? What does my answer mean then?

Let D = {all programmers and all projects}, R(x) mean: "x is a programmer," ...
1
vote
1answer
191 views

Question regarding translating English into first-order logic

Someone asked this question: "A language $L$ that is regular will have the following property: there will be some number $N$ (that depends on $L$) such that if $s$ is a string in $L$ (a $string$ is a ...
1
vote
4answers
76 views

How would I go about writing this proof in a formal way?

Let c ∈ Z: Write a detailed structured proof to prove the statement: If c^5 + 7 is even, then c is odd. I started out like this: ...
4
votes
1answer
94 views

Negating $(\forall a \in A)(\exists b \in B)(a \in C \leftrightarrow b\in C)$?

I'm not quite sure how to go about doing this. When negating I know the quantifiers themselves will be negated meaning that $\forall$ would become $\exists$ and vice-versa. Also I know that ...
0
votes
2answers
50 views

Prove the following with equivalence statements.

I need to prove the following statement with equivalence statements. $\exists x \in D,(P(x) \Rightarrow Q(x)) \ \text{is equivalent to} \ (\forall x \in D, P(x)) \Rightarrow (\exists x \in D, ...
6
votes
2answers
3k views

Is the null set a subset of every set?

Ever since day one of of my Mathematical Logic course, this fact has really bothered me. I cannot wrap my head around how an empty set is a subset of every possible set. Could someone kindly explain ...
0
votes
1answer
43 views

Define domain $X,$ predicate $A(X)$ and $B(X)$

I'm having trouble creating a domain $X$ and the predicates $A(X)$ and $B(X)$ to for this set of sentences to be evaluated to be true or false. $(T)\quad \forall x \in X, (A(x) \rightarrow B(x))$ ...
1
vote
2answers
379 views

Proving ${\sim p}\mid{\sim q}$ implies ${\sim}(p \mathbin\& q)$ using Fitch

I am struggling with proving something in Fitch. How can I prove from the premise ~p | ~q , that ~(p & q). Any ideas on how I should proceed?
1
vote
3answers
67 views

Distributive properties of quanitifiers

What is the difference between $\forall x~(~P(x) \to Q(x)~)$ and $\forall x P(x) \to \forall x Q(x)$ To me they seem to be the same thing, what difference does it make where the quantifiers go?
2
votes
4answers
164 views

Proving logical equivalence: $P \Leftrightarrow P \vee (P \wedge Q)$

I'm a first year CS student about to write his first term test and this question is part of our practice package. I have not been successful in writing a sequence of equivalences to justify this ...
2
votes
2answers
521 views

Disjunctive normal form expansion

I do not understand this at all. Find the sum-of-products expansions of these Boolean functions. $F(x, y, z) = x + y + z$ $F(x, y, z) = (x + z)y$ $F(x, y, z) = x$ $F(x, y, z) = x y$ ...
0
votes
1answer
77 views

Is DFA (Deterministic Finite Automata) a kind of predicate?

When I read a book on computation theory, I found a interesting thing: A Language L was defined by a DFA(Deterministic Finite Automata) like this, L = {$\omega$ | the last input of $\omega$ causes ...
4
votes
2answers
130 views

Reading on Mathematical Logic

I am looking for books to read, so as to dive into mathematical logical and related disciplines like set theory, model theory, and topos theory. I have a decent background in category theory and ...
3
votes
2answers
116 views

What is the opposite of the statement “$X$ and $Y$ is true”?

Suppose there are two propositions $X$ and $Y$. What is the opposite of the statement "$X$ and $Y$ is true"? I am guessing it is that either $X$ or $Y$ or both of them are false. Is this ...
1
vote
3answers
1k views

I need to show the validity of the below arguments by using a truth table

I need to show the validity of $P \rightarrow Q$ $P \rightarrow R$ $\therefore P \rightarrow (R \wedge Q)$ Can i just show the truth table for $P \rightarrow Q$ and the truth table for ...
1
vote
3answers
80 views

Proving that a statement about $<$ is valid

I need to do assignment for my homework, in which I need to prove that the following statement is valid. $$ (s<t \text{ and } t<u)\implies(s<u) $$ I need to do this assignment using the laws ...
0
votes
3answers
165 views

Natural Deduction (FeedBack)

I am looking for feedback to three proofs (alternatively derivations) that I have constructed. The first is: Theorem. Injectivity does not imply surjectivity. Proof: Suppose $\{\phi\} \vdash ...
2
votes
2answers
146 views

Not understanding valid argument form with implies, modus ponens

I understand that if you have if p then q p $\therefore$ q that when "if p then q" is true, and you know p to be true, then it follows that q is true. What I don't get is: wouldn't you have to know ...