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
98 views

Uniform continuity on empty set.

Let $\langle X,\rho \rangle$ be a metric space and $f:\emptyset\to X$ a function. Since $\emptyset$ is compact, I know that $f$ is uniformly continuous. But can it be proven by vacuous truth? It's the ...
7
votes
1answer
225 views

What are the formal properties of Godel numbering that are required to make it 'work'?

Godel numbering assigns a number to every formula. It appears to me that any encoding will do. However its also apparent, though I'm not sure how, that certain properties of the encoding used in Godel ...
6
votes
3answers
281 views

Formal definition of equation and unknowns

I was just wondering about the formal definition of equation, I mean in terms of logic and the theory of sets. Suppose for example I wanted to define an equation on $\mathbb{R}$, of course it might be ...
3
votes
2answers
146 views

Category-Theory and the modelling of $n$-ary functions (especially the $0$-ary functions)

Hi have a questioning regarding the modelling of $n$-ary functions and constants. First in the category of sets I know that the empty set $\emptyset$ is initial because for every other set $X$ there ...
2
votes
1answer
5k views

Boolean Algebra - Product of Sums

I converted from a truth table to sum of products and simplified that easily. What I am having problems with is simplifying the product of sums for that same truth table. I have: NOTE: $A' = ...
0
votes
1answer
52 views

Coding normalization

Working on a program that handles CNF (conjunctive normal form). If I have a formula like (a iff b) where iff is if and only if. I'd like to know which one of the following options is the correct ...
1
vote
2answers
2k views

Negating Quantified statements

The problem I am working on is: Express each of these statements using quantifiers. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express ...
2
votes
1answer
613 views

Determining The Truth Value Of Quantified Statements

The problem I am working on is: Determine the truth value of each of these statements if the domain consists of all integers. a) $∀n(n+1>n)$ b) $∃n(2n=3n)$ c) $∃n(n=−n)$ ...
0
votes
1answer
104 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
3
votes
3answers
960 views

Determining Whether Arguments Are Valid

The question is, "Determine whether each of these arguments is valid. If an argument is correct, what rule of inference is being used? If it is not, what logical error occurs? a) If $n$ is a real ...
2
votes
4answers
858 views

Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $

I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
1
vote
2answers
452 views

Logic gates analyses

How to write the output of the gates not, and, or, xor, nand and nor in terms of their inputs, expressed as zeros and ones, using base 10 addition and multiplication. Thanks much in advance!!!
0
votes
1answer
57 views

Does adjoining an induction schema to a theory of arithmetic interact nicely with adjoining its consistency statement?

I'm struggling to articulate this question, but here it goes. For any first order theory $T$ involving a unary function symbol $S$ (intuitively, the successor function), let $I(T)$ denote the theory ...
0
votes
2answers
143 views

Church's Thesis

If we let $f$ be a computable function and define $h(x) = 1$, if $x$ is an element of $\operatorname{dom}(f)$ and undefined otherwise. I am trying to prove that h is computable via Church's Thesis. ...
0
votes
1answer
403 views

URM computable indicating RAM computability

How can we show that every URM computable function is RAM computable? I can see that that from Church's thesis, URM Computability iff p.r., but now sure how to get this claim above. Taking the hint ...
0
votes
1answer
608 views

circuit in Conway’s Game of Life

Let's assume that the bits in the Moore neighborhood are numbere as follows: $$\begin{array}{lll} a_4 & a_3 & a_2 & a_{11}\\ a_5 & {\large a_0} & a_1 & a_{10} \\ a_6 & ...
1
vote
1answer
138 views

Moore neighborhood on a two-dimensional Cartesian lattice

How many distinct cellular automata rules are there that use the Moore neighborhood on a two-dimensional Cartesian lattice if we allow three bits (eight states) per site?
1
vote
1answer
785 views

Understanding common knowledge in logic and game theory

For $k = 2$, it is merely "first-order" knowledge. Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does ''not'' know that the other blue-eyed person ...
2
votes
3answers
124 views

Are PA and ZFC examples of logical systems?

Wikipedia says A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to ...
1
vote
2answers
49 views

For arbitrary theories T and S, is it meaningful to say “T proves the consistency of S”?

For arbitrary (first-order) theories T and S (where T needn't be a theory of arithmetic), is it meaningful to say "T proves the consistency of S"?
1
vote
2answers
378 views

Negate the following statements

1) For every shape A, there is a circle D, such that D surrounds A 2) There is a circle C, such that for every line l, l intersects C This is what I got are my answers correct 1) There is at least ...
4
votes
6answers
2k views

Does law of excluded middle prove itself?

Law of excluded middle says that for any proposition ($A$) either it is true or it's negation ($\bar{A}$) is true: $A\veebar\bar{A}$. When I was taught math logic, this was given as an axiom, but I ...
5
votes
2answers
153 views

Is it possible that two theories be equiconsistent, with Peano Arithmetic not able to prove this?

Do there exist first-order theories that are are equiconsistent, but which cannot be proven to be equiconsistent using Peano Arithmetic? (I hope not.)
1
vote
2answers
138 views

How can I prove the majority of three languages is also regular if the three languages are regular?

This is a question I've been stuck on recently: Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
3
votes
2answers
156 views

How bad is this analogy for logical independence?

It is an amazing and well-known fact that the Continuum Hypothesis is logically independent of Zermelo-Frankel set theory with the Axiom of Choice (ZFC), assuming it is consistent. In a similar vein, ...
4
votes
1answer
307 views

Gödel Completeness theorem

I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems. What I understand now (and you will see my understanding ...
4
votes
2answers
414 views

Is “reflexive transitive closure of relation $R$” a first-order property?

Suppose I have a language with two binary relation symbols $R$ and $R^\ast$. Suppose I have a first-order theory $T$ which says some things about $R$, but nothing about $R^\ast$. Is there a set of ...
2
votes
1answer
116 views

Are the brackets in formal box notation of recursive functions omittable?

So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
3
votes
1answer
108 views

Is first-order logic a sufficiently powerful metatheory to prove the “conditional independence” of CH from ZFC?

Lets define independence and conditional independence as follows. Define that an axiom $X$ is independent from a system $Y$ if and only if $Y$ can be used to prove neither $X$, nor its (syntactical) ...
4
votes
2answers
2k views

How to use the Rules of Inference to a statement from two premises

The problem is as follows: Given the premise ∀x(P (x) ∨ Q(x)) and ∀x((¬P (x) ∧ Q(x)) → R(x)) is true, use the rules of inference to show that ∀x(¬R(x) → P(x)) is also true. (The domains of all ...
3
votes
4answers
847 views

Quantified Statements To English

The problem I am working on is: Translate these statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) $∀x(C(x)→F(x))$ ...
1
vote
4answers
175 views

Would it also be useful to include an ordered pair function in first order logic?

Typically, first-order logic is assumed to include an equality relation $=$, even though this is "non-logical," together with some postulates about equality. Would it also be useful to include an ...
4
votes
1answer
136 views

Reference request - is there an axiomatic theory of consistency?

Is there an axiomatic theory whose domain of discourse can be interpreted as a collection of first order theories, which has a predicate $\mathrm{Con}$ such that $\mathrm{Con}(T)$ can be interpreted ...
2
votes
3answers
174 views

How to prove this with induction

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$ is the same as $$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$ Do I ...
2
votes
1answer
104 views

Successor axiom systems and sequences of axiom systems

Let $A$ denote a system of first-order axioms. Is there a canonical way to form a successor system $A'$ extending the ontology of $A$ to include all definable collections? Edit: Importantly we want ...
2
votes
2answers
3k views

Simplifying the following expression using Boolean Algebra

Simplify the following expression using Boolean Algebra into sum-of-products (SOP) expressions . refers to AND + refers to OR a'.b'.c' + a.b'.c' + a.b.c' This is what I have so far. a'.b'.c' + ...
2
votes
2answers
59 views

Definabilty of two functions on natural numbers

Is there a first order logic arithmetic ($0,+,\cdot$) formula $f(n,m)$ such that $f(n,m)$ is true in $\mathbb{N}$ iff $m$ is the $n$th prime number? Similarly, is there $g(k,n,m)$ which is equivalent ...
4
votes
3answers
674 views

Is A∨¬A a tautology when there is a proof (by contradiction)?

$A \lor \neg A$ is stated as a "tautology", but is it really a tautology? It can be proven by counterposition. And therefore it is not a tautology when it can be proven(?) Update Here's the proof ...
3
votes
1answer
786 views

Correct Path To Castle Riddle [duplicate]

I'm working on the following riddle that I found to be kind of interesting, but I can't figure it out. The problem is as follows: A prince visits an island inhabited by two tribes. Members of one ...
1
vote
2answers
554 views

Understanding Logical Inference Versus Logical Equivalence

Two statements are logically equivalent if they have the same truth table inputs and outputs. How do I know if one statement can be inferred from another? Does that just mean for inputs they share, ...
3
votes
1answer
125 views

Prove that a formal system is absolutely inconsistent

I'm using the book An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, and it does not have any solutions and barely any examples. I want to understand how to prove that all ...
0
votes
1answer
71 views

Completeness and consistency of system of calculus

It is widely held that ZFC cannot be shown to be self-consistent or complete. So, what happens to the system of calculus? Can it be shown to be complete or self-consistent? (Edit: Oops. So, two ...
4
votes
2answers
260 views

why does soundness seem to be less important than consistency for the structuralist?

If I am not wrong, many mathematicians (I believe this is not only restricted to structuralists) agree that an inconsistent formal system does not have any model. By model I mean some kind of set ...
10
votes
2answers
462 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
8
votes
1answer
750 views

Is “A and B imply C” equivalent to “For all A such that B, C”?

So I mostly study PDE, harmonic analysis, image processing, and so on, but for whatever reason I decided to be a TA for an undergraduate "introduction to proofs" course this semester. I suppose I ...
1
vote
1answer
319 views

Converse of Collatz Conjecture

How to write a pseudocode program that halts only if the Collatz Conjecture is false. Thanks much in advance!!!
1
vote
1answer
56 views

Uncountable models for a language $L_Q$

$L$ is first-order language with identity and $L_Q$ a language obtained by adding to $L$ the quantifier $Q$. Definition of $Q$: If $P$ is a formula and $x$ a variable, $QxP$ is a formula of ...
4
votes
2answers
76 views

Using Logical Operators in One Line

I am looking for a function that has this meaning: f(x)= if x>10 x+1 else x-1 or f(x)=x>10 : x+1 ? x-1 Similar to ...
1
vote
2answers
88 views

Is this negation correct?

The statement is: $\forall n \in \mathbb Z^+ \exists a \in \mathbb Z^+$ so that a|n and n/a is even The statement is false because there is a counterexample n= 1, a=1 correct? So its negation would ...
2
votes
2answers
176 views

How to show the statement is false?

How to do you show the statement is false and prove its negation is true? $$\forall n \in\mathbb Z^+ \exists a \in\mathbb Z^+ \text{ such that } a|n\text{ and }\frac na\text{ is odd}$$