# Tagged Questions

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 ...

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 ...
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?...
2k views

### What Maths are the most important for Artificial Intelligence?

354 views

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 ...
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 ) ?
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?
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?
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 ...
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, ...
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 ...
62 views

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, ...
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 ...
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 ...
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 ...
50 views

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 ...
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!
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, ...
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 ,(,)\}$. ...
81 views

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.
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 ...
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). ...
### $(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?
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 ...