Questions tagged [elementary-set-theory]

This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, relations and functions, countability and uncountability, etc. More advanced topics should use (set-theory) instead.

Filter by
Sorted by
Tagged with
-6 votes
0 answers
28 views

Кто может помочь доказать тождество? A ∪ В = (А \ C) ∪ (В \ А) ∪ (А ⋂ В) [closed]

A ∪ В = (А \ C) ∪ (В \ А) ∪ (А ⋂ В)
0 votes
0 answers
28 views

$f:\mathbb{R}\to\mathbb{R}$ is increasing. $\{y\in\mathbb{R}:\#f^{-1}(\{y\})\geq 2\}$ can contain at most countably many points. Why?

I am reading "Measure, Integration & Real Analysis" by Sheldon Axler. The following exercise is Exercise 24 on p.40 in Exercises 2B in this book. Exercise 24 Suppose $B\subset\mathbb{R}$...
  • 7,456
0 votes
0 answers
13 views

Is there a proof showing that all (absolutely) normal numbers are disjunctive?

I was reading the Wikipedia pages for normal numbers and disjunctive sequences (hadn't come across either of these terms before so I'm not an expert or anything, pls be nice. Just going on a tangent ...
1 vote
0 answers
16 views

If I can find two limits of a set relation, what effect does that have on set relationships?

I'm a bit new to set theory, so forgive me if I'm missing some formalisms here. Let x be some finite set of actions, and y be some finite set of actions, and $\omega$ be a scalar s.t. $0 \leq \omega \...
  • 111
-3 votes
0 answers
11 views

How to prove A△(A△B)=B and (A|B|C)&(A|not B|C)&not(A|C)=∅ [closed]

Problem : Prove the following properties of the symmetric difference: 1)A△(A△B)=B 2)(A|B|C)&(A|not B|C)&not(A|C)=∅
0 votes
0 answers
19 views

Handbook of Categorical Algebra Definition 1.1.2

In the definition mentioned in the title, an universe $\mathcal U$ is defined as a set satisfying some properties. One of this properties is that if $x\in \mathcal U$ and $f: x\to y$ is surjective ...
  • 149
-1 votes
0 answers
50 views

Why doesn't Cantor's diagonal argument also work for rational numbers? [duplicate]

Let's suppose that we don't know how to arrange all the rational numbers in such a way that easily shows that they're countably infinite. I present to you the following list which claims to include ...
3 votes
1 answer
124 views

Can superset and subset be used interchangeably?

Is it true that $A \subset B \iff B \supset A$? I have been using both interchangeably in order to save time when Latexing some notes, but this question gave me some pause.
  • 661
1 vote
1 answer
62 views

Injection from $\omega$ to set of finite tuples plus one element

Let $U$ be an infinite set and write $\omega$ for $\mathbb{N}$: $$ A=\bigcup_{n>0}\{f:n\to U \ f \text{ is injective}\}$$ That is, $f\in A$ is of the form $(i_0,...,i_n)$ for $i_j\in U,j\leq n$ and ...
  • 75
1 vote
0 answers
32 views

Existence and uniqueness of the equivalence closure

Given a relation $R \subseteq B \times B $, show the existence and uniqueness of the closure of R under the properties that define an equivalence relation. Does the order in which the closures of ...
3 votes
1 answer
35 views

Banach Decomposition Theorem from Fixpoint Theorem

Let $A$ be a set. Knowing that every monotone set function $F: \mathcal{P}(A)\to\mathcal{P}(A)$ (in the sense that $X\subseteq Y\subseteq A\implies F(X)\subseteq F(Y)$) has a fixpoint, prove the ...
  • 75
0 votes
0 answers
45 views

Monotone set function in a set [closed]

Let $A$ be a set and let $F:\mathcal{P}(A)\to \mathcal{P}(A)$ a monotone function, i.e. if $X\subseteq Y\subseteq A$, then $F(X)\subseteq F(Y)$. Let $$\mathcal Z:=\{X\subseteq A\mid X\subseteq F(X)\}\...
  • 75
0 votes
1 answer
47 views

Understanding the Union Axiom. Proving $x \cup y := \{z: z\in x \lor z\in y\}$ is a set.

Hi guys I'm really new to set theory and I'm trying to well understand the Union Axiom. First of all, the Union Axiom state the following (at least this is the definition I have): $$\forall \,x\ \...
  • 191
0 votes
1 answer
61 views

Is there a set of functions that span all "nice" functions?

I have been reading as to why there are elementary functions that have non-elementary antiderivatives and I have come to the conclusion that our notion of "elementary" functions is somewhat ...
1 vote
1 answer
37 views

If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$.

Question: If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$. My Working: If $A\cup B=A$, then we have $B \subset A$. If $B = \varnothing$, $ax-1\...
-2 votes
0 answers
75 views
+50

order property vs. antisymmetric property

The definition of order property is well known:for a first-order theory $T$ the order property means that for some first-order formula $\phi(\bar{x},\bar{y})$ linearly orders in $M$ some infinite $\...
  • 3,889
0 votes
1 answer
46 views

Image and preimage definition

I got the following very basic question: Why is an image - in contrast to a preimage - defined by using the existential quantifier? Let $f\colon A \to B$ be a mapping and $M$ a subset of $A$ and $N$ ...
1 vote
2 answers
100 views

For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ [closed]

For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ Confused on how to do this, any help would be great. Correction: Accidentally ...
0 votes
1 answer
69 views

Indexed sets Prove $(\bigcap_iA_i)^c=\bigcup_i A_i^c $

Here i my approach. I stuggle to get the curly brackets in. Attempt: $\bigcup_i A_i^c=({x: \exists i \in I, x \in A_i})^c $ $={x: \exists i \in I, x \not \in A_i}$ How can I proceed here? I dont see ...
1 vote
0 answers
55 views

Show that a monotone function has a fixpoint

Let $F:\mathcal{P}(A)\to\mathcal{P}(A)$ be a monotone function, i.e. $X\subseteq Y\subseteq A$ implies $F(X)\subseteq F(Y)$. Show that it has a greatest fixpoint (i.e. a fixpoint $X$ such that for ...
  • 75
2 votes
1 answer
28 views

Set notation iterating two variables over different lengths

How does one interpret the following set notation: $$ \{(x_i,y_j): i=1,...,4,j=1,...,6\} $$
3 votes
1 answer
94 views

Why is there no negative infinity in the extended complex plane?

I'm reading Ravi Agarwal's "Introduction to Complex Analysis". He says this: It is often convenient to add the element $\infty$ to $\mathbb{C}$. The enlarged set $\mathbb{C} \cup \{\infty\}$...
  • 155
0 votes
0 answers
26 views

Real Analysis Set Theory Related Question

I have no idea what this set would be $$-A = \{ t \in \mathbb{R}: -t \in A \}$$. I'm thinking that it means it's all negative real numbers in the set $-A$. Furthermore, I don't know what $A$ would be.
1 vote
1 answer
31 views

Symmetric difference of a set and its n-th preimage

I have a question about the following statement: Let $X$ be a set and $f:X\to X$ a map, then for any subset $A\subset X$ and all $n\in\mathbb{N}$ $$A\triangle f^{-n}(A)\subseteq\bigcup_{i=0}^{n-1}f^{-...
1 vote
0 answers
67 views

Possible Bijection Between Natural and Real Numbers [duplicate]

I'm studying the Cantor diagonal argument showing that there isn't any function $f:\mathbb N \to \mathbb R$ in one-to-one with each other and accepted it. But, thinking about it for awhile, I thought ...
0 votes
1 answer
86 views

I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… [closed]

enter image description here I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… as this would not be the case right? As only relations ...
0 votes
0 answers
30 views

List all the elements of $\{C \in \mathcal{P}(\{0,1,2\}) : \{0,1\} \nsubseteq C\}$.

I'm just really confused about what {0,1} not being contained in C would mean. Does it mean that the answer is all the elements of the powerset except for {0,1}, or does it mean the answer is all the ...
  • 1
-3 votes
0 answers
79 views

I dont understand the writers confusing use of "Set" as opposed to a "Relation". [closed]

enter image description hereenter image description hereenter image description here I dont understand the writers confusing use of "Set" as opposed to a "Relation". My only guess ...
  • 1
0 votes
1 answer
35 views

Question about a proof that addition from the left preserves the order of ordinals

I found the following proof that ordinal addition from the left preserves strict inequalities (see b)). I am having trouble understanding the limit stage. The proof uses the inequality $\gamma + \...
-4 votes
0 answers
27 views

I have tried proving this but I still couldn't get it [closed]

I was given two distinct sets, A and B. If A is a subset of B, prove that B is not a subset of A and that A is not equal to B.
1 vote
0 answers
38 views

Confusion on Authors use of the word into as opposed to onto

The function G, which is a mapping of B -> A by the definition in the screenshot should be a mapping from B onto A because all members of B would always mapped to A Right?
  • 21
0 votes
1 answer
17 views

What type of relation wrt arbitrary elements of a generic set exists between particular (distinct, not-nec unique) elements of that set?

What type of relation wrt ane arbitrary element of a generic (ostensibly non‑ordered) set exists between particular (distinct, not necessarily unique) elements of that set?  I.e.(e.g.): $𝑥∈\{𝚡₁,…,𝚡...
1 vote
2 answers
24 views

Proving by induction how many elements are in the $n$-ary cartesian product between the two same sets.

Here's a question that has been bugging me for a while. Let $A$ be a set such that $A = \{a, b\}$. Then, $A_1 = A$, $\;A_2 = A \times A$, and for $n \in \mathbb{N}$, $A_n = A_{n-1} \times A$. How ...
  • 33
1 vote
0 answers
42 views

Prove $A^c \setminus B^c=B \setminus A$ [duplicate]

Prove $A^c \setminus B^c=B \setminus A$ Attempt: let $A^c = \{ x:x \in U, x \not \in A\}$ and let $B^c = \{ x:x \in U, x \not \in B\}$ and $ B \setminus A =\{x:x \in B, x \not \in A\}$ Dont know how ...
0 votes
1 answer
54 views

What are the basics for notation used in cardinal arithmetic?

If $S$ and $T$ are sets, which of the following would you say is $T^{S}$? $T^{S}$ is the set of all functions from $S$ to $T$. $T^{S}$ is the Cartesian product of $T$ taken $\begin{vmatrix} S \end{...
1 vote
0 answers
17 views

Possible errors in a proof concerned with irreflexivity and asymmetry

I'm trying to prove that asymmetric relation R would also be irreflexive. My proof is as follows: Suppose R is not irreflexive. Then a is related to a by R for some a. Then either a is not related to ...
1 vote
1 answer
39 views

$S$ is any non empty set and $2^S$ is the power set of $S$. True or False for the following

$S$ is any non empty set and $2^S$ is the power set of $S$. let $S = \{ 1,2 \}$. Then the power set $P(S) = \{\{1,2\}, \{1\}, \{2\}, \emptyset \}$ where P(S) contains $2^2=4$ elements. True or False ...
3 votes
2 answers
55 views

Prove or disprove. $\bigcup_{i\in I} \bigcap_{j\in J} C_{i,j} = \bigcap_{j\in J} \bigcup_{i\in I} C_{i,j}.$ [duplicate]

Let $\{ C_{i,j} : i\in I \text{ and } j\in J \}$ be a family of sets. Assume the set $I$ (of indices $i$) is arbitrary, non-empty, and non-enumerable. Similarly, assume the set $J$ (of indices $j$) is ...
  • 13.9k
0 votes
0 answers
22 views

Notation regarding a set with two disjoint properties

I'm trying to write the solution to the following equation in set builder notation $$\max\{|x_1|,|x_2| \}=1$$ So far, I've come up with: $$\big\{ (x_1,x_2) \in \mathbb{R}^2: \big(|x_1|=1, -1\le x_2 \...
1 vote
0 answers
29 views

How to think about distence or closeness between various intersecting and non-intersecting sets?

Edit: I want to add more context. I'm interested in toying around with mathematical modeling of something, where it is helpful to represent the things I'm modeling with sets whose elements are points. ...
  • 87
1 vote
1 answer
26 views

Give an example of a relation $R$ on the given set $A$ that has the properties described: $A=\mathbb Q$, $R$ is both symmetric and anti-symmetric

$A=\mathbb Q$, $R$ is both symmetric and anti-symmetric What I have is "$R = \{(a, b)~ |~ a, b \in \mathbb Q~ ,~ a = b\}$". I just want to double check if my logic is correct and if not, ...
  • 13
1 vote
0 answers
38 views

For any three relations prove the $ (T \circ S) \circ R = T \circ (S \circ R) $ [duplicate]

Prove: For any three relations $R \subset W \times X$, $S \subset X \times Y$, and $T \subset Y \times Z$, $(T \circ S) \circ R = T \circ (S \circ R)$. (image link) Attempted Proof: suppose $ (a,b) ...
0 votes
0 answers
37 views

Notation: x randomly chosen with weights from set S

I have implemented $\epsilon$-greedy policy in the context of reinforcement learning in Python code: ...
  • 1
0 votes
1 answer
54 views

composition relations in Set Theory

I have provided my solution and I see there are subtle differences to those provide in picture. Is my solution equivalent? Which is more rigorously correct? \begin{align} (S \circ R)^{-1} & = \...
1 vote
0 answers
46 views

Kuratowski's definition of ordered pairs: proving $(x,y) = (u,v) \iff x=u \text{ and } y=v$

I'm new to set theory and I need to prove the following: $(x,y) = (u,v) \iff x=u,y=v$ where $(x,y) = \{\{x\},\{x,y\}\}$ as in Kuratowski's definition of ordered pairs. Now, I think I got the right to ...
  • 191
0 votes
0 answers
23 views

$\overline{F}:A/R\to A/R$ such that $\overline{F}([x]_R)=[F(x)]_R$ uniqueness extremely trivial im confused?

Assume that $R$ is an equivalence relation on $A$ and that $F:A\to A$. If $F$ is compatible with $R$, then there exists a unique $\overline{F}:A/R\to A/R$ such that $$\overline{F}([x]_R)=[F(x)]_R$$ ...
  • 170
3 votes
1 answer
299 views

Is this exercise from Tao's Analysis 1 erroneous?

On page 68 of the fourth edition of Tao's Analysis 1, is Exercise $3.5.12$, the first part of which I believe is erroneous. The exercise is stated as follows: (Note: $n++$ refers to the successor of $...
0 votes
0 answers
39 views

Injective function from N (naturals) to Q?

In this video (https://www.youtube.com/watch?v=Vp570S6Plt8) at 11:17, the speaker says that their argument proves that the size of infinity of Q is less than the size of infinity of N. This makes ...
1 vote
1 answer
38 views

Resources for "Bell Machover"

Recently, I've been reading through A Course In Mathematical Logic by John Bell and Moshé Machover. However, it's not always the easiest book to understand. What might be some good supplements to have ...
0 votes
1 answer
30 views

Proving $C = \{ x \in \mathbb R^n\colon Ax = b\}$is closed, for some $A \in \mathbb R^{m \times n}$ and $b \in \mathbb R^m$ s.t. system is feasible.

Consider the set $$ C = \{ x \in \mathbb R^n\colon Ax = b \}, $$ where $A$ is some matrix in $\mathbb R^{m \times n}$ and $b \in \mathbb R^m$ such that the system is feasible. I aim to prove such set ...
  • 1,171

1
2 3 4 5
550