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)

1
vote
2answers
64 views

Absoluteness and Extensionality

In the set theory text that I am reading, the author writes: Relative to the set $A = \{ 0, \{\{0\}\} \}$, the sets $0$ and $\{\{0\}\}$ are indistinguishable in the sense that $[$for all $x$ in ...
1
vote
2answers
38 views

When can we do induction over the language defined by a formal grammar?

We can define the grammar of propositional calculus as $G=(\{S\},V_T,D,S)$ where $V_T=\{(,),\land,\lor,\Rightarrow,\Leftrightarrow,\lnot\}\cup\mathcal{P}$. $\mathcal{P}$ is the set of propositional ...
1
vote
1answer
53 views

elementary equivalence and incompleteness

I read the following line in a text on set theory: "Peano Arithmetic has continuum many non-isomorphic countable models (including the standard model omega), all of them elementary equivalent." ...
1
vote
1answer
36 views

Skolem Theorem private case, preserving extension

Question: Let T be a theory of statements over a signature $\sigma$ and $\phi$ is a formula over $\sigma$ s.t. $x,y$ are the only free variables. We define a signature $\sigma'$ by adding a new binary ...
0
votes
2answers
43 views

Possible interpretations for a predicate symbol in first order logic

PART A So, given as structure A :{1,2,3} and we are studying the languge of the real numbers. We are asked to say how many possible interpretations for the predicate symbol $<$. My question is ...
0
votes
1answer
32 views

Disjunctive Normal Form conversion

Could someone show step by step how to convert the following formula into DNF ? $$ (X \lor \neg Y ) \land (¬Z \lor \neg U \lor W) \land (S \lor \neg T) $$
2
votes
2answers
133 views

On what sets other than $\mathbb{N}$ might we use proof by induction?

Suppose we have a set $S$ with $s_1\in S$ and $f: S\to S$ and $n\subset S$ such that $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ ($n$ not necessarily infinite). To establish properties of $n$, can we ...
1
vote
1answer
61 views

ACF universal is the theory of integral domains

When studying David Marker's "Model Theory: An Introduction" book trying to understand the proof of Lemma 3.2.1 which says: $ACF_{\forall}$ is the theory of integral domains, I couldn't understand the ...
1
vote
1answer
48 views

A test for quantifier eliumination

In David Marker's "Model Theory: An Introduction" book I was trying to prove Corollary 3.1.12 which is left for the reader, but I couldn't reach any solution. The aforementioned corollary states: ...
1
vote
3answers
71 views

Is 'Some of x are true' a negation of 'All of x are true'?

I don't think this necessarily means there exists a false x, just that at least some x are true. Is my logic correct here in ...
0
votes
3answers
49 views

How can I further simplify (P ∨ ¬Q) → ¬(P ∨ Q)?

I am trying to simplify this equation, (it was more complex before the current point), but I'm stuck at this juncture, and am not sure where to go from here. I've used De Morgan's Law and the Rule of ...
0
votes
0answers
33 views

Prove that The set of Sentences over a theory $T$ is a Cartesian Closed Category

i am sorry to bother but, I have doubts with this problem: In some elementary theory $\;$ $T$ $\;$ consider the set $S=\{p,q,\ldots \}$ of sentences of $T$ as a preorder, with $p\leq q$ meaning "$p$ ...
3
votes
2answers
54 views

An AE axiomatization of groups

Let $L=\{*\}$. The usual axiomatization of groups in this language has the EA axiom $\exists{e}\forall{x}$ $ e*x = x$. But the union of a chain of groups is also a group. This means that the theory of ...
0
votes
4answers
63 views

Using a truth table to show that an argument form $(p\rightarrow q) \land q \rightarrow p$ is invalid.

Use a truth table to show that the following argument form is invalid. p$\rightarrow$q q ∴p My attempt: I made a truth table as below, but in what column and row can I find the argument form is ...
0
votes
1answer
22 views

Odd sized dictionary

Question: Let $\sigma$ be a signature that has only equality as a relation in it. Prove that there doesn't exist a statement $\phi$ s.t it's valid in M $\iff$ $|D^M|$ is odd. My problem: I think the ...
0
votes
0answers
35 views

Dominating function easier to understand

Is there a pair of function $f$ and $g$ (both $\mathbb{N}\rightarrow\mathbb{N}$ and definable in the language of first-order Peano arithmetic) such that asymptotically $f$ dominates $g$, and $f$ has ...
4
votes
0answers
105 views

What is forcing isomorphism? [closed]

This question is from Kunen's set theory book. My questions are: What is the definition of isomorphism between forcing notions? When do we say that two forcing notions $\mathbb{P},\mathbb{Q}$ ...
29
votes
11answers
5k views

Is $[p \land (p \to q)] \to q$ a tautology?

I am new to discrete mathematics, and I am trying to simplify this statement. I'm using a chart of logical equivalences, but I can't seem to find anything that really helps reduce this. Which of ...
0
votes
1answer
41 views

How to decide whether a logical formula is satisfiable

I'm trying to solve one logical problem. I have Language L={P} with equality (there can be '='). And we have 4 formulas an theories of this language. We have to ...
2
votes
1answer
35 views

Trouble with Discrete Math proof

This seemingly easy proof is giving me some trouble.. For every number n $\in$ $Z$, if $n>n^2+1$ then $n\leq0$. I find that proving the conditional statement P implies Q is false. For example ...
1
vote
2answers
29 views

Possible structures in first order logic

So i was studying about structures in first order logic and i saw a question of this form: Given a syntax A:{P} where P is 2-ary predicate symbol and {0,1} as universe we work. How many different ...
0
votes
1answer
13 views

Distributivity of lattice $\left(N,\:\le \right)$

The exercises asks me to prove/verify the distributivity of the lattice $\left(N,\:\le \right)$ I've no clue on how to approach this problem, because at the seminar we didn't really study lattices as ...
0
votes
1answer
61 views

A question about two theories and their models

Suppose $T_1$ and $T_2$ are two theories in the same language and that every model of $T_1$ is a model of $T_2$. I want to show that $T_2$ is contained in $T_1$, but although I think it is clear I ...
6
votes
6answers
156 views

Proof of induction principle, Proof falsification

I just had a very frustating conversation with one of my Professors. I'm tutoring for a lecture course on Analysis and in the lecture he gave a proof of the induction principle. I was trying to tell ...
0
votes
1answer
30 views

What is the value of 0 XNOR 1 XNOR 1? [closed]

We know that for 3 variables $(A=0,B=1,C=1)$, $f_1 = (A \mathop{\text{ XNOR }} B \mathop{\text{ XNOR }} C) = 1$, since the input has even number of $1$'s. But if we were to do this step by step, $f_2 ...
2
votes
1answer
87 views

Definition for non-dividing

The definition for non-dividing is taken as the negation of the definition for dividing (as found in http://www.math.cmu.edu/~rami/simple.pdf : Definition 1.1 for example). Thus assuming ...
4
votes
1answer
51 views

Write formulas in specific languages of group.

So, for each of the following groups write a formula in the language of group theory, which holds in given group, but doesn't hold in others two. $(i)$ The integers with addition \ I think it's ...
7
votes
4answers
511 views

Negation of injectivity

I'm having some problems understanding the negation of injectivity. Take the function $f: \mathbb{R} \rightarrow \mathbb{R}$ given by $f(x) = x^2$. The formal definition of injectivity is $f(a)=f(b) ...
0
votes
2answers
87 views

Why is $a \implies b$ is true when $a$ is false [duplicate]

I understand that: $True \implies True$, is true. $True \implies False$, is False. But why is it that $False \implies True$, is True. and $False \implies False$, is True. If $a$ is false I ...
2
votes
0answers
27 views

Compactness Theorem (Propositional Logic) and Compactness (Metric spaces). [duplicate]

Definition. A subset $E$ of a metric space $(X,\tau)$ is compact if every open cover of $E$ has a finite subcover. Theorem (Compactness Theorem). A set $\Gamma$ of formulas is ...
0
votes
2answers
40 views

Definition of non-injective function

Let $f\in F^{E}$ so to show that $f$ is non injective it's suffice to find distinct elements in $E$ with equal images. $$f \text{ is non-injective } \iff \exists (x,y)\in E^{2} \text{ s.t } x\neq y ...
2
votes
1answer
55 views

When can independence of a statement in a theory be reduced to “truth”?

Since the Goldbach conjecture is in $\Pi_1^0$, if it were proven to be independent of Peano Arithmetic, it would follow that the Goldbach conjecture is true (i.e. true in the standard model), since ...
4
votes
1answer
130 views

Can certain things never *ever* be proved?

I'm not familiar with logic beyond simple boolean operators and the standard mathematical tools (quantifiers, implication, proof by contradication, etc.) I've known for a while that Gödel's ...
35
votes
4answers
3k views

What's between the finite and the infinite?

I'm wondering if there are any non-standard theories (built upon ZFC with some axioms weakened or replaced) that make formal sense of hypothetical set-like objects whose "cardinality" is "in between" ...
0
votes
0answers
25 views

Expanding a randomized Two Envelope Problem

There is a previous problem called the Envelope Paradox with a detailed explanation and solution given here. In short, the problem involves two envelopes with random (on some probability distribution ...
0
votes
1answer
27 views

Boolean Problem Simplification

I am trying to simplify the boolean function F= ~A~BC + A~B~C + A~BC + AB~C + ABC and I know that correct answer is F= A + ~BC. My attempt is: ~A~BC + A~B(~C+C) + AB(~C+C) ~A~BC+ A(~B+B) ~A~BC + A ...
2
votes
1answer
56 views

If $M[G] \subseteq M[H]$ are forcing extensions, why is $M[H]$ a generic extension of $M[G]$?

I know that, wlog, we may assume $G = H \cap A$ for some complete subalgebra $A$ of the complete Boolean algebra $B$ over which $H$ is $M$-generic.
0
votes
1answer
48 views

Recursively enumerable sets as image of a function

I want to show the following claim: An infinite recursively enumerable subset of the natural numbers is the image of an injective recursive function. What I know is that given a r.e. set $A\subset ...
1
vote
3answers
105 views

$\exists x ~ \forall y ~ f(x, y) \iff \forall y() ~ \exists x~ f(x, y(x))$ Name? Proof?

I was looking at potential theorems, and this one came up: $$\bigg(\exists x ~ \forall y ~:~ f(x, y) \bigg) \iff \bigg(\forall y() ~ \exists x ~:~ f(x, y(x))\bigg)$$ (where the second $y$ is ...
0
votes
1answer
9 views

How to find Cost Price (C.P.) of an article in this problem?

A man sells an article at a gain of 12.5%.If he had sold it at Rs 22.50 more, he would have gained 25%. The C.P. of the article is?
0
votes
2answers
59 views

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist for these statements

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist, such that this statement is true: $$(\forall{x} \in \mathbb{Z}:f(x) \geq 2)\Rightarrow(\forall{x}\in \mathbb{Z}:f(x)<10)$$ and this statement ...
0
votes
1answer
52 views

the definition of order relation in Munkres's Topology

In Munkres book, he defines an order relation as follows: A relation $C$ on a set is called an order relation if it has the following properties: 1.(comparability) for every $x$ and $y$ in $A$ for ...
0
votes
6answers
114 views

How to write “There is at least 3” in logic

I need to know how to write "There is at least 3 "in the logic language For example : There is at least 3 cars in the garage Thank you
5
votes
1answer
109 views

On the order of natural functions {f:N→N}

Define a partial order on natural-valued functions (or sequences, depends on how you see it): $f<g$ iff $\exists x:\forall n(n>x\rightarrow f(n)<g(n))$. Intuitively, $f<g$ if $g$ ...
1
vote
1answer
21 views

Legitimacy of using assumptions of a previously proven conditional in a biconditional proof

I am working on Velleman's How to Prove it, and I am asked to prove: For every integer n, 6|n iff 2|n and 3|n. In logical form, that is: $$\forall n\in Z(6|n\leftrightarrow(2|n \land3|n)) $$ Where ...
1
vote
1answer
90 views

Why are adjoints usually defined in terms of hom-sets?

The usual definition of adjoints one finds in many category theory textbooks is: Let $\mathcal{C}$ and $\mathcal{D}$ be categories and $F:{\mathcal {D}}\rightarrow {\mathcal {C}}$ and ...
1
vote
1answer
71 views

What are the applications of classical logic?

Can someone tell me some applications, direct or indirect of classical logics to solve real life problems? Outside of universities where it is used and for what? Thanks in advance.
2
votes
1answer
39 views

Prove that the Morley Rank is preserved under definable bijections.

I need to prove this: If there is a definable bijection between $\varphi(C)$ and $\psi(C)$ then $RM(\varphi)= RM(\psi)$. Where $C$ is the monster model. I can intuitively understand it, the Morley ...
0
votes
1answer
28 views

Prove that theory is not Henkin one

The definition as it was given to me: The theory $T$ is Henkin theory, if and only if for every formula $\phi$ in $T$ we have constant $c$ language of $T$ such as $T \vdash \exists x \phi \to ...
1
vote
2answers
32 views

Simplify Implication Expression (Predicate/Prop Logic)

I'm trying to do some past paper questions for revision and find myself perplexed on some of the expressions that need normalized/simplified which involves an implies. For example: (A ∧ ¬B) → B ∨ C ∨ ...