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
0answers
51 views

Finding simpler implied formulas while preserving contradiction

I have two Presburger formulas A and B such that $A\land B \equiv \text{False}$. From these I need to find shorter formula $A'$ such that $A \rightarrow A'$ and $A' \land B \equiv \text{False}.$ The ...
1
vote
1answer
99 views

$A*$ finite or infinite? (Set theory)

I have a question regarding the following: If $A$ is a set, then by $A*$ we mean the set of all finite rows of elements of $A$. Now suppose $A$ is finite. How big is $A*$, and how can you see that?...
8
votes
3answers
2k views

What Maths are the most important for Artificial Intelligence?

I am just curious about this. Please don't include anything about programming.
1
vote
3answers
354 views

Portia casket logic problem.

Two boxes, one is gold and the other silver. The sign on the gold box reads, "The portrait is not here." The sign on the silver one reads, "Exactly one of the two statements is true." Guess where the ...
0
votes
1answer
41 views

Question on the Truth Table

How do you find out the number of rows that is needed for the truth table. For example, for A => B is a 4x2 table. What about if we want to make a table for, say, A => ( P => R ) ?
0
votes
2answers
74 views

Proof in logic that $P \Leftrightarrow Q$ is the same as $ (P \lor Q) \rightarrow (P \land Q)$

How is it possible to prove that $P \Leftrightarrow Q$ is the same as $ (P \lor Q) \rightarrow (P \land Q)$ using logic laws?
1
vote
2answers
81 views

Proof in logic that $P \Leftrightarrow Q$ is the same as $ (\lnot P \lor Q) \land (\lnot Q \lor P)$

How is it possible to prove that $P \Leftrightarrow Q$ is the same as $ (\lnot P \lor Q) \land (\lnot Q \lor P)$ using logic laws?
5
votes
2answers
328 views

About proving that the Continuum Hypothesis is independent of ZFC

In Mathematical Logic, we were introduced to the concept of forcing using countable transitive models - ctm - of $\mathsf{ZFC}$. Using two different notions of forcing we were able to build (from the ...
3
votes
2answers
168 views

Converting open first order logic formulae to closed formulae

Let $A \in WFF_{FOL}^\Sigma$ be an open formula, ie. it has occurrences of free variables. How do you transform this formula into a closed formula $B$? It is my impression that you do this by adding, ...
2
votes
1answer
187 views

Hall's marriage Theorem and Tychonoff Theorem

I was reading this paper. In particular the second point. He proves the Hall's marriage Theorem for infinite family using the Tychonoff theorem on topological product of compact $T_2$ spaces and the ...
0
votes
1answer
62 views

Representability in a formal theory

A wff $\phi(v_{1}, \dots , v_{k})$ $represents$ a relation $R \subseteq N^k$ in theory $T$ iff for every $(n_{1},\dots,n_{k}) \in N^K$: $$ (n_{1},\dots,n_{k}) \in R \implies T \vdash \phi(\mathbf{n_{...
5
votes
2answers
230 views

In Whitehead and Russell's PM, does not identity imply existance?

At the end of ✳96.48, $ \sim(w=\overset{\smile}{R}‘max_R‘J_R‘x)$ is chosen over $ w\neq\overset{\smile}{R}‘max_R‘J_R‘x$, on account of the latter's implication of existence. But ✳13.02 states that ...
0
votes
1answer
66 views

In Whitehead and Russell's PM, when does an empty class $\Lambda$ become a member of generations $gen‘R$?

Take ✳97.45 for example. I can't think of an example where $\Lambda$ is a member of $gen‘R$. I wonder if $-\Lambda$ in $gen‘R -\iota‘\Lambda$ is needed at all. Please let me know if you can think of ...
4
votes
1answer
48 views

Basic Propositional Logic

I'm working through Thompson's Type Theory and Functional Programming. I've only read the first chapter and want to make sure I'm understanding the material. The first problem asks to prove the ...
4
votes
2answers
155 views

Why is the language of arithmetic usually $(+, \cdot, 0, s)$, not $(+, \cdot, 0, 1)$?

The formalized theory of arithmetic has usually $(+, \cdot, 0, s)$ as its language. However, from what we usually do in ring theory, it seems natural to use $(+, \cdot, 0, 1)$ as the language of ...
5
votes
1answer
122 views

Showing $2$ is not definable in $(\mathbb{Q},+)$.

As stated, I'm to show that $2$ is not definable in $(\mathbb{Q},+)$. I tried proving it by contradiction by showing that if $2$ were definable, then we could define $\mathbb{N}$ and multiplication ...
1
vote
2answers
45 views

Analytical approach to a quadratics problem

I'm a bit rusty on functions and this exercise got me thinking quite a bit. The function $y=x$ is tangent to the graph of a certain $g$ function in $x=0$. Function $g$ can be defined as: A)...
3
votes
2answers
113 views

Boolean Logic - Reduction - $a \vee (a \wedge b) = a$

How would I simplify / reduce the following equation using boolean identities/proofs? $$a \vee (a \wedge b) = a$$ So far I've used the distributivity identity and got $$(a\vee a) \wedge (a\vee b)$$ I ...
1
vote
3answers
81 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
1
vote
1answer
180 views

Advice on taking a Course in Logic.

Is a course in Mathematical Logic necessary for a well-rounded Mathematical education? I asked a question about taking a Set Theory course before and was advised to do so. However the course offered ...
1
vote
1answer
31 views

Reusing Variables First Order Logics

Assume we have a parametrized FO formula of this form: $$\varphi(x_1,x_2, y_1, \dots ,y_m) := \xi(x_1,x_2) \land \psi(y_1,\dots,y_m)$$ We want to use as few additional bound (quantified by $\exists$ ...
1
vote
0answers
164 views

Range/Image of a Non-Decreasing Total Recursive Function is Recursive

How do I show that the range of a non-decreasing, total-recursive function is recursive? I've made reference to this question, but the method used there is not clear to me. My attempt: Let $f$ be ...
1
vote
2answers
102 views

Can I use “: ,” instead of “, implies” for this example?

I've to write this statement in a formal manner: if $x>1$ then $x^{2}>1$. Writing the result of the exercise I face this problem, I wonder if these two statements are equivalent: $$\forall~...
2
votes
3answers
260 views

Do brackets around negation signify negating the input or output - Boolean Algebra Logic Circuits

I know that $\overline{p + q}$ will result in the input to the logic gate being p, and q, and we can negate this by using an or gate, followed by a not gate, or we can just use a nor gate. However, ...
2
votes
2answers
55 views

Is P XOR (IF P THEN L) equal to NOT (P AND L)?

I would like to reduce this statement:$$ P \veebar (P \implies B) $$ using only $\neg$, $\land$ I've found this solution but I don't know if I'm wrong: $$\neg(P \land B)$$ Because the book proposes ...
3
votes
2answers
186 views

Ultrafilter Lemma implies Compactness/Completeness of FOL

Apologies if this has been asked somewhere before, but I didn't see what I was looking for after several pages of Google results. I was reading Jech's The Axiom of Choice and was introduced to the ...
1
vote
1answer
169 views

Hilbert calculus: Proof that every provable formula has a proof

For my indroduction to logic course I have to proof, that every provable formula has a proof. It sounds first very funny, second also very logic, still I don't get to make of formally work.. The ...
1
vote
2answers
50 views

What is the proper way to prove this?

First of all, here is the question I am trying to answer for context. I can see that the statement $\forall x \in \mathbb{Z} , \exists y \in \mathbb{Z}((x\leq y ) \wedge (x+y=0)) $ negates to $\...
7
votes
2answers
309 views

New Axioms of Infinity

Axiom of Infinity says there is an inductive set (i.e. a set which includes $\emptyset$ and is closed under successor operator). Formally: $Inf:\exists x~(\emptyset\in x~\wedge~\forall y\in x~~~S(y)\...
1
vote
3answers
171 views

Basic question on Implication

Could anyone conceive of any predicates and Universe ( in mathematics, in the world, etc ) where we should use $\exists x ( P(x) \to Q(x) )$, and not necessarily $\forall x ( P(x) \to Q(x) )$ ? I was ...
-1
votes
5answers
98 views

Use the laws of logic to prove $(p∧q) \Rightarrow p$ is a tautology.

I have this problem on an assignment and I would like help with it: Use the laws of logic to prove $(p\land q) \Rightarrow p$ is a tautology. Thanks!
0
votes
3answers
87 views

Non-example of mathematical assertion.

In my logic class they gave this as a non-example of a statement. "Suppose n is divisible by 3." I can vaguely see why it is not a statement, but don't really see how I would defend that sentiment, ...
1
vote
0answers
54 views

Set of true statements generated by set of axioms with a binary operator

I wondered about this and I am having a hard time formulating it as a question at all, but I hope I can express something if my wondering here. Assume we have a set $V = \{\mathbb N, +, =, X ,(,)\}$. ...
1
vote
2answers
81 views

If $(P \lor Q) = (P \lor R)$ Can we conclude $Q = R$ ? What happens if we use AND instead of the operator OR?

So I am trying to solve this problem and not quite able to figure out the answer. So I'm not sure what two statements I could construct in my truth table to prove these true or false. I believe that $...
1
vote
3answers
555 views

How can I prove this statement by proving its contra-positive?

Prove the following statement by proving its contra-positive: If $ r $ is irrational, then $ r^{1/5} $ is irrational. I am totally confused! (1) How does proving the contra-positive prove ...
1
vote
2answers
68 views

What does it mean that “the constants true and false can represented with only nand”?

Does this statement mean that you can represent true and false without using AND or OR? I figured out that $ \lnot A\,\text{nand}\, A = \text{true}$ But how can I represent $ \text{false} $ without ...
2
votes
3answers
111 views

Logic counterexample to argument

$\sim \forall x \; (M(x) \vee W(x))$ $\exists x \; \sim M(x)$ $\exists x \; \sim W(x)$ This argument is invalid, could any one please provide a counterexample? The first two lines are the ...
1
vote
2answers
228 views

Is it possible to write this express with only nand and NOT?

Find an equivalent expression using only $ nand $ and $ \lnot $ as well as grouping parenthesis. You may use $ A $, $ B $ and the operators any number of times. (i) $ A \land B $ (ii) $ A \lor B $ ...
2
votes
3answers
95 views

Basic question concerning free variables

I - First doubt : free variables on open formulas . I'm having a hard time discovering what different kinds of variables in an open formula of fol are refering to., For example, lets take some ...
1
vote
1answer
55 views

How can i turn the Boolean Equation pq+r into a switch circuit?

How can I turn the Boolean Equation $pq+r$ into a switch circuit? I have synthesized this and drawn the NOR gates circuit however I'm not sure how to go about drawing/constructing the switch circuit.
0
votes
1answer
127 views

Confusion regarding Quadratic equations and RHS = 0

Recently, I am becoming confused with how it is said that in a quadratic equation you MUST make the RHS $ = 0$. But I am stumbling across many equations where it is calculated (The following is for ...
-1
votes
1answer
35 views

Applying De Morgans Laws to $a+bc+\overline{a}b\overline{c}d$ in terms of the NOR operator

I need to synthesize $f=a+bc+\overline{a}b\overline{c}d$ into the NOR form. Can I split this since I know that $a+bc=(a+b)(a+c)=\overline{\overline{a+b}+\overline{a+c}}$? I'm just not sure how to go ...
1
vote
1answer
120 views

Symbolic logic proof

Can any one please give me the correct proof for this, i got this far but i am stuck. Thank you!
1
vote
1answer
1k views

Propositional Logic simplification

I was wondering if anyone could help me to understand how this is simplified: P v (P ^ Q) The answer is: 1) (P ^ T) v (P v Q) - apply Identity. 2) P ^ (T v Q) - apply Distributive. 3) (P ^ T) - ...
0
votes
2answers
66 views

prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$

Let $A,B$ be two subsets of a set $X$,and let $f:X \to Y$ be a function.Prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$ So I first show what these sets are. The set $f(A) \backslash f(B)...
2
votes
1answer
68 views

Applying De Morgan's to express $pq+r$ in terms of NOR operator

In Boolean Algebras I have $pq+r$ which I think is the same as $(p+r)(q+r)$. Now, I need to use De Morgan's laws to synthesize this into the NOR form but I am not sure how to apply the laws here.
0
votes
1answer
37 views

Proving that operations give equal results given equal inputs

I was reading about the 9 or 12 basic properties of 'fields' (if that's what they're called) in a book called Spivak's Calculus, 3rd Edition, and got quite befuddled by dealing with as basic stuff as ...
3
votes
2answers
243 views

How to derive $\exists$ Elimination rule in Enderton's system

I'm trying to derive the following rule : from $α→β$, infer $(∃x)α→β$, provided that $x$ is not free in $β$ in the system of Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001). ...
1
vote
1answer
44 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
1
vote
2answers
95 views

Can I replace conjunction with implication here?

Using a model where the domain is $\mathbb{N}$ and one binary predicate $p$ exists, that returns $true$ if its second argument is divisible by the first one, show that each two numbers have a biggest ...