Questions about logic and 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)

6
votes
3answers
298 views

Does a proof by contradiction always exist?

Good day, Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For ...
4
votes
3answers
195 views

How can one quantify on a function in ZFC?

I have read that $ZFC$ and first-order logic could formalize all the mathematics, but I do not manage to conceive that. First, let me show what my understanding of $ZFC$ is. I have read that $ZFC$ was ...
1
vote
1answer
680 views

How to convert this first order sentence into conjunctive normal form?

This is one of my homework, but it seems to be so complicated that I really do not know where to start :( $$ \exists x\;\forall y\;\forall z \Bigl({\rm person}(x)\land \bigl(({\rm likes}(x,y)\land ...
0
votes
1answer
120 views

Homework, how to use resolution to prove these inferences are valid?

I am kind of a layman in this area, and now I have to prove these: $P\rightarrow Q,\neg Q\vdash\neg P$ $P\rightarrow Q\vdash\neg Q\rightarrow\neg P$ $P\rightarrow Q, Q\rightarrow R\vdash ...
0
votes
1answer
78 views

Proving Formula Equivalence using Equivalence Laws

I'm taking Discrete Math for CS, and we went over Equivalence Laws the other day. Prove equivalence of f and g for: $f(x,y) = \lnot ((x \land \lnot y) \lor (x \land y))$ Test Case 1: $f(F,F) = ...
1
vote
1answer
40 views

X and Y are sets of sentences. If X is a subset of Y then Model(Y) is a subset of Model (X)

How do we show that for any sets sentences X and Y, and any sentences a and b, if X is a subset of Y then Model(Y) is a subset of Model (X)? Also, how to show that X union {a} is a tautological ...
1
vote
1answer
74 views

How many distinct functions for a set containing four elements? [closed]

How many distinct unary and binary functions can be defined on a set containing four elements? Edit: How many distinct unary and binary operations can be defined on a set containing four elements?
3
votes
3answers
159 views

$(∀x)(∃y)(x>y)$ is false. But then why is $ (∀x)(∃y)(x\geq y)$ true?

Given the Universe is the set of natural numbers, then $(∀x)(∃y)(x>y)$ is false. But then why is $(∀x)(∃y)(x\geq y)$ true? The first equation and the second equation is the same except for "=" in ...
1
vote
1answer
69 views

What is the logical interpretation of this set?

$\{f \in C : f(x)>d$ for each $x$ for some $d\}$ Do you read the above set as "the set of functions in $C$ such that there exists $d$ such that for each $x, f(x)>d$" or do you read the $d$ as ...
2
votes
2answers
121 views

Why is $\forall x \in A:P(x)$ equivalent to $\forall x (x\in A \to P(x)) $? [duplicate]

In the book that I'm studying from it defines $\forall x \in A: P(x)$ equivalent to $\forall x (x\in A \to P(x))$ without any explanation as to why it is that way. The same thing for the existential ...
1
vote
1answer
54 views

To validate the $ \exists x [E(x) \land C(x)]$

Show the validity of (1) $\forall x [M(x) \implies C(x)]$ (2) $\exists x[M(x) \land H(x)]$ (3) $\forall x [E(x) \implies H(x)]$ so, (4) $ \exists x [E(x) \land C(x)]$ ...
2
votes
1answer
44 views

Mathematical logic - alternative of conjuncion AND

I want to know if the word "also" do the same thing like "AND"? For example, there's a statement like this: All the students who are good at Maths also work hard. ...
1
vote
1answer
39 views

Proof for a stubborn nonstandard model

This a theory in the book Computational Complexity by Christos Papadimitriou, on Page 111, as a corollary of Godel's Completeness Theorem. It asserts: Corollary 3: If $\Delta$ is a is a set of ...
2
votes
2answers
120 views

The use of any as opposed to every.

This is a really basic question, but it is one I never really thought about until now. Let $\mathscr{G}$ be a tree. Then every pair of vertices in $\mathscr{G}$ is connected by a unique walk. We ...
1
vote
2answers
93 views

Proof $(P \land S) \rightarrow \lnot q$ in hilbert system

How can I proof $(P \land S) \rightarrow \lnot q$ using this principles : $p \rightarrow (q \lor r) $ $q \rightarrow \lnot r $ $r \leftrightarrow s $ in Hilbert system and modus ponens?
4
votes
1answer
136 views

Determining the truth value of certain quantifiers based on this proposition being false.

Can you help me verify if I answered this question correctly? Consider $[(\forall x)(P(x)) \land (\exists x)(\lnot Q(x))] \implies \{(\forall x)(P(x)) \iff [\lnot(\forall x)(R(x)) \lor ...
0
votes
2answers
31 views

Discrete: Boolean Function

~(pV~q) v (~p^~q) is equal to ~p? I know the answer is yes and I've been using DeMorgans initially then distributive law after. However I keep messing up on the algebra. Help is appreciated so I can ...
1
vote
2answers
80 views

How do I show that a statement is true (Discrete Math)

How do i show that this statement is true? $$\forall x,y,z,w \in \mathbb{Z}\space \space xSy \wedge zSw \implies (x+z)S(y+w)$$ The relation S is defined with: $$ xSy \Leftrightarrow (x + y ...
2
votes
1answer
94 views

Which quantifier to include while converting implication to disjunction

Given a statement: Anything anyone eats and isn't killed by is food, I formed a predicate for it like: $$ \forall x \forall y ~ \operatorname{eats}(x,y) \land \lnot \operatorname{killedby}(x,y) ...
0
votes
2answers
83 views

How to take more than two in logical quantifiers

Let the universe of discourse be all humans. Let $F(x,y)$ denote $x$ is a friend of $y$. Stating the following logically: No one has more than two friends. $$ \neg ( \exists x \exists y \exists ...
1
vote
1answer
69 views

Question about using the modus ponens and modus tollen

How would i solve the following. Use the following premises to show the conclusion is t. $p\vee q$ $q-r$ $p\wedge s-t$ $\neg R$ $\neg Q-U \wedge S$ $-$ for if then in this question. I did the ...
1
vote
3answers
68 views

Is this argument correct?

A Porsche is a fast car. Dan's car is not a Porsche. Therefore, Dan's car is not fast. Let P(x) be a Porsche Let C(x) be a fast car Let x be Dan $$P(x) \rightarrow C(x) :premise$$ $$\neg P(x) ...
1
vote
1answer
76 views

Getting into formal logic

I found myself the motivation to translate some statements and either prove them in a specific setting (assumed premises) or at least decide on their provability. However, I have very little ...
1
vote
2answers
201 views

brain teaser: Mr. Honest, Mr. Liar, and Mr. Drunk

There are 3 guys, Mr. Honest, that always give the truth answer; Mr. Liar, that always give the false answer; and Mr. Drunk, that gives a random number. Now: allow you to ask 3 questions, each to be ...
1
vote
2answers
54 views

For what $a \in \Bbb R$ does $\neg(3a>21\implies a \leq 5)$ hold?

For what $a\in\mathbb{R}$ will the statement $\neg(3a>21\implies a\leq 5)$ hold? My gut feeling says $a>7$, but I do not know how to formally write it down or prove it. Can someone help me?
1
vote
2answers
162 views

When is $(\forall x \in U, P(x)) \implies (\exists x \in U, P(x))$ false?

Consider the statement $$(\forall x \in U, P(x)) \implies (\exists x \in U, P(x))$$ Write down a domain $U$ and a predicate $P$ for which this statement is false. What property exists that ...
0
votes
0answers
124 views

Definitions of different kinds of recursive reducability.

So this is just a definition check. In recursion theory we have many kinds of reduction, according to my notes we have $\leq_1,\leq_m,\leq_{tt},\leq_{wtt},\leq_{TT},\leq_{T}$. Now I can't for the ...
0
votes
4answers
80 views

How should I interpret a “but” when symbolizing logic statements?

If it is wednesday then I won't study, but if it rains then I will study and watch TV Let's make that into propositions: $P:$ It is wednesday $Q:$ I will study $R:$ It rains $S:$ I will watch ...
0
votes
1answer
23 views

How can I tell when an equivalence demonstration can be done bidirectionally?

I've been doing exercises that ask me to prove set equivalences like this: $(A \triangle B) \cup (A\triangle C) = [A - (B \cap C)] \cup [(B \cup C) - A]$ To prove them equivalent, there are two ...
2
votes
1answer
52 views

Equivalence between temporal logic and notions of forcing

I have come across literature comparing modal logic to forcing (by Hamkins et al). Has anything similar been done showing equivalences between temporal logic and forcing? This would be interesting to ...
2
votes
2answers
189 views

Steps to simplify a Boolean Expression

Simplify: (x ∧ y) ∨ (x ∧ ¬y) ∨ (¬x ∧ y) I need to simplify this using the using properties going step by step. I keep ending up with (x ∧ y) as the answer but when I map is out I get that is should ...
0
votes
1answer
137 views

Quantification and logical relations, shorthand notation $\forall/\exists x \in M…$

I know the following shorthand: \begin{align*} \exists x \in M : P(x) & := \exists x ( x \in M \to P(x) ) \\ \forall x \in M : P(x) & := \forall x ( x \in M \to P(x) ). \end{align*} Now for ...
3
votes
0answers
61 views

Question on a Theorem from Chang-Keisler's Model Theory concerning $\Sigma^0_n$ sentences

The Theorem is 3.1.11 and states that for $n>0$ the following are equivalent : $\phi$ is equivalent both to a $\Sigma^0_{n+1}$ and a $\Pi^0_{n+1}$ sentence. $\phi$ is equivalent to a Boolean ...
5
votes
3answers
114 views

Does the placement of the quantifier make any difference in the following examples.

I have trouble understanding if the placement quantifier matter in these following problems. Problem One: Nobody in calculus class is smarter than everybody in the discrete math class. Let S(x,y) ...
2
votes
1answer
88 views

“Generalization” of Gödel's Theorem

One question came to my mind while arguing with a friend about the necessity of Judges in society (I will explain...) In the reasoning, we came across the following argument: "If we put up a good ...
3
votes
1answer
73 views

A query about countability

Suppose we are working in an elementary context where we want to keep background assumptions modest (not take a stand on fancy issues in set theory, say). What should our attitude be to the idea of ...
0
votes
2answers
89 views

Discrete Mathematics - Logical Equivalence

I am stuck on the following problem: Without using a truth table, show for statements $P$ and $Q$ that $$\neg (P\vee((\neg P)\wedge Q)) \equiv (\neg P)\wedge(\neg Q)$$ Using De Morgan's laws ...
1
vote
1answer
136 views

Writing a proposition as the conjunction of two conditional statements

For each integer a, a is congruent to 3(mod 7) if and only if (a^2 + 5) is congruent to 3(mod 7). A)Writing a proposition as the conjunction of two conditional statements B) determine if the ...
1
vote
1answer
64 views

How to prove that $A \bigwedge ( \bigvee_{1< i <\infty} C_i) \equiv \bigvee_{1<i<\infty}(A\bigwedge C_i) $?

Suppose that $A , C_i$ are propositional formulas ( or for simplifications , variables ) for any $i \in \mathbb{N}$ , How to prove that $A \bigwedge ( \bigvee_{1 \leqslant i <\infty} C_i) ...
1
vote
2answers
36 views

How should I begin when trying to determine a proposition whose truth value is unknown?

I've been doing many exercises that ask me something like With whatever sets X, Y, A, and B, determine the truth value of $(X \subseteq (A \triangle B) \land Y \subseteq A) \implies X \cap Y ...
0
votes
1answer
85 views

If we have the vocabulary {$+,<,1,2,3$}, what does “$4$” mean?

I'm doing some logic exercises, a part of them is determining if a few formulas are sentences, satisfiable, tautologies and so on. We have that $\mathcal{V}$ is the vocabulary {$+,<,1,2,3$} with ...
1
vote
1answer
78 views

What can be proven within Simply Typed lambda calculus?

I was reading http://en.wikipedia.org/wiki/Simply_typed_lambda_calculus and I'm having a hard time thinking of anything remotely interesting that can be proven within Simply Typed lambda calculus. Am ...
0
votes
1answer
59 views

Enumerating relations that are true infinitely often

Let us concentrate on relations on natural numbers. Is it possible to enumerate all computable unary relations that are true infinitely often? I would guess no but I can't see a direct way to prove ...
1
vote
2answers
87 views

“Proof by Contradiction”

Proving a theorem $A \Rightarrow B$ (i.e. if $A$ is true then $B$ is true) by contradiction means: Assume $B$ is not true, and arrive at $A$ is not true. Consider a theorem of "if and only if" ...
5
votes
1answer
149 views

Can logic be significantly geometrised?

I've already asked this question on philosophy.stackexchange, I'm hoping for a different answer here: Descarte has been lauded for putting together geometry and algebra, and his achievement allowed ...
0
votes
1answer
54 views

First order logic derivations

I need to prove a variety of derivations of the first order formula $F$ using axioms and inferences rules of the proof system for first order logic. These are: \begin{gather} \vdash F \vee (F ...
1
vote
1answer
51 views

First Quantifier Rule Questions

I need a little help with the proof of the validity of the first quantifier rule. So let $F \rightarrow G$ is valid in a structure $S$. I must prove that $\exists F(x) \rightarrow G$ is valid in ...
1
vote
2answers
54 views

How to read this logical statement in English?

Statement: ∀n ∈ Z, [(P(n) ∧¬(n=2)) ⇒ O(n)] where Z is a set of natural numbers P(n) is the predicate "n is a prime number" O(n) is the predicate "n is an odd number" I got this, but I don't think it ...
1
vote
1answer
138 views

Proof by contradiction by first assuming proposition true?

In a proof by contradiction, we first assume a proposition $P$ false, then prove some known truth to be false, then that would imply the assumption $P$ should really be true. Do we really need to ...
1
vote
1answer
46 views

Propositional Logic - Semantics

Is it the case that: $\models(p_{2}\to p_{0}) \to p_{0}$? I took the liberty to rewrite the given expression into Boolean algebra $$(p_{2}\to p_{0}) \to p_{0} \approx (p_{2} \land \neg p_{0}) \lor ...