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
0 votes
0 answers
11 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 ...
0 votes
0 answers
7 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 ...
  • 41
0 votes
0 answers
21 views

Monotone set function in a set

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 $Z=\bigcup \{X\subseteq A|X\subseteq F(X)\}$. It ...
  • 41
0 votes
1 answer
46 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
60 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
36 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
58 views

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,935
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
96 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
64 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
49 views

Finite tuples of infinite set

Let $U$ be an infinite set. Let $A$ be the set $U^{<\omega}$ of finite tuples of elements of $U$, i.e. $f\in A$ is of the form $(i_0,…,i_n)$ for $i_j\in U,j\leq n$, and $n\in \omega$. Let $A\cup \{...
  • 41
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 ...
  • 41
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
66 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
81 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
23 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
53 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
47 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 ...
0 votes
0 answers
21 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
28 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
297 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
35 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 vote
1 answer
26 views

Sets that are half-satisfied

Let $S=\{1,2,\dots,n\}$ and $A_1,\dots,A_k\subseteq S$. Assume that, among the sets $A_i$'s, $1$ appears as least as frequently as $2$, which appears as least as frequently as $3$, etc. Let $B = \{2,4,...
  • 2,587
0 votes
0 answers
50 views

is there a function $f: \mathbb{Q} \rightarrow \mathbb{N}$ that is surjective but not injective?

I would like to know, is there a function $$f: \mathbb{Q} \rightarrow \mathbb{N}$$ that is surjective but not injective? I am rather new to the principle of cardinality. I know that $\mathbb{Q}$ has ...
  • 19
1 vote
1 answer
43 views

The geometric realisation $|\Gamma|_I$ of a graph $(\Gamma, I)$

Prove that the geometric realisation $|\Gamma|_I$ of a graph $(\Gamma, I)$ is the topological space $$|\Gamma|_I = E\times [0,1]\vert \sim$$where $\sim$ is the equivalence relation generated by the ...
1 vote
0 answers
32 views

Using theorem to prove a collection $\left \{ x:\phi (x) \right \}$ is not set.

As I was reading Set Theory: A First Course, I encountered a theorem in the page 31 that allows to prove if a given class $\left \{ x:\phi (x) \right \}$ is a set. It goes as follows: Theorem 2.1.3 ...
1 vote
1 answer
33 views

Is it true that $x (\bigcap\limits_{\alpha \in A} T_\alpha) \neq \bigcap_{\alpha \in A} (x T_\alpha)$?

I want to show that the intersection of normal subgroups are normal subgroup in direct way. It means that if $T_\alpha$'s are normal subgroups of a group $G$, then I want to show that $$x (\bigcap\...
  • 1,183
0 votes
2 answers
34 views

Transitive, Symmetric and Antisymmetric for relations.

Determining whether a relation is reflexive is straightforward, as it is for symmetric and transitive. But considering how strict the criteria, does it mean that any relation that simply fails the (P) ...
  • 55
1 vote
2 answers
203 views

How to use $\uparrow$ to define an explicit bijective mapping $f:\varepsilon_{1}\rightarrow\mathbb{N}$?

The map $f:\varepsilon_{1}\rightarrow\mathbb{N}$ which I am trying to define has to send $\varepsilon_{0}$ to some natural number. Since $\varepsilon_{0}=\omega\uparrow^{2}\omega$, a potential ...
  • 3,484
1 vote
1 answer
55 views

Does there exist a group $G$ with a proper subgroup $K$ in which for all $a, b \in G - K$ such that $ab \neq e$, we have $ab \in G - K$? [closed]

I am currently studying group theory and I asked myself various questions, though I was able to solve almost all of them, I could not answer the following one: Does there exist a group $G$ with a ...

1
2 3 4 5
550