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)

2
votes
2answers
169 views

What is a Complex Name?

On Page 38, Elementary Set Theory with a Universal Set, Randall Holmes(2012), which can be found here. We give a semi-formal definition of complex names (this is a variation on Bertrand ...
1
vote
3answers
215 views

Given an Inconsistent Set, find a Consistent Subset

I'm a student learning first-order logic, so forgive me if this is elementary. If I'm given an inconsistent set (that is, a set $\Sigma$ that can be used to show $\phi$ and $\lnot\phi$), is it ...
4
votes
2answers
2k views

How do you make a universal quantifier a existential quantifier in a multiple-quantifier statement?

So I'm studying for a final- and one of the study questions is "Express (as simply as you can) each of the following sentences without the use of universal quantification:" a) (∀x)(∃y)(∀z)[P(x,y,z)] ...
0
votes
1answer
268 views

First Order Logic Consistency and Compactness

First order logic: "consistency," "compactness"? Consistency: A set sigma ⊆ WFF is consistent iff there is no ϕ ∈ WFF such that sigma ⊢ ϕ and sigma ⊢ (¬ϕ) Compactness: A set sigma is consistent iff ...
1
vote
2answers
50 views

Logic - Will a second parameter value inherit negation if the first parameter is false?

Will a second parameter value inherit negation if the first parameter is false? Like: (~A & B) → X Is B false? Would it ...
3
votes
1answer
191 views

Consequences of axioms of Dense linear order without endpoints is complete

I've been musing over this problem over the past few days, and believe I have an answer. However, I am still a bit shaky with some of the definitions I am using, and would appreciate if anyone could ...
2
votes
2answers
74 views

In unification, what cannot be unified?

Looking at various examples online, some seem concrete, but some seem to not be explained properly. Can $f(x)$ be substituted with $g(x)$? I know that $x$ cannot be substituted with $f(x)$, but $x$ ...
5
votes
7answers
597 views

What are some examples of subtle logical pitfalls?

Here's an example: Demonstrating that the assumption $A=B$ leads to a true statement is a vacuous truth. In order the show that $A=B$, prove that the difference $\Delta =A-B$ is zero. The subtle ...
22
votes
1answer
510 views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...
4
votes
3answers
920 views

De Morgan's Second law

De Morgan's second law makes sense: not p and q is the same as not p or not q. However, when I tried to construct a sentence as an example of the law, it seemed not true. For example: Sequa does not ...
1
vote
1answer
85 views

What is/How to do Unification

I'm reviewing for a final exam on Monday, and I have a question I was unable to answer on a previous test. The professor's notes were horrendous, and I can't find anything better online. They all seem ...
0
votes
1answer
241 views

First Order Logic Example of Halting Problem

I am trying to understand the halting problem better. What would be a few examples of some first order formulas that express a halting problem? Any responses would be appreciated! Thank you!
8
votes
3answers
270 views

Does negation of Axiom of Choice imply symmetry?

It seems that every construction of a model in which the Axiom of Choice fails involves some kind of symmetry. Is there an example of a construction of a model where AC fails but no argument involving ...
1
vote
0answers
219 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
6
votes
4answers
3k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
2
votes
1answer
169 views

Does elementary embedding exist between two elementary equivalent structures?

By previous question, if there is a elementary embedding from $\mathfrak A$ into $\mathfrak B$, then $\mathfrak A \equiv \mathfrak B$. Now it is naturally to ask conversely, if $\mathfrak A \equiv ...
1
vote
1answer
227 views

Is one structure elementary equivalent to its elementary extension?

Let $\mathfrak A,\mathfrak A^*$ be $\mathcal L$-structures and $\mathfrak A \preceq \mathfrak A^*$. That implies forall n-ary formula $\varphi(\bar{v})$ in $\mathcal L$ and $\bar{a} \in \mathfrak A^n$ ...
1
vote
2answers
550 views

What is definability in First-Order Logic?

Can someone explain to me the definition of definability in first-order logic in simple terms and with an example? I would appreciate this. I just want to really understand this. Thank you. Here is ...
3
votes
2answers
311 views

Automorphisms of saturated models

This is basically Exercise 10.1.5(c) in Hodges's Model theory. First, a reminder of some definitions: Let $\lambda$ be a cardinal, and let $\Sigma$ be a finitary first-order signature. A ...
0
votes
2answers
75 views

Number mapping function

I can't find out a function f(x)=y that would map my x's to required y's. It is OK to write it in a programming language. Notation in mathematics is also OK. It ...
2
votes
3answers
145 views

Are these two statement equivalent?

$\forall x \exists y P(x,y)$ $\exists x \forall y P(x,y)$ where P(x,y) means x is smaller than y. I believe that they mean the same thing.
1
vote
3answers
195 views

Are these statements equivalent (quantifiers)?

$\neg \forall x \exists y \neg P(x,y)$ is equal to $\exists x \exists y \neg P(x,y)$ I had to make sure, because I wasn't sure at all.
4
votes
3answers
160 views

Want to show Quantifier elimination and completeness of this set of axioms…

Let $\Sigma_\infty$ be a set of axioms in the language $\{\sim\}$ (where $\sim$ is a binary relation symbol) that states: (i) $\sim$ is an equivalence relation; (ii) every equivalence ...
0
votes
2answers
215 views

Discrete Math Logic Homework

Consider the following statement: $$\forall \epsilon > 0,\space\exists\delta>0:(|x-a|\lt\delta\implies|f(x)-L|\lt\epsilon).$$ (a) Write the converse of the statement.(b) Write the ...
1
vote
1answer
206 views

Stuck on simple relations between sets

Find the relations between A, B and C when $[(A\cap B)\cup C]-A=(A\cap B)-C$ So we can write it as: $[(A\cup C)\cap(B\cup C)]-A=(A\cap B)-C$. Here comes the problem, though. Can I just assume ...
1
vote
4answers
142 views

How to prove this logic?

How to prove $\exists x (P(x) \lor Q(x)) \equiv \exists x P(x) \lor \exists x Q(x)$ I know it is tautology... but how to solve...? Please help.
3
votes
1answer
113 views

Feferman-Vaught theorem and Term Powers

In an example of usage of quantifier elimination in wikipedia, it briefly mentions Feferman-Vaught theorem and Term Powers, but I am finding little information on what these are. Can anyone explain ...
0
votes
1answer
192 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...
0
votes
2answers
123 views

Is this equivalence true?

Is this equivalence true? $(\forall x (P(x)) \wedge (\exists y Q(y)) \equiv \forall x \exists y(P(x) \wedge \exists x Q(y))$ Here is what I did so far. If the LHS is true, then there exists a x ...
1
vote
1answer
66 views

ZFC Union axiom

Maybe I'm just need to buff up on my logic notation, but I don't fully understand the following: $$\exists y\forall z \left(\exists w(z\in w\wedge w\in x)\implies z\in y\right)$$ How should I ...
0
votes
1answer
35 views

How to Understand Collection Principle in the Form of First-order Predicate Calulus

On Page 65, Set Theory, Jech(2006), Collection Principle is formulated as follows: $\forall{X}\exists{Y}(\forall{u}\in{X})[\exists{v} \psi(u, v, p) \to(\exists{v\in{Y}}) \psi(u, v, p)]$ ($p$ is ...
2
votes
1answer
332 views

Translate the following argument into symbolic notation.

Translate the following argument into symbolic notation. Use $P(x)$ for "$x$ is purple", $Q(x,y)$ for "$x$ questions $y$" and $R(x)$ for "$x$ is ridiculous". Somebody who is purple questions ...
0
votes
1answer
58 views

Question on Peano Arthmetic

This problem concerns the Peano Arthmetic. Px denotes: “x is prime”; that is: Show that a) ∀x∀y [(Px ∧ Py ∧ x|y) --> x=y] b) ∀x∀y∀z∀u∀v[Px ∧ Py ∧ Pz ∧ Pu ∧ Pu)-> x∙y∙z≠∙u∙v]. I am really clueless ...
5
votes
1answer
737 views

Why can't reachability be expressed in first order logic?

I'm wondering why we can't express graph reachability in first order logic in pretty much exactly the same way we express it in second order existential logic. For SOL, one definition is : 1 . L is ...
1
vote
4answers
367 views

Knights and Knaves

A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie. You meet four inhabitants: Bozo, Marge, Bart and Zed. Bozo says," ...
1
vote
1answer
209 views

What does the complement mean as it relates to Boolean Algebra?

For a lattice to be a Boolean Algebra it must be a distributive lattice and contain complements. What does the word complement mean?
4
votes
1answer
92 views

Proofs whose length depends on the input

This may be a question from proof theory, but I'm not sure, since I don't know any proof theory. What I will be asking about is what happens, if the length of a proof isn't fixed: I'm going to present ...
5
votes
1answer
125 views

Tarski's Undefinability Theorem Reference

There are many books articles that look to explain Godel's Incompleteness Theorems for laymen. Does anyone know of some good material (free online is most appreciated) that attempts to do the same ...
5
votes
2answers
186 views

Trying understand a move in Cohen's proof of the independence of the continuum hypothesis

I've read a few different presentations of Cohen's proof. All of them (that I've seen) eventually make a move where a Cartesian product (call it CP) between the (M-form of) $\aleph_2$ and $\aleph_0$ ...
1
vote
1answer
361 views

Evaluating Logical Statements

The problem I am working on is, "Analyze the logical forms of the following statements: (a) Alice and Bob are not both in the room. (b) Alice and Bob are both not in the room. (c) Either Alice or ...
8
votes
3answers
361 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
1
vote
5answers
150 views

How to show $A-B \subseteq C \Rightarrow A\cup B \subseteq B\cup C$?

I really need help with this logical proof. Show that $A-B \subseteq C \Rightarrow A\cup B \subseteq B\cup C$. Please show the steps to the solution. Thank you!
3
votes
2answers
158 views

Should I perform a disjunctive syllogism directly on three expressions simultaneously?

Consider $$\begin{align*} &1.\quad \lnot R \lor \lnot T \lor U\\ &2.\quad R\\ &3.\quad T \end{align*}$$ It seems clear that you can end up with this: $$4.\quad U$$ Now then, number $4$ ...
6
votes
1answer
191 views

Is Zermelo set theory finitely axiomatizable?

I know that ZF is not finitely axiomatizable, but what about Z (i.e. ZF without Replacement)?
2
votes
1answer
1k views

Difference between conditional and biconditional statement

So, I can see the difference between something like: A. A car is green if it is made in England. and B. A car is green if and only if it is made in England. Then, if you had a Russian-made green ...
0
votes
1answer
80 views

Verify these logical equivalences by writing an equivalence proof?

I have two parts to this question - I need to verify each of the following by writing an equivalence proof: $p \to (q \land r) \equiv (p \to q) \land (p \to r)$ $(p \to q) \land (p \lor q) \equiv q$ ...
1
vote
1answer
142 views

Prove/disprove this logical equivalence using basic equivalences?

I need to prove/disprove the logical equivalences of the following statement using basic equivalences: p→(q→r) and q→(p→r). I can do everything apart from the proofs in my work :/ Thank you if you ...
-1
votes
1answer
117 views

Need some help with some mathematical proofs (logical equivalences and normal proofs) [closed]

I need to prove/disprove the logical equivalences of the following two statements using basic equivalences: $p \to (q \to r)$ and $(p \to q) \to r$. $p \to (q \to r)$ and $q \to (p \to r)$. I ...
17
votes
3answers
4k views

Gödel's ontological proof - How does it work?

Gödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. Can someone please explain what those symbols are, and explain the proof? Thanks. $ ...
1
vote
3answers
142 views

Logic: Functions and statements

What is the relationship between the concept of an equation (a statement) and the concept of a function (and the concept of morphisms in category theory)? I'm going to use equations as the most ...